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

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


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

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

      Теорема 6. Либо обе взаимно двойственные задачи не имеют решения,
либо они обе имеют решение и при этом справедливо равенство

                                               I (u0 ) = I Д ( v0 ) ,

где u0 - решение прямой, а v0 - решение двойственной задачи.

      Доказательство. Выпишем функцию Лагранжа для задачи 1.

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

      Рассмотрим вспомогательную задачу.

      Задача 3*

                                        æ-b* ö÷         æ v * ö÷     æ b* ö÷       æ v * ö÷
                                        çç         ÷÷   çç ÷           ç      ÷     çç ÷
             I *Д ( v) = -I Д (v ) = - çç b** ÷÷ ,       çç v** ÷÷ = ççç-b** ÷÷,     çç v** ÷÷ ® min ,
                                         çç         ÷     çç ÷÷   ÷    çç     ÷÷      çç ÷÷÷
                                          çèç-b ÷÷ø÷       çè v ÷ø÷  çè b ø÷÷÷     èç v ø÷÷


                            ( A*T v* - A**T v** + AT v ) ³ -ci , i Î {1,L, l} ,
                                                              i




                         (- A*T v* + A**T v** - AT v ) = ci , i Î {l +1, L, n} ,
                                                             i




                                                      æ v * ö÷
                                                      çç ÷
                                                               ÷
                                                 v = çç v** ÷÷ Î V% .
                                                       çç ÷÷
                                                        çè v ÷ø÷




                                                        105