§4. Теорема Куна-Таккера.
Введем
понятие седловой точки функции многих
переменных. Дана некоторая функция
Q=Q(x1
,x2
,…, xn
, y1,
y2
,…, ym)
двух групп переменных x1
,x2
,…, xn
и y1,
y2
,…, ym
. Пусть по первой группе переменных
функцию Q
требуется максимизировать, по
второй-минимизировать.
Определение.
Точка
(xo1
,xo2
,…, xon
, yo1,
yo2
,…, yom
) = (Xo,Yo)
называется седловой точкой функции Q,
если в ней выполняется следующее
неравенство:
Q(X,
Yo)
≤ Q
(Xo,Yo)
≤ Q(Xo,Y).
Рассмотрим
следующую задачу выпуклого программирования:
(4.1)
Z
= f
(x1
,x2
,…, xn
) max,
1(x1
,x2
,…, xn
) ≤1,
(4.2)
2(x1
,x2
,…, xn
) ≤
2,
-
- - - - - - - - - - - - - -
m(x1
,x2
,…, xn
) ≤
m,
x1
≥ 0, x2
≥ 0, … , xn
≥ 0.
(4.3)
Перейдем
от этой задачи на условный экстремум к
задаче на безусловный экстремум с
помощью функции Лагранжа
(x1
,x2
,…, xn,
λ1,
λ2,…,
λm
) = f
(x1
,x2
,…, xn
) +
i
(bi
–
i(x1
,x2
,…, xn
)).
Предположим,
что найдена седловая точка функции
Лагранжа
(4.4)
(xo,
λo)
= (xo
1,
xo2,…,
xon
;
λo1,
λo2,…,
λom)
.
Тогда
справедливым будет следующее неравенство:
(x,
λo)
≤
(xo,
λo)
≤
(xo,
λ).
Задача
отыскания точки (xo,
λo)
из области определения функции(x,
λ),
удовлетворяющей неравенству (4.4),
называется задачей о седловой точке.
Теорема.
Точка xo
будет являться решением задачи ВП
(4.1)-(4.3) тогда и только тогда, когда
существует такая точка λo
≥ 0, что точка (xo,
λo)
является седловой точкой функции
Лагранжа
(x,
λ
).