Теорема (признак оптимальности опорного плана):

Если для некоторого опорного плана все оценки при решении задачи на максимум не отрицательны, а при решении задачи на минимум – не положительны, то такой план оптимален.

Пример:

Некоторое предприятие выпускает столы и стулья. На изготовление одного стула стоимостью 1 у.д.е. требуется 1 куб.м сосны и 1 куб.м дуба, а для производства стола стоимостью 4 у.д.е. требуется 2 куб.м сосны. На складе имеется 100 куб.м сосны и 40 куб.м дуба.

Решение:

Сведем к задаче в канонической форме:

Составляем симплексную таблицу (х₃ и х₄ - базисные):

БП	сБ	х1	х2	х3	х4	А0
		1	4	0	0
х3	0	1	2	1	0	100
х4	0	1	0	0	1	40
Δj		-1	-4	0	0	0

X= (0; 0| 100; 40)

План не оптимальный так как есть индексные оценки отрицательные.

Переход к не худшему плану.

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

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

Для того, чтобы определить индексную строку необходимо найти для каждой строки наименьшее симплексное отношение: , где j₀ – разрешающий столбец.

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

Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом.

При переходе к новой симплексной таблице будем пользоваться следующими правилами:

.

Эти же правила можно сформулировать по другому:

1. Элементы разрешающей строки новой симплексной таблицы равны элементам прежней симплексной таблицы, деленным на разрешающий элемент.

2. В разрешающем столбце все элементы, кроме =1, равны 0.

3. Все остальные элементы находятся по правилу прямоугольника:

Для получения элементов новой таблицы (α_ij), необходимо из произведения угловых элементов главной диагонали (содержащей искомый элемент и разрешающий элемент) вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент

Аналогичное правило можно сформулировать и для нахождения элементов индексной строки и столбца свободных членов.

Пусть, например, имеется симплексная таблица. Тогда правило прямоугольника выглядит следующим образом:

БП	СБ	х1	х2	х3	х4	х5	х6	А0	θ
		4	3	1	0	0	0
х3	0	1	2	3	1	0	0	15	15/1
х4	0	-7	-1	2	0	1	0	20	–
х5	0	2	0	4	0	0	1	4	4/2 min
Δj		-4 max по модулю	-3	-1	0	0	0

В табличке выделены:

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

После проведения преобразований на месте искомого элемента получим:

БП	СБ	х1	х2	х3	х4	х5		А0	θ
		4	3	1	0	0	0
х3	0	0
х4	0	0
х1	4	1	0	2	0	0	0,5	2
Δj		0

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

Замечания:

1. Шаг симплексных преобразований называют итерацией.

2. Если в индексной строке среди оценок свободных переменных в оптимальном плане есть равные 0, то имеет место случай альтернативного оптимума (т.е. существует по крайней мере еще хотя бы одна угловая точка ОДР являющаяся оптимальным планом => оптимальных планов бесконечно много)

3. После каждой итерации можно делать проверку правильности вычислений по следующим формулам: