Question

Project Operations Management

Linear Programming: Simplex Method

Minimization: By converting the min objective function to max, solve the following problem using simplex method Min 84x, + 4x2 + 30x3 s.. 8x1 + 1x2 + 3x3 S 240 16x, + 1x2 + 7x3 = 480 8x, - 1x2 + 4x3 > 160 X1, X2, X3 2 0

Answer 1

I have posted both the solutions (Min. and Max). Please please rate the answer. Thank you.

1) Min.Solution:
Problem is

Min Z = 84 x1 + 4 x2 + 30 x3

subject to

8 x1 + x2 + 3 x3 ≤ 240 16 x1 + x2 + 7 x3 ≤ 480 8 x1 + x2 + 4 x3 ≤ 160

and x1,x2,x3≥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 add slack variable S1

2. As the constraint-2 is of type '≤' we should add slack variable S2

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables

Min Z = 84 x1 + 4 x2 + 30 x3 + 0 S1 + 0 S2 + 0 S3

subject to

8 x1 + x2 + 3 x3 + S1 = 240 16 x1 + x2 + 7 x3 + S2 = 480 8 x1 + x2 + 4 x3 + S3 = 160

and x1,x2,x3,S1,S2,S3≥0

Iteration-1		Cj	84	4	30	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio
S1	0	240	8	1	3	1	0	0
S2	0	480	16	1	7	0	1	0
S3	0	160	8	1	4	0	0	1
Z=0		Zj	0	0	0	0	0	0
		Zj-Cj	-84	-4	-30	0	0	0

Since all Zj-Cj≤0

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

Min Z=0

2) Maximized Solution:
Problem is

Max Z = 84 x1 + 4 x2 + 30 x3

subject to

8 x1 + x2 + 3 x3 ≤ 240 16 x1 + x2 + 7 x3 ≤ 480 8 x1 + x2 + 4 x3 ≤ 160

and x1,x2,x3≥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 add slack variable S1

2. As the constraint-2 is of type '≤' we should add slack variable S2

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables

Max Z = 84 x1 + 4 x2 + 30 x3 + 0 S1 + 0 S2 + 0 S3

subject to

8 x1 + x2 + 3 x3 + S1 = 240 16 x1 + x2 + 7 x3 + S2 = 480 8 x1 + x2 + 4 x3 + S3 = 160

and x1,x2,x3,S1,S2,S3≥0

Iteration-1		Cj	84	4	30	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio XBx1
S1	0	240	8	1	3	1	0	0	2408=30
S2	0	480	16	1	7	0	1	0	48016=30
S3	0	160	(8)	1	4	0	0	1	1608=20→
Z=0		Zj	0	0	0	0	0	0
		Zj-Cj	-84↑	-4	-30	0	0	0

Negative minimum Zj-Cj is -84 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 20 and its row index is 3. So, the leaving basis variable is S3.

∴ The pivot element is 8.

Entering =x1, Departing =S3, Key Element =8

R3(new)=R3(old)÷8

R3(old) =	160	8	1	4	0	0	1
R3(new)=R3(old)÷8	20	1	0.125	0.5	0	0	0.125

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

R1(old) =	240	8	1	3	1	0	0
R3(new) =	20	1	0.125	0.5	0	0	0.125
8×R3(new) =	160	8	1	4	0	0	1
R1(new)=R1(old) - 8R3(new)	80	0	0	-1	1	0	-1

R2(new)=R2(old) - 16R3(new)

R2(old) =	480	16	1	7	0	1	0
R3(new) =	20	1	0.125	0.5	0	0	0.125
16×R3(new) =	320	16	2	8	0	0	2
R2(new)=R2(old) - 16R3(new)	160	0	-1	-1	0	1	-2

Iteration-2		Cj	84	4	30	0	0	0
B	CB	XB	x1	x2	x3	S1	S2	S3	MinRatio
S1	0	80	0	0	-1	1	0	-1
S2	0	160	0	-1	-1	0	1	-2
x1	84	20	1	0.125	0.5	0	0	0.125
Z=1680		Zj	84	10.5	42	0	0	10.5
		Zj-Cj	0	6.5	12	0	0	10.5

Since all Zj-Cj≥0

Hence, optimal solution is arrived with value of variables as :
x1=20,x2=0,x3=0

Max Z=1680