Учет нелинейных ограничений-равенств
Метод возможных направлений может быть модифицирован на случай, когда имеются нелинейные ограничения-равенства. Для иллюстрации обратимся к рис. 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
Дата добавления: 2019-07-15; просмотров: 177; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!