Question

Find the complete optimal solution to this linear programming problem.
Min	5x + 6y
s.t.	3x +   y >= 15
	x + 2y >= 12
	3x + 2y >= 24
	x , y >= 0
Find the complete optimal solution to this linear programming problem.
Min	5x + 6y
s.t.	3x +   y >= 15
	x + 2y >= 12
	3x + 2y >= 24
	x , y >= 0

Answer 1

let x1=x , x2=y  

Find solution using Simplex method (BigM method)
MIN Z = 5x1 + 6x2
subject to
3x1 + x2 >= 15
x1 + 2x2 >= 12
3x1 + 2x2 >= 24
and x1,x2 >= 0

Solution:
Problem is

Min Z = 5 x1 + 6 x2

subject to

3 x1 + x2 ≥ 15 x1 + 2 x2 ≥ 12 3 x1 + 2 x2 ≥ 24

and x1,x2≥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 = 5 x1 + 6 x2 + 0 S1 + 0 S2 + 0 S3 + M A1 + M A2 + M A3

subject to

3 x1 + x2 - S1 + A1 = 15 x1 + 2 x2 - S2 + A2 = 12 3 x1 + 2 x2 - S3 + A3 = 24

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

Iteration-1		Cj	5	6	0	0	0	M	M	M
B	CB	XB	x1	x2	S1	S2	S3	A1	A2	A3	MinRatio XB/x1
A1	M	15	(3)	1	-1	0	0	1	0	0	15/3=5→
A2	M	12	1	2	0	-1	0	0	1	0	12/1=12
A3	M	24	3	2	0	0	-1	0	0	1	24/3=8
Z=51M		Zj	7M	5M	-M	-M	-M	M	M	M
		Zj-Cj	7M-5↑	5M-6	-M	-M	-M	0	0	0

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

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

∴ The pivot element is 3.

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

R1(new)=R1(old)÷3

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

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

Iteration-2		Cj	5	6	0	0	0	M	M
B	CB	XB	x1	x2	S1	S2	S3	A2	A3	MinRatio XB/x2
x1	5	5	1	0.3333	-0.3333	0	0	0	0	5/0.3333=15
A2	M	7	0	(1.6667)	0.3333	-1	0	1	0	7/1.6667=4.2→
A3	M	9	0	1	1	0	-1	0	1	9/1=9
Z=16M+25		Zj	5	2.6667M+1.6667	1.3333M-1.6667	-M	-M	M	M
		Zj-Cj	0	2.6667M-4.3333↑	1.3333M-1.6667	-M	-M	0	0

Positive maximum Zj-Cj is 2.6667M-4.3333 and its column index is 2. So, the entering variable is x2.

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

∴ The pivot element is 1.6667.

Entering =x2, Departing =A2, Key Element =1.6667

R2(new)=R2(old)÷1.6667

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

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

Iteration-3		Cj	5	6	0	0	0	M
B	CB	XB	x1	x2	S1	S2	S3	A3	MinRatio XB/S1
x1	5	3.6	1	0	-0.4	0.2	0	0	---
x2	6	4.2	0	1	0.2	-0.6	0	0	4.2/0.2=21
A3	M	4.8	0	0	(0.8)	0.6	-1	1	4.8/0.8=6→
Z=4.8M+43.2		Zj	5	6	0.8M-0.8	0.6M-2.6	-M	M
		Zj-Cj	0	0	0.8M-0.8↑	0.6M-2.6	-M	0

Positive maximum Zj-Cj is 0.8M-0.8 and its column index is 3. So, the entering variable is S1.

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

∴ The pivot element is 0.8.

Entering =S1, Departing =A3, Key Element =0.8

R3(new)=R3(old)÷0.8

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

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

Iteration-4		Cj	5	6	0	0	0
B	CB	XB	x1	x2	S1	S2	S3	MinRatio
x1	5	6	1	0	0	0.5	-0.5
x2	6	3	0	1	0	-0.75	0.25
S1	0	6	0	0	1	0.75	-1.25
Z=48		Zj	5	6	0	-2	-1
		Zj-Cj	0	0	0	-2	-1

Since all Zj-Cj≤0

Hence, optimal solution is arrived with value of variables as :
x1=6,x2=3

Min Z=48

ANSWER: x=6 ,y=3   min z=5*6+6*3=48