Условия Куна–Таккера

Метод множителей Лагранжа можно использовать при построении критериев оптимальности для задач с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нелинейного программирования с ограничениями как в виде равенств, так и в виде неравенств. Рассмотрим следующую общую задачу нелинейного программирования

Минимизировать f(x) при ограничениях ,

,

где .

Ограничения в виде неравенства называется активным, или связывающим, в точке , если , и неактивным, или не связывающим, если где - допустимая точка, то есть удовлетворяющая всем ограничениям. Если существует возможность обнаружить ограничения, которые неактивны в точке оптимума, до непосредственного решения задачи, то эти ограничения можно исключить из модели и тем самым уменьшить ее размеры.

Кун и Таккер построили необходимые и достаточные условия оптимальности для задач нелинейного программирования, исходя из предположения о дифференцируемости функций Итак, задача Куна–Таккера состоит в том, чтобы найти векторы удовлетворяющие следующим условиям:

Прежде всего, проиллюстрируем условия Куна–Таккера на примере.

Минимизировать при ограничениях

Записав данную задачу в виде задачи линейного программирования, можно получить

Уравнение (2.1), входящее в состав условий Куна–Таккера, принимает следующий вид:

откуда

Неравенства (2.2) и уравнения (2.3) задачи Куна–Таккера в данном случае записываются в виде

Уравнения (2.4), известные как условие дополняющей нежесткости, принимают вид

Заметим, что на переменные U₁ и U₂ накладывается требование неотрицательности, тогда как ограничение на знак отсутствует. Таким образом, для данной задачи условия Куна–Таккера записываются в следующем виде: