Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
Отже матриця Гессе матиме вигляд:
Головні мінори :оскільки в ряді знаки чергуються, то дана матриця є від’ємно визначеною, я отже функція - вгнута.
Система обмежень задачі включає тільки лінійні нерівності, які утворюють опуклу множину, отже дана задача є задачею опуклого програмування.
Задачу такого типу можна розв’язувати методом Франка-Вулфа. Цей метод відноситься до групи градієнтних методів.
Розглянемо задачу:
Алгоритм методу Франка-Вулфа:
Спочатку в допустимій області задачі обирають довільну точку . Це можна зробити, наприклад, за допомогою методу штучного базису. Також обирають точність обчислень . Покладають
Знаходять в цій точці градієнт цільової функції .
Будують функцію і розв’язують задачу максимізації для функції в області 2-3, тобто таку задачу:
Нехай - оптимальний розв’язок задачі 4,2,3.
Шукаємо наступне наближення за формулою: , де - крок в точці. Його обирають довільно, однак краще його вибрати так, щоб при такому значенні мала найбільше значення. Для цього з формул 5 знаходять вираз координат вектора через : і підставляють цей вираз у функцію . Потім розв’язують систему . За вибирають найменший з коренів цього рівняння. Якщо цей корінь більше одиниці, то .
Перевіряють критерії зупинки: , . Якщо дані умови виконались, то покладають і зупиняють обчислення, якщо ні, то переходимо до наступного кроку.
Покладають, що і переходять до кроку 2.
Тепер перейдемо безпосередньо до нашої задачі. За початкове наближення до оптимального плану задачі обираємо точку , а обчислення будемо проводити з точністю , . Градієнт цільової функції в точці .
Розв’яжемо за допомогою симплекс методу задачу:
оптимізаційний одновимірний мінімізація дихотомія ньютон
і | Базис | Сб | В | 4 | 2 | 0 | 0 |
А1 | А2 | А3 | А4 | ||||
1 | А3 | 0 | 21 | 3 | 7 | 1 | 0 |
2 | А4 | 0 | 1 | 1 | -1 | 0 | 1 |
3 | 0 | - 4 | -2 | 0 | 0 | ||
1 | А3 | 0 | 18 | 0 | 10 | 1 | -3 |
2 | А1 | 4 | 1 | 1 | -1 | 0 | 1 |
3 | 8 | 0 | -6 | 0 | 4 | ||
1 | А2 | 2 | 9/5 | 0 | 1 | 1/10 | -3/10 |
2 | А1 | 4 | 14/5 | 1 | 0 | 1/10 | 7/10 |
3 | 74/5 | 0 | 0 | 3/5 | 11/5 |
Позначимо через оптимальний розв’язок даної задачі. Отже . Знайдемо новий допустимий розв’язок вихідної задачі за формулою 5:
Знайдемо похідну цієї функції по і прирівняємо її до нуля:
, отже покладаємо =1, таким чином . Знайдемо значення цільової функції в цій точці і перевіримо умови зупинки:
.
Отже знаходимо нове наближення оптимального плану вихідної задачі аналогічним чином. Покладаємо, що . Градієнт цільової функції в точці буде рівним:
.
Знаходимо за допомогою симплекс-методу максимум функції
і | Базис | Сб | В | 3 | 6/5 | 0 | 0 |
А1 | А2 | А3 | А4 | ||||
1 | А3 | 0 | 21 | 3 | 7 | 1 | 0 |
2 | А4 | 0 | 1 | 1 | -1 | 0 | 1 |
3 | 0 | - 3 | -6/5 | 0 | 0 | ||
1 | А3 | 0 | 18 | 0 | 10 | 1 | -3 |
2 | А1 | 3 | 1 | 1 | -1 | 0 | 1 |
3 | 3 | 0 | -21/5 | 0 | 3 | ||
1 | А2 | 6/5 | 9/5 | 0 | 1 | 1/10 | -3/10 |
2 | А1 | 3 | 14/5 | 1 | 0 | 1/10 | 7/10 |
3 | 264/5 | 0 | 0 | 21/50 | 87/50 |
Позначимо через оптимальний розв’язок даної задачі. Отже . Визначимо тепер :
. Тобто критерій зупинки виконано. Отже являється оптимальним розв’язком вихідної задачі, тобто .
метод штрафних функцій
Цей метод відноситься до групи непрямих методів розв’язання задач нелінійного програмування виду:
Він зводить задачу з обмеженнями в послідовність задач безумовної оптимізації деяких допоміжних функції. Останні отримуються шляхом модифікації цільової функції за допомогою функій-обмежень таким чином, щоб обмеження в явному вигляді в задачі оптимізації не фігурували. Це забезпечує можливість застосування методів безумовної оптимізації. В загальному випадку допоміжна функція має вигляд: , де функція визначається з обмежень вихідної задачі і називається штрафною функцією. Необхідно, щоб при порушенні обмеження вона “штрафувала” функцію Z, тобто збільшувала її значення. В такому випадку Z буде знаходитися всередині області обмежень. Штрафну функцію можна будувати різними способами. Розглянемо один з варіантів, коли , де , - параметр штрафної функції.
Далі розв’язують задачу мінімізації для функції , використовуючи один з відомих методів безумовної оптимізації. Будемо розв’язувати задачу мінімізації для градієнтним методом зі сталим кроком. Тоді алгоритм розв’язування задачі буде таким:
Обирається точність обчислень, а в якості початкової точки беруть довільну точку, яка належить допустимій множині задачі. Також зазначається крок і покладають .
Знаходять . Якщо точка належить допустимій множині задачі, то коефіцієнти будуть рівними нулю, якщо ж не належать, то вибираємо параметри так, щоб точка належала допустимій множині.
Перевіряють чи виконується умова . Якщо не виконується, то переходять до наступного кроку, якщо виконується , то .
Покладають, що і переходять до кроку 2.
Перейдемо тепер безпосередньо до нашої задачі. Так як ми розглянули алгоритм методу штрафних функцій для випадку пошуку мінімуму функції, то перейдемо від задачі максимізації до задачі мінімізації:
Запишемо штрафну функцію: і розв’яжемо тепер задачу мінімізації для цієї функції.
За точність обчислень оберемо ,