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

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


программирования на минимум целевой функции (см. задача 3), вектор
неизвестных 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 ® min ,
                                              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



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

                    -å (-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 = b k +1 Þ å ak +1iu i = bk +1 ,
                     l                                     n                                     n


                    i =1                                 i=l +1                              i =1



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

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

                                                  ni
                                i =1                           i=l +1                       i =1




                                                                                 97