Численные методы. Корнюшин П.Н. - 97 стр.

                                                       97


       Теорема 2. Если на каком-то шаге жордановых исключений в столбце над отрицательным
элементом заключительной строки все элементы оказались неположительными, то целевая
функция может принимать сколь угодно большие значения (max Z = ∞) .
       Действительно, если в s-м столбце γs<0 и α is ≤ 0 (i=1, 2,…, m), то при сколь угодно
большом значении xs>0 все значения yi=αis(-xs)+βi ≥ 0, так что ограничения не нарушаются,
значение же целевой функции Z=γs(-xs)+D → ∞ при x s → ∞ . Таким образом, если на каком-то
шаге жордановых исключений оказалась такая ситуация, как в условии теоремы 2, то вычисления
обрываются, т.к. целевая функция не ограничена. Одновременно это свидетельствует о том, что
область ограничений является неограниченной (а не многогранником).
       В заключение отметим, что процесс улучшения плана с помощью жордановых
исключений всегда требует конечного числа шагов, т.к. число вершин у многогранника
ограничений конечное. При этом либо на каком-то шаге достигается оптимум целевой функции,
либо эта функция неограниченна.
       Пример. Требуется максимизировать функцию
                                   Z=3x1-x2+8x3+2x4-x5+9x6
при ограничениях
                                         − 6 x1 + 9 x 2 + 3x3 − 2 x5 − x6 ≤ 12;
                                            − 4 x 2 + 3x3 − 3 x4 + x5 − x6 ≤ 5;
                                − 2 x1 + 8 x2 − 5 x3 + 6 x 4 − 8 x5 + 4 x6 ≤ 20;
                                         − x1 − 3x 2 − 4 x3 − 8 x4 + 4 x6 ≤ 10;
                                   5 x1 + x2 + 2 x3 + 4 x4 + 9 x5 + 5 x6 ≤ 24;
                               x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x 4 ≥ 0; x5 ≥ 0; x6 ≥ 0.
       Введем дополнительные переменные и перепишем ограничения в виде.
                         y1 = −6(− x1 ) + 9(− x2 ) + 3(− x3 ) − 2(− x5 ) − (− x6 ) + 12 ≥ 0;
                               y 2 − 4(− x2 ) + 3(− x3 ) − 3(− x 4 ) + (− x5 ) − (− x6 ) + 5 ≥ 0;
              y3 = −2(− x1 ) + 8(− x2 ) − 5(− x3 ) + 6(− x 4 ) − 8(− x5 ) + 4(− x6 ) + 20 ≥ 0;
                          y 4 = −(− x1 ) − 3(− x2 ) − 4(− x3 ) − 8(− x4 ) + 4(− x6 + 10 ≥ 0;
                 y5 = 5(− x1 ) + (− x2 ) + 2(− x3 ) + 4(− x4 ) + 9(− x5 ) + 5(− x6 ) + 24 ≥ 0.
       Отсюда получаем исходную таблицу (табл. 12).

       Таблица 12
                          -x1      -x2    -x3    -x4        -x5   -x6    1

                 y1=      -6        9      3      0         -2    -1    12

                 y2=       0       -4      3      -3        1     -1     5

                 y3=       2        8     -5      6         -8    4     20         20/4=5

                 y4=      -1       -3     -4      -8        0     4     10      10/4=2,5

                 y5=       5        1      2      4         9     5     24      24/5=4,8

                    Z     -3       1      -8      -2        1     -9     0