Математическое программирование (линейное программирование). Киселева Э.В - 28 стр.

    1      8       1                                                                       ⎧a11 x1 + K + a1n x n = b1 ,
Z=    x1 + x 2 + 8 x3 − 9 13 → min , то введение в базис любой                             ⎪⎪
    6      9      18
из них не приведет к уменьшению значения целевой функции.                                   ⎨K        K K         K
                                                                                            ⎪
    Замечание. Если найденный опорный план не является                                      ⎩⎪a m1 x1 + K + a mn x n = bm ,
оптимальным (в целевую функцию входит какая-либо свобод-
ная переменная x j с отрицательным коэффициентом) и                                                 x j ≥ 0,   j = 1, n.
все коэффициенты j -го столбца в системе ограничений, со-             Пусть ранг матрицы A системы ограничений равен m, и все
ответствующего этой переменной, неположительны, то целевая       bi ≥ 0 , i = 1, m . В матричной форме ЗЛП имеет вид:
функция Z не ограничена снизу. В этом случае ЗЛП не имеет                                        Z = cX → min ,
                                                                                               AX = b ,
решения.
                                                                                                X ≥ 0.
    Поясним это на рассмотренном примере 6.1. Пусть, напри-          Запишем условие задачи в виде таблицы:
мер, в системе (*) коэффициенты при переменной x5 , которую                              A             b
хотим ввести в базис, в обоих уравнениях отрицательны:                                   c             0
                                                                     Предположим, что x1 , x2 ,K, xm являются базисными пере-
                 ⎧ x1 − 2 x5 = 8,          ⎧ x1 = 8 + 2 x5 ,     менными (при необходимости можно произвести перенумера-
                 ⎨                  Откуда ⎨
                 ⎩ x2 − 3 x5 = 9.          ⎩ x2 = 9 + 3 x5 .     цию). Тогда первые m столбцов матрицы:
      Очевидно, увеличение значения переменной x5 приведет к                        ⎛ a11 a12 K a1m a1,m +1 K a1n ⎞
                                                                                    ⎜                                  ⎟
увеличению значений переменных x1 и x2 , и мы никогда не                            ⎜ a21  a22 K a2 m a2 ,m +1 K a2 n ⎟
получим нулевых значений x1 и x2 , т.е. x1 и x2 нельзя вывес-                   A = ⎜K K K K K K K ⎟
                                                                                    ⎜                                  ⎟
ти из базиса. Но при неограниченном увеличении x5 значение                          ⎜ am1 am 2 K amm am ,m +1 K amn ⎟
целевой функции будет неограниченно уменьшаться ( Z → −∞ ),                         ⎜ 144424443 1442443 ⎟
                                                                                    ⎝       Матрица В        Матрица F ⎠
т.е. оптимальное решение не существует в этом случае по причи-
не неограниченности снизу функции Z .
                                                                 образуют квадратную невырожденную матрицу B (базисную мат-
                                                                 рицу) m-го порядка, а оставшиеся (n – m) столбцов дают матрицу
                  6.2. Алгебра симплекс-метода                   F размеров m ⋅ (n − m ) . Аналогичным образом вектор с разбивает-
    Дадим изложение симплекс-метода для ЗЛП вида:                ся на два вектора (c B , c F ) , где c B − вектор коэффициентов при
                 Z = c1 x1 + c 2 x 2 + K + c n x n → min ,       базисных неизвестных x1 , x2 ,K, xm ; вектор c F − при остальных
при ограничениях                                                 n − m свободных неизвестных. x m+1 , K , x n – функции цели Z.
                                                                 Вектор X = ( X В , X F ) T .
                                    57                                                                    58