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

        На начальной итерации в качестве исключаемой можно выбрать как переменную x3, так и x4. Если оставить в базисе переменную x4, на следующей итерации она примет значение 0 (как показано в таблице), т.е. получим вырожденное базисное решение. Оптимальное решение получается на следующей итерации.

      Что же практически приводит к вырожденности  решения? Рассмотрим рис. 3.4, графически представляющий решение этой задачи. Точка оптимума x1 = 0, x2 = 2 является пересечением трёх прямых. Поскольку данная задача двухмерна, эта точка переопределена (на плоскости для определения точки достаточно двух прямых), и, следовательно, одно из ограничений избыточно. На практике информация о том, что некоторые ресурсы недефицитны, может быть полезной при интерпретации результатов решения задачи. Эти сведения также могут помочь выявить неточности и ошибки в постановке исходной задачи. К сожалению, не существует способов определить избыточное ограничение непосредственно из данных симплекс-таблиц. 

        

      Рис. 3.1 

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

      Во-вторых, последствие вырожденности решения можно обнаружить, сравнивая первую и вторую итерации в приведённой выше таблице. Хотя в этих итерациях состав базисных и небазисных переменных различен, значения всех переменных и значение целевой функции не изменяются: 

      x1 = 0, x2 = 2, x3 = 0, x4 = 0, z = 18. 

      Можно ли, несмотря на то что оптимальное  решение не достигнуто, остановить вычисления на первой итерации (когда  впервые обнаруживается вырожденность)? Ответ отрицательный, так как  решение может быть только временно. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      3.2. Альтернативные оптимальные решения. 

      Когда прямая (если рассматривается двухмерная задача ЛП, в общем случае – гиперплоскость), представляющая целевую функцию, параллельна  прямой (гиперплоскости), соответствующей  связывающему неравенству (которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то же оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения называются альтернативными оптимальными решениями. Следующий пример показывает, что таких решений (если они существуют) бесконечное множество. Этот пример также проиллюстрирует практическую значимость альтернативных практических решений. 

      Пример 3.2-1 (Бесконечное множество решений)

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

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

      при ограничениях

          x1 + 2x2 <= 5,

        x1 + x2 <= 4,

      x1, x2 >= 0. 

      На  рис. 3.2 показано множество альтернативных оптимальных решений, которые являются следствием того, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей связывающему ограничению. Каждая точка отрезка BC соответствует оптимальному решению со значением целевой функции z = 10.

      

      Рис. 3.2 

      Последовательные  итерации выполнения симплекс-метода представлены в следующей таблице. 

 

      На  первой итерации получаем оптимальное решение x1 = 5/2 и z = 10, которое соответствует точке B на рис. 3.2. Как узнать из симплекс-таблицы, что существует альтернативное оптимальное решение? Посмотрите на коэффициенты небазисных переменных в z-строке первой итерации. Коэффициент небазисной переменной x1 равен нулю, это означает, что данную переменную можно ввести в базис без изменения значения целевой функции, но значение самой переменной x1 изменится. Введение переменной x1 в базисное решение выполнено на второй итерации, при этом из базиса исключена переменная x4. Получено новое решение x1 = 3, x2 = 1, z = 10, которое соответствует точке C на рис. 3.2.

      Симплекс-метод  может определить только две угловые  точки B и C. Математически мы можем найти все точки (x1’,x2’) отрезка BC как взвешенное среднее (с неотрицательными весами) точек B и C. Полагая 0 <= α <= 1 и

         B: x1 = 0, x2 = 5/2,

      C: x1 = 3, x2 = 1,

      координаты  любой точки отрезка BC можно записать следующим образом:

x1’ = α * 0 + (1 - α) * 3 = 3 – 3 α,

      x2’ = α * 5/2 + (1 - α) * 1 = 1 – 3/2 α, 

      При α = 0 (x1’,x2’) = (3, 1), что соответствует точке C. При α = 1 получаем (x1’,x2’) = (0, 5/2) – это точка B. Если значение α лежит строго между 0 и 1, получаем внутренние точки отрезка BC. 

      На  практике альтернативные оптимальные решения весьма полезны, поскольку позволяют сделать выбор среди множества решений без ухудшения значения целевой функции. Например, в рассмотренной выше задаче переменная x2, принимает нулевое значение в точке B, тогда как в других альтернативных оптимальных решениях её значение положительно. Если интерпретировать задачу как задачу организации производства двух видов товара (которые соответствуют переменным x1 и x2), то, с учётом конкуренции на рынке, более рационально производить оба вида товара, а не один. В этом случае решение, соответствующее точке C, предпочтительнее. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      3.3 Неограниченные решения. 

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

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

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

      Пример 3.3–1. (Неограниченная целевая функция) 

      Рассмотрим  задачу 

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

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

            x1 – x2 <= 10,

      2x1 <= 40,

        x1, x2 >= 0. 

      Симплекс-таблица  начальной итерации этой задачи имеет  следующий вид. 

 

      Из  этой таблицы видно, что в качестве вводимой переменной можно взять как x1, так и x2. Поскольку переменная x1 имеет максимальный (по абсолютной величине) отрицательный коэффициент в z-строке, именно её следует ввести в базисное решение. Однако заметим, что во всех ограничениях коэффициенты, стоящие перед переменной x2, отрицательны или равны нулю. Это означает, что значение переменной x2 может возрастать до бесконечности, и при этом не нарушается ни одно ограничение. Поскольку увеличение на 1 значения переменной x2 приводит к увеличению на 1 значения целевой функции, значит, неограниченное увеличение значения переменной x2 ведёт к неограниченному увеличению значения целевой функции. Эта ситуация проиллюстрирована на рис. 3.3. На этом рисунке видно, что пространство допустимых решений не ограничено в направлении оси x2 и значение целевой функции может быть каким угодно большим. 

      

      Рис. 3.3 

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

      3.4 Отсутствие допустимых решений. 

      Если  ограничения задачи ЛП несовместны (т.е. они не могут выполняться  одновременно), то задача не имеет допустимых решений. Такая ситуация не может  возникнуть, если все неравенства, составляющие систему ограничений, имеют тип «<=» с неотрицательными правыми частями, так как в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений мы используем искусственные переменные. И хотя в оптимальном решении все искусственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В противном случае, в оптимальном решении будет присутствовать хотя бы одна положительная искусственная переменная.