Методи прийняття рішень в умовах визначеності

(Задачі оптимізації)

4.1. Основні поняття і класифікація методів рішення задач оптимізації

Під оптимізацією будемо розуміти цілеспрямовану діяльність, яка полягає в отриманні найкращих результатів у відповідних умовах.

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

Іншими словами, об'єкт оптимізації має певні міри свободи – дії, за допомогою яких можна змінювати його стан відповідно до певних вимог. Кількісну оцінку якості об'єкта, що оптимізується, зазвичай називають критерієм оптимальності (критерієм оптимізації).

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

Природно, що оптимізація на стадії проектування більш ефективна, оскільки є додаткові конструктивні параметри, якими можна варіювати. Математичні методи оптимізації можна ефективно застосовувати лише при наявності математичного опису об'єкта, що оптимізується. Вибір того чи іншого методу вирішення конкретної задачі оптимізації в значній мірі визначається постановкою задачі, а також використовуваною математичною моделлю об'єкта оптимізації.

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

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

Якщо таких функцій кілька, то говорять про розв’язання багатокритеріальної задачі або задачі векторної оптимізації.

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

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

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

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

У математичному програмуванні зазвичай виділяють наступні розділи (класи задач):

– лінійне програмування (цільова функція і всі обмеження лінійні);

– нелінійне програмування (нелінійна цільова функція довільного виду визначена на множині, що задається нелінійними обмеженнями різного виду);

– квадратичне програмування (цільова функція – квадратична і опукла, а допустима множина рішень визначається лінійними рівностями і нерівностями);

– опукле програмування (цільова функція і допустимі множини опуклі);

– геометричне програмування (цільова функція і всі обмеження є позитивними поліномами;

– дискретне програмування (рішення шукається лише в дискретних, наприклад цілочисельних точках множини допустимих рішень);

– стохастичне програмування (на відміну від детермінованих задач вхідна інформація носить елемент невизначеності);

– динамічне програмування (особливий вид задач оптимізації, де незалежно від конкретного виду цільової функції і обмежень пошук оптимального рішення представляється у вигляді багатокрокового процесу).

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

Очевидно, що не існує єдиного методу вирішення всіх можливих задач оптимізації. Одні з методів є більш загальними, а інші – менш загальними.

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

Інші методи найкращим чином підходять для вирішення оптимальних задач з математичними моделями певного виду (наприклад, лінійне, геометричне і динамічне програмування).

Цікаво, що у задач лінійного, квадратичного та опуклого програмування є загальна властивість: знайдена точка локального екстремуму (мінімуму або максимуму) є оптимальною точкою. Ці задачі є одноекстремальними, а в основі теорії опуклого і, отже, лінійного і квадратичного програмування лежить теорема Куна-Такера про необхідні і достатні умови існування оптимальної точки.

Менш вивченими і більш складними є багатоекстремальні задасі, для яких зазначена вище властивість не виконується.

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