Рефераты Метод Зойтендейка

Вернуться в Информатика

Метод Зойтендейка
.Пусть (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. При этом значении активным становится ограничение . Значение получается из решения следующей задачи одномерной минимизации: минимизировать 6 2-2.5 -3.375 при условии 0 0.414Оптимальное значение равно 1= 0.2083. Следовательно, х2 = (x1 + 1d1) -(0.2083,0.5417)T.Итерация 2Поиск направления. В точке x2= (0.2083, 0.5417)T имеем (х2)=(-4,2500, -4.2500)T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет видминимизировать zпри условиях -4.25d1-4.25d2-z 0, -1
Добавить в Одноклассники    

 

Rambler's Top100