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

             6.2.2. Выбор разрешающей строки                                       Действительно, согласно правилам преобразований Жорда-
              в симплексных преобразованиях                                    на–Гаусса имеем:
   Переход от одного опорного плана к другому называется                           a) для разрешающей строки ( i = k ) очевидно:
симплексным преобразованием.                                                                             b
   Пусть при решении ЗЛП получена таблица:                                                        bk′ = k ≥ 0 , так как bk ≥ 0, a ks > 0;
                                                                                                         aks
 БП   x1   x2   …    xm        xm+1     …     xs     …    xn     Свобод-
                                                                  ный              б) для остальных строк ( i ≠ k ) имеем
                                                                  член
                                                                                                     b ⋅ a − bk ⋅ ais          ⎛b     b ⎞
 x1   1    0    …    0        a′1,m+1   …    a′1,s   …   a′1,n     b′1                        bi′ = i ks              = ais ⋅ ⎜⎜ i − k ⎟⎟ ≥ 0 .
 x2   0    1    …    0        a′2,m+1   …    a′2,s   …   a′2,n     b′2                                      a ks               ⎝ ais a ks ⎠
 …    …    …    …    …          …       …     …      …    …        …
 xm   0    0    …    1        a′m,m+1   …    a′m,s   …   a′m,n     b′m             В самом деле,
 Z    0    0    …    0          r1      …     rs     …   rn–m       q                              ⎛b       b ⎞                   b         ⎧b   ⎫
                                                                           ,           ais ≥ 0 и ⎜⎜ i − k ⎟⎟ ≥ 0 , так как k = min ⎨ i ≥ 0⎬ .
                                                                                                   ⎝ ais a ks ⎠                   aks    i ⎩ ais ⎭
в которой все bi ≥ 0 , i = 1, m , т.е. найден опорный план:
                                                          T
                           ⎛                      ⎞                                              6.2.3. Альтернативный оптимум
                       X = ⎜ b1 ,K ,bm ,01
                          1
                                          02
                                         ,4 ,K ,0 ⎟
                                               3⎟ .                                Пусть в последней симплекс-таблице получен оптималь-
                           ⎜                 4
                           ⎝               n−m    ⎠                            ный план Х*. Если среди неотрицательных компонент вектора
     И пусть определен разрешающий s-столбец, для которого                     r при этом имеется хотя бы одна нулевая компонента r p = 0 , то
rs < 0 , т.е. свободную переменную x s можно ввести в число ба-
                                                                               введение переменной x p в базис не изменит величины функции
зисных переменных, за счет чего уменьшить значение целевой
функции.                                                                       цели Z Действительно, выполнив шаг преобразований Жордана–
     Возникает вопрос, какую из переменных x1 , x2 ,..., x j ,K , xm           Гаусса с разрешающим элементом a kр , получим новое опорное

следует при этом вывести из базиса, чтобы в новой симплекс-                    решение, для которого
таблице значения свободных членов bi оставались неотрицатель-                                    q ⋅ akp − bk ⋅ rp         bk
                                                                                        qнов =                       =q−       ⋅ rp = q    ( rp = 0 ) .
ными (согласно определению опорного плана). Из этих сообра-                                            akp                 аkp
жений и следует выбирать разрешающую строку.                                                                                   Свободный
    Как было указано, за разрешающую строку принимают k-ю                                        БП       K          xp   K
                                                                                                                                  член
строку, для которой выполняется условие                                                           K       K      K        K        K
                         bk       ⎧b     ⎫                                                        xk      K      a kp     K        bk
                            = min ⎨ i ≥ 0⎬ .
                        aks    i ⎩ ais   ⎭                                                        K       K      K        K        K
   Покажем, что при таком выборе разрешающей стро-                                             Z          rp
                                                                                                          K             q K
ки неотрицательные свободные члены bi симплекс-                                    Следовательно, новое опорное решение является новым оп-
таблицы после преобразования Жордана–Гаусса перей-                             тимальным решением. Обозначим эти оптимальные планы со-
дут в неотрицательные.                                                         ответственно Х*1 и Х*2. Тогда согласно свойствам допустимых

                                        63                                                                                64