Me-02_Gavrilyak (2)

Гавриляк

Me-02

1. Решить М-симплекс-методом ЗЛП

,

f(x)=3x1-2x2+0*x3+0*x4+0*x5+0*x6-M*x7 ---> max

2x1+x2+1*x3+0*x4+0*x5+0*x6=15

3x1+2x2+0*x3-1*x4+0*x5+0*x6+1*x7=6

4x1-2x2+0*x3+0*x4+1*x5+0*x6=18

5x1-5x2+0*x3+0*x4+0*x5+1*x6=16

№ итерации	Базис	Сi	bi решение	3	-2	0	0	0	0	(-M)
				х1	х2	х3	х4	х5	х6	х7
0	x3	0	15	2	1	1	0	0	0	0
	x7	(-M)	6	3	2	0	-1	0	0	1
	x5	0	18	4	-2	0	0	1	0	0
	x6	0	16	5	-5	0	0	0	1	0
	f	Δj	6M	3+3M	(-2+2M)	0	(-M)	0	0	0
f= - (-M*6)=6M			7 1/2
Δ1=3-(-M*3)=3+3M			2
Δ2= -2- (-M*2)= -2+2M			4 1/2
Δ3=0-0=0			3 1/5
Δ4=0-(-M*(-1))=-M
Δ5=0-0=0
Δ6=0-0=0
Δ7= -M-(-M*1)=0

№ итерации	Базис	Сi	bi решение	3	-2	0	0	0	0
				х1	х2	х3	х4	х5	х6
1	x3	0	11	0	- 1/3	1	2/3	0	0	-2
	x1	3	2	1	2/3	0	- 1/3	0	0
	x5	0	10	0	-4 2/3	0	1 1/3	1	0	-4
	x6	0	6	0	-8 1/3	0	1 2/3	0	1	-5
	f	Δj	-6	0	-4	0	1	0	0
f= - (3*2)= 6			16 1/2
Δ1=3-(3*1)=0			-6
Δ2= -2-(3*2/3)=-4			7 1/2
Δ3=0-0=0			3 3/5
Δ4=0-(3*(-1/3))=1
Δ5=0-0=0
Δ6=0-0=0

№ итерации	Базис	Сi	bi решение	3	-2	0	0	0	0
				х1	х2	х3	х4	х5	х6
2	x3	0	8 3/5	0	3	1	0	0	- 2/5	- 2/3
	x1	3	3 1/5	1	-1	0	0	0	1/5	1/3
	x5	0	5 1/5	0	2	0	0	1	- 4/5	-1 1/3
	x4	0	3 3/5	0	-5	0	1	0	3/5
	f	Δj	-9 3/5	0	1	0	0	0	- 3/5
f= - (3*3 1/5)=- 9 3/5			2 7/8
Δ1=3-(3*1)= 0			-3 1/5
Δ2= -2-(3*(-1))=1			2 3/5
Δ3=0-0=0			- 5/7
Δ4=0-0=0
Δ5=0-0=0
Δ6=0-(3*1/5)=-3/5

№ итерации	Базис	Сi	bi решение	3	-2	0	0	0	0
				х1	х2	х3	х4	х5	х6
2	x3	0	4/5	0	0	1	0	-1 1/2	4/5	-3
	x1	3	5 4/5	1	0	0	0	1/2	- 1/5	1
	x2	-2	2 3/5	0	1	0	0	1/2	- 2/5
	x4	0	16 3/5	0	0	0	1	2 1/2	-1 2/5	5
	f	Δj	-12 1/5	0	0	0	0	- 1/2	- 1/5
f= - (3*5 4/5+(-2)*2 3/5)=- 12 1/5
Δ1=3-(3*1)= 0
Δ2= -2-(-2*1)=0
Δ3=0-0=0
Δ4=0-0=0
Δ5=0-(3*1/2+(-2)*1/2)=-1/2
Δ6=0-(3*(-1/5)+(-2)*(-2/5)=-1/5

2. Для выпуска 4 видов товара нужно 3 вида сырья. Расход сырья на единицу каждого товара, запасы сырья и прибыль от продажи единицы товара - в таблице. Найти план выпуска товаров для максимизации прибыли, решая ЗЛП симплекс-методом. Решить двойственную к ней задачу. Если решение не целочисленно, найти целочисленное решение методом Гомори.	Вариант задачи
	Вид сырья	Товар				Запас сырья
		1	2	3	4
	1	5	4	6	7	275
	2	2	0	4	2	100
	3	3	2	0	1	85
	Прибыль	50	27	34	54

f(x)=50x1+27x2+34x3+54x4--->max

f(x)=50x1+27x2+34x3+54x4+0*x5+0*x6+0*x7--->max

5x1+4x2+6x3+7x4≤275

5x1+4x2+6x3+7x4+1*x5+0*x6+0*x7 = 275

2x1+4x3+2x4≤100

2x1+4x3+2x4+0*x5+1*x6+0*x7=100

3x1+2x2+x4≤85

3x1+2x2+x4+0*x5+0*x6+1*x7 = 85

№ итерации	Базис	Сi	bi решение	50	27	34	54	0	0	0
				х1	х2	х3	х4	х5	х6	х7
0	x5	0	275	5	4	6	7	1	0	0
	x6	0	100	2	0	4	2	0	1	0
	x7	0	85	3	2	0	1	0	0	1
	f	Δj	0	50	27	34	54	0	0	0
f= 0			39 2/7
Δ1=50-0=50			50
Δ2=27-0=27			85
Δ3=34-0=34
Δ4=54-0=54
Δ5=0-0=0
Δ6=0-0=0
Δ7=0-0=0

№ итерации	Базис	Сi	bi решение	50	27	34	54	0	0	0
				х1	х2	х3	х4	х5	х6	х7
1	х4	54	39 2/7	5/7	4/7	6/7	1	1/7	0	0
	x6	0	21 3/7	4/7	-1 1/7	2 2/7	0	- 2/7	1	0	-2
	х7	0	45 5/7	2 2/7	1 3/7	- 6/7	0	- 1/7	0	1	-1
	f	Δj	-2121 3/7	11 3/7	-3 6/7	-12 2/7	0	-7 5/7	0	0
f= -(54*39 2/7)=-2121 3/7			55
Δ1=50-(54*5/7)=11 3/7			37 1/2
Δ2=27-(54*4/7)= -3 6/7			20
Δ3=34-(54*6/7)=-12 2/7
Δ4=54-(54*1)=0
Δ5=0-(54*1/7)=-7 5/7
Δ6=0-0=0
Δ7=0-0=0

№ итерации	Базис	Сi	bi решение	50	27	34	54	0	0	0
				х1	х2	х3	х4	х5	х6	х7
2	х4	54	25	0	1/8	1 1/8	1	1/5	0	- 1/3	- 5/7
	х6	0	10	0	-1 1/2	2 1/2	0	- 1/4	1	- 1/4	- 4/7
	х1	50	20	1	5/8	- 3/8	0	-0,06	0	4/9
	f	Δj	-2350	0	-11	-8	0	-7	0	-5
f= -(54*25+50*20)=-2350
Δ1=50-(50*1)=0
Δ2=27-(54*1/8+50*5/8)=-11
Δ3=34-(54*1 1/8+50*(-3/8)=-8
Δ4=54-(54*1)=0
Δ5=0-(54*1/5+50*(-0,06)=-7
Δ6=0-0=0
Δ7=0-(54*(-1/3)+50*4/9)=-5