Линейное программирование. Филькин Г.В. - 16 стр.

        ⎧2 x1 + x2 − 2 x3 + x4 = 24
        ⎪ x + 2 x + 4 x ≤ 22
        ⎪ 1           2   3
        ⎨
        ⎪ x1 − x2 − 2 x3 ≥ 10
        ⎪⎩ x1, 2,3, 4 ≥ 0


        Приведем задачу к каноническому виду, имеем
        W = − Z = 2 x1 − 3 x2 + 6 x3 + x4 − Mx7 → max

      ⎧2 x1 + x2 − 2 x3 + x4 = 24
      ⎪ x + 2 x + 4 x + x = 22
      ⎪ 1       2       3   5
      ⎨
      ⎪ x1 − x2 + 2 x3 − x6 + x7 = 10
      ⎪ x j ≥ 0, j = 1,7
      ⎩
      Переменная x7 была введена только для того, чтобы получилась еди-
ничная подматрица, она называется искусственной и в процессе работы обя-
зательно должна быть выведена из базиса. Поэтому необходимо ввести её в
целевую функцию так, чтобы она вышла из базиса в автоматическом режиме.
Для этого умножаем эту переменную на очень большое ( превосходящее на
несколько порядков все остальные коэффициенты целевой функции) число
М и помещаем это произведение в целевую функцию со знаком -. Тогда це-
левая функция может достигнуть максимума только в том случае, если эта
переменная будет выведена из базиса и при этом ,естественно, станет равной
нулю.
      Составим симплексную таблицу, в которой будет на одну строку боль-
ше чем в простейшем варианте симплекс-метода.

                             2        -3         6     1    0    0    -М
Базис      Сб       А0
                             А1       А2         А3    А4   А5   А6   А7
А4        1          24      2         1         -2    1    0    0     0
А5        0          22      1         2          4    0    1    0     0
←А7      -M          10       1       -1          2    0    0    -1    1
   Zj-Cj             24      0         4         -8    0    0    0     0
                    -10      -1        1        -2 ↑   0    0    1     0

        Таблица 6. Первое опорное решение.

      Последняя строка будет Zj-Cj двойной, при этом числа будут поме-
щаться в верхнюю подстроку, а коэффициенты при М в нижнюю подстроку.
Наприме, для столбца A0 имеем 1*24+0*22+(-М)*10=24-10М, для столбца А1
      1*2+0*1+(-М)*1-2=0-М и так далее. План не является оптимальным,
так как среди коэффициентов при М в строке Zj-Cj есть отрицательные. Наи-

                                           15