Question

Use the simplex method to solve the linear programming problem.

Maximize	P = 4x + 3y
subject to	3x + 6y ≤ 33 x + y ≤ 7 3x + y ≤ 19 x ≥ 0, y ≥ 0

The maxium P= ____ at (x,y) ____

Answer 1

Find solution using Simplex method
MAX Z = 4x + 3y
subject to
3x + 6y <= 33
x + y <= 7
3x + y <= 19
and x,y >= 0

Solution:
Problem is

Max Z = 4 x + 3 y

subject to

3 x + 6 y ≤ 33 x + y ≤ 7 3 x + y ≤ 19

and x,y≥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 = 4 x + 3 y + 0 S1 + 0 S2 + 0 S3

subject to

3 x + 6 y + S1 = 33 x + y + S2 = 7 3 x + y + S3 = 19

and x,y,S1,S2,S3≥0

Iteration-1		Cj	4	3	0	0	0
B	CB	XB	x Entering variable	y	S1	S2	S3	MinRatio XBx
S1	0	33	3	6	1	0	0	333=11
S2	0	7	1	1	0	1	0	71=7
S3 Leaving variable	0	19	(3) (pivot element)	1	0	0	1	193=6.33→
Z=0 0= Zj=∑CBXB		Zj Zj=∑CBxj	0 0=0×3+0×1+0×3 Zj=∑CBx	0 0=0×6+0×1+0×1 Zj=∑CBy	0 0=0×1+0×0+0×0 Zj=∑CBS1	0 0=0×0+0×1+0×0 Zj=∑CBS2	0 0=0×0+0×0+0×1 Zj=∑CBS3
		Cj-Zj	4 4=4-0↑	3 3=3-0	0 0=0-0	0 0=0-0	0 0=0-0

Positive maximum Cj-Zj is 4 and its column index is 1. So, the entering variable is x.

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

∴ The pivot element is 3.

Entering =x, Departing =S3, Key Element =3

R3(new)=R3(old)÷3

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

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

Iteration-2		Cj	4	3	0	0	0
B	CB	XB	x	y Entering variable	S1	S2	S3	MinRatio XBy
S1	0	14 14=33-3×193 R1(new)=R1(old)-3R3(new)	0 0=3-3×1 R1(new)=R1(old)-3R3(new)	5 5=6-3×13 R1(new)=R1(old)-3R3(new)	1 1=1-3×0 R1(new)=R1(old)-3R3(new)	0 0=0-3×0 R1(new)=R1(old)-3R3(new)	-1 -1=0-3×13 R1(new)=R1(old)-3R3(new)	145=2.8
S2 Leaving variable	0	23 23=7-193 R2(new)=R2(old)-R3(new)	0 0=1-1 R2(new)=R2(old)-R3(new)	(23) 23=1-13 (pivot element) R2(new)=R2(old)-R3(new)	0 0=0-0 R2(new)=R2(old)-R3(new)	1 1=1-0 R2(new)=R2(old)-R3(new)	-13 -13=0-13 R2(new)=R2(old)-R3(new)	2323=1→
x	4	193 193=19÷3 R3(new)=R3(old)÷3	1 1=3÷3 R3(new)=R3(old)÷3	13 13=1÷3 R3(new)=R3(old)÷3	0 0=0÷3 R3(new)=R3(old)÷3	0 0=0÷3 R3(new)=R3(old)÷3	13 13=1÷3 R3(new)=R3(old)÷3	19313=19
Z=763 763=4×193 Zj=∑CBXB		Zj Zj=∑CBxj	4 4=0×0+0×0+4×1 Zj=∑CBx	43 43=0×5+0×23+4×13 Zj=∑CBy	0 0=0×1+0×0+4×0 Zj=∑CBS1	0 0=0×0+0×1+4×0 Zj=∑CBS2	43 43=0×(-1)+0×(-13)+4×13 Zj=∑CBS3
		Cj-Zj	0 0=4-4	53 53=3-43↑	0 0=0-0	0 0=0-0	-43 -43=0-43

Positive maximum Cj-Zj is 53 and its column index is 2. So, the entering variable is y.

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

∴ The pivot element is 23.

Entering =y, Departing =S2, Key Element =23

R2(new)=R2(old)×32

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

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

Iteration-3		Cj	4	3	0	0	0
B	CB	XB	x	y	S1	S2	S3	MinRatio
S1	0	9 9=14-5×1 R1(new)=R1(old)-5R2(new)	0 0=0-5×0 R1(new)=R1(old)-5R2(new)	0 0=5-5×1 R1(new)=R1(old)-5R2(new)	1 1=1-5×0 R1(new)=R1(old)-5R2(new)	-152 -152=0-5×32 R1(new)=R1(old)-5R2(new)	32 32=(-1)-5×(-12) R1(new)=R1(old)-5R2(new)
y	3	1 1=23×32 R2(new)=R2(old)×32	0 0=0×32 R2(new)=R2(old)×32	1 1=23×32 R2(new)=R2(old)×32	0 0=0×32 R2(new)=R2(old)×32	32 32=1×32 R2(new)=R2(old)×32	-12 -12=(-13)×32 R2(new)=R2(old)×32
x	4	6 6=193-13×1 R3(new)=R3(old)-13R2(new)	1 1=1-13×0 R3(new)=R3(old)-13R2(new)	0 0=13-13×1 R3(new)=R3(old)-13R2(new)	0 0=0-13×0 R3(new)=R3(old)-13R2(new)	-12 -12=0-13×32 R3(new)=R3(old)-13R2(new)	12 12=13-13×(-12) R3(new)=R3(old)-13R2(new)
Z=27 27=3×1+4×6 Zj=∑CBXB		Zj Zj=∑CBxj	4 4=0×0+3×0+4×1 Zj=∑CBx	3 3=0×0+3×1+4×0 Zj=∑CBy	0 0=0×1+3×0+4×0 Zj=∑CBS1	52 52=0×(-152)+3×32+4×(-12) Zj=∑CBS2	12 12=0×32+3×(-12)+4×12 Zj=∑CBS3
		Cj-Zj	0 0=4-4	0 0=3-3	0 0=0-0	-52 -52=0-52	-12 -12=0-12

Since all Cj-Zj≤0

Hence, optimal solution is arrived with value of variables as :
x=6,y=1

Max Z = 27