Алгоритм метода Зойтендейка (случай нелинейных ограничений-неравенств)

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Начальный этап. Выбрать начальную точку х₁, для которой g_i(x_i)£0 при i= 1, ..., m. Положить k= 1 и перейти к основному этапу.

Основной этап. Шаг 1. Положить и решить следующую задачу:

Пусть (z_k, d_k) — оптимальное решение. Если z_k=0, то остановиться; x_k является точкой Ф. Джона. Если z_k < 0, то перейти к шагу 2.

Шаг 2. Взять в качестве ^ оптимальное решение следующей задачи одномерной минимизации:

где. Положить . заменить k на k+1 и перейти к шагу 1.

ПРИМЕР. Рассмотрим задачу

Решим эту задачу методом Зойтендейка. Начнем процесс из точки .Отметим, что

Итерация 1

Поиск направления. В точке х₁ = (0.00, 0.75)^T имеем а множество индексов активных ограничений есть I= {3}. При этом Задача нахождения направления имеет вид

Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор

Линейный поиск. Любая точка по направлению d₁== (1.00, —1.00)^T из точки x_i = (0.00, 0.75)^T может быть представлена в виде ,а соответствующее ей значение целевой функции равно . Максимальное значение , для которого остается допустимой точкой, равно == 0.414. При этом значении l активным становится ограничение . Значение l получается из решения следующей задачи одномерной минимизации:

минимизировать 6l²—2.5l—3.375

при условии 0£l£0.414

Оптимальное значение равно l₁= 0.2083. Следовательно, х₂ = (x₁ +l₁d₁) -(0.2083,0.5417)^T.

Итерация 2

Поиск направления. В точке x₂= (0.2083, 0.5417)^T имеем (х₂)=(—4,2500, —4.2500)^T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет вид

минимизировать z

при условиях —4.25d₁—4.25d₂—z£0,

-1<d₁<1, j=1,2.

Оптимальным решением является вектор d₂=(1, 1)^T, а z₂ = -8.50.

Линейный поиск. Можно легко проверить, что максимальное l, при котором точка x₂+ld₂ допустима, равно l_max == 0.3472. При этом активным становится ограничение . Значение l₂ получается минимизацией при условии и, очевидно, равно l₂ = 0.3472, так что х_з = х₂ +l₂d₂ = (0.5555, 0.8889)^T.

Итерация 3

Поиск направления. В точке x_з= (0,5555, 0.8889)^T имеем (х_з)=(—3.5558, —3.5554)", а множество индексов активных ограничений есть I ={1}. Задача определения направления имеет вид

Оптимальным решением является вектор .

Линейный поиск. Максимальное значение l при котором точка x_з + ld_з допустима, равно l_max= 0,09245. При этом l активным становится ограничение . Значение l₃ получается минимизацией при условии 0,09245. Оптимальным решением этой задачи является l₃ = 0.09245, так что = (0.6479, 0.8397)^T.

Итерация 4

Поиск, направления. Для точки х₄= (0.6479, 0.8397)^T имеем =(— 3.0878, —3.9370)^ а I={2}. Задача определения направления имеет вид

Оптимальным решением этой задачи является вектор d₄ = (-0.5171, 1.0000)^T и z₄=— 2.340.

Линейный поиск. Максимальное значение К, для которого точка х₄ +ld₄ допустима, равно l_m_ах= 0.0343. При этом ограничение становится активным. Значение l₄ получается минимизацией f(x₄+ ld₄) == 3,569l²— 2.340l —6.4681 при условии и равно l₄= 0.0343. Следовательно, новой точкой является x₅==x₄ + l₄d₄ = (0.6302, 0.8740)^T. Значение целевой функции в этой точке равно -6.5443, т. е. сравняю со значением —6.5590 в оптимальной точке (0.658872, 0.808226)^T .

В табл. 2 приведены результаты вычислений на первых четырех итерациях метода. На рис. 7 показан процесс поиска оптимума.

Таблица 2

Рис 7

Дата добавления: 2019-07-15; просмотров: 345; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 Следующая ⇒

Мы поможем в написании ваших работ!