══ Задачей линейного программирования со смешанными ограничениями называется задача максимизации по переменным ═линейного функционала
═══════════════════════════════════════════════════ ════════════════════════════ (1)
при линейных ограничениях
,═════════════════════════════════════════════════ ════════════════════════════ (2)
,════════════════════════════════════════════════ ════════════════════════════ (3)
.═════════════════════════════════════════════════════════════════════════ ════════════════════════════ (4)
Здесь , матрицы ═имеют соответственно размеры . Будем называть задачу (1)-(4) прямой задачей линейного программирования.
══ Двойственной задачей к задаче (1)-(3) называется задача линейного программирования минимизации по переменным ═линейного функционала
══════════════════════════════════════════════════ ════════════════════════════ (5)
при линейных ограничениях
,═════════════════════════════════════════════════ ════════════════════════════ (6)
,════════════════════════════════════════════════ ════════════════════════════ (7)
.══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════ ═══════════════════════════════════════════════ (8)
Здесь через ═обозначается матрица полученная транспонированием матрицы .
══ Теорема двойственности. Для того, чтобы задача линейного программирования (1)-(4) имела решение необходимо и достаточно, чтобы имела решение двойственная задача (5)-(8). При в случае существования решений оптимальные значения функционалов в этих задачах совпадают.
══ Критерий оптимальности. Пусть ═удовлетворяют
ограничениям (2)-(4), ═удовлетворяют
ограничениям (6)-(8). Для того, чтобы ═являлись решением задачи
(1)-(4), а ═являлись решением задачи
(5)-(8), необходимо и достаточно, чтобы выполнялись следующие условия
называемые условиями дополняющей
нежесткости:
,
.
Определение. Функцией Лагранжа задачи линейного программирования (1)-(4) называется функция
.
Если следующим образом перегруппировать слагаемые функции Лагранжа
,
то получается функция Лагранжа двойственной задачи. На этом замечании основан способ построения двойственной задачи в результате преобразования функция Лагранжа прямой задачи:
╥ слагаемые, в которые не входят переменные прямой задачи, образуют функционал двойственной задачи;
╥ слагаемые, умножаемые на одну и ту же переменную прямой задачи, образуют ограничение двойственной задачи;
╥ переменным прямой задачи на знак, которых не наложены ограничения, соответствуют ограничения типа равенства в двойственной задаче;
╥ переменным прямой задачи на знак, которых═ наложены ограничения неотрицательности, соответствуют ограничения типа неравенства в двойственной задаче, причем знак его выбирается таким образом, чтобы при нарушении неравенства, соответствующее слагаемое штрафовало функционал в функции Лагранжа двойственной задачи;
╥ ограничениям типа неравенства в прямой задаче соответствуют неотрицательные переменные в двойственной задаче;
╥ ограничениям типа равенства в прямой задаче соответствуют═ переменные произвольного знака в двойственной задаче.
══ Будем говорить, что набор векторов ═образует седловую точку функции Лагранжа, если для любых ═справедливы неравенства
.
1. Если ═решение задачи линейного программирования (1)-(4), то существуют такие векторы , что набор векторов ═образует седловую точку функции Лагранжа.
2. Если набор векторов ═образует седловую точку функции Лагранжа, то ═является решением задачи линейного программирования (1)-(4), а ═является решением задачи линейного программирования (5)-(8).