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

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

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

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

Зміст

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

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

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

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

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

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

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

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

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

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

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

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

Залежно від природи множиниXзадачі математичного програмування класифікуються як:

• задачі дискретного програмування (або комбінаторної оптимізації) - якщоXкінцево або лічильно;
• завдання цілісного програмування — якщоXє підмножиною безлічі цілих чисел;
• завдання нелінійного програмування, якщо обмеження або цільова функція містять нелінійні функції іXє підмножиною кінцевого векторного простору.
• Якщо всі обмеження і цільова функція містять лише лінійні функції, це завдання лінійного програмування.

Математичне програмування використовується під час вирішення оптимізаційних завдань дослідження операцій.

Спосіб знаходження екстремуму повністю визначається класом завдання. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:

• Визначення меж системи оптимізації

• Відкидаємо ті зв'язки об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а точніше ті, без яких рішення спрощується

Вибір керованих змінних

"Заморожуємо" значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення в галузі допустимих рішень (керовані змінні)

Визначення обмежень на керовані змінні

… (рівності та/або нерівності)

Вибір числового критерію оптимізації (наприклад, показника ефективності)

Створюємо цільову функцію

Завдання лінійного програмування були першими докладно вивченими завданнями пошуку екстремуму функцій за наявності обмежень типу нерівностей. У 1820 році Фур'є і потім в 1947 Джордж Данциг запропонував метод спрямованого перебору суміжних вершин у напрямку зростання цільової функції - симплекс-метод, що став основним при вирішенні завдань лінійного програмування.

Присутність у назві дисципліни терміна "програмування" пояснюється тим, що першідослідження та перші додатки лінійних оптимізаційних завдань були у сфері економіки, тому що в англійській мові слово programming означає планування, складання планів або програм. Цілком природно, що термінологія відбиває тісний зв'язок, що існує між математичною постановкою задачі та її економічною інтерпретацією (вивчення оптимальної економічної програми). Термін «лінійне програмування» було запропоновано Дж. Данцигом 1949 року вивчення теоретичних і алгоритмічних завдань, пов'язані з оптимізацією лінійних функцій при лінійних обмеженнях.

Тому найменування «математичне програмування» пов'язані з тим, що метою вирішення завдань вибір оптимальної програми дій.

Виділення класу екстремальних завдань, що визначаються лінійним функціоналом на множині, що задається лінійними обмеженнями, слід віднести до 1930-х років. Одними з перших, які досліджували у загальній формі завдання лінійного програмування, були: Джон фон Нейман — математик і фізик, який доказав основну теорему про матричні ігри та вивчив економічну модель, що носить його ім'я, та Л. В. Канторович — радянський академік, лауреат Нобелівської премії (1975), що сформулював ряд завдань лінійного програмування і запропонував у 1939 метод їх вирішення (метод дозволяючих множників), незначно відрізняється від симплекс-метода.

У 1931 році угорський математик Б. Егерварі розглянув математичну постановку і вирішив завдання лінійного програмування, що має назву «проблема вибору», метод вирішення отримав назву «угорського методу».

Л. В. Канторовичем спільно з М. К. Гавуріним в 1949 розроблений метод потенціалів, який застосовується при вирішенні транспортних завдань. У наступних роботах Л. В. Канторовича, В. С. Немчінова, В.В. Новожилова, А. Л. Лур'є, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдіна, Є. Г. Гольштейна та інших математиків та економістів отримали подальший розвиток як математична теорія лінійного та нелінійного програмування, так і додаток її методів для вивчення різних економічних проблем.

В даний час для ефективного застосування методів математичного програмування та вирішення задач на комп'ютерах розроблено алгебраїчні мови моделювання, представниками якими є AMPL та LINGO.

">

---