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

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


      Доказательство. В процессе доказательства теоремы 3 было
установлено, что u0 Î U . Равенство (11) следует непосредственно из
соотношений (3)-(5). Правому неравенству в (1) можно придать вид

        I (u0 ) £ I (u ) + v0* , A*u - b* - v0** , A**u - b** + v0 , Au - b         "u Î U% .            (12)

      Для всех u Î U справедливы соотношения

                            A*u - b* £ 0,      A**u - b** ³ 0,     Au - b = 0 .

     Тогда в силу v0* ³ 0, v0** ³ 0 из неравенства (12) для всех u Î U следует
I (u0 ) £ I (u ) . Теорема доказана.

      Теорема 5 (Куна-Таккера). Пусть точка u0 Î U является решением
задачи 1 линейного программирования. Тогда необходимо существует
вектор v0 Î V% такой, что пара (u0 , v0 ) Î U% ´V% образует седловую точку

функции Лагранжа для задачи 1 линейного программирования.

      Доказательство. Введем множества индексов

            {                                  }          {
       I * = i Î {1,L, m} ( A*u0 - b* ) = 0 , I ** = i Î {m + 1,L, k } (- A**u0 + b** ) = 0 ,
                                          i                                                     i
                                                                                                    }
                                       J% = { j Î {1, L, l } u0j = 0}

и построим множество

            ïìï    æ e1 ö÷                                                                       ïüï
              ïï   ççç ÷÷                                                                          ï
        K = íe = çL÷÷ Î R n ( A*e) £ 0, i Î I * ;( A**e) ³ 0; i Î I ** ; Ae = 0; e j ³ 0, j Î J%ïý .
                                  i                     i

               ïï    ç    ÷
                     ç n ÷÷                                                                        ïï
                ïï   çèe ÷ø                                                                         ïï
                 î                                                                                   þ

      Покажем, что для всех e Î K и достаточно малого числа t ³ 0
справедливо        включение           u0 + te Î U .          Действительно,           последовательно
вычисляем

                                      A (u0 + te) = Au0 + tAe = 0 ,


            i Î I * Þ ( A*u0 ) = b*i Þ ( A* (u0 + te)) = ( A*u0 ) + t ( A*e) £ b*i , "t ³ 0 ,
                              i                           i         i           i




                                                    102