Математическое программирование (линейное программирование). Киселева Э.В - 47 стр.

    Модель двойственной задачи примет вид:                                  Решение. Прежде всего приведем модель к виду, для которо-
             W = b1 y1 + b2 y 2 + L + bn y n → min,                    го изложены правила построения двойственных задач.
                                                                            Преобразуем третье ограничение, умножив обе части нера-
                  ⎧ a11 y1 + a21 y 2 + L + am1 y m ≥ c1 ,              венства на –1 и изменив знак неравенства на противоположный:
                  ⎪a y + a y + L + a y ≥ c ,                                                     − 6 х1 − х2 + 4 х3 ≤ −1.
                  ⎪ 12 1      22 2          m2 m      2
                  ⎨                                            (7.2)
                  ⎪ L L L L L L L                                          В результате исходная задача примет вид:
                  ⎪⎩a1n y1 + a2n y 2 + L + amn y m ≥ cm ,                    Z = x1 + 2 x2 − 3 x3 + x4 → max ,
                                                                               ⎧ x1 − 3 x2          + x4 ≤ 5 , y1 ≥ 0
                        yi ≥ 0 (i = 1, m).                                     ⎪                                                   (7.3)
                                                                               ⎨ 2 x1 − 7 x2 + 3 x3 − x4 = 7 , y 2 0
    Если ввести в рассмотрение матрицы:                                        ⎪ − 6x − х + 4x
                                                                               ⎩       1    2      3     ≤ 1, y3 ≥ 0
             ⎛ a11 L a1n ⎞
             ⎜            ⎟                                                     x1 ≥ 0 , x2 ≥ 0 ,    x3 ≥ 0.
         A = ⎜ LLL ⎟ , b = (b1 ,K ,bm ) , c = (c1 ,K ,cn ),
                                                T

             ⎜ a La ⎟
             ⎝ m1     mn ⎠                                                  Согласно правилам двойственная задача будет содержать три
                   X = ( x1 ,K , xn ) , Y = ( y1 ,K , ym ) ,
                                     T                                 переменные (они записаны справа от ограничений), причем
                                                                        у1 ≥ 0 , у3 ≥ 0,    так    как    соответствуют   ограничениям-
то пара симметричных двойственных задач в матричной форме
примет вид:                                                            неравенствам исходной задачи, а у2 является свободной перемен-
       Прямая задача            Двойственная задача                    ной: у2 <> 0 (у2 соответствует ограничению-равенству исходной за-
                                                                       дачи).
       AX ≤ b ,                                Y ≥ 0,                       Матрицей системы ограничений двойственной задачи явля-
                                                                       ется матрица, транспонированная к исходной:
       X ≥ 0,                                  YA ≥ с ,
                                                                                                   ⎛ 1 2 − 6⎞
       Z = сX → max.                           W = Yb → min.                                       ⎜            ⎟
                                                                                                   ⎜ − 3 − 7 − 1⎟
                                                                                                А =⎜
                                                                                                 Т
                                                                                                                  .
   Пример 7.2. Составить двойственную задачу к следующей                                               0   3 4⎟
                                                                                                   ⎜            ⎟
ЗЛП:                                                                                               ⎜ 1   − 1  0 ⎟
                Z = x1 + 2 x2 − 3 x3 + x4 → max ,                                                  ⎝            ⎠
                                                                           Правыми частями системы ограничений двойственной зада-
                       ⎧ x1 − 3 x2          + x4 ≤ 5 ,                 чи станут коэффициенты (1, 2, –3, 1) целевой функции исходной
                       ⎪                                               задачи.
                       ⎨ 2 x1 − 7 x2 + 3 x3 − x4 = 7 ,
                       ⎪ 6x + х − 4x                                       Каждой неотрицательной переменной исходной задачи соот-
                       ⎩ 1                       ≥ 1,
                                  2      3                             ветствует ограничение-неравенство того же смысла:
                     x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0
и показать взаимосопряженность полученной пары двойственных
задач.
                                    95                                                                         96