Учет нелинейных ограничений-равенств - Метод Зойтендейка - Физика - Каталог статей - AlexLat
Главная » Статьи » Физика » Метод Зойтендейка

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

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

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





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

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

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

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

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





Пусть xkдопустимая точка и l= {i. gik)==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—достаточно малое число. Метод возможных направлений не обязательно сходится к точке Ф. Джона. Это

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


Категория: Метод Зойтендейка | Добавил: alexlat (27.04.2012)
Просмотров: 286 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]