4. Признак оптимальности злп

4.1. Если найдётся свободный вектор A_j (см жёлтый фон), у которого и есть положительные координаты, то полученный в этой итерации план не является оптимальным. Его можно улучшить за счёт введения в ортонормированный базис этого вектора (в симплексной таблице будем называть его ведущий столбец). Лучше всего для этого выбрать вектор с максимальным

. В нашем примере это будет

_{Следовательно, второй столбец будет ведущим и вектор А2 будем вводить в базис (j=2).}

Имена всех векторов, входящих в базис записаны в столбце “С_б”. Чтобы найти, какой из них нужно вывести из базиса, надо заполнить столбец , каждый элемент которого вычисляется следующим образом (i-номер строки, напомню, j=2 ):

a₂₂=-1<0, (j=2, i=2), поэтому Θ₂=0, a₁₂=+1>0, (j=2, i=1) Θ₁=b₁/a₁₂=2/1=2, Θ₁=2, a₃₂=+3>0, (j=2, i=3) Θ₃=b₃/a₃₂=14/3=14/3, Θ₃=14/3 В строке с минимальным >0 находится вектор, выводимый из базиса (это 1-я строка). Эту строку будем называть “ведущая строка”. На пересечении ведущей (i-ой, у нас – 1-ой) строки и ведущего (j-го, у нас 2-го) столбца находится ведущий элемент (у нас a₁₂=1).

Итак, над ведущим столбцом написано имя вектора, вводимого в базис (это А₂) , а в самом начале ведущей строки – имя вектора, выводимого из базиса (это А₃). В нашем примере

_{Следовательно, вторая ПЕРВАЯ строка – ведущая и базисный вектор этой строки А3 выводим из базиса.}

_{Вектор А3 был ортом Е2, теперь нужно, чтобы вектор А2=Е2. Эта операция выполняется с помощью одного шага метода полного исключения:}

_{1) Ведущую строку (у нас – 1-я) делим на ведущий элемент} (у нас a₁₂=1) _{, получим новую ведущую строку для следующей симплексной таблицы;}

_{2) все остальные элементы ведущего столбца обнуляем с помощью новой ведущей строки (это мы умеем – домножаем, складываем…).}

_{В результате получим новую симплексную таблицу (первая итерация).}

_{В нашем примере в первой итерации получили х1=0; х2=2; z1=8M+6. Или 8М-6?}

_Теперь для каждого вектора при неизвестном вычислить оценку по формуле: _{умножение векторов скалярное (см. выше)}

_{В первой итерации план ещё не оптимальный, так как оценка}

_{При этом следовательно, вектор А1 вводим в базис вместо вектора А6.}

_{Переменная х6 - искусственная, следовательно, в следующих итерациях этот столбец учитывать не нужно.}

_{Во второй итерации вводим в базис вектор А5 вместо вектора А4 и получаем третью итерацию, в которой все оценки}

				-1	-3	0	0	0	М	θ	NT
	Cб	Базис	B	А1	А2	А3	А4	А5	А6
1	0	А3	2	-1	1	1	0	0	0	2 min	0
2	0	А4	+2 12	-1 3	+1 -1	0  0	0 1	0  0	0 0	0
3	М	А6	-61 14	+3 1	-3  3	-3  0	0  0	0 -1	0 1	14/3
			z0= 14М	М+1	3М+3 max	0	0	-М	0
1	-3	А2	-1 2	+1  -1	0 1	-1  1	0  0	-1/3  0	0	0	1
2	0	А4	-1 14	-2 2	0 0	+2 1	0 1	+2/3  0	0	7
3	М	А6	8	3	0	-3	0	-1	1	8/3 min
			z1= 8М-6	3М+34 max	0	-3M-3	0	-М	0
1	-3	А2	-1 14/3	0  0	0 1	+3/2 0	+1/2  0	+1/3  -1/3		0	2
2	0	А4	26/3	0	0	3	1	2/3		13 min
3	-1	А1	-1 8/3	0  1	0 0	+3/2 -1	+1/2  0	+1/3  -1/3		0
			z2= -50/3	0	0	1	0	4/3 max
1	-3	А2	9	0	1	3/2	1/2	0			3
2	0	А5	13	0	0	9/2	3/2	1
3	-1	А1	7	1	0	1/2	1/2	0
			z3= -34	0	0	-5	-2	0

4.2. Если в результате очередной операции получим, что все искусственные переменные (у нас х₆ (это вместо w) ) выведены из условия задачи (равны нулю) и при этом оценки всех векторов-коэффициентов _{то полученный в этой итерации план является оптимальным.}

_{В нашем примере третья итерация даёт оптимальный план:} х₁=7; х₂=9; z₀=-34.

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

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