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

      Это опорное решение не является оптимальным, так как в строке Zj- Cj
       есть отрицательные числа. После пересчета получим следующую таб-
лицу. Введем в базис вектор А5, сравнивая симплексные отношения, видим,
что из базиса надо удалить вектор А4.
А3       0       12       -5/3    5/3     1       -1/3    0        0
А5       5       8        -1/3    -2/3    0       1/3     1        0
А6       0       114      -1      -9      0       1       0        1
Zj-Cj            40       -11/3 ↑ 8/3     0       5/3     0        0

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

      В столбце, соответствующем вектору A1 в строке Zj- Cj
находится отрицательное число, поэтому этот вектор надо ввести в базис, но
это невозможно сделать, так как в данном столбце нет положительных чисел,
следовательно, невозможно рассматривать симплексные отношения, и мы не
можем из старого базиса вывести какой-либо вектор. Получили противоре-
чие. В данном примере наблюдается особый случай - целевая функция неог-
раничена на области допустимых решений, следовательно, не существует оп-
тимального плана. Если с таким случаем сталкиваются на практике, то в
системе ограничений не хватает какого то важного ограничения (или огра-
ничений).

               Модифицированный симплекс метод (М-метод).

      Мы рассмотрели наиболее простой случай симплекс-метода, а именно
тот случай когда в канонической задаче сразу существуют единичные векто-
ра, образующие единичную подматрицу порядка m. Обычно это легко дости-
гается в тех задачах, у которых исходные ограничения были со знаком ≤, а
все свободные члены неотрицательны. Например, такая ситуация была в за-
даче использования сырья.
      Однако часто такой единичной подматрицы не существует и для созда-
ния её приходится вводить искусственные переменные и применять метод
искусственного базиса. Обычно такие ситуации возникают в тех случаях, ко-
гда в системе ограничений исходной задачи правые части неотрицательны, а
в системе ограничений есть знаки ≥ или =. Например, в задаче составления
рациона.
      Рассмотрим применение метода искусственного базиса на примере.
      Пример: Найти минимум функции Z=-2X1+3X2-6X3-X4 → min




                                    14