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

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

 

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

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

 

Пример 2. в стандартной форме

 

 

Б	с
							8:4=2	Признак вырожденного решения
							4:2=2
		-3	-9
								- вырожденная оптимальная точка.
					-		0 - min
		-
						-		- оптимальная точка.
					-1

 

 

 

опт

избыточная

 

Вырожденная точка = оптимальной точке

 

Значение целевой функции не меняется

 

 

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

 

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

 

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

(1)

, (2)

, (3) ,

, (4)

(5)

 

 

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

 

 

 

 

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

 

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

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

Б	с							Замечания
							5/2-min
		-2	-4
								Появление лишнего нуля для небазисной переменной – признак бесконечного множества решений. Начальная точка (0; 5/2)
					-		3-min
						-1		Конечная точка (3: 1). Решение между этими точками на прямой.
					-1

z

А

В

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

 

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

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

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

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

 

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

 

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

(1)

(2)

(3)

(4)

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

z

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

 

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

конечно)

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

(1)

(2)

(3)

(4)

 

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

 

 

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

 

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

 

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

 

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

(1)

(2)

(3)

(4)

 

Б	с						-М		Замечания
								2-min
	-М					-1
		-12M	-3M-3	-4M-2		M
									Отсутствие отрицательных значений в результирующей строке и присутствие искусственной переменной в базе свидетельствует об отсутствии решения
	-M		-5		-4	-1
		-4M+4	5M+1		4M+2	M