Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

курсовая работа

Розвязання задачі умовної оптимізації за допомогою методу Франка-Вулфа і методу штрафних функції

4. Розвяжемо задачу умовної оптимізації

a. методом Франка-Вулфа

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

Отже матриця Гессе матиме вигляд:

Головні мінори :оскільки в ряді знаки чергуються, то дана матриця є відємно визначеною, я отже функція - вгнута.

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

Задачу такого типу можна розвязувати методом Франка-Вулфа. Цей метод відноситься до групи градієнтних методів.

Розглянемо задачу:

Алгоритм методу Франка-Вулфа:

1. Спочатку в допустимій області задачі обирають довільну точку . Це можна зробити, наприклад, за допомогою методу штучного базису. Також обирають точність обчислень . Покладають

2. Знаходять в цій точці градієнт цільової функції .

3. Будують функцію і розвязують задачу максимізації для функції в області 2-3, тобто таку задачу:

Нехай - оптимальний розвязок задачі 4,2,3.

4. Шукаємо наступне наближення за формулою: , де - крок в точці. Його обирають довільно, однак краще його вибрати так, щоб при такому значенні мала найбільше значення. Для цього з формул 5 знаходять вираз координат вектора через : і підставляють цей вираз у функцію . Потім розвязують систему . За вибирають найменший з коренів цього рівняння. Якщо цей корінь більше одиниці, то .

5. Перевіряють критерії зупинки: , . Якщо дані умови виконались, то покладають і зупиняють обчислення, якщо ні, то переходимо до наступного кроку.

6. Покладають, що і переходять до кроку 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

Позначимо через оптимальний розвязок даної задачі. Отже . Визначимо тепер :

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

b. метод штрафних функцій

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

Він зводить задачу з обмеженнями в послідовність задач безумовної оптимізації деяких допоміжних функції. Останні отримуються шляхом модифікації цільової функції за допомогою функій-обмежень таким чином, щоб обмеження в явному вигляді в задачі оптимізації не фігурували. Це забезпечує можливість застосування методів безумовної оптимізації. В загальному випадку допоміжна функція має вигляд: , де функція визначається з обмежень вихідної задачі і називається штрафною функцією. Необхідно, щоб при порушенні обмеження вона “штрафувала” функцію Z, тобто збільшувала її значення. В такому випадку Z буде знаходитися всередині області обмежень. Штрафну функцію можна будувати різними способами. Розглянемо один з варіантів, коли , де , - параметр штрафної функції.

Далі розвязують задачу мінімізації для функції , використовуючи один з відомих методів безумовної оптимізації. Будемо розвязувати задачу мінімізації для градієнтним методом зі сталим кроком. Тоді алгоритм розвязування задачі буде таким:

1. Обирається точність обчислень, а в якості початкової точки беруть довільну точку, яка належить допустимій множині задачі. Також зазначається крок і покладають .

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

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

4. Покладають, що і переходять до кроку 2.

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

Запишемо штрафну функцію: і розвяжемо тепер задачу мінімізації для цієї функції.

За точність обчислень оберемо , а крок , а початкову точку візьмемо таку ж як ми брали у методі Франка-Вулфа, тобто . Отже

;

.

Тобто ,

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі:

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

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі:

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

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розвязку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розвязку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розвязку.

Точка належить допустимій множині задачі, оскільки задовольняє обмеженням задачі.

Обчислимо значення штрафної функції в цій точці: .

Тепер перевіримо критерій зупинки:

, отже шукаємо наступне наближення до оптимального розвязку.

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

З другого обмеження задачі маємо:

Отже в якості параметру візьмемо . Тоді

Точка належить допустимій множині задачі. Обчислимо значення штрафної функції в цій точці: .

І так далі продовжується процес пошуку нового наближення до розвязку задачі.

Як бачимо, метод штрафних функцій сходиться значно повільніше, ніж метод Франка-Вулфа. Це може бути повязано з тим, що початкове наближення знаходиться далеко від мінімуму функції, або ж необхідно обрати більший крок.

Делись добром ;)