Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 94 стр.

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


     Пример 2. Прямая задача линейного программирования на максимум
целевой функции имеет вид

                               2u1 - 2u 2 + 4u 3 + 6u 4 + 9u 5 ® max,
                              3u1 - 22u 2 - u 3 + 14u 4 -12u 5 £ 5,
                              -14u1 + 5u 2 + 3u 3 + u 4 + 4u 5 £ 22,
                              12u1 - 4u 2 + 3u 3 + 15u 4 -12u 5 ³ 19,
                               22u1 -14u 2 + 71u 3 + 4u 4 + 12u 5 ³ -10,
                               21u1 -16u 2 -14u 3 - 4u 4 + 13u 5 = 18,
                               4u1 + 17u 2 + 2u 3 + u 4 - 4u 5 = 10,
                              u1 ³ 0, u 2 ³ 0, u 3 ³ 0.

     Запишем для нее двойственную задачу (задача 4).

                           5v1 + 22v 2 -19v3 + 10v 4 + 18v5 + 10v 6 ® min,
                           3v1 -14v 2 -12v3 - 22v 4 + 21v5 + 4v 6 ³ 2,
                           -22v1 + 5v 2 + 4v3 + 14v 4 -16v 5 + 17v 6 ³ -2,
                           -v1 + 3v 2 - 3v3 - 71v 4 -14v 5 + 2v 6 ³ 4,
                           -14v1 - v 2 + 15v3 + 4v 4 + 4v 5 - v6 = -6,
                          12v1 - 4v 2 -12v3 + 12v 4 -13v5 + 4v 6 = -9,
                           v1 ³ 0, v 2 ³ 0, v 3 ³ 0, v 4 ³ 0.

     Теорема 1. Задача 1 и задача 3 являются взаимодвойственными.

     Доказательство. Требуется доказать, что задача двойственная к
задаче 3 совпадает с задачей 1. Запишем задачу 3 в координатной форме.

     Задача 3а

       I Д (v) = -b1v1 -L- b m v m + b m+1v m+1 + L + b k v k - b k +1v k +1 - L- b s u s ® max ,

            a11v1 + L + am1v m - am+11v m+1 -L- ak1v k + ak +11v k +1 + L + as1u s ³ -c1 ,

       ………………………………………………………………………

             a1l v1 + L + aml v m - am+1l v m+1 - L- akl v k + ak +1l v k +1 + L + asl u s ³ -cl ,

      -a1l +1v1 -L- aml +1v m + am+1l +1v m+1 + L + akl +1v k - ak +1l +1v k +1 -L- asl +1u s = cl +1 ,

       ………………………………………………………………………


                                                      94