ОСОБЫЕ СЛУЧАИ ПРИМЕНЕНИЯ СИМПЛЕКС-МЕТОДА
Вырожденность.
Альтернативные оптимальные решения.
Неограниченные решения.
Отсутствие допустимых решений.
1. Вырожденность
В ходе выполнения симплекс-метода проверка условия допустимости может привести к неоднозначному выбору исключаемой переменной. В этом случае на следующей итерации одна или несколько базисных переменных примут нулевое значение. Тогда новое решение будет вырожденным.
В вырожденном решении нет никакой опасности, за исключением небольших теоретических неудобств. С практической точки зрения вырожденность объясняется тем, что в исходной задаче присутствует по крайней мере одно избыточное ограничение.
Пример:
На начальной итерации в качестве исключаемой можно выбрать как переменную Х3, так и Х4.
Если оставить в базисе переменную Х4, на следующей итерации она примет значение 0 (как показано в таблице), т.е. получим вырожденное базисное решение.
Оптимальное решение получается на следующей итерации.
Графически представление решения задачи показывает, что точка оптимума Х1= 0, Х2= 2 является пересечением трех прямых. Но данная задача двухмерна, и на плоскости для определения точки достаточно двух прямых), и одно из ограничений избыточно.
Способов определить избыточное ограничение непосредственно из данных симплекс-таблиц, к сожалению, не существует. (Выявить неточности и ошибки в постановке исходной задачи может помочь информация о том, что некоторые ресурсы недефицитны)
С вычислительной точки зрения вырожденность может привести к двум последствиям.
1). Во-первых, в процессе вычислений может возникнуть зацикливание.
Если в приведенной таблице сравнить первую и вторую итерации, то можно заметить, что значение целевой функции не изменилось: Z = 18. Поэтому может возникнуть ситуация, когда некоторая последовательность будет повторяться, не изменяя значения целевой функции и не приводя к завершению вычислительного процесса.
(Методы, предотвращающие зацикливание существуют, однако они значительно замедляют процесс вычислений. Поэтому в большинстве программ, реализующих симплекс метод, отсутствуют специальные средства защиты от зацикливания, тем более, что вероятность зацикливания очень мала).
2). Последствие вырожденности решения можно обнаружить, сравнивая две последовательные итерации (1 и 2 итерации в приведенной выше таблице): Хотя в этих итерациях состав базисных и небазисных переменных различен, значения всех переменных и значение целевой функции не изменяются:
Х1 = 0, Х2 = 2, Х3 = 0, X4 = 0, Z = 18.
Несмотря на то, что оптимальное решение не достигнуто, остановить вычисления на (первой) итерации (когда впервые обнаруживается вырожденность) не рекомендуется, так как решение может быть только временно вырожденным.
Альтернативные оптимальные решения
Когда гиперплоскость/(прямая), представляющая целевую функцию, параллельна
гиперплоскости/(прямой), соответствующей связывающему неравенству (которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то же оптимальное значение на некотором множестве точек границы пространства решений.
Эти решения называются альтернативными оптимальными решениями.
Таких решений (если они существуют) бесконечное множество.
Пример:
Последовательные итерации выполнения симплекс-метода:
На рис. множество альтернативных оптимальных решений (точки отрезка ВС) параллельны прямой, соответствующей связывающему ограничению. Каждая точка отрезка ВС соответствует оптимальному решению со значением целевой функции Z = 10.
Неограниченные решения
В некоторых задачах ЛП значения переменных могут неограниченно возрастать без нарушения ограничений. Это означает, что пространство допустимых решений не ограничено по крайней мере по одному направлению и в результате этого целевая функция может неограниченно возрастать (в задаче максимизации) или убывать (в задаче минимизации).
Неограниченность решения задачи свидетельствует только об одном: модель разработана не достаточно корректно.
Типичные ошибки, приводящие к построению таких моделей, заключаются в том, что не учитываются ограничения, не являющиеся избыточными, и не точно оцениваются параметры (коэффициенты) ограничений.
В следующем примере показано, как на основе данных, приведенных в симплекс-таблице, можно определить, когда не ограничено пространство решений и значения целевой функции:
Симплекс-таблица начальной итерации этой задачи имеет следующий вид.
Из таблицы видно, что в качестве вводимой переменной можно взять как X1 так и Х2,
Но Х1 имеет максимальный (по модулю) отрицательный коэффициент в z-строке, именно ее следует ввести в базисное решение.
Однако во всех ограничениях коэффициенты, стоящие перед переменной Х 2, отрицательны или равны нулю. Это означает, что значение переменной Х2 может возрастать до бесконечности, и при этом не нарушается ни одно ограничение.
Поскольку увеличение на 1 значения Х2 приводит к увеличению на 1 значения Z, то неограниченное увеличение значения переменной Х2 приведет к неограниченному увеличению значения целевой функции.
По графическому решению видно, что пространство допустимых решений не ограничено в направлении оси Х2, и значение целевой функции Z может быть каким угодно большим.
Правило выявления неограниченности решения:
Если на какой-либо симплекс-итерации коэффициенты в ограничениях для какой-нибудь небазисной переменной будут неположительными, значит, пространство решений не ограничено в направлении возрастания этой переменной.
Кроме того, если коэффициент этой переменной в Z-строке отрицателен, когда рассматривается задача максимизации, или положителен в задаче минимизации, целевая функция также не граничена.