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

• y 1 < y 2, a 1=a 0 іb 1=x 2 ;

• y 1 > y 2, a 1=x 1 іb 1=b 0 ;

• y 1 = y 2, a 1=x 1 іb 1= x 2 .

В цьому звуженому проміжку [a 1, b 1] знову розраховуються дві точки х1(1) іх2(1) , симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова Δk = bk -ak ≤ ε , де ε – точність пошуку, і тоді в якості точки локального мінімуму можна наближено прийняти середину відрізку .

Назва методу половинного ділення мотивована тим, що якщо величина ε достатньо мала, то довжина відрізка унімодальності (b – a ) зменшується майже вдвічі.

Наступним методом знаходження екстремуму для задач одновимірної оптимізації є метод золотого перерізу .

Термін “золотий переріз” ввів Леорандо да Вінчі. Точка х1 являється золотим перерізом відрізка , якщо відношення довжини b - a всього відрізка до довжини b -х1 більшої частини дорівнює відношенню довжини більшої до довжини х1-а меншої частини, тобто х1 – золотий переріз, якщо справедлива рівність: . Аналогічно, точка х2 симетрична точці х1 відносно середини відрізка , являється другим золотим перерізом цього відрізка.

Відмітимо властивість золотого перерізу: точка х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. Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації

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