тивістю регулярності, відображення має бути симетричним, тобто br/>В
Якщо деяка вершина симплекса не виключається протягом декількох ітерацій, то необхідно зменшити розмір симплекса і побудувати новий симплекс, вибравши в якості базової точку з мінімальним значенням цільової функції.
Знаходження мінімуму цільової функції методом рівномірного симплекса
Вихідні дані:
В
- початкова точка
- масштабний множник
Мінімізуємо цільову функцію до першого зменшення розміру симплекса
Нехай масштабний множник -
В В
-я ітерація:
В В В
- максимально, отже, замінюємо
В В В В
-я ітерація:
В В В
- максимально, отже, замінюємо
В
-я ітерація:
В В
- максимально, отже, замінюємо
В В
4-я ітерація:
В
- максимально отже, про замінюємо
В В В
5-я ітерація:
В В В
- максимально, отже, замінюємо
В
-я ітерація:
В
- максимально, отже, замінюємо
В В В
-я ітерація:
В В
- максимально, отже, замінюємо
В В
-я ітерація:
В В В
- максимально, отже, замінюємо
В
-я ітерація:
В В В В В
Так як найбільше значення цільової функції відповідає, яке отримано на попередній ітерації, відкидаємо.
-я ітерація:
В В В В В
Координати точки, отримані на 10-й ітерації, збігаються з координатами, отриманими на 4-й ітерації. Симплекс накрив точку мінімуму. Далі слід зменшити масштабний множник (наприклад, у 2 рази) і побудувати новий вихідний симплекс, взявши в якості вихідної точку
Отримане рішення не є точним, тому мало б сенс продовжити обчислення.
В
Рис 2. Графічне пояснення методу рівномірного симплекса
Метод Хука-Дживса
Опис алгоритму
Процедура Хука-Дживса являє собою комбінацію "досліджує" пошуку з циклічним зміною змінних і прискорює пошуку по знайденому зразком. Досліджує пошук орієнтований на виявлення напрямків вздовж "ярів". Отримана в результаті досліджує пошуку інформація використовується потім у процесі пошуку за зразком при русі по "ярах". p> Досліджує пошук:
Для проведення досліджує пошуку необхідно задати величину кроку, яка може бути різна для різних координатних напрямків, і змінюватися в процесі пошуку. Пошук починається в деякій вихідної точки. Робиться пробний крок уздовж одного з координатних напрямків. Якщо значення цільової функції в пробної точці менше, ніж у вихідній, то крок вважається вдалим. В іншому випадку повертаються у вихідну точку і роблять крок у протилежному напрямку. Після перебору всіх координат досліджує пошук закінчується. Отриману в результаті досліджує пошуку точку називають базовою. p> Пошук за зразком:
Пошук за зразком у полягає в реалізації єдиного кроку з отриманої базової точки вздов...