Найпростіша задача знаходження максимуму функції вирішується за наступним алгоритмом:
1. Задаються межі a і b, в межах яких є максимум функції.
2. Інтервал [a, b] розбивається на певну кількість кроків.
3. Функція табулірует в межах заданого інтервалу, і кожне обчислене значення функції порівнюється з максимальним (заданим до початку табулирования).
4. Знаходиться максимальне значення функції на заданому інтервалі з певним кроком і виводиться на друк.
БЛОК-СХЕМА АЛГОРИТМУ МАЄ ВИД:
Мал. 4. Блок - схема алгоритму знаходження максимуму функції
Природно, що зі зменшенням кроку зміни аргументу точність обчислення максимуму збільшується.
Можна скористатися і таким алгоритмом:
1. Знайти значення максимуму за алгоритмом, представленим вище.
2. Для подальшого розгляду вибрати відрізок [xmax-dx, xmax + dx] і виконати обчислення максимуму з кроком, наприклад, dx / 10.
3. Порівняти два знайдених значення.
max1 - значення максимуму з кроком dx і max2 - значення максимуму з кроком dx / 10. Якщо | max2-max1 | <=E (где Е – заданная степень точности вычисления), то закончить решение задачи и max2 вывести на печать, если нет, то вычисление продолжить дальше, повторяя п.2.
Таке завдання зручніше вирішувати, використовуючи процедуру знаходження максимального значення функції.
Блок - схема рішення задачі має вигляд:
Мал. 5. Блок - схема алгоритму знаходження максимуму функції
Методи оптимізації функцій однієї змінної
Метод рівномірного пошуку
Цей метод заснований на тому, що змінної x присвоюються значення x + # 8710; x з кроком # 8710; x = const і обчислюються значення F (x). Якщо F (x n + 1)> F (xn), змінної x дається нове збільшення. Як тільки F (xn + 1) стане менше F (x) пошук зупиняється. При малої заданої похибки цей метод неекономічний за витратами машинного часу.
Метод порозрядного наближення
Цей метод є різновидом методу рівномірного пошуку і реалізується наступним алгоритмом:
1. Задаємо початкове наближення x = x # 8320; зліва від максимуму F (x) і обчислюємо F (x # 8320;). Задаємо D = h, де h = # 8710; x - початковий крок пошуку.
2. Вважаємо, що G = F (xn), де спочатку F (xn) = F (x # 8320;), задаємо x = x + D і обчислюємо F (x n + 1) = F (x).
3. Перевіряємо умову F (x n # 8330; # 8321;)> G; якщо воно виконується, йдемо до п.2, якщо немає, то до п.4.
4. Вважаємо D = -D / 4. Перевіряємо умову | D |> E / 4, де E - задана похибка обчислення xn в точці максимуму. Якщо воно виконується, йдемо до п.2, тобто забезпечуємо пошук максимуму в іншому напрямку з кроком в 4 рази менше, ніж раніше. Якщо дана умова виконується, процес обчислення закінчуємо.
Метод дихотомії (ділення інтервалу пошуку [a, b] навпіл) реалізується наступним алгоритмом:
1. Перевіряємо умову | b-a |<2E, где E – заданная погрешность вычисления xn. Если это условие выполняется, идём к п.6; если не выполняется, идём к п.2.
2. Ділимо інтервал пошуку [a, b] навпіл і обчислюємо дві абсциси, симетрично розташовані відносно точки
3. Для цих значень x обчислюємо F (x # 8321;)> F (x # 8322;).
4. Перевіряємо умову F (x # 8321;)> F (x # 8322;). Якщо воно виконується, вважаємо b = x # 8322; і йдемо до п.1. Якщо не виконується, йдемо до п.5.
5. Вважаємо a = x # 8321; і йдемо до п.1.
6. Виводимо на друк xn = (a + b) / 2 і обчислюємо F (xn).
У методі Фібоначчі точка поділу інтервалу дослідження визначається з кожним новим розрахунком (в методі дихотомії необхідно на кожному кроці виконувати два розрахунку). У інтервал дослідження потрапить попередній розрахунок і для продовження пошуку досить провести розрахунок симетрично наявного.
Припустимо, задано число розрахунків (кроків) N. Необхідно їх зробити так, щоб інтервал, в якому лежить оптимум, був мінімальним. Числа Фібоначчі, використовувані в цьому методі, визначаються наступним чином:
Алгоритм методу Фібоначчі складається з наступних етапів:
1) Змінюють масштаб вихідного інтервалу, в якому лежить оптимум. В якості одиниці вимірювання приймають 1 = X # 8320; / FN. або якщо задана довжина l, в якому лежить оптимум, знаходять його на вихідному інтервалі довжиною X # 8320 ;. Для цього, розділивши X # 8320; на 1, знаходять найближче більше число Фібоначчі FN,
а по ньому визначають N - число необхідних розрахунків для визначення інтервалу.
2) Розставляють перші дві точки і на інтервалі дослідження X0 на відстані FN-2 від кінця b.
3) Обчислюють значення цільової функції в цих точках для звуження інтервалу дослідження. Нехай>. тоді інтервал [. FN] виключається з розгляду.
4) На новому інтервалі дослідження знову розставляють дві точки і. але в одній з них вже відомо значення цільової функції =.
5) Переходять до етапу 3 і т.д. поки не досягають шуканого інтервалу, в якому знаходиться значення змінної, максимізуючи її цільову функцію.
На рис. 6 показаний процес звуження інтервалу дослідження:
Мал. 6. Процес звуження інтервалу дослідження.
Останній N-й розрахунок визначає інтервал довжиною l, в якому знаходиться екстремум цільової функції.
Метод золотого перерізу
Золотий перетин проводить розподіл відрізка АВ на дві нерівні частини так, щоб було справедливо співвідношення (рис. 7).
Метод золотого перерізу дозволяє звужувати відрізок [a, b] кожен раз обчислюючи лише одне значення F (x), а не два, як в методі дихотомії.
Даний метод реалізується наступним алгоритмом:
1. Знаходимо коефіцієнт дроблення k = (√5-1) / 2 відрізка [a, b].
2. Знаходимо абсциссу х1 = a + (1-k) * (b-a) і обчислюємо F (x1).
3. Знаходимо абсциссу х2 = a + k * (b-a) і обчислюємо F (х2).
4. Перевіряємо виконання умови | x2 -x1 | 5. Перевіряємо умову F (x1)