Метод пошуку по симплексу ( метод)
Робота симплексного методу починається з побудови регулярного симплекса в просторі незалежних змінних і оцінювання цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якій відповідає найбільше значення цільової функції.
а б
Рис. 3. Побудова нового симплекса.
а
– початковий симплекс
;
б
– новий симплекс
.
Після цього знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершина нового симплекса. Якщо функція спадає достатньо плавно, ітерації продовжуються доти, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох чи більше симплексах. В таких ситуаціях можна скористатись наступними трьома правилими.
Правило 1. “Накриття” точки мінімуму.
Якщо вершина, якій відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якій відповідає наступне по величині значення цільової функції.
Правило 2. Циклічний рух.
Якщо
деяка вершина симплекса не виключається
на протязі більше
ітерацій, то необхідно зменшити розміри
симплекса з допомогою коефіцієнта
редукції і побудувати новий симплекс,
вибравши за базову точку ту, якій
відповідає мінімальне значення цільової
функціїх. Спендлі, Хекст і Хімсворт
запропонували обраховувати
по формулі
,
де
- розмірність задачі, а
заокруглюється до найближчого цілого
числа. Для застосування даного правила
вимагається встановлювати величину
коефіцієнта редукції.
Правило 3. Критерій закінчення пошуку.
Пошук завершується, коли або розмір симплекса, або різниця між значеннями функції у вершинах стають достатньо малими. Щоб можна було застосувати це правило, необхідно задати величину параметра закінчення пошуку.
Реалізація
даного алгоритму грунтується на
обчисленнях двох типів: (1) побудові
регулярного симплекса при заданих
базовій точці і масштабному множнику
та (2) розрахунку координат відображуваної
точки. Побудова симплексу є достатньо
простою процедурою, оскільки з елементарної
геометрії відомо, що при заданих
початковій (базовій) точці
і масштабному множнику
координати інших
вершин симплекса в
-вимірному
просторі обчислюються за формулою
,
.
Прирости
і
,
що залежать тільки від
і вибраного масштабного множника
,
визначаються за формулами
,
.
Зауважимо,
що величина масштабного множника
вибирається дослідником, виходячи з
особливостей задачі, яка розв”язується.
При
ребра регулярного симплекса мають
одиничну довжину.
Обчислення
другого типу, пов’язані
з відображенням відносно центра ваги,
також не є складної процедурою. Нехай
- точка, яку потрібно відобразити. Центр
ваги інших
точок розміщений в точці
.
Всі
точки прямої, яка проходить через
і
,
задаються формулою
.
При
отримуємо вихідну точку
,
тоді як значення
відповідає центру ваги
.
Для того, щоб побудований симплекс
володів властивістю регулярності,
відображення повинно бути симетричним.
Отже, нова вершина отримується при
.
Таким чином,
.
Проілюструємо обчислювальну схему методу наступним прикладом.
Приклад. Обчислення у відповідності з симплекс-методом.
Мінимізувати
функцію
.
Розв’язок.
Для побудови початкового симплекса
задомо початкову точку і масштабний
множник. Нехай
і
.
Тоді
,
.
Використовуючи ці два параметри, обчислимо координати двох інших вершин симплекса:
,
,
яким
відповідають значення цільової функції,
рівні
і
.
Оскільки,
,
то необхідно відобразити точку
відносно центра ваги двох інших вершин
симплекса
.
Використовуючи
формулу для
,
отримаємо
,
.
В
отриманій точці
,
тобто спостерігається зменшення цільової
функції. Новий симплекс створюється
точками
,
і
.
У відповідності з алгоритмом, необхідно
відобразити точку
,
якій відповідає найбільше значення
цільової функції, відносно центра ваги
точок
і
.
Ітерації продовжуються до тих пір, поки
не виникне потреба застосування правил
1, 2 і 3, які були сформульовані вище.
Викладений вище алгоритм -методу має декілька очевидних переваг.
1. Розрахунки і логічна структура методу є досить простими, отже, відповідна програма для ПК виявляється досить простою.
2.
Рівень вимог до обсягу пам’яті
ПК невисокий, масив має розмірність
.
3. Використовується порівняно невелика кількість наперед заданих параметрів: масштабний множник , коефіцієнт зменшення множника (якщо застосовується правило 2) і параметри закінчення пошуку.
4. Алгоритм виявляється ефективним навіть у тих випадках, коли похибка обчислення значень функції велика, оскільки при його реалізації оперують найбільшими значеннями функції у вершинах, а не найменшими.
Алгоритм володіє рядом суттєвих недоліків.
1. Не виключено виникнення труднощів, пов’язаних з масштабуванням, оскільки всі координати вершин симплекса залежать від одного і того ж масштабного множника . Щоб позбутися цих труднощів, в практичних задачах необхідно промасштабувати всі змінні з тим, щоб їх значення були порівняльні за величиною.
2. Алгоритм працює досить повільно, оскільки отримана на попередніх ітераціях інформація не використовується для прискорення пошуку.
3. Не існує простого способу розширення симплекса, який не вимагає перерахунку значень цільової функції у всіх точках зразка. Таким чином, якщо по якій-небудь причині зменшується (наприклад, якщо зустрічається область з вузьким “яром” або “хребтом”), то пошук повинен продовжуватись із зменшеною величиною кроку.