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

нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.

нові межі відрізка , .

Перевіряємо умову зупинки:

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

.

· метод золотого перерізу

На першій ітерації відрізок

ділимо двома симетричними відносно центра точками за формулами:

Обчислюємо значення функції в цих точках:

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

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

Так як і в методі дихотомії процедура буде продовжуватись до тих пір, поки не буде виконуватись умова

. Отже перевіримо умову зупинки:

. Тому знову аналогічно шукаємо нові межі відрізка. Оскільки маємо:

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки:

, тому продовжуємо процедуру.

Знову перевіряємо умову зупинки:

, отже продовжуємо процедуру.

Перевіряємо умову зупинки:

, тому продовжуємо процедуру.

Перевіряємо умову зупинки:

, отже продовжуємо процедуру.

Перевіряємо умову зупинки:

, отже продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , тому продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

Перевіряємо умову зупинки: , отже продовжуємо процедуру.

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

.

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

(в методі дихотомії ми зробили 11 ітерацій, а в методі золотого перерізу - 16). Крім того, метод дихотомії потребує вдвічі менше обчислень, ніж метод золотого перерізу. Однак мінімальне значення функції знайдене обома методами співпадає, тому можемо зробити висновок, що доцільніше використовувати метод дихотомії для зменшення затрат часу на розв’язання задачі.

· метод Фібоначчі

Спочатку згенеруємо послідовність чисел Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … . Початкові обрахунки проводяться в точках:

, де - число Фібоначчі, яке обирається з умови , тобто в нашому випадку це 18-те число Фібоначчі: . Ці точки розташовані симетрично відносно середини відрізку . На кожному кроці точка наступного обрахунку обирається симетрично відносно середини відрізка локалізації до точки уже проведеного обрахунку, що лежить на цьому відрізку. В силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена і дорівнює N=18. Отже можемо знайти початкові точки ділення:

. Далі обчислюємо значення функції в цих точках: