ть методу Зойтендейка, а також основні розрахункові формули. У обчислювальної частини наведено приклад розв'язання задачі нелінійного програмування зазначеним методом. Викладений нижче матеріал може бути використаний студентами як приклад при вивченні важливого розділу курсу «Методів оптимізації математичного програмування».
1. МЕТОДИ МОЖЛИВИХ НАПРЯМІВ
Для вирішення задач умовної оптимізації в пошуку мінімального або максимального значення скалярної функції f (x) n-мірного векторного простору застосовуються прямі і не прямі методи оптимізації алгоритму. У загальному випадку чисельні методи розв'язання задач нелінійного програмування можна розділити на прямі і непрямі.
Прямі методи оперують безпосередньо з вихідними завданнями оптимізації і генерують послідовності точок {x [k]}, таких, що f (х [k +1]) f (x [k]). У силу цього такі методи часто називають методами спуску. Математично перехід на деякій k-му кроці (k. 0, 1, 2, ...) від точки х [k] до точки x [k +1] можна записати в наступному вигляді:
[k + l] x [k] + akp [k],
де р [k] - вектор, який визначає напрямок спуску; аk - довжина кроку вздовж даного напрямку. При цьому в одних алгоритмах прямих методів точки х [k] вибираються так, щоб для них виконувалися всі обмеження задачі, в інших ці обмеження можуть порушуватися на деяких або всіх ітераціях. Таким чином, у прямих методах при виборі напрямку спуску обмеження, що визначають допустиму область G, враховуються в явному вигляді.
Непрямі методи зводять вихідну завдання нелінійного програмування до послідовності задач безумовної оптимізації деяких допоміжних функцій. При цих методах обмеження вихідної задачі враховуються в неявному вигляді.
2. МЕТОД ЗОЙТЕНДЕЙКА
.1 Постановка завдання
Знайти мінімум двічі безперервно диференціюється функцііпрі умови, що вектор задовольняє обмеженням j=1, ...., m, в яких функції x, тобто таку точку, що
,
.2 Стратегія пошуку
Стратегія рішення методом Зойтендейка [Zoutendijk G.] полягає в побудові послідовності допустимих точок {}, таких, що
Правило побудови точок послідовності {}:
де точка - допустима і така, що
- безліч індексів j активних обмежень, для яких виконана умова; величина кроку знаходиться в результаті рішення задачі одновимірної мінімізації:
Завдання може бути вирішена з використанням алгоритму застосування необхідних і достатніх умов мінімуму, інакше величину слід вибирати із співвідношення
де величина визначається з умови а величина, задовольняє умовам:
Напрямок спуску задовольняє системі нерівностей
Можливий напрямок спуску, задовольняє умовам, визначається з рішення задачі лінійного програмування
Якщо рішення задачі менше, то для пошуку нового можливого напрямку спуску вважають Якщо ж то розрахунок за бажанням користувача спуску закінчити, так як в точці з точністю до виконуються умови мінімуму в задачі, або продовжити, з метою домогтися більш високої точності, поклавши де.
.3 Алгоритм
Крок 1. Задати, граничне число ітерацій...
