Завданням оптимізації в математиці називається задача про знаходження екстремуму (мінімуму або максимуму) речової функції в деякій області. Як правило, розглядаються області, що належать і задані набором рівностей і нерівностей.
Математичне програмування - математична дисципліна, що вивчає теорію і методи вирішення завдань про знаходження екстремумів функцій на множинах конечномерного векторного простору. визначених лінійними і нелінійними обмеженнями (рівностями і нерівностями).
В процесі проектування ставиться зазвичай завдання визначення найкращих, в деякому сенсі, структури або значення параметрів об'єктів. Таке завдання називається оптимизационной. Якщо оптимізація пов'язана з розрахунком оптимальних значень параметрів при заданій структурі об'єкта, то вона називається параметричної. Завдання вибору оптимальної структури є структурною оптимізацією.
Постановка завдання оптимізації
Стандартна математична задача оптимізації формулюється таким чином. Серед елементів χ, що утворюють безлічі Χ, знайти такий елемент χ *. який доставляє мінімальне значення f (χ *) заданої функції f (χ). Для того, щоб коректно поставити задачу оптимізації необхідно задати:
- Допустиме безліч - безліч;
- Цільову функцію - відображення;
- Критерій пошуку (max або min).
Тоді вирішити задачу означає одне з:
- Показати що .
- Показати, що цільова функція не обмежена знизу.
- Знайти.
- Якщо, то знайти.
Якщо мінімізується функція не є опуклою. то часто обмежуються пошуком локальних мінімумів і максимумів: точок x0 таких, що всюди в деякій їх околиці для мінімуму і для максимуму.
Якщо допустиме безліч. то таке завдання називається завданням безумовної оптимізації. в іншому випадку - завданням умовної оптимізації.
Класифікація методів оптимізації
Методи оптимізації класифікують відповідно до завдань оптимізації:
- Локальні методи: сходяться до якого-небудь локального екстремуму цільової функції. У разі унімодальної цільової функції, цей екстремум единственен, і буде глобальним максимумом / мінімумом.
- Глобальні методи: мають справу з багатоекстремального цільовими функціями. При глобальному пошуку основним завданням є виявлення тенденцій глобального поведінки цільової функції.
Існуючі в даний час методи пошуку можна розбити на три великі групи:
- детерміновані;
- випадкові (стохастичні);
- комбіновані.
За критерієм розмірності допустимого безлічі, методи оптимізації ділять на методи одновимірної оптимізації та методи багатовимірної оптимізації.
По виду цільової функції і допустимого безлічі, завдання оптимізації та методи їх вирішення можна розділити на наступні класи:
- Завдання оптимізації, в яких цільова функція і обмеження є лінійними функціями, вирішуються так званими методами лінійного програмування.
- В іншому випадку мають справу з завданням нелінійного програмування і застосовують відповідні методи. У свою чергу з них виділяють дві приватні задачі:
- якщо і - опуклі функції, то таке завдання називають завданням опуклого програмування;
- якщо, то мають справу із завданням целочисленного (дискретного) програмування.
За вимогами до гладкості і наявності у цільової функції приватних похідних, їх також можна розділити на:
- прямі методи, можуть бути використані лише обчислень цільової функції в точках наближень;
- методи першого порядку. вимагають обчислення перших приватних похідних функції;
- методи другого порядку: вимагають обчислення друге приватних похідних, тобто гессіан цільової функції.
Крім того, оптимізаційні методи діляться на наступні групи:
Залежно від природи множини X завдання математичного програмування класифікуються як:
Спосіб знаходження екстремуму повністю визначається класом завдання. Але перед тим, як отримати математичну модель, потрібно виконати 4 етапи моделювання:
- Визначення меж системи оптимізації
- Відкидаємо ті зв'язку об'єкта оптимізації із зовнішнім світом, які не можуть сильно вплинути на результат оптимізації, а, точніше, ті, без яких рішення спрощується
- Вибір керованих змінних
- «Заморожуємо» значення деяких змінних (некеровані змінні). Інші залишаємо приймати будь-які значення з області допустимих рішень (керовані змінні)
- Визначення обмежень на керовані змінні
- ... (рівності і \ або нерівності)
- Вибір числового критерію оптимізації
- Створюємо цільову функцію