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

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

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