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

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


                            -å (-aki )u i + å aki u i ³ b k Þ å aki u i ³ b k ,
                                  l                         n            n


                                 i=1                      i=l +1        i =1




                   å ak +1iu i - å (-ak +1i )u i = -(-bk +1 ) Þ å ak+1iu i = bk +1 ,
                    l                     n                                        n


                   i =1                 i=l +1                                 i=1



                    …………………………………………………..

                          å aniu i - å (-ani )u i = -(-b n ) Þ å ani u i = b n .
                           l                     n                             n


                          i =1                i= l +1                        i=1



     Таким образом, построенная задача линейного программирования
является задачей 1. Теорема доказана

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

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

     Задача 4а

        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 ® min ,

             a11v1 + L + am1v m - am+11v m+1 -L- ak 1v 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 ,

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

          -a1n v1 - L- amn v m + am+1n v m +1 + L + akn v k - ak +1n v k +1 - L- asn u s = -cn ,

                                       v1 ³ 0,L, v m ³ 0, v m +1 ³ 0,L, v k ³ 0 .

    Эта задача является задачей линейного программирования на минимум
целевой функции с n ограничениями. Первые l ограничений имеют форму
неравенств, причем со знаком « ³ ».

     Построим двойственную задачу к задаче 4а. В соответствии с
формализмом построения                                  двойственной    задачи         к   задаче    линейного
                                                                   96