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

Сентябрь 2, 2022

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

Содержание

2. 1. Математичне формулювання загальної задачі оптимізації Вирішення багатьох теоретичних і практичних завдань зводиться до відшукання екстремуму
3. Функцію f(x), що оптимізується, називають цільовою функцією або критерієм оптимальності. Надалі говоритимемо про пошук мінімального значення
4. 2. Геометрична інтерпретація задач оптимізації Якщо х* - точка мінімуму функції у = f(x), то для
5. У реальних умовах на змінні xj, j =1 .. n, та деякі функції gi (х), hi(х),
6. Точка х* визначає глобальний мінімум функції однієї змінної f(x), заданою на числовій прямій Х, якщо x
7. Точка х* Х визначає локальний мінімум функції f(x) на множині Х, якщо при деякому достатньо малому
8. 3. Класифікація методів оптимізації за видом цільової функції В даний час для вирішення оптимальних задач застосовують
9. Методи дослідження функцій класичного аналізу Звичайною областю використання даних методів є завдання з відомим аналітичним виразом
10. Метод множників Лагранжа застосовують для вирішення завдань такого ж класу складності, як і при використанні звичайних
11. Методи варіаційного числення зазвичай використовують для вирішення завдань, в яких критерії оптимальності представляються у вигляді функціоналів
12. Динамічне програмування служить ефективним методом вирішення завдань оптимізації дискретних багатостадійних процесів, для яких критерій оптимальності задається
13. Принцип максимуму застосовують для вирішення завдань оптимізації процесів, описуваних системами диференціальних рівнянь. Перевагою математичного апарату принципу
14. Лінійним програмуванням є математичний апарат, розроблений для вирішення оптимальних завдань з лінійними виразами для критерію оптимальності
15. Методи нелінійного програмування застосовують для вирішення оптимальних завдань з нелінійними функціями мети. На незалежні змінні можуть
17. Скачать презентацию

Слайд 2

1. Математичне формулювання загальної задачі оптимізації
Вирішення багатьох теоретичних і практичних завдань

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

Слайд 3

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

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

Слайд 4

2. Геометрична інтерпретація задач оптимізації
Якщо х* - точка мінімуму функції у

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

Слайд 5

У реальних умовах на змінні xj, j =1 .. n, та

деякі функції gi (х), hi(х), що характеризують якісні властивості об'єкту, системи, процесу, можуть бути накладені обмеження (умови) вигляду:
gi (х) = 0, i=1 .. N;
hi (х) <= 0, i=1 .. N;
а <= x <= b,
де
Таке завдання називають завданням умовної оптимізації. За відсутності обмежень має місце завдання безумовної оптимізації.
Кожна точка х в n-мірному просторі змінних х1 ., хn, в якій виконуються обмеження, називається допустимою точкою завдання. Безліч всіх допустимих крапок називають допустимою областю G. Рішенням задачі (оптимальною крапкою) називають допустиму точку х*, в якій цільова функція f(х) досягає свого мінімального значення.

Слайд 6

Точка х* визначає глобальний мінімум функції однієї змінної f(x), заданою

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

Слайд 7

Точка х* Х визначає локальний мінімум функції f(x) на множині Х,

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

Слайд 8

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

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

Слайд 9

Методи дослідження функцій класичного аналізу
Звичайною областю використання даних методів є

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

Слайд 10

Метод множників Лагранжа застосовують для вирішення завдань такого ж класу складності,

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

Слайд 11

Методи варіаційного числення зазвичай використовують для вирішення завдань, в яких критерії

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

Лінійним програмуванням є математичний апарат, розроблений для вирішення оптимальних завдань з

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

Слайд 15

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

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