Алгоритм симплекс-метода

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

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

Опорное решение предполагает, что остаточные переменные приравниваются ресурсам, а основные переменные равны нулю.

Коэффициенты индексной строки вычисляются по формуле:

; - коэффициенты при неизвестных в уравнении для целевой функции;

- оценка целевой функции;

- коэффициенты ограничений;

Если среди дополнительных переменных есть только остаточные, то , т. к. =0, т. е. каждый j-ый элемент индексной строки равен взятому с обратным знаком коэффициенту при соответствующей переменной в целевой функции.

Значение целевой функции при этом равно 0, .

Решение оптимально, когда все элементы индексной строки положительны в задачах на максимум; (отрицательны в задачах на минимум).

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

Увеличивая соответствующую небазисную переменную, в данном примере это X₃,, вводя ее в базис, мы увеличиваем значение Z. Для определения выводимой из базиса переменной поочередно разделим значения элементов столбца свободных членов A_io на соответствующие положительные элементы ключевого столбца A_io/A_iкл..

Формирование исходной матрицы в общем виде

Таблица 20

№ ограничений	Базисн. переменные	Оценка целевой функц.	значение базисной переменной												Контроль	Частное от деления
				Коэффициенты замещения
				Основные переменные					Дополнительные переменные
1		0							+1	0	0	0	0
2		0							0	1	0	0	0
3		0							0	0	1	0	0
		0		Коэффициенты при неизвестных в системе ограничений основных элементов. Единичная матрица
Индексная строка			0						0	0	0		0

Таблица 21

Первая симплекс-таблица (первое опорное решение).

№ огр.	Баз.переменные.	Оценка цел.функции	Значение баз. пер. Аiо										Контроль	Частное от деления
				Коэффициенты замещения
				Основные перемен.				Дополнит. перемен.
				Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост)	Х8 (ост)
1	Х5(ост.)	0	1000	1	1	0	0	1	0	0	0	1003		-
2	Х6(ост.)	0	40000	5	5	50	100	0	1	0	0	40161		800
3	Х7(ост.)	0	120000	3	16	24	10	0	0	1	0	120054		5000
4	Х8(ост.)	0	3000	-6	-50	50	10	0	0	0	1	3005		60min
zj – cj			0	-100	0	-650	-320	0	0	0	0	-1070		-

Таблица 22

Вторая симплекс-таблица

№ огр..	Баз. переменные	Оценка цел.функции	Значение баз. пер. Аiо										Контроль	Частное от деления
				Коэффициенты замещения
				Основные перемен.				Дополнит. перемен.
				Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост)	Х8 (ост)
1	Х5(ост.)	0	1000	1	1	0	0	1	0	0	0	1003		1000
2	Х6(ост.)	0	37000	11	55	0	90	0	1	0	-1	37156		673
3	Х7(ост.)	0	118600	5,9	40	0	5,2	0	0	1	-0,5	118651		2960
4	Х3(осн.)	0	60	-0,12	-1	1	0,2	0	0	0	0,02	60,1		-
zj – cj			39000	-178	-650	0	-190	0	0	0	13	37995		-

Таблица 23

Третья симплекс-таблица

№ огр..	Баз. переменные	Оценка цел.функции	Значение баз. пер. Аiо										Контроль	Частное от деления
				Коэффициенты замещения
				Основные перемен.				Дополнит. перемен.
				Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост	Х8 (ост)
1	Х5(ост.)	0	327,3	0,8	0	0	-1,64	1	-0,018	0	0,018	327,46		409
2	Х2(осн.)	0	672,7	0,2	1	0	1,64	0	0,018	0	-0,018	675,54		3360
3	Х7(ост.)	0	118600	-2,12	0	0	-60,3	0	-0,73	1	0,25	118538		-
4	Х3(осн.)	0	732,7	0,08	0	1	1,84	0	0,018	0	0,018	735,656		9160
zj – cj			476272	-48	0	0	874	0	1,18	0	1,18	477101

Таблица 24

Результаты решения симплексной задачи

(Максимизация целевой функции)

№ огр..	Баз. переменные	Оценка цел.функции	Значен. базис. пер. Аiо										Контроль
				Коэффициенты замещения
				Основные перемен.				Дополнит. перемен.
				Х1 (осн)	Х2 (осн)	Х3 (осн)	Х4 (осн)	Х5 (ост)	Х6 (ост)	Х7 (ост)	Х8 (ост)
1	Х1(осн)	0	409,1	1	0	0	-2,05	1,25	-0,023		0,023	409,3
2	Х2(осн.)	0	590,9	0	1	0	2,05	-0,25	0,023		-0,023	593,7
3	Х7(ост.)	0	92520	0	0	0	-64,6	2,65	-0,775		0,295	92457,57
4	Х3(осн.)	0	700	0	0	1	2	-0,1	0,02		0	702,92
zj – cj			495909	0	0	0	775	60	10,7		2,27	496757

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

Переменная X₈ подлежит выводу из базиса в нашем примере. Элемент, находящийся на пересечении ключевого столбца и ключевой строки, называют ключевым (разрешающим).