Страница: 5/7
Пусть (z, d)—оптимальное решение этой задачи линейного программирования. Если z<0, то очевидно, что d—возможное направление спуска. Если же z = 0, то, как показано ниже, текущая точка является точкой Ф. Джона.
 |
ТЕОРЕМА Рассмотрим задачу минимизации f(х) при условиях gi(х)£0, i = 1, ., m. Пусть х—допустимая точка, а . Рассмотрим следующую задачу нахождения направления:
Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.
Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.
 |
Доказательство. Оптимальное значение целевой функции в сформулированной задаче нахождения направления равно нулю в том и только в том случае, если система неравенств при не имеет решения. По теореме для того, чтобы эта система не имела решения, необходимо и достаточно, чтобы существовали такие числа uo и ui, , что
Это и есть условие Ф. Джона.
Алгоритм метода Зойтендейка (случай нелинейных ограничений-неравенств)
Начальный этап. Выбрать начальную точку х1, для которой gi(xi)£0 при i= 1, ., m. Положить k= 1 и перейти к основному этапу.
Основной этап. Шаг 1. Положить и решить следующую задачу:
 |
Пусть (zk, dk) — оптимальное решение. Если zk=0, то остановиться; xk является точкой Ф. Джона. Если zk < 0, то перейти к шагу 2.
 |
Шаг 2. Взять в качестве ^ оптимальное решение следующей задачи одномерной минимизации:
где.Положить заменить k на k+1 и перейти к шагу 1.
 |
ПРИМЕР. Рассмотрим задачу
Решим эту задачу методом Зойтендейка. Начнем процесс из точки .Отметим, что
Итерация 1
 |
Поиск направления. В точке х1 = (0.00, 0.75)T имеем а множество индексов активных ограничений есть I= {3}. При этом Задача нахождения направления имеет вид
Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор
Линейный поиск. Любая точка по направлению d1== (1.00, —1.00)T из точки xi = (0.00, 0.75)T может быть представлена в виде ,а соответствующее ей значение целевой функции равно . Максимальное значение , для которого остается допустимой точкой, равно == 0.414. При этом значении l активным становится ограничение . Значение l получается из решения следующей задачи одномерной минимизации:
Реферат опубликован: 8/06/2009