Третья итерация

Вторая итерация

Табл. 2						q
i	Csi	базис	A0	A1	A2	A3	A4
		A1	8/3			1/3	1/3
		A2	2/3			-2/3	1/3	---
	D	28/3			-1/3	5/3
	Z	28/3			-1/3	5/3
					Ýmin

Элемент a₁₃ =1/3 является направляющим(в таблице выделен зеленым цветом).

Табл. 3
i	Csi	базис	A0	A1	A2	A3	A4
		A3
		A4
	D
	Z

Поскольку все D_j³0, то план представленный в данной таблице будет оптимальным.

Ответ: x₁ =0; x₂=6; x₃=8; x₄=0; L=12;

Если в системе ограничений имеются неравенствами вида > и/или =, начальный план не может быть найден так же просто, как в рассмотренном проимере. В таких случаях начальный план отыскивают с помощью искусственных переменных.

Пример: Найти максимум функции

L=2x₁+3x₂-5x₃;

при ограничениях:

2x₁+x₂-x₃³7,

x₁+2x₂+x₃³6,

x₁+4x₂=8,

x_j³0

Вводим в систему три искусственные переменные: x₆, x_7, x₈, позволяющие получить начальный базис.

Для исключения из базиса этих переменных последние вводятся в целевую функцию с большим отрицательным коэффициентом М (в задаче минимизации - с положительным М)

L¢=L-M*x₆-M*x₇-M*x₈®max

при ограничениях

2x₁+x₂-x₃-x₄+x₆=7,

x₁+2x₂+x₃-x₅+x₇=6,

x₁+4x₂+x₈=8,

x_j³0

Выбрав в качестве начального базиса векторы A₆ , A₇, A₈, решаем полученную задачу с помощью табличного симплекс-метода.

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

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

Табл 0					-5			-M	-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7	A8
-M	A6				-1	-1
-M	A7						-1
-M	A8										2Ümin
	D	-21M	-4M -2	-7M -3		M	M
				Ýmin

Элемент a₈₂=4 является направляющим(в таблице выделен зеленым цветом).

Столбцы, соответствующие искусственным переменным по мере вывода из базиса из расчета исключаются.

Табл 1					-5			-M	-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7
-M	A6		7/4		-1	-1				20/7Ümin
-M	A7		1/2				-1
	A2		1/4
	D	-7M+6	-9М/4-3/4		M+5	M	M
			Ýmin

Элемент a₆₁=7/4 является направляющим(в таблице выделен зеленым цветом).

Табл 2					-5			-M	q
Csi	базис	A0	A1	A2	A3	A4	A5	A6
	A1	20/ 7			-4/ 7	-4/ 7			---
-M	A7	4/ 7			9/ 7	2/ 7	-1		4/9Ümin
	A2	9/ 7			1/ 7	1/ 7
	D	-4M/ 7 +67/ 7			-9M/ 7 +30/ 7	2M/ 7 -5/ 7	M
					Ýmin

Направляющий элемент a₇₃=9/ 7(в таблице выделен зеленым цветом).

Табл 3					-5
Csi	базис	A0	A1	A2	A3	A4	A5
	A1	28/9					-4/9
-5	A3	4/9				2/9	-7/9
	A2	11/9				-1/9	1/9
	D	23/3				23/9	30/9

Дата добавления: 2013-12-12