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

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


      Таким образом, построенная задача линейного программирования
является задачей 2. Теорема доказана.                             Доказанные                  теоремы                    1,2
позволяют принять следующее соглашение. В паре взаимодвойственных
задач прямая задача всегда является задачей на минимум целевой функции, а
«двойственная» задача – на максимум целевой функции.

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

                                     ïìï      æ u% ö÷                    ïüï
                                       ïï     çç ÷           æu1 ö÷        ïï
                                               ççu l +1 ÷÷   çç ÷
                                 %      ï                ÷     ç    ÷
                                                                    ÷       ï
                                 U = íu = çç ÷÷ Î R u% = çL÷ Î R , u% ³ 0ý ,
                                                           n          l
                                        ïï      çç L ÷÷       ç
                                                              ç l ÷÷÷       ïï
                                         ïï      ç n ÷÷÷      çèu ÷ø         ïï
                                          ïîï    çèç u ø÷                     ïþï
         ïìï    æ v* ö÷           æ v1 ö÷                æv m +1 ö÷             æv k +1 ö÷                       ïüï
           ïï   ççç ** ÷÷       ç  ç ÷
                                        ÷             ç  ç        ÷
                                                                  ÷           ç  ç       ÷
                                                                                         ÷                         ï
    V% = ív = ççv ÷÷ Î R s v* = ççç L÷÷ Î R m , v** = ççç L ÷÷ Î R k -m , v = ççç L ÷÷ Î R s-k ; v* ³ 0, v** ³ 0ïý
            ïï   çç ÷÷          çç m ÷÷               çç k ÷÷                 çç s ÷÷                              ïï
             ï    çèç v% ÷ø      çèçv ÷ø               çèç v ÷ø                çèç v ÷ø                             ï
             îï                                                                                                     þï

        Определение 2.Функция L : U% ´V% ® R1 , определенная формулой

          L (u , v) = c, u + v* , A*u - b* + v** , - A**u + b** + v , Au - b , u Î U% , v Î V% ,

называется функцией Лагранжа для задачи 1 линейного программирования.
        Определение 3. Точка (u0 , v0 ) Î U% ´V% называется седловой точкой
функции Лагранжа для задачи 1, если

                                           L (u0 , v) £ L (u0 , v0 ) £ L (u , v0 )                                       (1)

для всех u Î U% , v Î V% .

        Теорема 3. Для того чтобы точка (u0 , v0 ) Î U% ´V% была седловой точкой

функции Лагранжа для задачи 1, необходимо и достаточно, чтобы
выполнялись следующие условия:

                                           L (u0 , v0 ) £ L (u , v0 ) , "u Î U% ,                                        (2)

                                          v0i ( A*u0 - b* ) = 0, i = 1,L, m, .
                                                            i
                                                                                                                         (3)


                                                            98