Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Теорема Куна—Таккера

Теорема Куна—Таккера. Центральное место в теории нелинейного программирования занимает теорема Куна— Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.

Теорема 2.3. (Достаточное условие экстремума).

Если (х, и) — седловая точка функции Лагранжа, в области xX⊇D, и≥0,то х является оптимальным планом задачи (2.28), причем справедливо так называемое правило дополняющей нежесткости:

Доказательство.

По определению седловой точки

при всех xX, и≥0. Из второго неравенства в (2.32) следует, что


Однако (2.33) может иметь место только тогда, когда gi(x)≤0 при всех i∊1:m. Действительно, если существует такое k, что gk(x)>0, то, положив иi=0 для всех i ≠ k и выбрав достаточно большое иk > 0, можно добиться того, что значение

окажется больше постоянного выражения

Из того, что для всех i∊1:m выполняются неравенства gi(x)≤0, следует, что х является допустимым планом задачи (2.28).

Если в левую часть неравенства (2.33) подставить значения ui = 0, i∊1:m, то получим, что

Вместе с тем из того что, gi(x)≤0 и ui ≥0, следует оценка

Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке х:

Тогда на основании левой части неравенства седловой точки (2.32) имеем, что для всех хХ (в том числе и для хD)

Но условию ЗНП для любых хD верны неравенства gi(x)≤0, что, в сочетании с условием ui ≥0, позволяет записать

Значит,

Окончательно получаем, что для любых хD справедливо соотношение f(x)f(x), т. е. х — оптимальный план задачи (2.28). A