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

большее нарушение находится в столбце вектора A3-следовательно, в новый
базис введем этот вектор. Рассмотрев симплексные отношения, видим, что из
базиса исключается вектор A7. После пересчета получим таблицу 7. Заметим,
что столбец, соответствующий вектору A7 из таблицы можно исключить, так
как он соответствует искусственной переменной и в базис уже не вернется.

 А4           1        35         5/2          2          0        1    0    0
 А5           0         1         -1/2        -2          0        0    1    1
 А3           6       11/2        1/4         1/2         1        0    0    0
      Zj-Cj            68          2           8          0        0    2    0

       Таблица 7. Второе опорное решение.

     План оптимальный, так как в строке отрицательных чисел нет.
     Xопт(0,0,11/2,35,0,1), Wопт=68. Так как при приведении задачи к канони-
ческому виду у целевой функции менялся знак, то имеем ), ), Zопт=-Wопт=-68.
     Проверка: подставим в целевую функцию полученные оптимальные
значения переменных, получим.
     Z=-2*0+3*0+6*11/2-3*5+0*0+0*1=-68

ОСОБЫЙ СЛУЧАЙ ПРИ РЕШЕНИИ ЗАДАЧ ЛП СИМПЛЕКС-МЕТОДОМ
( ОБЛАСТЬ ДОПУСТИМЫХ РЕШЕНИЙ ПУСТАЯ ).

 Рассмотрим этот особый случай на примере.
     Пример 4.
     Z=2X1-X2-X4 → min
       ⎧ x1 − 2 x2 + x3 = 10
       ⎪− 2 x − x − 2 x ≥ 18
       ⎪          1    2  4
       ⎨
       ⎪3 x1 + 2 x2 + x4 ≥ 36
       ⎪⎩ x1, 2, 3 ≥ 0
       Приведем задачу к каноническому виду
        F = − Z = −2 x1 + x2 + x4 + Mx7 − Mx8 → max
       ⎧       x1 − 2 x2 + x3 = 10
       ⎪
       ⎨− 2 x1 − x2 − 2 x4 − x5 + x7 = 18
       ⎪ 3x + 2 x + x − x + x = 36
       ⎩ 1         2     4   6   8

       x j ≥ 0 , j = 1,8
       Здесь х7, х8 – искусственные переменные.

Базис Сб          А0         -2          1          0         1    0    0    -М   -М
                             А1          А2         А3        А4   А5   А6   А7   А8
А3      0         10         1           -2         1         0    0    0    0    0
А7      -M        18         -2          -1         0         -2   -1   0    1    0
                                                     16