Двойственная задача

   На основе двойственной задачи создан эффективный симплекс-метод решения линейных задач. Двойственная задача - это вспомогательная задача, формулируемая по  определенным правилам  из условий исходной задачи в стандартной форме. Чтобы сформулировать условия двойственной задачи расположим коэффициенты прямой задачи в виде

                                           переменные прямой задачи

                                                  х₁   х₂   х₃    х_j     х_n

правые части ограничений   c₁   c₂   c₃    c_j     c_n

кoэффициенты                      a₁₁   a₁₂        a_1j    a_1n     b₁ <-  y₁ переменные

левых частей                           .     .           .      .    .                  двойственной

ограничений                          a_m1  a_m2        a_mj    a_mn   b_m <-  y_m задачи

двойственной                                            ^               ^

задачи                                    ограничение j         коэффициенты

                                                  двойственной       целевой функции

                                                 задачи                    двойственной

                                                                                 задачи

Получаем задачу:

Определить min или max линейной формы

        W= b₁y₁+b₂y₂  +...+ b_my_m

с ограничениями:

a₁₁y₁+a₂₁y₂+    a_m1y_m >=c₁

a₂₁y₁+a₂₂y₂+    a_m2y_m >=c₂

  .     .         .      .

a_1my₁+a_2my₂+    a_mny_m >=c_n

Следовательно, двойственная задача получается путем симметричного структурного преобразования условий прямой задачи по следующим правилам:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи

2)    каждой переменной прямой задачи соответствует ограничение двойственной задачи

3)    коэффициенты при переменных в ограничении прямой задачи становятся коэффициентами левой части соответствующего ограничения двойственной задачи, а коэффициенты в целевой функции становятся постоянной правой части этого же ограничения. Максимизация заменяется минимизацией со знаком >= в ограничении, а минимизация заменяется максимизацией со знаком <= в ограничении. Неограниченность в знаке переменной прямой задачи всегда обуславливает появление ограничения двойственной задачи в виде равенства. Двойственный симплекс-метод получает сначала недопустимое, но лучшее  чем оптимальное решение, обычный метод дает сначала допустимое, но неоптимальное решение. Заинтересованность  в определении оптимального решения прямой задачи путем решения двойственной задачи обусловлена тем, что трудоемкость вычислений в большей степени зависит от числа ограничений, чем от количества переменных.

На итерации, приводящей к оптимуму max Z=min W. В задаче максимизации целевая функция последовательно увеличивается от начального до оптимального, а в задаче минимизации она уменьшается от начального до оптимального.

        min

Z----à<--------W

        max