лгоритму
Метод орієнтований на вирішення завдань з квадратичними цільовими функціями. Основна ідея алгоритму полягає в тому, що якщо квадратична функція:
В
приводиться до виду сума повних квадратів
В
то процедура знаходження оптимального рішення зводиться до одномірним пошукам по перетвореним координатним напрямами.
У методі Пауелла пошук реалізується у вигляді:
В
вздовж напрямків,, званих-сполученими при лінійної незалежності цих напрямків.
Парні напрями визначаються алгоритмічно. Для знаходження екстремуму квадратичної функції змінних необхідно виконати одновимірних пошуків. p> Крок 1. Задати вихідні точки, і напрям. Зокрема, напрямок може співпадати з напрямом координатної осі;
Крок 2. Провести одновимірний пошук з точки в напрямку отримати точку, яка є точкою екстремуму на заданому напрямку;
Крок 3. Провести одновимірний пошук з точки в напрямку отримати точку;
Крок 4. Обчислити напрямок;
Крок 5. Провести одновимірний пошук з точки (чи) в напрямку c висновком в точку. p> Знаходження мінімуму цільової функції методом сполучених напрямків Пауелла.
Рішення:
Цільова функція:
В
Початкова точка:
Значення цільової функції в цій точці:
Крок 1. Задамо вихідні точки S (1) і S (2):
S (1) = [1; 0] S (2) = [0; 1]
Крок 2. Знайдемо значення l, при | [Х (0) +2 S (2)]. Довільна точка на промені з точки Х (0) у напрямку S (2) визначається як
Х = Х (0) + lS (2) = [-9; -10] + l [0; 1]
звідки X1 = -9 X2 = l - 10
Підставляючи ці значення в цільову функцію, отримуємо
| (Х) =
Диференціюючи цей вираз по і прирівнюємо нулю:
| (X) = 2l - 31
l - 31 = 0
Звідси знаходимо l:
l = 15.5
X (1) = [-9; -10] + 15.5 [0; 1] = [-9; 5.5]
| [X (1)] = 99
Аналогічно знайдемо значення l, при | [Х (1) + S (1)].
Х = Х (1) + lS (1) = [-9; 5.5] + l [1; 0]
звідки X1 = l -9 X2 = 5.5
Підставляючи ці значення в цільову функцію, отримуємо
| (Х) =
Диференціюючи цей вираз по і прирівнюємо нулю:
| (X) = 2l - 29
l - 29 = 0
Звідси знаходимо l:
l = 14.5
X (2) = [-9; 5.5] + 10.5 [1; 0] = [0.5; 5.5]
| [X (2)] = 21
Також знайдемо значення l, при | [Х (2) +2 S (2)].
Х = Х (2) + lS (2) = [0.5; 5.5] + l [0; 1]
звідки X1 = 3 X2 = 5.5 + l
Підставляючи ці значення в цільову функцію, отримуємо
| (Х) =
Диференціюючи цей вираз по і прирівнюємо нулю:
| (X) = 2l +12
+ 2l = 0
Звідси знаходимо l:
l = -6
X (3) = [0.5; 5.5] -6 [0; 1] = [1.5; -0.5]
