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

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

2. Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації

Визначимо найменше значення функції на відрізку з точністю , використовуючи

· метод дихотомії:

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

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

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

В нашому випадку . Тому знову розраховуємо дві точки:

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

Спочатку згенеруємо послідовність чисел Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … . Початкові обрахунки проводяться в точках: , де - число Фібоначчі, яке обирається з умови , тобто в нашому випадку це 18-те число Фібоначчі: . Ці точки розташовані симетрично відносно середини відрізку . На кожному кроці точка наступного обрахунку обирається симетрично відносно середини відрізка локалізації до точки уже проведеного обрахунку, що лежить на цьому відрізку. В силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена і дорівнює N=18. Отже можемо знайти початкові точки ділення:

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

Оскільки , то покладаємо, що N=N-1=18-1=17. Нові межі відрізка тепер будуть рівними . Знаходимо нові точки ділення: . Значення функції в цих точках:

Оскільки N=16, нові межі відрізка -.

Оскільки N=15, нові межі відрізка -.

Оскільки N=14, нові межі відрізка -.

Оскільки N=13, нові межі відрізка -.

Оскільки N=12, нові межі відрізка -.

Оскільки N=11, нові межі відрізка -.

Оскільки N=10, нові межі відрізка -.

Оскільки N=9, нові межі відрізка -.

Оскільки N=8, нові межі відрізка -.

Оскільки N=7, нові межі відрізка -.

Оскільки N=6, нові межі відрізка -.

Оскільки N=5, нові межі відрізка -.

Оскільки N=4, нові межі відрізка -.

Оскільки N=3, нові межі відрізка -.

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

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