Функция достижимости задачи с неравенствами

Функция достижимости задачи с неравенствами.

как отмечалось выше, монотонно уменьшается с ростом с, так как множество допустимых решений задачи (2.111) при этом сужается:

Если множество D в задаче (2.111) содержит внутренние точки, то для ее решения используют методы внутренней точки (методы барьерных функций). При этом вместо задачи (2.111) решают задачу.

в которой функция Ф (г, ф) неограниченно уменьшается при ф, стремящейся к нулю. Например,.

или.

причем г > 0 в обоих выражениях. Задача (2.113) не является расширением для задачи с неравенствами, так как не выполнено условие равенства R и /₀ на D, однако подход, основанный на анализе функции достижимости, полезен и в этом случае. Действительно, функция достижимости, соответствующая (2.113), имеет вид.

При выборе Ф по формулам (2.114) и (2.115) слагаемые К*© изображены на рис. 2.35. При г —> 0 второе слагаемое в (2.116) стремится к нулю для всех с > 0, а так как функция /о © имеет максимум при с = 0 (см. (2.112)), то с*(г) при г —?> 0 приближается к нулю. При этом, согласно (2.99), для Ф (г, ф) в форме (2.115).

Таким образом, для выпуклой функции /₀Чс) знаменатель в (2.117) всегда отрицателен, а так как с* больше нуля для любых г, то dc*/dr > > 0, и при г —> 0 значение с* также стремится к нулю. Причем при малых с* можно считать, что.

Puc. 2.35. Характер составляющих функции достижимости при использовании методов внутренней точки Если при некотором достаточно малом г = г¹ величина с* (г¹) = с¹, то из (2.118) следует, что при дальнейшем уменьшении г.

Важно, что при этом штрафная добавка.

стремится к нулю со скоростью, пропорциональной г. Чтобы показать это, нужно представить первое слагаемое в форме In г/т¹ и оценить его предел при г —> 0 по правилу Лопиталя. Таким образом, limR (c*(г)) =/о*(0) — значению исходной задачи. Если функция /₀*© не выпукла, то в ряде случаев существенно улучшает решение переход к эквивалентной задаче с использованием монотонного преобразования целевой функции (см. выше).

Преимуществом методов внутренней точки является то, что:

• а) в процессе поиска решение всегда остается в допустимой области, так что, прервав поиск, мы всегда получаем допустимое, хотя и приближенное решение;
• б) в процессе поиска мы получаем оценку снизу для значения задачи.

Действительно,.

так как значение левой части этого неравенства равно величине функции /о в точке х*(г), являющейся решением задачи (2.113), которое допустимо, но не оптимально.

Недостатки этих методов следующие.

• 1. Имеется опасность выхода за пределы барьеров и необходимость проверки соблюдения ограничений.
• 2. При малых значениях г функция имеет овражный характер, что существенно затрудняет поиск максимума R на V_x.
• 3. Многие эффективные методы поиска безусловного максимума основаны на квадратичной аппроксимации целевой функции. Применительно к функции R такая аппроксимация для малых г неприменима.

В задачах, где наряду с неравенствами имеются равенства или неравенства таковы, что множество D не имеет внутренних точек, барьерные функции непригодны. В этом случае к задачам с неравенствами применяют методы штрафных функций. Иногда их называют методами внешней точки. Для задач с неравенствами квадратичная функция штрафа запишется как.

При больших значениях, а все недостатки методов внутренней точки, связанные с овражностью, проявляются и в методах штрафных функций. От них свободны, однако, методы, основанные на использовании функции Лагранжа и ее комбинации со штрафными добавками различного типа.

Расширение за счет ослабления ограничений. Чувствительность значения и решения задачи к изменению ее условий.

Расширение задачи НП может быть связано с ослаблением ограничений, когда вместо задачи (2.8) рассматривают расширенную задачу.

Величина значения этой задачи /₀* зависит от в, так же как и решение х*. В реальных условиях мы не знаем функцииДх) абсолютно точно, поэтому практическую ценность представляет решение таких задач, для которых в окрестности е = 0 зависимости /₀*(е) и х*(е) непрерывны. В первом случае говорят, что задача корректна относительно значения, во втором — относительно решения. Так как зависимость /₀* (s) может быть легко получена по функции достижимости задачи (2.8) как

то непрерывность /₀ (s) в точке 8 = 0 соответствует непрерывности /₀* © в этой точке. Как уже упоминалось выше, эта непрерывность тесно связана с невырожденностью решения.

Некорректность по решению задачи также возникает в случае, когда решение вырождено. Так, на рис. 2.36 в точке л:^Л(0) градиенты ограничений и ф₂ коллинеарны и решение вырождено. Изменение любого из этих условий на 8 приводит к тому, что решением оказывается точка х*(е), «далекая» от х*(0), и значение задачи также изменится существенно.

Рис. 2.36. Линии уровня функций ф₂ и f₀ в задаче, некорректной по решению Некорректность по решению может быть и в невырожденном случае, когда на некотором подмножестве множества V_x функция /₀(х) практически постоянна. На рис. 2.37 показаны функция/₀(х) и линия А на плоскости х_1? х₂, вдоль которой эта функция минимальна. Небольшое изменение функции/(х) (пунктир на рис. 2.37) приводит к резкому перемещению точки х*.

Рис. 2.37. Вид функции f₀ и проекции ее минимума в задаче, некорректной по решению.