Задачи Выпуклое программирование (примеры)
Задачи Выпуклое программирование (примеры)
Пример 1. Рассмотрим задачу

Точка X°=(2,1) — оптимальный план задачи,
— функция Лагранжа. Проверим выполнение условий Куна-Таккера:


(5)
Легко видеть, что эти условия выполняются на плане X°=(2,1) при
. Таким образом, пара
является седловой точкой функции Лагранжа:

Т. е., для любых
, и выполняется условие дополняющей нежесткости.
Пример 2. Пусть имеем задачу
(6)
Где
— матрица (
).
Задача (6) является задачей выпуклого программирования
(задача квадратичного программирования). Запишем для нее функцию Лагранжа
.
Тогда двойственная функция запишется в виде:
. (7)
Так как функция Лагранжа строго выпукла по X (D>0), то точка минимума X(l) задачи (7) совпадает со стационарной точкой функции Лагранжа:

Найденное значение
подставим в функцию Лагранжа. Тогда
.
Из теории матриц известно, что
, если
, и, значит, функция
является строго вогнутой. Следовательно, ее точка максимума совпадает с ее стационарной точкой, т. е.
.
Итак, l° — решение двойственной задачи
, к задаче (6). Подставив в выражение для X(l) вектор l° получим решение X°=X(l°) исходной задачи (6).