Цей термін має також інші значення див. оптимізація .
Оптимізація - в математики , інформатики і дослідженні операцій задача знаходження екстремуму (Мінімуму або максимуму) цільової функції в деякій області конечномерного векторного простору , Обмеженою набором лінійних і / або нелінійних рівності і / або нерівностей .
Теорію і методи розв'язання задачі оптимізації вивчає математичне програмування.
Математичне програмування - це область математики, що розробляє теорію, чисельні методи рішення багатовимірних задач з обмеженнями. На відміну від класичної математики, математичне програмування займається математичними методами вирішення завдань знаходження найкращих варіантів з усіх можливих. [1]
Постановка завдання оптимізації
В процесі проектування ставиться зазвичай завдання визначення найкращих, в деякому сенсі, структури або значень параметрів об'єктів. Таке завдання називається оптимизационной. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною оптимізацією. Завдання вибору оптимальної структури є структурною оптимізацією.
Стандартна математична задача оптимізації формулюється таким чином. Серед елементів χ, що утворюють безлічі Χ, знайти такий елемент χ *, який доставляє мінімальне значення f (χ *) заданої функції f (χ). Для того, щоб коректно поставити задачу оптимізації, необхідно задати:
- Допустиме безліч - безліч X = {x → | gi (x →) ≤ 0, i = 1, ..., m} ⊂ R n {\ displaystyle \ mathbb {X} = \ {{\ vec {x}} | \; g_ {i} ({\ vec {x }}) \ leq 0, \; i = 1, \ ldots, m \} \ subset \ mathbb {R} ^ {n}}
;
- Цільову функцію - відображення f: X → R {\ displaystyle f: \; \ mathbb {X} \ to \ mathbb {R}}
;
- Критерій пошуку (Max або min).
Тоді вирішити задачу f (x) → min x → ∈ X {\ displaystyle f (x) \ to \ min _ {{\ vec {x}} \ in \ mathrm {X}}} 
- Показати, що X = ∅ {\ displaystyle \ mathbb {X} = \ varnothing}
.
- Показати, що цільова функція f (x →) {\ displaystyle f ({\ vec {x}})}
не обмежена знизу.
- Знайти x → * ∈ X: f (x → *) = min x → ∈ X f (x →) {\ displaystyle {\ vec {x}} ^ {*} \ in \ mathbb {X}: \; f ( {\ vec {x}} ^ {*}) = \ min _ {{\ vec {x}} \ in \ mathbb {X}} f ({\ vec {x}})}
.
- Якщо ∄ x → * {\ displaystyle \ nexists {\ vec {x}} ^ {*}}
, То знайти inf x → ∈ X f (x →) {\ displaystyle \ inf _ {{\ vec {x}} \ in \ mathbb {X}} f ({\ vec {x}})}
.
Якщо мінімізується функція не є опуклою , То часто обмежуються пошуком локальних мінімумів і максимумів: точок x 0 {\ displaystyle x_ {0}} 
Якщо допустиме безліч X = R n {\ displaystyle \ mathbb {X} = \ mathbb {R} ^ {n}} 
Відео по темі
Класифікація методів оптимізації
Загальна запис завдань оптимізації задає велика різноманітність їх класів. Від класу завдання залежить підбір методу (ефективність її рішення). Класифікацію задач визначають: цільова функція і допустима область (задається системою нерівностей і рівностей або більш складним алгоритмом). [2]
Методи оптимізації класифікують відповідно до завдань оптимізації:
- Локальні методи: сходяться до якого-небудь локального екстремуму цільової функції. У разі унімодальної цільової функції, цей екстремум единственен, і буде глобальним максимумом / мінімумом.
- Глобальні методи: мають справу з багатоекстремального цільовими функціями. При глобальному пошуку основним завданням є виявлення тенденцій глобального поведінки цільової функції.
Існуючі в даний час методи пошуку можна розбити на три великі групи:
- детерміновані;
- випадкові (стохастичні);
- комбіновані.
За критерієм розмірності допустимого безлічі, методи оптимізації ділять на методи одновимірної оптимізації та методи багатовимірної оптимізації.
По виду цільової функції і допустимого безлічі, завдання оптимізації та методи їх вирішення можна розділити на наступні класи:
За вимогами до гладкості і наявності у цільової функції приватних похідних, їх також можна розділити на:
- прямі методи, можуть бути використані лише обчислень цільової функції в точках наближень;
- методи першого порядку : Вимагають обчислення перших приватних похідних функції;
- методи другого порядку: вимагають обчислення друге приватних похідних, тобто гессіан цільової функції.
Крім того, оптимізаційні методи діляться на наступні групи:
Залежно від природи множини X завдання математичного програмування класифікуються як:
Крім того, розділами математичного програмування є параметричне програмування , динамічне програмування і стохастичне програмування .
Математичне програмування використовується при вирішенні оптимізаційних задач дослідження операцій .
Спосіб знаходження екстремуму повністю визначається класом завдання. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:
- Визначення меж системи оптимізації
- Відкидаємо ті зв'язку об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких рішення спрощується
- Вибір керованих змінних
- «Заморожуємо» значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з області допустимих рішень (керовані змінні)
- Визначення обмежень на керовані змінні
- ... (рівності і / або нерівності)
- Вибір числового критерію оптимізації (наприклад, показника ефективності )
- Створюємо цільову функцію
Історія
завдання лінійного програмування були першими детально вивченими завданнями пошуку екстремуму функцій при наявності обмежень типу нерівностей . В 1820 році Фур'є і потім в 1947 році Джордж Данциг запропонував метод спрямованого перебору суміжних вершин в напрямку зростання цільової функції - симплекс-метод , Що став основним при вирішенні задач лінійного програмування.
Присутність в назві дисципліни терміна «програмування» пояснюється тим, що перші дослідження і перші програми лінійних оптимізаційних задач були в сфері економіки, так як в англійській мові слово «programming» означає планування , Складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, який існує між математичною постановкою завдання і її економічної інтерпретацією (вивчення оптимальної економічної програми). термін « лінійне програмування »Був запропонований Дж. Данцигом в 1949 році для вивчення теоретичних та алгоритмічних задач, пов'язаних з оптимізацією лінійних функцій при лінійних обмеженнях.
Тому найменування «математичне програмування» пов'язане з тим, що метою рішення завдань є вибір оптимальної програми дій.
Виділення класу екстремальних задач, що визначаються лінійним функціоналом на безлічі, що задається лінійними обмеженнями, слід віднести до 1930-х років. Одними з перших, що досліджували в загальній формі завдання лінійного програмування, були: Джон фон Нейман - математик і фізик, який довів основну теорему про матричних іграх і вивчив економічну Модель , Що носить його ім'я, і Л. В. Канторович - радянський академік, лауреат Нобелівської премії (1975), який сформулював ряд завдань лінійного програмування і запропонував в 1939 році метод їх вирішення ( метод дозволяють множників ), Незначно відрізняється від симплекс-методу.
В 1931 році угорський математик Б. Егерварі розглянув математичну постановку і вирішив задачу лінійного програмування, що має назву «проблема вибору», метод вирішення отримав назву « угорського методу ».
Л. В. Канторовичем спільно з М. К. Гавуріним в 1949 році розроблено метод потенціалів , Який застосовується при вирішенні транспортних завдань . У наступних роботах Л. В. Канторовича, В. С. Немчинова , В. В. Новожилова , А. Л. Лур'є , А. Брудно , А. Г. Аганбегяна , Д. Б. Юдіна , Е. Г. Гольштейна та інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування , Так і додаток її методів до дослідження різних економічних проблем.
Методам лінійного програмування присвячено багато робіт зарубіжних вчених. В 1941 році Ф. Л. Хітчкок поставив транспортну задачу . Основний метод розв'язання задач лінійного програмування - симплекс-метод - був опублікований в 1949 році Дж. Данцигом. Подальший розвиток методи лінійного та нелінійного програмування отримали в роботах Г. Куна , А. Таккера , Гасса (Saul. I. Gass), Чарнеса (A. Charnes), била (EM Beale) і ін.
Одночасно з розвитком лінійного програмування велика увага приділялася завданням нелінійного програмування , В яких або цільова функція , Або обмеження, або те й інше нелінійні. У 1951 році була опублікована робота Г. Куна і А. Таккера , В якій наведено необхідні і достатні умови оптимальності для вирішення завдань нелінійного програмування. Ця робота стала основою для подальших досліджень в цій області.
Починаючи з 1955 році опублікований багато робіт, присвячених квадратическому програмування (Роботи Била, Баранкіна і Р. Дорфман , Франка (M. Frank) і Ф. Вулфа [En] , Г. Марковіца та ін.). У роботах Денніса (JB Dennis), Розена (JB Rosen) і Зонтендейка (G. Zontendijk) розроблені градієнтні методи вирішення завдань нелінійного програмування.
В даний час для ефективного застосування методів математичного програмування і рішення задач на комп'ютерах розроблені алгебраїчні мови моделювання , Представниками якими є AMPL і LINGO .
Див. також
Примітки
література
- Абакаров А. Ш., Сушков Ю. А. Статистичне дослідження одного алгоритму глобальної оптимізації . - Праці ФОРА, 2004.
- Акуліч І. Л. Математичне програмування в прикладах і завданнях: Учеб. посібник для студентів економ. спец. вузів. - М.: Вища школа, 1986.
- Гілл Ф., Мюррей У., Райт М. Практична оптимізація. Пер. з англ. - М.: Мир, 1985.
- Гірсанов І. В. Лекції з математичної теорії екстремальних задач. - М.; Іжевськ : НДЦ «Регулярна і хаотична динаміка», 2003. - 118 с. - ISBN 5-93972-272-5 .
- Жіглявскій А. А., Жілінкас А. Г. Методи пошуку глобального екстремуму. - М.: Наука, Физматлит, 1991.
- Кишень В. Г. Математичне програмування. - Вид-во фіз.-мат. літератури, 2004.
- Корн Г., Корн Т. Довідник з математики для науковців та інженерів. - М.: Наука, 1970. - С. 575-576.
- Коршунов Ю. М., Коршунов Ю. М. Математичні основи кібернетики. - М.: Вища школа, 1972.
- Максимов Ю. А., Філліповская Е. А. Алгоритми рішення задач нелінійного програмування. - М.: МІФІ, 1982.
- Максимов Ю. А. Алгоритми лінійного і дискретного програмування. - М.: МІФІ, 1980.
- Плотніков А. Д. Математичне програмування = експрес-курс. - 2006. - С. 171. - ISBN 985-475-186-4 .
- Растригин Л. А. Статистичні методи пошуку. - М., 1968.
- Діагональні методи глобальної оптимізації (Електронний ресурс) / Сергєєв Я.Д., Квасов Д.Є. - М.: ФИЗМАТЛИТ, 2008. 341с.
- Хемді А. Таха. Введення в дослідження операцій = Operations Research: An Introduction. - 8 видавництво. - М.: Вільямс , 2007. - С. 912. - ISBN 0-13-032374-8 .
- Кіні Р. Л., Райфа Х. Прийняття рішень при багатьох критеріях: переваги і заміщення. - М.: Радио и связь, 1981. - 560 с.
- С.І.Зуховіцкій , Л.І.Авдеева. Лінійне і опукле програмування. - 2-е изд., Перераб. і доп .. - М.: Видавництво «Наука», 1967.
- Мінаєв Ю. М. Стабільність економіко-математичних моделей оптимізації. - М.: Статистика, 1980.
- Моїсеєв Н. Н. Чисельні методи в теорії оптимальних систем. - М: Наука, 1971. - 424 с.
- Моїсеєв Н. Н. Елементи теорії оптимальних систем. - М: Наука, 1975. - 528 с.
- Моїсеєв Н. Н. , Іванілов Ю. П., Столярова Є. М. Методи оптимізації. - М: Наука, 1978. - 352 с.
- Дегтярьов Ю. І. Методи оптимізації. - М: Радянське радіо, 1980. - 272 с.
- Реклейтіс Г., Рейвіндран А., Регсдел К. Оптимізація в техніці. - М.: Мир, 1986. - 400 с.