МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» / Звіт до лабораторної роботи № 4 з курсу: «Методи синтезу та оптимізації» на тему: «Дослідження методів багатопараметричної оптимізації на прикладі методів прямого пошуку» Мета роботи: вивчити основні методи багатопараметричної оптимізації на основі алгоритмів прямого пошуку. 1.Короткі теоретичні відомості: Прямі методи Прямі методи, або методи нульового порядку не вимагають знання цільової функції в явному вигляді. Вони не вимагають регулярності і неперервності цільової функції й існування похідних. Це є істотною перевагою при розв’язуванні складних технічних і економічних задач. При реалізації прямих методів істотно скорочується етап підготовки рішення задачі, тому що немає необхідності у визначенні перших і других похідних. Прямі методи в основному носять евристичний характер. До прямих методів відноситься цілий ряд алгоритмів, що відрізняються по своїй ефективності. Методи призначені для рішення безумовних задач оптимізації
. Метод пошуку по симплексу (
метод) Робота симплексного методу починається з побудови регулярного симплекса в просторі незалежних змінних і оцінювання цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якій відповідає найбільше значення цільової функції.
а б Рис. 2. Побудова нового симплекса. а – початковий симплекс
; б – новий симплекс
. Після цього знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершина нового симплекса. Якщо функція спадає достатньо плавно, ітерації продовжуються доти, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох чи більше симплексах. В таких ситуаціях можна скористатись наступними трьома правилими. Правило 1. “Накриття” точки мінімуму. Якщо вершина, якій відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якій відповідає наступне по величині значення цільової функції. Правило 2. Циклічний рух. Якщо деяка вершина симплекса не виключається на протязі більше
ітерацій, то необхідно зменшити розміри симплекса з допомогою коефіцієнта редукції і побудувати новий симплекс, вибравши за базову точку ту, якій відповідає мінімальне значення цільової функціїх. Спендлі, Хекст і Хімсворт запропонували обраховувати
по формулі
, де
- розмірність задачі, а
заокруглюється до найближчого цілого числа. Для застосування даного правила вимагається встановлювати величину коефіцієнта редукції. Правило 3. Критерій закінчення пошуку. Пошук завершується, коли або розмір симплекса, або різниця між значеннями функції у вершинах стають достатньо малими. Щоб можна було застосувати це правило, необхідно задати величину параметра закінчення пошуку. Реалізація даного алгоритму грунтується на обчисленнях двох типів: (1) побудові регулярного симплекса при заданих базовій точці і масштабному множнику та (2) розрахунку координат відображуваної точки. Побудова симплексу є достатньо простою процедурою, оскільки з елементарної геометрії відомо, що при заданих початковій (базовій) точці
і масштабному множнику
координати інших
вершин симплекса в
-вимірному просторі обчислюються за формулою
,
. Прирости
і
, що залежать тільки від
і вибраного масштабного множника
, визначаються за формулами
,
. Зауважимо, що величина масштабного множника
вибирається дослідником, виходячи з особливостей задачі, яка розв”язується. При
ребра регулярного симплекса мають одиничну довжину. Обчислення другого типу, пов’язані з відображенням відносно центра ваги, також не є складної процедурою. Нехай
- точка, яку потрібно відобразити. Центр ваги інших
точок розміщений в точці
. Всі точки прямої, яка проходить через
і
, задаються формулою
. При
отримуємо вихідну точку
, тоді як значення
відповідає центру ваги
. Для того, щоб побудований симплекс володів властивістю регулярності, відображення повинно бути симетричним. Отже, нова вершина отримується при
. 2.Індивідуальне завдання: (Варіант 13). 113. 
Знайти максимум за допомогою симплекс-методу  3.Результат виконання: Задомо початкову точку і масштабний множник. Нехай
і
. Тоді
,
. Використовуючи ці два параметри, обчислимо координати двох інших вершин симплекса:
,
. Ітерація 1. F(x1)=-22.5689-min F(x2)=-4.3274 F(x0)=6 Використовуючи формулу для
, отримаємо: x3=x0+x2-x1=(1.4142;-1.4142). F(x3)=15.3136. Ітерація 2. F(x2)=-4.3274-min F(x0)=6 F(x3)=15.3136 Використовуючи формулу для
, отримаємо: x4=x0+x3-x2=(-0.5176;-1.9318). F(x4)=-6.365. Використовуючи правило 1: x4=x2+x3-x0=(3,346;-0,8966). F(x4)=9,9141. Ітерація 3. F(x2)=-4.3274-min F(x3)=15.3136 F(x4)=9,9141 Використовуючи формулу для
, отримаємо: x5=x4+x3-x2=(2,8284;-2,8284). F(x5)=20,0273. Ітерація 4. F(x3)=15.3136 F(x4)=9,9141-min F(x5)=20,6273. Використовуючи формулу для
, отримаємо: x6=x3+x5-x4=(0.8966;-3.346). F(x6)=-5.9707. Використовуючи правило 1: X6=x4+x5-x3=(4.7602;-2.3108). F(x6)=20.1557. Ітерація 5. F(x4)=9,9141-min F(x5)=20,6273 F(x6)=20.1557. Використовуючи формулу для
, отримаємо: x7=x5+x6-x4=(4.2426;-4.2426). F(x7)=21.9411. Ітерація 6. F(x5)=20,0273-min F(x6)=20.1557 F(x7)=21.9411. Використовуючи формулу для
, отримаємо: x8=x6+x7-x5=(6.1744;-3.725). F(x8)=26.3974. Ітерація 7. F(x6)=20.1557-min F(x7)=21.941 F(x8)=26.3974. Використовуючи формулу для
, отримаємо: x9=x7+x8-x6=(5.6568;-5.6568). F(x9)=19.2550. Використовуючи правило 1: x9=x6+x8-x7=(6.962;-5.2568). F(x9)=28.6845. За правилом 3 завершуємо пошук. Первірка: package lab_4MSO; import java.math.*; public class Max { public static void main(String [] args) { double A=0,B=0,C=0; double x=0,y=0; double dx=-4*x-5*y+3; double dy=-5*x-8*y-5; double a=-4,b=-5,c=-3,d=-5,e=-8,f=5; y=(a*f-c*d)/(a*e-b*d); x=(c*e-b*f)/(a*e-b*d); String s="M("+x+";"+y+")"; System.out.print("Початкова точка:"+s); System.out.println(); double d2x=-4,d2y=-8,dxy=-5; A=d2x; B=dxy; C=d2y; double D=A*C-B*B; double z=(-2*x*x-5*x*y-4*y*y+3*x-5*y+6); if(D>0 && A>0) { System.out.println("Мінімум в точці:" + s + "становить:" + z); } else if(D>0 && A<0) { System.out.println("Максимум в точці:" + s + "становить:" + z); } else { System.out.println("Немає екстремуму."); } } } Початкова точка:M(7.0;-5.0) Максимум в точці:M(7.0;-5.0)становить:29.0 Висновок: на цій лабораторній роботі я вивчив основні методи багатопараметричної оптимізації на основі алгоритмів прямого пошуку.