Особые случаи применения симплекс-метода

Вырожденное оптимальное решение

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

Наличие вырожденного решения не свидетельствует о какой-либо «опасности» для исследователя и вызывает лишь некоторое неудобство в теоретическом отношении. С практической точки зрения специфика ситуации целиком объясняется наличием в модели по крайней мере одного избыточного ограничения.

Пример 1.

1.7.2 Бесконечное множество решений

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

Пример 2.

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

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

Пример 3.

(1)

(2)

(3)

(4)

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

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

Неограниченность решения ЗЛП свидетельствует только об одном: разработанная модель недостаточно точна. Бессмысленность использования модели, прогнозирующей «бесконечную» прибыль, вполне очевидна. Наиболее типичные ошибки, приводящие к построению моделей такого рода, состоит в том, что

а) не учтено одно (или несколько) ограничение, не являющееся избыточным;

б) неточно оценены параметры, фигурирующие в некоторых ограничениях.

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

В стандартной форме

(1)

(2)

(3)

Б	с							Замечания
				-1			10-min
		-2	-1
				-1			отр
					-1		30-min
			-3
								Отсутствие - признак неограниченности решения. Присутствие отрицательного числа в результирующей строке признак неограниченности целевой функции.
					-1		отр
				-1

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

Пример 5. (Пространство решений не ограничено, а оптимальное значение целевой функции

конечно)

В стандартной форме

(1)

(2)

(3)

(4)

Б	с			-2				Замечания
				-1			1-min
		-6
				-			отр
					-		6- min
			-1
	-2				-1

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

1.7.5 Промежуточное вырожденное решение

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

Пример 6. В стандартной форме

(1)

, (2)

, (3) ,

, (4)

(5)

Б	с								Замечания
									Признак вырожденности
				-1
		-3	-2
									- вырожденное неоптимальное решение
						-1		2-min
				-2		-1		отр
			-
					-				- оптимальное вырожденное решение.
						-
						-2