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

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


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


                         é             *i ù            é ** i   **i ù
                    å    ê-( A u0 ) + b ú × v0 + å ê( A u0 ) - b ú × v0 = 0 .
                     m             i                 k
                              *              i*                       i**
                                                                                                 (5)
                    i =1 ë                û     i= m+1 ë            û

      Все слагаемые в равенствах (4) и (5) неотрицательны в силу
ограничений задач 1 и 3, следовательно, все они равны нулю. Для слагаемых,
содержащих строго положительные вторые сомножители u0i > 0, i Î {1,L, l } ,
v i > 0, i Î {m + 1,L, k } ,           v i > 0, i Î {m + 1,L, k }    последнее           утверждение
выполняется, только в том случае, если первый сомножитель слагаемого
равен нулю. Теорема доказана.
        Пример 4. Рассмотрим взаимно двойственные задачи из примера 2 и
выпишем их решения.
                                 8765 2                 7164 4 52834 5 59627
                         u10 =        , u 0 = 0, u 30 =      , u0 =      , u0 =      ,
                                 2093                   6279        6279        6279
                             583 2 2033 3                            433 6 42919
                    v01 =        , v0 =     , v0 = 0, v04 = 0, v05 =     , v0 =      .
                            6279        483                          273        6279
        По теореме 8 первые два ограничения прямой задачи на оптимальном
векторе должны выполняться со знаком «=», а следующие два со знаком
«>». Действительно,
                  8765             7164          52834         59627
               3×       - 22 × 0 -        + 14 ×        - 12 ×        = 5,
                  2093             6279          6279           6279
                      8765              7164 52834             59627
               -14 ×       + 5 × 0 + 3×       +          +4×          = 22,
                      2093              6279 6279               6279
                    8765              7164         52834         59627 202484
               12 ×      - 4 × 0 + 3×       + 15 ×        - 12 ×        =         > 19,
                    2093              6279          6279          6279      2093
                    8765                 7164        52834         59627 6591932
               22 ×      - 14 × 0 + 71 ×       + 4×         + 12 ×        =          > 10.
                    2093                 6279         6279          6279      6279
      По той же теореме 8 первое и третье ограничение двойственной
задачи на оптимальном векторе должны выполниться со знаком «=»,
второе со знаком «>». Действительно,




                                                         109