Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 30 стр.

Линейное программирование


     Если провести аналогичные рассуждения для построения ДЗ для ЗЛП,
записанной в канонической форме, то мы получим задачу вида:
                                     m
                                   ∑ bi y i → min
                                     i =1
                            m
                            ∑ a ij y i ≥c j ,    j =1,..., n .
                            i =1
      Пример 1. Построить ДЗ к следующей задаче
                        4 x1 +5 x 2 −x 3 −6 x 4 → min
                           4 x1 −x 2 −x3 −3x 4 ≤7
                           −x1 +x 2 −x 3 −x 4 ≥6
                             −x1 +2 x 2 −x 3 =−1
                                x1 ≥0, x 2 ≤0
Решение.
      В ДЗ к исходной задаче будет 3 переменных (в исходной задаче 3 огра-
ничения) и 4 ограничения (в исходной задаче 4 переменных). Поскольку в
исходной задаче целевая функция минимизируется, воспользуемся таблицей
слева направо. Для иллюстрации построим аналогичную таблицу для данной
конкретной задачи.

            Исходная задача                              Двойственная задача
     4 x1 +5 x 2 −x 3 −6 x 4 → min                       7 y1 +6 y 2 − y 3 → max
        4 x1 −x 2 −x 3 −3x 4 ≤7                                   y1 ≤0
        −x1 +x 2 −x 3 −x 4 ≥6                                     y 2 ≥0
          −x1 +2 x 2 −x 3 =−1                               y 3 −любого знака
                  x1 ≥0                                     4 y1 − y 2 − y 3 ≤4
                  x 2 ≤0                                   − y1 + y 2 +2 y 3 ≥5
           x 3 −любого знака                               − y1 − y 2 − y 3 =−1
           x 4 −любого знака                                 −3 y1 − y 2 =−6

     Заметим, что прежде чем строить двойственную задачу, исходную
можно вначале привести к симметричной или канонической форме, а затем
по шаблону к полученной форме задачи построить двойственную. При этом
полученные разными способами двойственные задачи будут эквивалентны-
ми.
     Выпишем основные практически значимые свойства, которые справед-
ливы для пары двойственных задач. Рассмотрим, например, в качестве пары
двойственных задач симметричную и двойственную к ней. В матричной
форме они записываются следующим образом:
       c T x → max          b T y → min


                                            32