
	Главная Схемы Документация Студентам Программы Поиск Top50

Поиск по сайту

Навигация

Главная

Схемы

Документация

Файлы

Информация

Студентам

Студентам > Рефераты > Метод Зойтендейка

Метод Зойтендейка

Страница: 3/3

Рис 7

Учет нелинейных ограничений-равенств

Метод возможных направлений может быть модифицирован на случай, когда имеются нелинейные ограничения-равенства. Для иллюстрации обратимся к рис. 8, который отвечает единственному ограничению-равенству. Для заданной допустимой точки хk, в этом случае не существует ненулевого направления d, такого, что при для некоторого положительного d. Это затруднение можно преодолеть, если двигаться вдоль касательного направления dk, для которого , а затем скорректировать движение и возвратиться в допустимую область.

Рис. 8. Нелинейные ограничения-равенства. 1—касательное направление; 2 — корректирующее движение в допустимую область.

Чтобы быть более точным, рассмотрим следующую задачу:

минимизировать f(х)

при условиях gi(х)£0, i= 1,..., m,

hi(х)=0, i=1, ...,i.

Пусть xk—допустимая точка и l= {i. gi(хk)==0}. Решим следующую задачу линейного программирования:

Искомое направление dk является касательным к ограничениям-равенствам и к некоторым активным нелинейным ограничениям-неравенствам. Линейный поиск вдоль dk н последующее возвращение в допустимую область приводят в точку хk+1, после чего процесс повторяется.

Рис. 9. Использование почти активных ограничений. 1 — оптимальное решение; 2— линии уровня целевой функции; 3—1-е ограничение; 4— 2-е ограничение.

Использование почти активных ограничений

Напомним задачу определения направления как для случая линейных, так и нелинейных ограничений-неравенств. Если заданная точка близка к границе, определяемой одним из ограничений, и если это ограничение не используется в процессе нахождения направления движения, то может случиться так, что удастся сделать только маленький шаг и мы окажемся на границе, определяемой этим ограничением. На рис. 9 в точке х активным является только первое ограничение. Однако точка х близка к границе, определяемой вторым ограничением. Если множество I в задаче определения направления задать в виде I= {1}, то оптимальным будет направление d и до выхода на границу допустимой области можно сделать только маленький шаг. Если же в множество активных ограничений включить оба ограничения, т. е. положить I={1, 2), то решение задачи Р

определения направления даст вектор и, который обеспечивает большие возможности для движения в рамках допустимой области. Таким образом, это наводит на мысль о том, что в качестве множества I следует брать совокупность индексов почти активных ограничений. Точнее, вместо множества {i: gi(х)=0} в качестве I следует брать множество {i, gi(х)+е³0}, где е>0—достаточно малое число. Метод возможных направлений не обязательно сходится к точке Ф. Джона. Это

следует из того, что соответствующее алгоритмическое отображение незамкнуто. При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического отображения и, следовательно, сходимость общего алгоритма.

Список литературы

1. М. Базара, К. Шеттл «Нелинейное программирование. Теория и алгоритмы» М.: Мир 1982

2. Д. Химмельблау «Прикладное нелинейное программирование» М.: Мир 1975


¹	²	³