Студентам > Рефераты > Метод Зойтендейка
Метод ЗойтендейкаСтраница: 2/3
Рис 4.
Итерация 3
Поиск направления. В точке х3= имеем
Кроме того,
множество активных ограничений в точке хз
равно l = {2}, так что направление движения получается из решения
следующей задачи:
Можно легко
проверить по рис. 4. что действительно
является решением этой задачи линейного программирования. Соответствующее
значение целевой функции равно нулю, и процедура заканчивается. Более того,
точка является точкой
Куна—Таккера.
В этой
конкретной задаче функция f выпукла, и по теореме 4.3.7 точка х является оптимальным решением.
Таблица 1
Результаты вычислений по методу Зойтендейка для случая линейных ограничений
Рис. 5. Поиск решения методом Зойтендейка
(случай линейных ограничений).
В табл. 1
приведены результаты вычислений для рассмотренной задачи. На рис. 10.5
изображен процесс поиска решения в соответствии с описанным алгоритмом.
Задачи с нелинейными ограничениями-неравенствами
Теперь
рассмотрим задачу, в которой допустимая область задается системой
ограничений-неравенств не обязательно линейных:
минимизировать
f(х)
при условиях
gi (х)£0, i=1, ...,m.
В теореме
формулируются достаточные условия, при которых
вектор d является возможным направлением спуска.
ТЕОРЕМА. Рассмотрим задачу минимизации f(х)
при условиях gi (х)£0, i=1, ...,m.. Пусть х—допустимая
точка, а I—множество индексов активных в этой точке ограничений, т. е. . Предположим,
кроме того, что функции f и gi для дифференцируемы в х,
а функции gi для непрерывны в
этой точке. Если при
, то вектор d
является возможным направлением спуска.
Рис. 6. Совокупность возможных направлений
спуска в задаче с нелинейными ограничениями. 1— 1-е ограничение; 2—3-е
ограничение; 3—4-е ограничение; 4— 2-е ограничение; 5— возможные направления
спуска; 6— линии уровня целевой функции.
Доказательство.
Пусть вектор и удовлетворяет неравенствам
и при . Для выполняются неравенства , и так как gi непрерывны в точке х, то
для достаточно
малых . В силу дифференцируемости
функций gi при имеем
где при . Так как
, то при
достаточно малых . Следовательно,
при i = 1, . . .,m, т.е. точка
допустимая
для достаточно малых положительных значений .
Аналогично из следует, что
для достаточно малых > 0 имеем . Следовательно, вектор и
является возможным направлением спуска.
На рис. 6
показана совокупность возможных направлений спуска в точке х. Вектор d, удовлетворяющий равенству
, является касательным к множеству
в точке х.
Поскольку функции gi нелинейны, движение вдоль такого
вектора d может привести в недопустимую точку, что
вынуждает нас требовать выполнения строгого
неравенства .
Чтобы найти вектор d, удовлетворяющий
неравенствам для , естественно
минимизировать максимум из и для
. Обозначим
этот максимум через z. Вводя
нормирующие ограничения Для каждого j, получим
следующую задачу для нахождения направления.
Пусть (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 получается из решения следующей задачи одномерной минимизации:
минимизировать 6l2—2.5l—3.375
при условии 0£l£0.414
Оптимальное
значение равно l1= 0.2083.
Следовательно, х2 = (x1 +l1d1) -(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<d1<1, j=1,2.
Оптимальным
решением является вектор d2=(1, 1)T, а z2 = -8.50.
Линейный
поиск. Можно легко проверить, что максимальное l, при котором
точка x2+ld2 допустима,
равно lmax == 0.3472. При этом
активным становится ограничение . Значение l2 получается
минимизацией при условии и,
очевидно, равно l2 = 0.3472, так что хз = х2 +l2d2 = (0.5555, 0.8889)T.
Итерация 3
Поиск направления. В точке xз=
(0,5555, 0.8889)T имеем (хз)=(—3.5558, —3.5554)",
а множество индексов активных ограничений есть I ={1}. Задача определения направления имеет вид
Оптимальным
решением является вектор .
Линейный поиск. Максимальное значение l при котором
точка xз + ldз допустима,
равно lmax = 0,09245. При этом l активным становится ограничение . Значение l3 получается
минимизацией при условии 0,09245.
Оптимальным решением этой задачи является l3 = 0.09245, так что = (0.6479,
0.8397)T.
Итерация 4
Поиск, направления. Для точки х4= (0.6479, 0.8397)T имеем =(— 3.0878,
—3.9370)^ а
I={2}. Задача определения направления имеет вид
Оптимальным
решением этой задачи является вектор d4 = (-0.5171, 1.0000)T и z4=— 2.340.
Линейный
поиск. Максимальное значение К, для которого точка х4 +ld4 допустима,
равно lmах= 0.0343. При этом ограничение становится
активным. Значение l4 получается минимизацией f(x4+ ld4)
== 3,569l2— 2.340l —6.4681 при условии и
равно l4= 0.0343.
Следовательно, новой точкой является x5==x4 + l4d4 = (0.6302, 0.8740)T. Значение целевой функции в этой точке равно -6.5443, т. е. сравняю со значением
—6.5590 в оптимальной точке (0.658872, 0.808226)T .
В табл. 2
приведены результаты вычислений на первых четырех итерациях метода. На рис. 7 показан процесс поиска оптимума.
Таблица
2
|
Главная
Документация
Файлы
Информация
