Математичне формулювання загальної задачі оптимізаці

Геометрична інтерпретація задач оптимізації.
3. Класифікація методів оптимізації за видом цільової

функції.

завдань зводиться до відшукання екстремуму (найбільшого або найменшого значення) скалярної

функції f(х) n-мірного векторного аргументах. Надалі під x розумітимемо вектор-стовпець (крапку в n-мірному просторі):





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

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

записувати це завдання таким чином:
f(x ) --> min.

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

у = f(x), то для функції у = – f(x)

вона є точкою максимуму, оскільки графіки функцій f(x) і – f(x), симетричні щодо осі абсцис(рис. 1). Отже, мінімум функції і максимум функції – f(x) досягаються при одному і тому ж значенні змінної. Мінімальне ж значення функції f(x), дорівнює максимальному значенню функції – f(x) , узятому з протилежним знаком, тобто min f(x)= – max(f(x)).








Рис. 1. Екстремум

та деякі функції gi (х), hi(х), що характеризують якісні властивості

об'єкту, системи, процесу, можуть бути накладені обмеження (умови) вигляду:
gi (х) = 0, i=1 .. N;
hi (х) <= 0, i=1 .. N;
а <= x <= b,
де



Таке завдання називають завданням умовної оптимізації. За відсутності обмежень має місце завдання безумовної оптимізації.
Кожна точка х в n-мірному просторі змінних х1 ., хn, в якій виконуються обмеження, називається допустимою точкою завдання. Безліч всіх допустимих крапок називають допустимою областю G. Рішенням задачі (оптимальною крапкою) називають допустиму точку х*, в якій цільова функція f(х) досягає свого мінімального значення.

змінної f(x), заданою на числовій прямій Х, якщо x *

X і f(x*)< f(x) для всіх x* X (рис.2, а). Точка х* називається точкою строгого глобального мінімуму, якщо ця нерівність виконується як строге. Якщо ж у виразі f(х*) <= f(x) рівність можлива при х, не рівних  х*, то реалізується нестрогий мінімум, а під рішенням в цьому випадку розуміють безліч х* = [x* X: f(x)= f(x*)] (рис.2, б).








Рис. 2. Глобальний мінімум. а - строгий, б - нестрогий

Х, якщо при деякому достатньо малому e > 0 для

всіх х, не рівних  х*, x X, що задовольняють умові |х - х*|<= e, виконується нерівність f(х*)< f(х). Якщо нерівність строга, то х* є точкою строгого локального мінімуму.
На Рис. 3 показані екстремуми функції однієї змінної f(х) на відрізку [а, b] . Тут х1, х3, х6 − точки локального максимуму, а х2, х4 − локального мінімуму. У точці х6 реалізується глобальний максимум, а в точці х2 − глобальний мінімум.









Рис 3. Екстремуми функції

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

дослідження функцій класичного аналізу;
методи, засновані на використанні невизначених множників Лагранжа;
варіаційне числення;
динамічне програмування;
принцип максимуму;
лінійне програмування;
нелінійне програмування.

областю використання даних методів є завдання з відомим аналітичним виразом

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

складності, як і при використанні звичайних методів дослідження функцій, але

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

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

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

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

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

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

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

з лінійними виразами для критерію оптимальності і лінійними обмеженнями на

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

функціями мети. На незалежні змінні можуть бути накладені обмеження також

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

оптимизации. - М.: Наука, 1978.
Зайченко Ю. П. Исследование операций. -

К.: Вища математика, 1979.
Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. - М.: Наука, 1978.
Эльогольц Л. Э. Дифференциальные уравнения и вариационное исчисление. - М.: Наука, 1975.