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

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


     Заметим, что

                                     æ m         ö                                          æ k          ö
             æ å ai1v i ö÷ çç a v i ÷÷                             æ å ai1v i ö÷ çç a v i ÷÷
             çç *            ÷÷ çç i=1 å    i1 0 ÷
                                                 ÷÷                ç
                                                                   çç iÎI **         ÷÷ çç i =må    i1 0 ÷
                                                                                                         ÷÷
             çç iÎI           ÷÷ ç                ÷                 ç                 ÷÷ ç                ÷
    AI * v = çç L ÷÷÷ = çç L ÷÷ = A v0 , AI ** v = çç L ÷÷÷ = çç L ÷÷÷ = A**T v0** , (14)
     *T *                            ç            ÷   * T * **T **                          ç
              ççç           i÷ ÷÷ çç m
                                                  ÷÷                çç              i÷ ÷÷ çç k
                                                                                                           ÷÷
                  å
               çç *   a   v          ç             ÷
                                                   ÷                 ç å
                                                                     çç **   a    v          ç
                                                                                        ÷÷ ç a v ÷÷
                                                                                                            ÷
                                 ø÷ ççå in 0 ÷÷                                          ø÷ ççå in 0 ÷÷
                       in       ÷÷ ç a v ÷     i                               in                      i
                è iÎI                                                 èiÎI
                                     çè i=1        ø÷                                       èç i =m       ø÷

    где

                          ìïv i ,     i Î I *,             ìïv i , i Î I ** ,
                   v0i = ïí                          v i
                                                         =  ïí                                         (15)
                           ïï 0 i Î {1,L, m} \ I * , 0 ïï 0 i Î {M + 1,L, k } \ I ** .
                            î                                î

     Из соотношений (14) следует, что равенству (13) можно придать вид

                             -c = A*T v0* - A*T v0** + AT v0 - E%JT% m% .                              (16)

                    æ *ö
                   çç v0 ÷÷
    Полагаем v0 = ççç v0** ÷÷÷÷ Î V% . Тогда для всех u Î U% в силу (16) имеем
                    ç ÷÷
                    çè v0 ÷ø

                                         L (u, v0 ) - L (u0 , v0 ) =

                 = c, u + v0* , A*u - b * + v0** , - A**u + b** + v0 , Au - b -


                - c, u0 - v0* , A*u0 - b* - v0** , - A**u0 + b** - v0 , Au0 - b =

           = c, u - u0 + v0* , A* (u - u0 ) + v0** , - A** (u - u0 ) + v0 , A (u - u0 ) =


                             = c + A*T v0* - A**T v0** + AT v0 , u - u0 =


           = -( A*T v0* - A*T v0** + AT v0 - E%JT% m%) + A*T v0* - A**T v0** + AT v0 , u - u0 =


                                 = E%JT% m%, u - u0 = E%JT% m%, u ³ 0 .

     Таким образом, справедливо неравенство

                                   L (u , v0 ) ³ L (u0 , v0 ) , "u Î U% .




                                                    104