Постановка і класифікація задач оптимізації
У загальному випадку вираз "розв’язати оптимізаційну задачу" означає пошук найкращого рішення задачі серед можливих варіантів.
Якщо оптимізаційна задача пов’язана з розрахунком оптимальних значень параметрів при заданій структурі об’єкта, то вона називається параметричною. Задача вибору оптимальної структури об’єкта називається структурною оптимізацією.
Розв’язання будь-якої оптимізаційної задачі засновано на побудові математичної моделі досліджуваного об’єкта та проведення обчислювального експерименту. Проведення експерименту не з самим об’єктом, а з його моделлю, тобто проведення обчислювального (комп’ютерного) експерименту надає можливість ефективно досліджувати його властивості в будь-яких ситуаціях.
Основу обчислювального експерименту складає тріада "модель – алгоритм – програма". Схема обчислювального експерименту наведена на рис. 4.
На першому етапі будується деякий еквівалент об’єкта, його модель, яка відображає в математичній формі найважливіші властивості об’єкта. На другому етапі розробляється алгоритм для реалізації моделі на комп’ютері. Модель подається в формі, зручній для застосування числових методів, при цьому визначається послідовність обчислювальних і логічних операцій, які треба виконати для того, щоб знайти шукані величини з заданою точністю. На третьому етапі розробляються програми, що реалізують алгоритми доступною для комп’ютера мовою.
Знаходження оптимальних значень параметрів – це один з етапів обчислювального експерименту, який дозволяє виробити керуючий вплив на об’єкт дослідження.
Теорія оптимізації – це сукупність фундаментальних математичних результатів і числових методів, які дозволяють уникнути повного перебору всіх рішень.
В залежності від виду цільової функції та співвідношення обмежень виділяють різноманітні задачі оптимізації, класифікація яких наведена на рис. 5.
Існує кілька ознак класифікації. Основні критерії класифікації наступні.
1. За типом параметрів задачі оптимізації. Розрізняють неперервні, дискретні та цілочислові задачі оптимізації.
2. За критерієм розмірності допустимої множини параметрів. Задачі оптимізації за цим критерієм діляться на задачі одновимірної та багатовимірної оптимізації.
3. За критерієм наявності чи відсутності обмежень на допустиму множину параметрів. Розрізняють задачі умовної та безумовної оптимізації. Цей признак класифікації має місто як для одновимірних, так і для багатовимірних задач оптимізації.
4. За характером обмежень розрізняють детерміновану та стохастичну оптимізацію. Якщо множина допустимих значень параметрів допускає випадкові компоненти, то має місце стохастична оптимізація, яка також може відноситися і до дискретної задачі.
5. За видом цільової функції та виду обмежень розрізняють лінійне та нелінійне програмування.
Задачі лінійного програмування містять лінійну цільову функцію та лінійні обмеження.
При порушенні лінійності цільової функції або обмежень має місце нелінійна задача оптимізації. Класифікація задач нелінійного програмування наведена на рис. 6. Вона в основному визначається видом цільової функції.
Відзначимо, що на цей час особливо розвинуті випукле та квадратичне програмування.
2.3. Класифікація методів оптимізації[
Методи оптимізації – це методи побудови алгоритмів знаходження (мінімального або максимального) значення деякої функції.
При вирішенні конкретної задачі оптимізації дослідник перш за все повинен вибрати математичний метод, який призводив би до кінцевих результатів з найменшими витратами на розрахунок або ж давав можливість отримати найбільший обсяг інформації про рішення поставленої оптимізаційної задачі.
Найбільш поширеними методами вирішення оптимізаційних задач є:
· методи дослідження функцій, засновані на класичному аналізі;
· методи, засновані на використанні невизначених множників Лагранжа;
· варіаційне обчислення;
· динамічне програмування;
· принцип максимуму;
· лінійне програмування;
· нелінійне програмування.
· метод геометричного програмування.
Існуючі в цей час методи оптимізації можна розбити на три великі групи:
1. детерміновані;
2. випадкові (стохастичні);
3. комбіновані.
За кількістю параметрів оптимізація розділяється на:
– одновимірна оптимізацію;
– багатовимірну оптимізацію.
За вимогами до гладкості й наявності в цільовій функції частинних похідних, їх також можна розділити на:
– методи нульового порядку (прямі методи, що вимагають тільки обчислень цільової функції в точках наближень);
– методи першого порядку (градієнтні методи, які вимагають обчислення перших частинних похідних функції, тобто якобіана цільової функції;);
– методи другого порядку, які вимагають обчислення других частинних похідних.
Практика свідчить, що як правило, не можна рекомендувати якийсь один метод для розв’язання всіх без винятку практичних задач. Одні методи щодо цього є більш загальними, інші – менш загальними. Нарешті, цілу групу методів (методи дослідження функцій класичного аналізу, метод множників Лагранжа, методи нелінійного програмування) на певних етапах розв'язання задачі оптимізації можна застосовувати комбінацію методів.
Найкращим шляхом при виборі методу оптимізації, найбільш придатного для розв'язку відповідного завдання, слід визнати дослідження можливостей і досвіду застосування різних методів оптимізації.
Розглянемо зазначені методи.
Методи дослідження функцій, що базуються на класичному аналізі є найбільш відомими методами розв'язання нескладних оптимізаційних задач. Звичайною областю використання цих методів є задачі з відомими аналітичними виразами критерію оптимальності, що дозволяє знайти аналітичні вирази для похідних.
Метод множників Лагранжа застосовують для розв'язання задач такого ж класу складності, як і при використанні звичайних методів дослідження функцій, але за наявності обмежень типу рівностей на незалежні змінні. До вимоги можливості одержання аналітичних виразів для похідних від критерію оптимальності при цьому додається аналогічна вимога до аналітичного виду рівнянь обмежень.
Методи варіаційного обчислення використовують для розв'язання задач, в яких критерії оптимальності представляються у вигляді функціоналів і розв'язками яких служать невідомі функції. Такі задачі виникають при статичній оптимізації процесів з розподіленими параметрами або в задачах динамічної оптимізації.
Принцип максимуму застосовують для розв'язання задач оптимізації процесів, що описуються системами диференціальних рівнянь. Перевагою математичного апарата принципу максимуму є те, що розв'язок може визначатися у вигляді розривних функцій; це властиво багатьом задачам оптимізації, наприклад задачам оптимального управління об'єктами, що описуються лінійними диференціальними рівняннями.
Лінійне програмування є математичним апаратом, розробленим для рішення оптимізаційних задач з лінійним виразом для критерію оптимальності та лінійними обмеженнями на область змінних значень. Такі задачі, зазвичай, зустрічаються при вирішенні питань оптимального планування виробництва з обмеженою кількістю ресурсів, при визначенні оптимального плану перевезень (транспортні задачі) та ін.
Методи нелінійного програмування застосовують для рішення оптимізаційних задач з нелінійними цільовими функціями. На незалежні змінні можуть бути накладені обмеження також у вигляді нелінійних співвідношень, що мають вигляд рівностей та нерівностей.
Геометричне програмування є метод розв'язання одного спеціального класу задач нелінійного програмування, в яких критерій оптимальності й обмеження задаються у вигляді виразів, що представляють собою суму функцій від незалежних змінних. З подібними задачами іноді доводиться зустрічатися в проектуванні.
Важливою характеристикою будь-якої оптимізаційної задачі є її розмірність n, що відповідає кількості змінних, визначення значень яких необхідно для однозначного визначення стану об’єкта, що оптимізується. Як правило, рішення задач високої розмірності пов’язане з необхідністю виконання великого обсягу обчислень.