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

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. Знаходять

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