2.10 Двойственность в линейном программировании

В задаче ЛП есть интересные аспекты, связанные с понятием двойственности и имеющие важное теоретическое и практическое значение. К рассмотрению этого понятия мы и перейдем.

Для задачи линейного программированния (2.1)-(2.3) в кано­нической форме рассмотрим функцию Лагранжа ги/ = сх + и{Ь — Ах), которая при фиксированном векторе-строке и = (щ,..., ит) совпадает на множестве допустимых решений <5 с целевой функ­цией ио = сх. Следовательно, при ж 6 <5 и с — и А > 0 имеем ю = сх + и{Ь — Ах) = иЬ-\- (с — иА)х > иЬ, т.е. величина иЬ являет­ся в этом случае оценкой снизу для оптимального значения целе­вой функции задачи (2.1)-(2.3). Поиск наилучшей нижней оценки приводит к задаче

М' = MrsM.

 

 

и

 

иА < с

которая представляет собой задачу ЛП относительно и £ Пт ■ Полученная таким образом задача (Д) называется двойственной к исходной задаче (2.1)-(2.3), которая в свою очередь называется прямой. Если исходная (прямая) задача ЛП дана в общей форме, то двойственная задача определяется следующим образом:

Прямая задача

 

Двойственная задача

п

 

т

тш ^ с

 

тах ^ ЬiUi

3 = 1

 

1=1

