1)Все индексные оценки «хорошие», следовательно, получен оптимальный план. Если при этом решали м-задачу и все , то получен и оптимальный план исходной задачи.

Если хотя бы одна из искусственных базисных переменных не равна нулю, то исходная задача решения не имеет. Ее ограничения противоречивы и ОДЗ пусто.

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

3)Если есть «плохие» оценки, но в соответствующих столбцах нет ни одного положительного элемента, то целевая функция неограниченна.

При применении симплекс метода переходят от вершины к вершине ОДЗ, двигаясь в направлении градиента по ребру.

Пример

		1	2	0	0	М	B
	0	2	4	1	0	0	10
	М	1	1	0	-1	1	2
		М	М	0	-М	0	2М
		-1	-2	0	0	0	0

.

.

Оценка (М-1) определяет разрешающий столбец.

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

		1	2	0	0	М
	0	2	4	1	0	0	10	10:2=5
	М	1	1	0	-1	1	2	2:1=2-min
		М	М	0	-М	0	2М
		-1	-2	0	0	0	0

Верхняя строка индексных оценок :

.

Нижняя строка :

.

Проверим индексные оценки

.

		1	2	0	0	М
	0	2	4	1	0	0	10	10:2=5
	М	1	1	0	-1	1	2	2:1=2-min
		М	М	0	-М	0	2М
		-1	-2	0	0	0	0
	0	0	2	1	2	-2	6
	1	1	1	0	-1	1	2
		0	0	0	0	-М	0
		0	-1	0	-1	1	2

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

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

Пример

		1	2	0	0	-М
	0	2	4	1	0	0	10	10:4=2,5
	-М	1	1	0	-1	1	2	2:1=2-min
		-М	-М	0	М	0	-2М
		-1	-2	0	0	0	0

.

.

Нижняя строка

.

		1	2	0	0	-М
	0	2	4	1	0	0	10	10:4=2,5
	-М	1	1	0	-1	1	2	2:1=2-min
		-М	-М	0	М	0	-2М
		-1	-2	0	0	0	0
	0	-2	0	1	.4.	-4	2	2 : 4 = 1/2
	2	1	1	0	-1	1	2
		0	0	0	0	М	0
		1	0	0	-2	2	4

Проверим индексные оценки

.

		1	2	0	0	-М
	0	2	4	1	0	0	10	10:4=2,5
	-М	1	1	0	-1	1	2	2:1=2-min
		-М	-М	0	М	0	-2М
		-1	-2	0	0	0	0
	0	-2	0	1	.4.	-4	2	2 : 4 = 1/2
	2	1	1	0	-1	1	2
		0	0	0	0	М	0
		1	0	0	-2	2	4
	0	-1/2	0	1/4	1	-1	1/2
	2	1/2	1	1/4	0	0	5/2	5/2 : 1/2= 5
		0	0	0	0	М	0
		0	0	1/2	0	0	5

Так как все индексные оценки неотрицательны, то найдено оптимальное решение задачи. При этом все свободные переменные (отсутствующие в столбце последней симплекс таблицы) равны 0. Базисные переменные . Значение целевой функции равно .

То есть, Так как , то получено и решение первоначальной задачи . Оптимальный план . Проверим, является ли он единственным.

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

		1	2	0	0	-М
	0	2	4	1	0	0	10	10:4=2,5
	-М	1	1	0	-1	1	2	2:1=2-min
		-М	-М	0	М	0	-2М
		-1	-2	0	0	0	0
	0	-2	0	1	.4.	-4	2	2: 4 = 1/2
	2	1	1	0	-1	1	2
		0	0	0	0	М	0
		1	0	0	-2	2	4
	0	-1/2	0	1/4	1	-1	1/2
	2	1/2	1	1/4	0	0	5/2	5/2: 1/2= 5
		0	0	0	0	М	0
		0	0	1/2	0	0	5
	0	0	1	1/2	1	-1	3
	1	1	2	1/2	0	0	5
		0	0	0	0	М	0
		0	0	1/2	0	0	5

Выпишем полученное решение М-задачи и решение первоначальной задачи . Оптимальный план .

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

Если обозначить , то ответ можно записать так: задача имеет бесконечное множество решений.

.

Пример

Приведем задачу к каноническому виду, заменяя неравенства равенствами.

В первом уравнении нет базисной переменной, поэтому вводим искусственную базисную переменную и, так как решается задача на max, то в целевую функцию войдет с коэффициентом (-М).

		2	3	0	0	-М
	-M	2	1	-1	0	1	2	2:2=1
	0	1	-1	0	1	0	0	0:1=0-min
		-2М	-М	M	0	0	-2М
		-2	-3	0	0	0	0

Строка индексных оценок

.

Верхняя строка

.

Нижняя строка

.

		2	3	0	0	-М
	-M	2	1	-1	0	1	2	2:2=1
	0	1	-1	0	1	0	0	0:1=0-min
		-2М	-М	M	0	0	-2М
		-2	-3	0	0	0	0
	-M	0	3	-1	.-2	1	2	2:3=2/3
	2	1	-1	0	1	0	0
		0	-3M	M	2M	0	-2M
		0	-5	0	2	0	0

Проверим индексные оценки

.

		2		3		0		0		-М
	-M	2		1		-1		0		1		2		2:2=1
	0	1		-1		0		1		0		0		0:1=0-min
			-2М		-М		M		0		0		-2М
			-2		-3		0		0		0		0
	-M	0		3		-1		.-2		1		2		2:3=2/3
	2	1		-1		0		1		0		0
			0		-3M		M		2M		0		-2M
			0		-5		0		2		0		0
	3	0		1		-1/3		.-2/3		1/3		2/3
	2	1		0		-1/3		1/3		1/3		2/3
			0		0		0		0		M		0
			0		0		-5/3		-4/3		5/3		10/3

«Самая плохая» оценка равна (-5/3). Но в этом столбце нет ни одного положительного элемента. Такая ситуация и соответствует неограниченности целевой функции. Итак, .

Пример

			1		2		0		0		М
	М		2		1		-1		0		1		8		8:2=4
	0		1		2		0		1		0		2		2:1=2-min
		2М		М		-М		0		0		8М
		-1		-2		0		0		0		0
	М		0		-3		-1		-2-2.		1		4
	1		1		2		0		1		0		2
		0		-3М		-М		-2М		0		4М
		0		0		0		1		0		2

Все оценки неположительные, следовательно, получено оптимальное решение М-задачи. Но т.к. то исходная задача решений не имеет