Двойственность в задачах линейного программирования

══ Задачей линейного программирования со смешанными ограничениями называется задача максимизации по переменным ═линейного функционала

═══════════════════════════════════════════════════ ════════════════════════════ (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).