Алгоритм решения задачи условной оптимизации в общем виде

Условный экстремум в общем случае

Условный экстремум в случае ограничений неравенств

(1.13)

Решим эту задачу без ограничений

и удовлетворяет условию

при

где УЭ – условный экстремум,

БЭ – безусловный экстремум.

Если объединить два условия, то получаем необходимое условие существование экстремума (условие дополняющей нежесткости):

(1.14)

Рассмотрим неравенства такого вида:

Составляем функцию Лагранжа

Необходимое условие (теорема Куна-Таккера)

Если – точка минимума функции f(x)при ограничении удовлетворяющих условию регулярности (линейная независимость градиентов), то существуют такие неотрицательные числа , что выполняется

(1.16)

(1.17)

(1.18)

(1.19)

Общий вид задачи или задача условной минимизации в общем виде записывается следующим образом:

(1.20)

Необходимые условия Куна-Таккера:

(1.21)

(1.22)

(1.23)

(1.24)

(1.25)

(1.26)

(1.27)

(1.28)

- общее число ограничений неравенств

1)Найти без учета всех ограничений неравенств. Если , в которой достигается удовлетворяет всем ограничениям неравенства, то задача решена. В противном случае (не удовлетворяет хотя бы оному ограничению неравенств, либо не существует) принять ν=1 где ν – количество ограничений неравенств, рассматриваемых как равенство и перейти к пункту 2.

2)Решить методом Лагранжа задач поиска , каждый из которых ν ограничений неравенств рассматриваются как равенства, а остальные r- ν ограничений неравенств не рассматриваются.

3)Выбрать из полученных в пункте 2 точек , которые удовлетворяют отброшенным неравенствам. Если ν>r принять ν= ν+1 и перейти к пункту 2. Если ν=r, то перейти к пункту 4.

4)Выбрать из полученных в пункте 3 точек ту, для которой целевая функция минимальна. Данная точка является решением задачи.

Недостаток этого способа – высокая трудоемкость:

- число уравнений

Достоинство этого способа – дает точное решение задачи. Решение улучшено быть не может.