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

Відмітимо властивість золотого перерізу: точка х1 одночасно являється золотим перерізом відрізка

, а друга точка х2 – золотим перерізом відрізка .

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

знаходяться точки х1 і х2 по наступним формулам:

- коефіцієнт зжимання.

Потім обчислюють значення функції в точках х1 і х2, тобто

. При цьому можливі два випадки:

1.

, в цьому випадку новий відрізок буде рівним і . На цьому відрізку знову обираються дві точки

2.

, тоді новий відрізок будуть становити: . На новому відрізку також обираються дві точки

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

, де - точність пошуку.

Розглянемо також метод Фібоначчі для розв’язуванняодновимірних задач . Цей метод названий так зважаючи на появу при пошуку проміжків унімрдальності чисел Фібоначчі і використовується, якщо кількість ітерації обмежена . Суть методу в тому, що на кожному кроці точка наступного обчислення обирається симетрично відносно середини відрізка локалізації до точки, що лежить всередині цього відрізку, уже проведеного обчислення. Тобто в процесі пошуку інтервалу (x1; x3) з точкою х2, вже лежачою в цьому інтервалі, наступна точка х4 завжди вибирається так, що х3–х4 = х2–х1або х4-х1 = х3-x2, тобто x4=х1-х2+х3.

Алгоритм методу Фібоначчі поляга в наступному:

1) задаються початкові границі відрізку

і , точність обчислень .

2) розраховуються початкові точки ділення:

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

3) покладають

. Тоді

· якщо

, то , .

· інакше

, .

4) якщо n=1, то

і зупиняються. Значення цільової функції в цій точці і буде мінімумом функції. Інакше повертаються до 3-го кроку.

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

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

Визначимо найменше значення функції

на відрізку з точністю , використовуючи

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

Розіб’ємо відрізок

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

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

в цих точках:

Оскільки

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

В нашому випадку

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

Оскільки

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

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

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

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

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