• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тема: Оптимізація функцій

Завдання: 1) Методом золотого перетину знайти найбільше значення унімодальної функції на заданому відрізку з точністю до 0.01.

2) Методом золотого перетину знайти найменше значення унімодальної функції на заданому відрізку з точністю до 0.01.

Вар.	Функція

Теоретичні відомості.

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

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

Метод золотого перетину

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

Точка здійснює золотий перетин відрізка якщо відношення довжини всього відрізка до довжини його більшої частини дорівнює відношенню довжини більшої частини відрізка до довжини його меншої частини (рис. 4):

.

Число називають золотим числом.

Рис. 4. Золотий перетин відрізка точкою х

Зауважимо, що на відрізку можна визначити дві симетрично розміщені відносно центру відрізка точки ( та ), що реалізують золотий перетин (рис. 5). Їх знаходимо за формулами:

, .

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

Рис. 5. Точки золотого перетину відрізка

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

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

, , .

Якщо ж , очевидно, що мінімум функції розташований на одному з відрізків: чи . Отже можна відкинути відрізок . Другу ітерацію в цьому випадку проводимо на новому відрізку , ввівши позначення:

, , .

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

Процес оптимізації триває до тих пір, поки довжина чергового відрізка не стане меншою за задану величину :

, де

Переглядів: 911