Задача линейного программирования. Горячев Л.В. - 4 стр.

4

                                        прямая        двойственная
                                      (c, x) − min     (b, y) − max
                                         Ax ≥ b          AT y ≤ c
                                          x≥0              y≥0

Двойственную задачу к задаче линейного программирования также легко вывести с помощью функ-
ции Лагранжа.

                                       (c, x) − max    (b, y) − min
                                          Ax = b         AT y ≥ c
                                           x≥0

Каждой задаче ЛП в произвольной форме можно поставить в соответствие двойственную задачу,
руководствуясь следующими, достаточно общими правилами:

    1. Каждому i – му ограничению типа неравенства или равенства соответствует переменная yj
       двойственной задачи и, наоборот, каждому j – му ограничению типа равенства или неравен-
       ства двойственной задачи соответствует переменная xj прямой задачи.

    2. Матрица коэффициентов A при переходе к двойственной задаче транспонируется, то есть
       строка коэффициентов (a1j , a2j , . . . , amj ) в j – м ограничении двойственной задачи при пере-
       менных y1 , y2 , . . . , ym есть столбец коэффициентов при xj в ограничениях задачи.

    3. Свободные члены ограничений одной из задач являются коэффициентами при соответствую-
       щих переменных в целевой функции другой задачи. При этом максимизация (минимизация)
       меняется на минимизацию (максимизацию).

    4. В исходной (прямой) задаче ограничения–неравенства следует записать со знаком ”≤” при
       максимизации и со знаком ”≥” при минимизации.

    5. Каждому j – му ограничению-неравенству исходной задачи, записанному в соответствии с
       пунктом 4, отвечает в двойственной задаче условие неотрицательности yi ≥ 0, а равенству —
       переменная yi без ограничений на знак, то есть произвольная. Наоборот, ограничению неот-
       рицательности на xj – ю переменную соответствует в двойственной задаче j – е ограничение-
       неравенство, а произвольной по знаку переменной xj равенство.

Пример: построить двойственную задачу к следующей:

                                     x1 −2x2 +x3 −x4 +x5 − min
                                     x1 −2x2 −x3 +3x4 −2x5 = 6
                                    2x1 +3x2 −2x3 −x4 +x5 ≤ 4
                                     x1      +3x3     −4x5 ≥ 8
                                     x1 ≥ 0   x3 ≥ 0 x5 ≥ 0

Решение. Прежде чем уступить к построению двойственной задачи с помощью элементарных пре-
образований в соответствии со сформулированными правилами, приведем задачу к виду

                                     x1 −2x2 +x3 −x4 +x5 − min
                                     x1 −2x2 −x3 +3x4 −2x5 = 6
                                   −2x1 −3x2 +2x3 +x4 −x5 ≥ −4
                                     x1      +3x3     −4x5 ≥ 8
                                    x1 ≥ 0    x3 ≥ 0 x5 ≥ 0

В таком виде наша задача отличается от задачи (7)–(9) ограничением-равенством и отсутствием
ограничения на знак переменных x2 и x4 . Согласно правилам записи двойственная задача прини-