13.1 Метод загального пошуку

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

    

     Рисунок 13.6 – Метод загального пошуку

В результаті інтервал невизначеності звужується до двох кроків сітки. Звичайно говорять про дроблення інтервалу невизначеності, яке характеризується коефіцієнтом f. Розділивши інтервал невизначеності на N частин, отримаємо N+1 вузол, і тоді

.

Щоб отримати значення f = 0,01, необхідно обчислити цільову функцію в 199 точках, а при f = 0,001 N=1999. Звідси видно, що ефективність цього методу при зменшенні інтервалу невизначеності швидко падає. Напрошується інший варіант: щоб отримати f=0,01, необхідно обчислити спочатку функцію в 19 точках і отримати f = 0,1, а потім обчислити ще 19 значень функції на скороченому інтервалі невизначеності, отримати f = 0,01, зробивши при цьому всього 38, а не 199 обчислень. Таким чином, при деякій винахідливості ефективність пошуку можна різко збільшити.

13.2 Метод половинного ділення (розділення відрізка навпіл)

Суть метода полягає в постійному діленні відрізка дослідження цільової функції [a, b] навпіл і визначенні на ньому координат трьох точок х₁, х₂, х_m. При чому значення їх визначаються як:

, L=b-a, , .

    

     Рисунок 13.7 - Геометрична інтерпретація методу половинного ділення

Точки , поділяють відрізок [a,b] на чотири рівні частини (рис. 13.6), обчислюємо значення цільової функції Потім порівнюємо значення і , якщо , то виключаємо з дослідження відрізок та покладемо . Тоді середньою точкою нового відрізка [a, b] стає . Але якщо , то порівнюємо значення цільової функції і ; якщо , то виключаємо відрізок , покладемо ; якщо , то виключаємо відрізок та , покладемо , тобто формуємо новий відрізок дослідження. Обчислюємо L = b - a, якщо , якщо немає, то знову повертаємося до початку.

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

    

     Рисунок 13.8 – Схема алгоритму метода половинного ділення

Цей метод відрізняється великою ефективністю.

13.3 Метод дихотомії

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

    

     Рисунок 13.9 – Позначення, які використовуються в методі дихотомії

Якщо значення цільової функції при х₁ більше, ніж при х₂, то новий інтервал невизначеності дорівнює Z₁ = z₁ + z₂. В протилежному випадку він визначається виразом Z₂ = z₂ + z₃. Задача полягає в тому, щоб одночасно мінімізувати Z₁ i Z₂, задовольнивши умовам

z1+z2+z3 = Z,

z₁ > 0,

z2 > 0,

z₃ > 0.

Із рівності можна виключити z₂. Тоді

Z – z₃ = min, Z – z₁ = min.

Так як величина Z задана, то праві частини цих рівнянь будуть тим менше, чим більше z₁ i z₃. Отже, оптимум відповідає умові

z1 = z3 = 0,5Z.

Але тоді z₂ = 0, що суперечить умові z₂ > 0.

    

     Рисунок 13.10 – Метод дихотомії

Нехай z₂ має деяке дуже маленьке значення . Тоді із z₁ i z₃ віднімемо по . В результаті після обчислення першої пари значень цільової функції при близьких значеннях х інтервал невизначеності звузиться, як показано на рис. 13.10, і коефіцієнт ділення буде дорівнювати

.

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