WikiZero - Оптимізація (математика)

open wikipedia design.

Цей термін має також інші значення див. оптимізація .

Оптимізація - в математики , інформатики і дослідженні операцій задача знаходження екстремуму (Мінімуму або максимуму) цільової функції в деякій області конечномерного векторного простору , Обмеженою набором лінійних і / або нелінійних рівності і / або нерівностей .

Теорію і методи розв'язання задачі оптимізації вивчає математичне програмування.

Математичне програмування - це область математики, що розробляє теорію, чисельні методи рішення багатовимірних задач з обмеженнями. На відміну від класичної математики, математичне програмування займається математичними методами вирішення завдань знаходження найкращих варіантів з усіх можливих. [1]

В процесі проектування ставиться зазвичай завдання визначення найкращих, в деякому сенсі, структури або значень параметрів об'єктів. Таке завдання називається оптимизационной. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричною оптимізацією. Завдання вибору оптимальної структури є структурною оптимізацією.

Стандартна математична задача оптимізації формулюється таким чином. Серед елементів χ, що утворюють безлічі Χ, знайти такий елемент χ *, який доставляє мінімальне значення f (χ *) заданої функції f (χ). Для того, щоб коректно поставити задачу оптимізації, необхідно задати:

1. Допустиме безліч - безліч 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}} ;
2. Цільову функцію - відображення f: X → R {\ displaystyle f: \; \ mathbb {X} \ to \ mathbb {R}} ;
3. Критерій пошуку (Max або min).

Тоді вирішити задачу f (x) → min x → ∈ X {\ displaystyle f (x) \ to \ min _ {{\ vec {x}} \ in \ mathrm {X}}} означає одне з:

1. Показати, що X = ∅ {\ displaystyle \ mathbb {X} = \ varnothing} .
2. Показати, що цільова функція f (x →) {\ displaystyle f ({\ vec {x}})} не обмежена знизу.
3. Знайти 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}})} .
4. Якщо ∄ 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}} таких, що всюди в деякій їх околиці f (x) ≥ f (x 0) {\ displaystyle f (x) \ geq f (x_ {0})} для мінімуму і f (x) ≤ f (x 0) {\ displaystyle f (x) \ leq f (x_ {0})} для максимуму.

Якщо допустиме безліч X = R n {\ displaystyle \ mathbb {X} = \ mathbb {R} ^ {n}} , То таке завдання називається завданням безумовної оптимізації, в іншому випадку - завданням умовної оптимізації.

Загальна запис завдань оптимізації задає велика різноманітність їх класів. Від класу завдання залежить підбір методу (ефективність її рішення). Класифікацію задач визначають: цільова функція і допустима область (задається системою нерівностей і рівностей або більш складним алгоритмом). [2]

Методи оптимізації класифікують відповідно до завдань оптимізації:

• Локальні методи: сходяться до якого-небудь локального екстремуму цільової функції. У разі унімодальної цільової функції, цей екстремум единственен, і буде глобальним максимумом / мінімумом.
• Глобальні методи: мають справу з багатоекстремального цільовими функціями. При глобальному пошуку основним завданням є виявлення тенденцій глобального поведінки цільової функції.

Існуючі в даний час методи пошуку можна розбити на три великі групи:

1. детерміновані;
2. випадкові (стохастичні);
3. комбіновані.

За критерієм розмірності допустимого безлічі, методи оптимізації ділять на методи одновимірної оптимізації та методи багатовимірної оптимізації.

По виду цільової функції і допустимого безлічі, завдання оптимізації та методи їх вирішення можна розділити на наступні класи:

За вимогами до гладкості і наявності у цільової функції приватних похідних, їх також можна розділити на:

• прямі методи, можуть бути використані лише обчислень цільової функції в точках наближень;
• методи першого порядку : Вимагають обчислення перших приватних похідних функції;
• методи другого порядку: вимагають обчислення друге приватних похідних, тобто гессіан цільової функції.

Крім того, оптимізаційні методи діляться на наступні групи:

Залежно від природи множини 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 с.
• Романовський І. В. Алгоритми рішення екстремальних задач. - М: Наука, 1977. - 352 с. - 16 000 прим.