Лабораторная работа - Розв’язування задач симплексним методом - файл n1.doc

Лабораторная работа - Розв’язування задач симплексним методом

Доступные файлы (2):

n1.doc	128kb.	04.02.2011 17:26	скачать
n2.xls	32kb.	05.03.2010 17:09	скачать

n1.doc

Варіант №7

Лабораторна робота №3

з ЕММ

Тема: «Розв’язування задач симплексним методом»
Алгоритм розв’язання

1. 
   Маємо задачу лінійного програмування та її спрощений варіант:
   

Z=45x1+41x2=max





Зводимо до канонічного вигляду:
Z=45x1+41x2=max



За допомогою жорданових перетворень проводимо розрахунки, а потім у останній таблиці перетворень знаходимо відповідь задачі:

			45	51	0	0	0
Баз	Сбаз	А0	A1	A2	A3	A4	A5
А3	0	178	6,8	5,3	1	0	0
А4	0	94	4,3	2,1	0	1	0
А5	0	118	2,9	4,2	0	0	1
		0	-45	-51	0	0	0
			45	51	0	0	0
Баз	Сбаз	А0	A1	A2	A3	A4	A5
А3	0	29,09524	3,140476	0	1	0	-1,2619
А4	0	35	2,85	0	0	1	-0,5
А5	0	28,09524	0,690476	1	0	0	0,238095
		1432,857	-9,78571	0	0	0	12,14286
			45	51	0	0	0
Баз	Сбаз	А0	A1	A2	A3	A4	A5
А3	0	9,264594	1	0	0,318423	0	-0,40182
А4	0	8,595906	0	0	-0,90751	1	0,645186
А5	0	21,69826	0	1	-0,21986	0	0,515542
		1523,518	0	0	3,115997	0	8,210766

Відповідь:

Z=	1523,517817
X1=	9,26459439
X2=	21,69825625

Скориставшись даними першої симплексної таблиці, можна записати матричні співвідношення, які дозволяють знайти той самий розв’язок:

	6,8	5,3	0
D=	4,3	2,1	1
	2,9	4,2	0

D-1=	0,318423048	0	-0,40182
	-0,219863533	0	0,515542
	-0,907505686	1	0,645186

A*=D-1*A	9,26459439	1	-2,22045E-16	0,318423	0	-0,40182
	21,69825625	0	1	-0,219864	0	0,515542
	8,595905989	-6,66134E-16	-4,44089E-16	-0,907506	1	0,645186

C=	45		51	0

Z=C*A0 Z=

1523,517817

Розглянемо розв’язок задачі лінійного програмування методом штучного базису.

Z=45x1+41x2=max
Наявність від’ємного знаку біля додаткового невідомого х4 не дозволяє використати його для побудови початкового опорного розв’язку у симплексному методі, тому створимо для цього умови :


Z=45x1+41x2-1000х4=max




i = 1,2,…,7
Для розв’язку задачі алгоритм залишається тим самим:

			45	51	0	0	0	0	-1000
Баз	Сбаз	А0	A1	A2	A3	A4	A5	A6	A7
А3	0	178	6,8	5,3	1	0	0	0	0
A7	-1000	23	1	1	0	0	0	-1	1
А4	0	94	4,3	2,1	0	1	0	0	0
А5	0	118	2,9	4,2	0	0	1	0	0
		-23000	-1045	-1051	0	0	0	1000	0
			45	51	0	0	0	0	-1000
Баз	Сбаз	А0	A1	A2	A3	A4	A5	A6	A7
А3	5300	56,1	1,5	0	1	0	0	5,3	-5,3
A7	0	23	1	1	0	0	0	-1	1
А4	2100	45,7	2,2	0	0	1	0	2,1	-2,1
А5	4200	21,4	-1,3	0	0	0	1	4,2	-4,2
		1173	6	0	0	0	0	-51	1051
			45	51	0	0	0	0	-1000
Баз	Сбаз	А0	A1	A2	A3	A4	A5	A6	A7
А3	0	29,0952381	3,14047619	0	1	0	-1,2619	0	0
A7	1000	28,0952381	0,69047619	1	0	0	0,238095	0	0
А4	0	35	2,85	0	0	1	-0,5	0	0
А5	1000	5,095238095	-0,30952381	0	0	0	0,238095	1	-1
	51000	1432,857143	-9,785714286	0	0	0	12,14286	0	1000
			45	51	0	0	0	0	-1000
Баз	Сбаз	А0	A1	A2	A3	A4	A5	A6	A7
А1	45	9,26459439	1	0	0,318423	0	-0,40182	0	0
A2	51	21,69825625	0	1	-0,21986	0	0,515542	0	0
А4	0	8,595905989	0	0	-0,90751	1	0,645186	0	0
А6	1000	7,962850644	0	0	0,09856	0	0,113723	1	-1
	51000	1523,517817	0	0	3,115997	0	8,210766	0	1000

Отже, отримали такий самий розвязок:

Х1=9,26

Х2=21,7