5.6) результати аналітичного розрахунку мінімумів квадратичної F5 та індивідуальної функцій F6 ;

5.7) результати розрахунку мінімумів квадратичної F5 та індивідуальної функцій F6 на ПЕОМ (табл. 5.2);

5.8) висновки.

6 Контрольні запитання

6.1) Місце задачі одномірного пошуку у загальній задачі оптимізації

6.2) Чому задача пошуку оптимального кроку перетворюється у задачу одномірного пошуку?

6.3) Загальна стратегія одномірного пошуку.

6.4) У скільки разів зменшується інтервал пошуку за одну ітерацію: а) у методі золотого перетину; б) у методі Фібоначчі; в) у методі ділення відрізку навпіл?

6.5) Які використовуються критерії закінчення пошуку?

6.6) Скільки необхідно обрахунків значень ЦФ для зменшення початкового інтервалу невизначеності у p разів а) методом золотого перетину, б) методом ділення відрізку навпіл?

45

ЛАБОРАТОРНА РОБОТА № 6.

АЛГОРИТМИ ЗНАХОДЖЕННЯ ІНТЕРВАЛУ НЕВИЗНАЧЕНОСТІ

1 Мета роботи

Ознайомитись з алгоритмами знаходження інтервалу невизначеності [a, b ] для задач одномірної оптимізації.

2 Короткі теоретичні відомості

У більшості випадків, для визначення інтервалу невизначеності використовується алгоритм Девіса–Свенна–Кемпі (іноді в літературі зустрічається назва : ДСК або рекурентна формула Свенна).

Припускаючи, що в межах інтервалу невизначеності цільова функція

єопуклою, алгоритм виглядає наступним чином.

Зпочаткової точки x(k ) виконуються зростаючі по розміру кроки

x( k +1) = x( k ) ± h 2k , k = 0,1K

до тих пір, поки при якому-небудь k = p , цільова функція не почне зростати. Як тільки знайдена точка, в якій значення функції перевищує значення функції в попередній точці, здійснюється повернення на половину останнього кроку і обчислюється значення функції в даній точці. Останні чотири точки розташовані на рівній відстані. Оцінюючи значення функції f (x) в цих точках, на основі правила виключення інтервалів визначається інтервал, що містить мінімум функції f (x) .

46

x(0)–|h| x(0) x(0)+|h|

)

Рисунок 6.3

Якщо f (x(0) − h ) ≤ f (x(0) ) ≥ f (x(0) + h ) , то це суперечить припущенню про унімодальність функції f (x) . На практиці подібні ситуації

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

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

3 Завдання

3.1) Побудувати графіки квадратичної F5 та індивідуальної F6 функцій (ЛР №5) в околі точки x(0) = 0 , в межах ±5 для визначення можливості знаходження інтервалу невизначеності. У випадку розривів функції в околі точки x(0) = 0 , обрати іншу початкову точку, використовуючи графік функції.

3.2) Скласти програму для знаходження інтервалу ЦФ F5 та F6 при початкових значеннях розміру кроку h1 =1e −4, h2 =1e − 2 , h3 =1 та h4 =10 та початкової точки x(0) = 0 (або обрану у п.3.1).

48

3.3) Використовуючи програму з ЛР №5, для кожного з інтервалів невизначеності провести розрахунки сумарної кількості оцінок ЦФ (КОЦФ) при використанні методу пошуку інтервалу невизначеності та пошуку мінімуму методом «золотого перетину» (МЗП) зведені у таблицю (табл. 6.1). Для МЗП точність обрати ε =1e −3. Врахувати оцінки ЦФ, що необхідні для знаходження напряму пошуку інтервалу невизначеності. Передбачити в програмі перевірку, щодо розрахунку МЗП лише за умов, коли початковий інтервал більший за необхідну точність ε .

Таблиця 6.1 – Результати пошуку інтервалу невизначеності

49