Линейное программирование в примерах и задачах. Методические указания. Корытов И.В - 3 стр.

                          ⎛2    4 −1 0 0             0 12 ⎞
                          ⎜                               ⎟                      F = 3x1 + 5 x 2 + M (22 − 5 x1 − 6 x6 + x3 + x 4 ) =
                          ⎜3    2  0 −1 0            0 10 ⎟
                          ⎜0    1 0   0 1            0 6⎟                        = (3 − 5M ) x1 + (5 − 6M ) x 2 + Mx3 + Mx 4 + 22 M .
                          ⎜                               ⎟
                          ⎜1    0  0  0 0            1 5 ⎟⎠
                          ⎝                                                   Условие задачи с искусственным базисом в канониче-
                                                                         ском виде:
не содержит в себе единичную матрицу, следовательно ба-
лансовые переменные не образуют базиса. Умножение на
                                                                         F − (3 − 5M ) x1 − (5 − 6 M ) x 2 − Mx3 − Mx 4 = 22M
− 1 обеих частей первого и второго уравнений приведет к
недопустимому базисному решению. Поэтому необходимо                      ⎧2 x1    + 4 x2   − x3                          + r1           = 12
ввести в эти уравнения искусственные переменные r1 и r2 :                ⎪3x      + 2 x2          − x4                           + r2   = 10
                                                                         ⎪ 1
                                                                         ⎨
                                                                         ⎪            x2                  + x5                          = 6
⎧2 x1     + 4 x2   − x3                             + r1          = 12   ⎪⎩ x1                                   + x6                   = 5
⎪3x       + 2 x2           − x4                            + r2   = 10
⎪ 1                                                                                        x j ≥ 0, j = 1,K ,6; r1 ≥ 0, r2 ≥ 0
⎨
⎪             x2                   + x5                           = 6
⎪⎩ x1                                       + x6                  = 5         Расширенная матрица задачи линейного программиро-
                   x j ≥ 0, j = 1,K,6; r1 ≥ 0, r2 ≥ 0                    вания:

        Выражение искусственных переменных через свобод-                 ⎛ 1 5M − 3 6 M − 5 − M − M 0 0 0                        0 22M ⎞
                                                                         ⎜                                                               ⎟
ные:                                                                     ⎜0       2       4   −1   0 0 0 1                       0   12 ⎟
                          r1 = 12 − 2 x1 − 4 x 2 + x3 ,                  ⎜0       3       2    0  −1 0 0 0                       1   10 ⎟
                                                                         ⎜                                                               ⎟
                          r2 = 10 − 3 x1 − 2 x 2 + x 4 .                 ⎜0       0       1    0   0 1 0 0                       0    6⎟
                                                                         ⎜0       1       0    0   0 0 1 0                       0    5 ⎟⎠
                                                                         ⎝
        Составление штрафной функции:
                                                                         В матрице отделены сплошными линиями: столбец, соот-
M (r1 + r2 ) = M (12 − 2 x1 − 4 x2 + x3 + 10 − 3x1 − 2 x2 + x4 ) =       ветствующий переменной F , строка коэффициентов целе-
              = M (22 − 5 x1 − 6 x6 + x3 + x4 ).                         вой функции и столбец свободных членов. Пунктирной ли-
                                                                         нией отделены столбцы единичной матрицы.
     В задаче минимизации штрафная функция вводится в                         Ранг расширенной матрицы rang = 5 , следовательно,
целевую функцию со знаком «+»1:                                          количество базисных переменных равно пяти.
                                                                              Базисные переменные: F , x5 , x6 , r1 , r2 .
1
    В задаче максимизации, соответственно, со знаком «–».
4                                                                                                                                              5