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

Пусть дана задача нелинейного программирования
max: Z= z(X)(1)
qi (X) ≤ bi, i = 1.. m(2)
xj ≥0, j = 1.. n(3)
Запишем функцию Лагранжа: (4)
где λi, i=1..m – неопределенные множители Лагранжа; z(X) и qi(X)– выпуклые вверх функции.

Теорема Куна-Таккера. Чтобы план X0 был решением задачи (1) – (4) необходимо и достаточно, чтобы существовал вектор λ0 ≥ 0 такой, что пара (X00) для всех X ≥ 0 и λ ≥ 0.
L(X, λ0) ≤ L(X00) ≤ L(X0 ,λ)

Назначение сервиса. Онлайн-калькулятор используется для нахождения экстремума функции через множители Лагранжа в онлайн режиме с проверкой решения в MS Excel. При этом решаются следующие задачи:

  1. составляется функция Лагранжа L(X) в виде линейной комбинации функции F(X) и ограничений gi(x);
  2. находятся частные производные функции Лагранжа, ∂L/∂xi, ∂L/∂λi;
  3. составляется система из (n+m) уравнений, ∂L/∂xi = 0.
  4. определяются переменные xi и множители Лагранжа αi.
Количество ограничений, gi(x)
Заданы ограничения xi ≥ 0.
Примеры решения задач на тему Условия Куна-Таккера.

Чтобы функция двух векторных переменных (4) имела седловую точку, необходимо и достаточно выполнения следующих условий Куна-Таккера:
(5)
(6)
(7)
(8)

Если решается задача минимизации, то имеет место седловая точка (X0, Y0), если выполняются соотношения
L(X, λ0) ≤ L(X0, Y0) ≤ L(X0, Y)
Условия же Куна-Таккера существования седловой точки функции Лагранжа поменяют знак в (5) и (7) на противоположный.
Условия Куна-Таккера для максимизации функции
Условия Куна-Таккера для максимизации функции

По содержанию условия Куна-Таккера (5)–(8) эквивалентны условиям второй теоремы двойственности задач линейного программирования.

Пример. Проверить выполнение условий Куна-Таккера. Найти точку оптимума задачи линейного программирования с ограничениями:
f(x) = x12-x2 → min
g1(x) = x1 - 1 ≥ 0
g2(x) = 26 - x12-x22 ≥ 0
h1(x) = x1+x2 - 6 = 0

Решение:
Функция Лагранжа: L(X, λ) = x12-x2 - λ1(1-x1) + λ2(26-(x12+x22)) + λ3(6-(x1+x2))
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным хi и неопределенным множителям λ.
Проверим выполнение условий Куна-Таккера. Вычислим матрицы вторых производных целевой функции и функций ограничений.

Матрица Гессе Hf положительно полуопределена при всех значениях x, следовательно f(x) – выпуклая функция.
Ограничение g1(x) – линейная функция, которая одновременно является выпуклой и вогнутой.
Матрица Гессе для функции g2(x) имеет вид:

Δ1 = -2, Δ2 = 4.
Так как матрица Hg2 отрицательно определена, то g2(x) является вогнутой.
Функция h1(x) входит в линейное ограничение в виде равенства. Следовательно, условия (а), (б) и (в) Теоремы 1 выполнены. Найдем теперь точку оптимума x*.
Имеем:

Уравнение принимает следующий вид:

Для j=1 и j=2 соответственно можно получить следующие выражения:
j=1, 2x11 + 2x2μ2 + λ1 = 0
j=2, -1 + 2x2μ2 + λ1 = 0
Таким образом, условия Куна-Таккера для нашего примера имеют следующий вид:
2x11 + 2x2μ2 + λ1 = 0
-1 + 2x2μ2 + λ1 = 0
x1 + x2 – 6=0
μ1(x1-1) = 0
μ2(26 - x12 – x22) = 0
μ1, μ2 ≥ 0

Из третьего уравнения находим: x1 = 6-x2. Подставив значение x1 в остальные уравнения, получим:
2(6-x2) - μ1 + 2μ2(6-x2)
-1 + 2x2μ2 + λ1 = 0
μ1(6-x2 -1) = 0 → x2 = 5, x1 = 1
μ2(26 – (6-x2)2 – x22) = 0
Подставим x2 = 5 в первое и второе уравнения:

Из второго уравнения выразим λ и подставим в первое уравнение:
3 - μ1 - 8μ2 = 0
Пусть μ1 = 0,1 ≥ 0, тогда μ2 = 2,2 ≥ 0. Таким образом, точка x*=[5;1] является точкой минимума.