а{Х > Ь{

г £ 1\

щ > 0

(ЦХ = Ь{

г £ 12

щ — своб.

х3 > 0

з е Л

иА,3 < с3-

х3- — своб.

з е з2

иА3 = с3

где а{ = (ац,..., агга) — г-я строка матрицы А, А; = (а^-, ..., атз)Т — 3~ъ столбец матрицы А, II и 12 = {1, • • •, т}, 11 П /2 = 0; Л и /2 = {1,..., га}, Л П 32 = 0.

Важной чертой отношения двойственности является симме­трия, выражающаяся в том, что задача, двойственная к двой­ственной задаче ЛП, совпадает с прямой задачей ЛП. В самом деле, запишем двойственную задачу в виде

т i=l

{-А])иТ > -с3, 2 £ Л, {-А])чт = -с,-, 2 е Зг, Щ > 0, г £ 1\, и{ — своб., г £ 12

и, рассматривая ее как прямую, воспользуемся приведенными вы­ше правилами и сформулируем двойственную к ней задачу:

п

шах^-еЛж.?

3 = 1

х3 > 0, 1 е .11, х3- — своб., ; е

хТ{-а1) < ~Ьг, г е II, хт(-а[) = -Ъг, г £ 12-

Нетрудно видеть, что полученная задача совпадает с исход­ной прямой задачей. Таким образом, можно считать, что все за­дачи ЛП разбиваются на пары взаимно двойственных задач. Из простых, но достаточно важных свойств взаимно двойственных задач отметим следующие.

Свойство 2.1 Если х и и - допустимые решения соответ­ственно прямой и двойственной задачи, то ги(х) > г(и).

В частном случае, когда прямая задача дана в канонической форме, приведенное выше неравенство использовалось фактиче­ски для определения двойственной задачи. В общем случае оно также легко проверяется:

п та

ио(х) = сх > ^2(иАз)хз = ^иг(аг'ж) > иЬ = г(и).

3 = 1 г = 1

Свойство 2.2 Если ж и ¥ — допустимые решения соответ­ственно прямой и двойственной задачи и ио(ж) = г(й), то ж и и - оптимальные решения соответствующих задач.

Доказательство. Пусть ж - произвольное допустимое решение прямой задачи.   Тогда, учитывая Свойство 2.1, имеем ги(х) >

30г(й) = ио(х), что и означает оптимальность ж. Аналогичным образом устанавливается оптимальность ¥.

Фундаментальный характер имеют две рассматриваемые ни­же теоремы двойственности.

Теорема 2.2 (Первая теорема двойственности.) Прямая и двойственная к ней задачи либо одновременно разрешимы, либо одновременно неразрешимы. При этом в первом случае опти­мальные значения целевых функций этих задач совпадают, а во втором случае, по крайней мере, одна из задач неразрешима в силу несовместности ее ограничений.

Доказательство. Без органичения общности можно считать, что прямая задача представлена в канонической форме (2.1)-(2.3), а двойственная к ней имеет вид (Д). Пусть задача (2.1)-(2.3) раз­решима и В - ее прямо и двойственно допустимый базис, суще­ствование которого гарантируется Утверждением 5. Согласно определению прямой и двойственной допустимости имеют место неравенства В~1Ь > 0 и сдг — свВ~1И > 0. Первое из этих нера­венств, как известно, свидетельствует о том, что базисное реше­ние х с компонентами хв = В~1Ь, ждг = 0 является допустимым решением задачи (2.1)-(2.3). Из второго неравенства следует, что вектор ¥ = свВ~1 является допустимым решением двойственной задачи (Д), поскольку ~й~В = св, сдг — йИ > 0 и, следовательно, НА < с.

Для указанных допустимых решений ж и ¥ соответственно прямой и двойственной задачи имеют место равенства

ги(х) = св~х~в = свВ~1Ь = ~й~Ъ = г(й),

что согласно Свойству 2.2 означает оптимальность этих реше­ний. Таким образом, предположив разрешимость прямой задачи, мы доказали разрешимость двойственной к ней задачи и совпаде­ние оптимальных значений целевых функций этих задач. В виду симметричности ситуации из разрешимости двойственной задачи аналогичным образом следует разрешимость прямой задачи и совпадение оптимальных значений целевых функций.

Для завершения доказательства теоремы остается лишь по­казать, что задачи разрешимы, если их ограничения совместны. Последнее легко следует из Свойства 2.1 и критерия разрешимо­сти задачи ЛП. В самом деле, пусть ¥ — некоторое допустимое решение двойственной задачи (Д). Тогда по Свойству 2.1 для лю­бого допустимого решения ж задачи (2.1)-(2.3) имеет место нера­венство ги(х) > г (и), т.е. целевая функция прямой задачи огра­ничена снизу на (непустом) множестве допустимых решений, что согласно Теореме 2.1 влечет разрешимость задачи (2.1)-(2.3). Из этого далее следует разрешимость и двойственной задачи. Тео­рема доказана.

В формулировке следующей теоремы мы предполагаем, что прямая и двойственная задачи заданы в общей форме.

Теорема 2.3 (Вторая теорема двойственности или теорема о дополняющей нежесткости). Допустимые решения ж и¥ соот­ветственно прямой и двойственной задачи оптимальны тогда и только тогда, когда

¥г(агж — 6г) = 0 для всех г, (2-9)

(cj — 'й~Aj)~Xj = 0 для всех ]. (2.10) Доказательство. Введем обозначения тг- = ¥г(агж — 6г), а3- =

(cj — ИА^х^ и заметим, что из допустимости решений ж и ¥ сле­дует неравенство тг- > 0 для всех г и а3- > 0 для всех ]. Отсюда в свою очередь следует, что равенство имеет место, если и только если выполняются равенства (2.9) и (2.10). С другой стороны, сх—йЬ = 0 в том и только в том случае, если х и й - оптимальные решения задач. Наконец, чтобы за­вершить доказательство, к сказанному достаточно добавить, что справедливо равенство

проверяемое непосредственно. Теорема доказана.

Полезным (и вполне очевидным) следствием последней теоре­мы является, например, следующее утверждение. Если некото­рая неотрицательная переменная прямой (соответственно, двой­ственной) задачи принимает положительное значение в каком-нибудь оптимальном решении данной задачи, то соответствую­щее ограничение-неравенство двойственной (соответственно, пря­мой) задачи выполняется в виде равенства для любого оптималь­ного решения этой задачи.

Возвращаясь к первой теореме двойственности и ее доказа­тельству, мы видим, что, решая задачу (2.1)-(2.3) симплекс-ме­тодом, мы одновременно с ее оптимальным решением получаем также и оптимальное решение двойственной задачи (Д) или уста­навливаем неразрешимость обеих задач. Это позволяет опреде­лить другой метод решения задачи ЛП, а именно, двойственный симплекс-метод. В связи с этим исходный симплекс-метод приня­то называть прямым.