Question

MAX Z = 2x1 + 8x2 + 4x3 + 9x4
subject to
2x1 + 3x2 + 2x4 <= 8
2x2 + 5x3 + x4 <= 12
3x1 + x2 + 4x3 + 2x4 <= 15
and x1,x2,x3,x4 >= 0

apply the Primal Simplex Method to recover optimality.

Answer 1

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 = 2 x1 + 8 x2 + 4 x3 + 9 x4 + 0 S1 + 0 S2 + 0 S3

subject to

2 x1 + 3 x2 + 2 x4 + S1 = 8 2 x2 + 5 x3 + x4 + S2 = 12 3 x1 + x2 + 4 x3 + 2 x4 + S3 = 15

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

Iteration-1		Cj	2	8	4	9	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x4
S1	0	8	2	3	0	(2)	1	0	0	8/2=4→
S2	0	12	0	2	5	1	0	1	0	12/1=12
S3	0	15	3	1	4	2	0	0	1	15/2=7.5
Z=0		Zj	0	0	0	0	0	0	0
		Zj-Cj	-2	-8	-4	-9↑	0	0	0

Negative minimum Zj-Cj is -9 and its column index is 4. So, the entering variable is x4.

Minimum ratio is 4 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 2.

Entering =x4, Departing =S1, Key Element =2

R1(new)=R1(old)÷2

R1(old) =	8	2	3	0	2	1	0	0
R1(new)=R1(old)÷2	4	1	1.5	0	1	0.5	0	0

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

R2(old) =	12	0	2	5	1	0	1	0
R1(new) =	4	1	1.5	0	1	0.5	0	0
R2(new)=R2(old) - R1(new)	8	-1	0.5	5	0	-0.5	1	0

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

R3(old) =	15	3	1	4	2	0	0	1
R1(new) =	4	1	1.5	0	1	0.5	0	0
2×R1(new) =	8	2	3	0	2	1	0	0
R3(new)=R3(old) - 2R1(new)	7	1	-2	4	0	-1	0	1

Iteration-2		Cj	2	8	4	9	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio XB/x3
x4	9	4	1	1.5	0	1	0.5	0	0	---
S2	0	8	-1	0.5	(5)	0	-0.5	1	0	8/5=1.6→
S3	0	7	1	-2	4	0	-1	0	1	7/4=1.75
Z=36		Zj	9	13.5	0	9	4.5	0	0
		Zj-Cj	7	5.5	-4↑	0	4.5	0	0

Negative minimum Zj-Cj is -4 and its column index is 3. So, the entering variable is x3.

Minimum ratio is 1.6 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 5.

Entering =x3, Departing =S2, Key Element =5

R2(new)=R2(old)÷5

R2(old) =	8	-1	0.5	5	0	-0.5	1	0
R2(new)=R2(old)÷5	1.6	-0.2	0.1	1	0	-0.1	0.2	0

R1(new)=R1(old)

R1(old) =	4	1	1.5	0	1	0.5	0	0
R1(new)=R1(old)	4	1	1.5	0	1	0.5	0	0

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

R3(old) =	7	1	-2	4	0	-1	0	1
R2(new) =	1.6	-0.2	0.1	1	0	-0.1	0.2	0
4×R2(new) =	6.4	-0.8	0.4	4	0	-0.4	0.8	0
R3(new)=R3(old) - 4R2(new)	0.6	1.8	-2.4	0	0	-0.6	-0.8	1

Iteration-3		Cj	2	8	4	9	0	0	0
B	CB	XB	x1	x2	x3	x4	S1	S2	S3	MinRatio
x4	9	4	1	1.5	0	1	0.5	0	0
x3	4	1.6	-0.2	0.1	1	0	-0.1	0.2	0
S3	0	0.6	1.8	-2.4	0	0	-0.6	-0.8	1
Z=42.4		Zj	8.2	13.9	4	9	4.1	0.8	0
		Zj-Cj	6.2	5.9	0	0	4.1	0.8	0

Since all Zj-Cj≥0

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

Max Z=42.4

****Please please please LIKE THIS ANSWER, so that I can get a small benefit, Please****