Question

0 STAR Co. provides paper to smaller companies whose volumes are not large enough to warrant dealing directly with the paper mill. STAR receives 100-feet-wide paper rolls from the mill and cuts the rolls into smaller rolls of widths 12, 15, and 30 feet. The demands for these widths vary from week to week. The following cutting patterns have been established: Number of: Pattern 12ft. 15ft. 30ft. Trim Loss 1 0 0 3 10 ft. 2 0 6 0 10 ft. 3 3 4 0 4 ft. 4 3 0 2 4 ft. 5 2 5 0 1 ft. Trim loss is the leftover paper from a pattern (e.g., for pattern 4, 3(12) + 0(15) + 2(30) - 96 feet used resulting in 100-96 - 4 foot of trim loss). Demands this week are 5,686 12-foot rolls, 1,660 15-foot rolls, and 3,490 30-foot rolls. Develop an all-integer model that will determine how many 100-foot rolls to cut into each of the five patterns in order to meet demand and minimize trim loss (leftover paper from a pattern). Optimal Solution: Pattern Number Rolls Used 1 2 3 4 5 Trim Loss: 2835 feet

Answer 1

Answer:- and x5 foot rolls let d., 22, 23, 24. be the number of 100 - Jeet-wide paper volls from the mill and cutting patterns 1, 2, 3, 4 25 Objective function Minimize the trim loss lox, + 10x + 4x3+4x4+25 Mini = 10x + 10x2 +423 + 4x4+25 Demand of 12-foot rolls 5, 686 . Demand Constraint 12- foot rolul oxi + 0x2 + 3x3 +34 + 2x5 71 5686 Demand of 15- - 1,660 & Demand Constraint 15-foot role ox, + 6x2 + 4x3 +004 +505 711660 Demand of 30 foot roll 3,490 8. Demand Constrainst 30-foot roll 37g torg 1023 +224 tony 713 490 The optimization Constraint is as written below X, 22, 23, 24, 710 linear programming model Mini(z)= 102, + 10x +423 +4x4 + 25 all are ox, + Oxgt 323+ 304+ 205 7,5670 on + 6x2 + 4x + Oxu + 505 7,1660 Constant) 301 toxat Oxz + 2x4 + 015 713490 1,22 123, de 15 70 Subjected to (demand

13 Stap: 4 rewrite Objective function 0 M 11 Mini z = loxiflox2 + 4 X₂ + 4 X 4 tag tos, tosa tosz TMA, + M Agt MA3 which should be avoided to minimisel Co-officients of Sweplus variables: Artificial Cost - next page for Calculation Here. I attached the text file. - Calculation purpose. 11 Infinity cost firal answer Optimal Solution : pattern. Number rollsused a 0 - ee Ha 23 VALDO 3 4 du 1945 5 25 = 332 Minimum Trimloss (4*1745)+(1433a) 7312.

MIN Z = 10x1 + 10x2 + 4x3 + 4x4 + x5
subject to
3x3 + 3x4 + 2x5 >= 5670
6x2 + 4x3 + 5x5 >= 1660
3x1 + 2x4 >= 3490
and x1,x2,x3,x4,x5 >= 0

Solution:
Problem is

Min Z = 10 x1 + 10 x2 + 4 x3 + 4 x4 + x5

subject to

3 x3 + 3 x4 + 2 x5 ≥ 5670 6 x2 + 4 x3 + 5 x5 ≥ 1660 3 x1 + 2 x4 ≥ 3490

and x1,x2,x3,x4,x5≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '≥' we should subtract surplus variable S1 and add artificial variable A1

2. As the constraint-2 is of type '≥' we should subtract surplus variable S2 and add artificial variable A2

3. As the constraint-3 is of type '≥' we should subtract surplus variable S3 and add artificial variable A3

After introducing surplus,artificial variables

Min Z = 10 x1 + 10 x2 + 4 x3 + 4 x4 + x5 + 0 S1 + 0 S2 + 0 S3 + M A1 + M A2 + M A3

subject to

3 x3 + 3 x4 + 2 x5 - S1 + A1 = 5670 6 x2 + 4 x3 + 5 x5 - S2 + A2 = 1660 3 x1 + 2 x4 - S3 + A3 = 3490

and x1,x2,x3,x4,x5,S1,S2,S3,A1,A2,A3≥0

Iteration-1		Cj	10	10	4	4	1	0	0	0	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	A1	A2	A3	MinRatio XBx5
A1	M	5670	0	0	3	3	2	-1	0	0	1	0	0	56702=2835
A2	M	1660	0	6	4	0	(5)	0	-1	0	0	1	0	16605=332→
A3	M	3490	3	0	0	2	0	0	0	-1	0	0	1	---
Z=10820M		Zj	3M	6M	7M	5M	7M	-M	-M	-M	M	M	M
		Zj-Cj	3M-10	6M-10	7M-4	5M-4	7M-1↑	-M	-M	-M	0	0	0

Positive maximum Zj-Cj is 7M-1 and its column index is 5. So, the entering variable is x5.

Minimum ratio is 332 and its row index is 2. So, the leaving basis variable is A2.

∴ The pivot element is 5.

Entering =x5, Departing =A2, Key Element =5
R2(new)=R2(old)÷5

R1(new)=R1(old) - 2R2(new)

R3(new)=R3(old)

teration-2		Cj	10	10	4	4	1	0	0	0	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	A1	A2	A3	MinRatio XBx4
A1	M	5006	0	-125	75	(3)	0	-1	25	0	1	-25	0	50063=1668.6667→
x5	1	332	0	65	45	0	1	0	-15	0	0	15	0	---
A3	M	3490	3	0	0	2	0	0	0	-1	0	0	1	34902=1745
Z=8496M+332		Zj	3M	-12M5+65	7M5+45	5M	1	-M	2M5-15	-M	M	-2M5+15	M
		Zj-Cj	3M-10	-12M5-445	7M5-165	5M-4↑	0	-M	2M5-15	-M	0	-7M5+15	0

Positive maximum Zj-Cj is 5M-4 and its column index is 4. So, the entering variable is x4.

Minimum ratio is 1668.6667 and its row index is 1. So, the leaving basis variable is A1.

∴ The pivot element is 3.

Entering =x4, Departing =A1, Key Element =3
1(new)=R1(old)÷3

R2(new)=R2(old)

R3(new)=R3(old) - 2R1(new)

Iteration-3		Cj	10	10	4	4	1	0	0	0	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	A1	A2	A3	MinRatio XBx1
x4	4	50063	0	-45	715	1	0	-13	215	0	13	-215	0	---
x5	1	332	0	65	45	0	1	0	-15	0	0	15	0	---
A3	M	4583	(3)	85	-1415	0	0	23	-415	-1	-23	415	1	45833=4589=50.8889→
Z=458M3+210203		Zj	3M	8M5-2	-14M15+83	4	1	2M3-43	-4M15+13	-M	-2M3+43	4M15-13	M
		Zj-Cj	3M-10↑	8M5-12	-14M15-43	0	0	2M3-43	-4M15+13	-M	-5M3+43	-11M15-13	0

Positive maximum Zj-Cj is 3M-10 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 50.8889 and its row index is 3. So, the leaving basis variable is A3.

∴ The pivot element is 3.

Entering =x1, Departing =A3, Key Element =3

R3(new)=R3(old)÷3

R1(new)=R1(old)

R2(new)=R2(old)

Iteration-4		Cj	10	10	4	4	1	0	0	0	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	A1	A2	A3	MinRatio XBS1
x4	4	50063	0	-45	715	1	0	-13	215	0	13	-215	0	---
x5	1	332	0	65	45	0	1	0	-15	0	0	15	0	---
x1	10	4589	1	815	-1445	0	0	(29)	-445	-13	-29	445	13	458929=229→
Z=676409		Zj	10	103	-49	4	1	89	-59	-103	-89	59	103
		Zj-Cj	0	-203	-409	0	0	89↑	-59	-103	-M-89	-M+59	-M+103

Positive maximum Zj-Cj is 89 and its column index is 6. So, the entering variable is S1.

Minimum ratio is 229 and its row index is 3. So, the leaving basis variable is x1.

∴ The pivot element is 29.

Entering =S1, Departing =x1, Key Element =29
R3(new)=R3(old) ×92

R1(new)=R1(old) + 13R3(new)

R2(new)=R2(old)

Iteration-5		Cj	10	10	4	4	1	0	0	0	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	A1	A2	A3	MinRatio
x4	4	1745	32	0	0	1	0	0	0	-12	0	0	12
x5	1	332	0	65	45	0	1	0	-15	0	0	15	0
S1	0	229	92	125	-75	0	0	1	-25	-32	-1	25	32
Z=7312		Zj	6	65	45	4	1	0	-15	-2	0	15	2
		Zj-Cj	-4	-445	-165	0	0	0	-15	-2	-M	-M+15	-M+2

Since all Zj-Cj≤0

Hence, optimal solution is arrived with value of variables as :
x1=0,x2=0,x3=0,x4=1745,x5=332

Min Z=1745*4+1*332=7312