Симплекс-метод, его сущность

 

      Как и в М-методе, сначала вычисляется  новая r-строка. 

      Старая  r-строка: (0 0 0 -1 -1 0 | 0)

      + 1 * R1-строка: (3  1 0  1 0 0 | 3)

      + 1 * R2-строка: (4  3 -1 0 1 0 | 6)

      = Новая r-строка: (7 4 -1 0 0 0 | 9) 

      Новая строка 

      r + 7x1 + 4x2 – x3 + 0R1 + 0R2 + 0x4 = 9 

      используется  для решения первого этапа, что  приведёт к следующему оптимальному решению (проверьте!). 

      Поскольку достигнут минимум r = 0, значит, на первом этапе получено допустимое базисное решение x1 = 3/5, x2 = 6/5 и x4 = 1. Искусственные переменные полностью выполнили свою «миссию», поэтому из последней таблицы можно удалить их столбцы. Переходим ко второму этапу. 

      Этап 2 

      После удаления искусственных переменных исходная задача будет записана следующим образом. 

      Минимизировать  z = 4x1 + x2 

      с ограничениями  

      x1 + 1/5 x3 = 3/5,

      x2 + 3/5 x3 = 6/5,

      x3 + x4 = 1,

      x1, x2, x3, x4 >= 0. 

      Обратите  внимание, что после первого этапа  исходная задача претерпела некоторые  изменения, которые учитывают полученное базисное решение. Этой трансформированной задаче соответствует следующая таблица: 

 

      Поскольку базисные переменные x1 и x2 имеют ненулевые коэффициенты в z-строке, эту строку следует преобразовать. 

      Старая  z-строка: (-4  -1 0 0  |   0)

           + 4 * x1-строка: (4  0  4/5  0  | 12/5)

           + 1 * x2-строка: (0  1  -3/5 0  | 6/5)

        = Новая z-строка: (0  0  1/5  0  | 18/5) 

      Начальная таблица второго этапа примет следующий вид: 

 

      Так как решается задача минимизации, следует  ввести переменную x3 в базис. Применение алгоритма симплекс-метода уже на следующей итерации приведёт к оптимальному решению (проверьте!). 

      Удаление искусственных переменных в конце первого этапа имеет смысл только тогда, когда все они являются небазисными (как в примере 2.2-4). Однако возможна ситуация, когда в конце первого этапа искусственные переменные останутся в базисе, но будут иметь нулевые значения. В этом случае такие переменные при необходимости будут формировать часть начального базисного решения для второго этапа. При этом необходимо так изменить вычисления, выполняемые на втором этапе, чтобы искусственные переменные никогда не смогли принять положительные значения ни в каких итерациях симплекс-метода.

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

      Итак, правило для второго этапа заключается в том, чтобы искусственные переменные оставлять в базисе всегда, когда коэффициент в ведущем столбце положительный или отрицательный. Фактически это правило применяется в конце первого этапа, когда удаляем нулевые искусственные переменные из базисного решения, перед тем как приступить ко второму этапу. 
 

      Глава 3. Особые случаи симплекс-метода. 

      В этом разделе рассмотрим четыре особых случая, встречающихся при использовании  симплекс-метода. 

1. Вырожденность.
2. Альтернативные оптимальные решения.
3. Неограниченные решения.
4. Отсутствие допустимых решений.

 

      При изучении этих случаев основное внимание мы уделим (1) теоретическому обоснованию причин, приводящих к таким ситуациям, и (2) их практическим интерпретациям применительно к реальным задачам. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      3.1 Вырожденность. 

      В ходе выполнения симплекс-метода проверка условия допустимости может привести к неоднозначному выбору исключаемой переменной. В этом случае на следующей итерации одна или более базисных переменных примут нулевое значение. Тогда новое решение будет вырожденным.

      В вырожденном решении нет никакой  опасности, за исключением небольших  теоретических неудобств, которые  мы далее кратко обсудим. С практической точки зрения вырожденность объясняется тем, что в исходной задаче присутствует, по крайней мере, одно избыточное ограничение. Для того чтобы лучше понять практические и теоретические аспекты явления вырожденности, рассмотрим численный пример. Графическая интерпретация задачи поможет наглядно разобраться в этом явлении. 

      Пример 3.1-1. (Вырожденное оптимальное решение) 

      Рассмотрим  следующую задачу ЛП. 

      Максимизировать z = 3x1 + 9x2 

      При выполнении условий

         X1 + 4x2 <= 8,

         X1 + 2x2 <= 4,

      X1, x2 >= 0.