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

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


           = - A*T v * , u + A**T v ** , u - AT v , u = - v* , A*u + v** , A**u - v , Au ³

                                                              æ-b* ö÷                æ v * ö÷
                                                                çç     ÷÷               çç ÷
                                                                                          ** ÷
                        ³ - v * , b* + v** , b**   - v , b = çç b** ÷÷ ,             ççç v ÷÷÷ = I Д (v ) .       (3)
                                                              çç       ÷
                                                               çè b ÷÷÷ø
                                                                ç-
                                                                                       ç ÷÷
                                                                                       çè v ÷ø


          Таким образом,

                                         I (u ) ³ I Д ( v ), "u Î U , "v Î V .

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

          Теорема 8 (равновесия). Пусть u0 Î U и v0 Î V                                              решения взаимно
двойственных задач 1 и 3 соответственно. Тогда из неравенства
u0i > 0, i Î {1,L, l } следует равенство


                                        (-A*T v0* + A**T v0** - AT v0 ) = ci ,
                                                                            i




из неравенства v i > 0, i Î {1,L, m} - равенство

                                                    ( A*u0 ) = b*i ,
                                                               i




а из неравенства v i > 0, i Î {m + 1,L, k } - равенство

                                                    ( A**u0 ) = b**i .
                                                               i




          Доказательство. Неравенство (3) справедливо при всех u Î U и v Î V . В
частности, оно верно и для пары u0 Î U , v0 Î V . По теореме 6 выполняется
равенство I (u0 ) = I Д ( v0 ) . Для этой пары все знаки неравенств в (3) следует

поменять на знаки равенств. Имеем

  å ci u0i + å ciu0i = å (- A*T v0* + A**T v0** - AT v0 ) u0i + å (- A*T v0* + A**T v0** - AT v0 ) u0i Þ
   l            n              l                                                n
                                                                    i                                         i

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




                                        å éêë(- A                                      ù
                                                        v0* + A**T v0** - AT v0 ) - ci ú × u0i = 0 ,
                                          n                                      i
                                                   *T
                                                                                                                  (4)
                                         i =1                                          û

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

                                                             108