Линейное программирование в примерах и задачах. Методические указания. Корытов И.В - 7 стр.

                                                                                 ⎛ 3 5 F⎞
     Составление условия двойственной задачи                                     ⎜           ⎟
                                                                                 ⎜ 2 4 12 ⎟
                                                                                 ⎜ 3 2 10 ⎟
    Пример 2. Составить условие задачи, двойственной к                           ⎜           ⎟
данной.                                                                          ⎜ 0 −1 − 6⎟
                                                                                 ⎜ − 1 0 − 5⎟
                                                                                 ⎝           ⎠
                 F = 3 x1 + 5 x 2 → min                        Матрица, транспонированная к матрице исходной за-
                    ⎧2 x1 + 4 x 2 ≥ 12                    дачи (расширенная матрица двойственной задачи):
                    ⎪ 3 x + 2 x ≥ 10
                    ⎪ 1           2
                    ⎨                                                            ⎛3 2 3      0 − 1⎞
                    ⎪           x 2   ≤ 6                                        ⎜                 ⎟
                    ⎪⎩ x1             ≤ 5                                        ⎜ 5 4 2 −1 0⎟
                                                                                 ⎜ Z 12 10 − 6 − 5 ⎟
                        x1 ≥ 0, x 2 ≥ 0                                          ⎝                 ⎠

                                                          Составление ограничений и целевой функции двойст-
                                                          венной задачи
Приведение условия к стандартному виду
                                                               Ограничения двойственной задачи (на основе первых
     Поскольку в исходной задаче требуется найти мини-
                                                          двух строк расширенной матрицы):
мум целевой функции, то ограничения в системе необходи-
мо привести к неравенствам типа "≥" .                                     ⎧3 ≥ 2 y1 + 3 y 2       − y4
                                                                          ⎨
                                                                          ⎩5 ≥ 4 y1 + 2 y 2 − y 3
                 F = 3 x1 + 5 x 2 → min
                   ⎧ 2 x1 + 4 x 2 ≥ 12                         Целевая функция двойственной задачи (на основе по-
                   ⎪ 3 x + 2 x ≥ 10                       следней строки расширенной матрицы):
                   ⎪ 1
                   ⎨
                                 2
                                                                      Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max
                   ⎪        −  x 2  ≥ −6
                   ⎪⎩− x1           ≥ −5                  Условие двойственной задачи
                      x1 ≥ 0, x 2 ≥ 0                                Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max
                                                                          ⎧2 y1 + 3 y 2           − y4 ≤ 3
Работа с расширенными матрицами                                           ⎨
                                                                          ⎩4 y1     2 y 2 − y3         ≤ 5
    Расширенная матрица исходной задачи:
                                                                                y j ≥ 0, j = 1, K,4.


12                                                                                                              13