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

                 x1 ≥ 0 ⇒    y1 + 2 y 2 − 6 y 3 ≥ 1,                                           Z 1 = − x1 − 2 x 2 + 3 x3 − x 4 → min ,

                 x2 ≥ 0 ⇒     − 3 y1 − 7 y 2 − y 3 ≥ 2,                    ⎧− x1 + 3 x2 − x4 ≥ −5,             так как       y1 ≥ 0 ,
                                                                           ⎪
                                                                           ⎨− 2 x1 + 7 x2 − 3 x3 + x4 = −7 ,   так как       y2 ≥ 0,
                 x3 ≥ 0 ⇒ 3 y 2 + 4 y 3 ≥ −3.                              ⎪6 x + x − 4 x ≥ 1,
                                                                           ⎩ 1 2           3                   так как       y3 ≥ 0,
    Свободной   переменной х4 соответствует               ограничение-
равенство:
                        х4 <> 0 ⇒ у1 – у2=1.                                           x1 ≥ 0 ,     x 2 ≥ 0, x3 ≥ 0.
     Коэффициентами целевой функции W двойственной задачи,                   Умножив обе части первых двух ограничений на –1 и введя
которая (согласно правилам) минимизируется, становятся сво-              функцию Z= –Z1, получим эквивалентную ЗЛП:
бодные члены системы ограничений исходной задачи.                                       Z = x1 + 2 x 2 − 3 x 3 + x 4 → max,
     Итак, математическая модель двойственной задачи примет                            ⎧ x1 − 3 x 2 + x 4 ≤ 5 ,
вид:                                                                                   ⎪
                 W = 5 y1 + 7 y2 − y3 → min,                                           ⎨ 2 x1 − 7 x 2 + 3 x 3 − x 4 = 7 ,
                                                                                       ⎪ 6 x + x − 4 x ≥ 1,
                  ⎧ y1 + 2 y2 − 6 y3 ≥ 1,                                              ⎩ 1        2       3
                  ⎪ − 3 y − 7 y − y ≥ 2,                                                 x1 ≥ 0 ,    x2 ≥ 0, x3 ≥ 0,
                  ⎪      1       2     3                         (7.4)
                  ⎨
                  ⎪    3 y 2 + 4 y 3 ≥ − 3,                              которая совпадает с исходной.
                  ⎪⎩       y1 − y 2 = 1,                                     Таким образом, показана взаимосопряженность пары двой-
                        y1 ≥ 0, y3 ≥ 0.                                  ственных задач, что позволяет считать одну из них (безразлично
                                                                         какую) исходной, а вторую – двойственной к ней.
     Далее покажем взаимосопряженность полученной пары
двойственных задач, т.е. покажем, что задача, двойственная к                 Пример 7.3. Для задачи:
(7.4), совпадает с исходной (7.3).
                                                                                                 Z = 2 x1 + 6 x2 → max ,
     Для этого прежде всего преобразуем модель (7.4) к виду:
                  W1 = −5 y1 − 7 y 2 + y3 → max ,                                                ⎧ x1 + x2 ≤ 10 ,
                                                                                                 ⎨
                 ⎧− y1 − 2 y 2 + 6 y3 ≤ −1,   x1 ≥ 0                                             ⎩ − x1 + 2 x2 ≤ 11,
                 ⎪ 3 y + 7 y + y ≤ −2 ,       x2 ≥ 0                                             x1 ≥ 0 , x2 ≥ 0
                 ⎪ 1          2      3
                 ⎨                                                       составить двойственную и найти решение обеих задач.
                 ⎪    − 3 y 2 − 4 y 3 ≤ 3,    x3 ≥ 0
                 ⎪⎩   − y1 + y2 = −1,         x4   0                         Решение. Двойственной является задача:
                    y1 ≥ 0 , y3 ≥ 0.
    Согласно правилам построения двойственных задач получим
модель двойственной задачи:


                                97                                                                                98