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

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


обратном направлении, приходим к выводу, что точка u0 является решением
задачи 1. При этом снова справедливы равенства (2). Теорема доказана.

     Пример 3. Приведем решения взаимнодвойственных задач 1, 3 из
примера 1 и задач 2, 3 из примера 2.

     Для первой пары задач имеем

                  131006         41443 2 3225 3 7323 4                 19058 5 15410
    I (u0 ) = -          , u10 =      , u0 =      , u0 =      , u0 = -       , u0 =      .
                   5269          5269        5269        5269           5269        5269

                    131006         6635 2                 505 4       73 5 470 6 7164
    IД (v0 )= -            , v10 =      , v 0 = 0, v 30 =     , v0 =     , v0 =     , v0 =      .
                     5269          5269                   479        479        479        5269

     Аналогично для второй пары задач

                      1192805         8765 2                 7164 4 52834 5 59627
         I (u0 ) =            , u10 =      , u 0 = 0, u 30 =      , u0 =      , u0 =      .
                        6279          2093                   6279        6279        6279

                    1192805          583 2 2033 3                            433 6 42919
     I Д ( v0 ) =           , v01 =      , v0 =     , v0 = 0, v04 = 0, v05 =     , v0 =
                      6279          6279        483                          273        6279 .


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

     В       следующей               теореме           приводятся       условия        разрешимости
взаимнодвойственных задач.

     Теорема 7. Для существования решения взаимнодвойственных задач
достаточно, чтобы обе взаимно двойственные задачи были допустимыми.

     Доказательство. В силу теоремы 3.6. достаточно установить
ограниченность целевых функций взаимно двойственных задач: для задачи
на минимум целевой функции – ограниченность снизу, а для задачи на
максимум целевой функции – ограниченность сверху. Имеем

       I (u ) = c, u = å ci u i = å ci u i + å ci u i ³ å (- A*T v* + A**T v** - AT v ) u i +
                               n       l          n           l
                                                                                              i

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




               + å (- A*T v * + A**T v ** - AT v ) u i = - A*T v * + A**T v ** - AT v , u =
                      n                            i

                    i =l +1




                                                       107