Признак оптимальности ЗЛП

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

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

Следовательно, второй столбец будет ведущим и вектор А₂ будем вводить в базис (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).

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

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

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

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

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

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

В нашем примере в первой итерации получили х₁=0; х₂=2; z₁=8M+6. Или 8М-6?

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

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

При этом следовательно, вектор А₁ вводим в базис вместо вектора А₆.

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

Во второй итерации вводим в базис вектор А₅ вместо вектора А₄ и получаем третью итерацию, в которой все оценки

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

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

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

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

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

Дата добавления: 2014-01-07