Элементы теории двойственности. Чернышова Г.Д - 6 стр.

    Таким образом под двойственной задачей (ДЗ) к исходной понимается
задача линейного программирования, которая строится по следующим пра-
вилам, приведенным в таблице.

          Исходная задача                   Двойственная задача
            n                                    m

           � c j x j � max
            j �1
                                                �b y
                                                i �1
                                                         i    i   � min

                   n
                                                             yi � 0
                �a
                j �1
                        ij   x j � bi

                   n
                                                             yi � 0
                �a
                j �1
                        ij   x j � bi

                   n
                                              y i – любого знака
                �a
                j �1
                        ij   x j � bi

                       xj � 0                        m

                                                 �a
                                                  i �1
                                                             ij   yi � c j

                       xj � 0                        m

                                                 �a
                                                  i �1
                                                             ij   yi � c j

         x j – любого знака                          m

                                                 �a
                                                  i �1
                                                             ij   yi � c j


     Замечание. Когда целевая функция в исходной задаче минимизирует-
ся, таблица прочитывается справа налево.
     Данная таблица позволяет формулировать несколько общих правил
построения двойственных задач:
       ● каждому i-му ограничению исходной задачи соответствует пере-
          менная yi в ДЗ, и, наоборот, каждому k-му ограничению ДЗ соот-
         ветствует переменная xk исходной задачи;
      ● матрицы ограничений в исходной и двойственной задачах взаим-
        но транспонированы;
      ● правые части ограничений исходной задачи становятся коэффи-
        циентами целевой функции в ДЗ, а коэффициенты целевой функ-
        ции исходной задачи – правыми частями ограничений в ДЗ;
      ● если целевая функция в исходной задаче максимизировалась (ми-
        нимизировалась), то в ДЗ целевая функция минимизируется (мак-
        симизируется).
                                        6