Методи пошуку.

Числові методи пошуку екстремальних значень функції розглянемо на прикладі знаходження мінімуму функції f(x) на відрізку [a,b]. Припустимо, що цільова функція унімодальна, тобто на даному відрізку вона має тільки один мінімум. Процес розв’язання задачі методом пошуку полягає в послідовному звуженні інтервалу зміни проектного параметра, який називається інтервалом невизначеності. На початку процесу оптимізації його довжина дорівнює b-a, а до кінця, вона повинна стати менше заданого допустимого значення , тобто оптимальне значення проектного параметра повинне знаходитись в інтервалі невизначеності – відрізку [xn, xn+1], причому xn+1 - xn < .

Найбільш простим способом звуження інтервалу невизначеності є його ділення на деяке число рівних частин з наступним обчисленням значень цільової функції в точках розбиття. Нехай n – число елементарних відрізків, h=(b-a)/n – крок розбиття. Обчислимо значення цільової функції yk=fk(x) у вузлах xk=a+kh (k=0,1,…,n). Порівняємо отримані значення f(xk), знайдемо серед них найменше yi=f(xi).

Число mn = yi можна наближено взяти як найменше значення цільової функції f(x) на відрізку [a, b]. Очевидно, що наближеність mn до мінімуму m залежить від числа точок, і для неперервної функції f(x)

Lim mn = m1,

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

В даному методі, який можна назвати методом перебору, головні труднощі полягають у виборі n і оцінці погрішності. Можна наприклад, провести оптимізацію з різними кроками і дослідити схожість такого ітераційного процесу. Але це трудомісткий шлях.

Більш економічним способом уточнення оптимального параметра є використання властивості унімодальної цільової функції, яке дозволяє побудувати процес звуження інтервалу невизначеності. Хай, як і раніше, серед всіх значень унімодальної функції y = f(x), обчисленої у вузлах xk (k = 0,1,…,n), найменшим виявилось yi, це значить, що оптимальне значення проектного параметру знаходиться на відрізку [xi-1 ,xi+1],тобто інтервал невизначеності звузився до довжини двох кроків. Якщо розмір інтервалу недостатній для задоволення даної погрішності, тобто xi+1 - xi-1 > , то його знову можна зменшити шляхом нового розбиття, і т.д. Процес оптимізації продовжується до досягнення заданого розміру інтервалу невизначеності. В описаному методі загального пошуку можна з допомогою деякої винахідливості, а також розумного вибору кроку розбиття досягнути ефективного пошуку.

Наприклад, нехай початкова довжина інтервалу невизначеності дорівнює b – a = 1. Треба добитись його зменшення в 100 разів. Цього легко досягнути розбиттям інтервалу на 200 частин. Обчисливши значення цільової функції f(xk) (k = 0,1,…,200), знайдемо її мінімальне значення f(xі). Тоді шуканим інтервалом невизначеності буде відрізок [xi-1, xi+1].

Але можна поступити інакше. Спочатку розіб’ємо відрізок [a, b] на 20 частин і знайдемо інтервал невизначеності довжиною 0.1, при цьому ми обчислимо значення цільової функції в точках xk = a+0.05k (k = 0,1,…,20). Тепер відрізок [xi-1, xi+1] знову розіб’ємо на 20 частин; дістанемо шуканий інтервал довжиною 0.01, причому значення цільової функції обчислюємо в точках xk = xi-1+0.05k (k = 0,1,…,19) (в точках xi-1 і xi+1 значення f(x) вже знайдені). Таким чином, в другому випадку в процесі оптимізації зроблено 40 обчислень значень цільової функції проти 201 в першому випадку, тобто спосіб розбиття дозволяє дістати суттєву економію обчислень.

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

Блок –схема методу випадкового пошуку

Пояснення до блок – схеми:

Блок1. Встановлення початкових значень площі, параметра C0, кроку D1.

Блок2. Задаємо параметри циклу.

Блок3. Викликаємо підпрограми Ейлера – Коші та прямокутників для пошуку площі.

Блок4. Перевіряємо чи дана площа є мінімальною, якщо ні то присвоюємо значенню параметра р значення отриманої площі.

Блок5. Запам’ятовування значень оптимізованої функції.

Блок6. Встановлення нового значення С0.

Блок7. Повернення в головну програму.