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

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


          -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 ограничений имеют форму
неравенств, причем со знаком « ³ ».

     Построим двойственную задачу к задаче 3а.                                                    В соответствии с
формализмом построения                              двойственной                     задачи   к    задаче   линейного
программирования на максимум целевой функции (см. задача 4), вектор
неизвестных u двойственной задачи должен быть n -мерным и иметь
первые l положительных координат

                                                æ u1 ö÷
                                                çç               ÷
                                                 çç L ÷÷
                                                  çç             ÷÷
                                                   çç u l ÷÷÷
                                           u = çç l +1 ÷÷ Î R n , u i ³ 0, i Î {1,L, l } ,
                                                    ççu ÷÷÷
                                                     çç           ÷÷
                                                      çç L ÷÷÷
                                                       ççè u n ÷ø÷
                                                         ç         ÷÷

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

                  I (u ) = -å (-ci ) u i + å ci u i = å ci u i = c, u ® max .
                                       l                         n             n


                                      i =1                     i =l +1        i =1




                          -å a1i u i + å (-a1i ) u i ³ -b1 Þ å a1i u i £ b1 ,
                                 l                     n                              n


                                i=1               i =l +1                            i =1



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

                         -å ami u i + å (-ami ) u i ³ -b m Þ å ami u i £ b m ,
                            l                      n                                   n


                           i=1                   i= l +1                              i =1




                  -å (-am+1i ) u i + å am+1i u i ³ b m+1 Þ å am+1i u i ³ b m+1 ,
                     l                                     n                           n


                    i=1                             i =l +1                           i =1



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



                                                                         95