Question

What's the optimal solution to this linear programming problem?

Max	2X + 3Y
s.t.	4X +   9Y ≤ 72
	10X + 11Y ≤ 110
	17X +   9Y ≤ 153
	X, Y ≥ 0

Answer 1

We have,

Max	2X + 3Y
s.t.	4X +   9Y ≤ 72
	10X + 11Y ≤ 110
	17X +   9Y ≤ 153
	X, Y ≥ 0

To convert the problem to canonical form we will add adding slack variable to each constraint as all constraints are of  type '≤'
After introducing slack variables

Max	2X + 3Y+0S1 +0S2 + 0S3
s.t.	4X +   9Y + S1≤ 72
	10X + 11Y + S2 ≤ 110
	17X +   9Y +S3 ≤ 153
	X, Y ≥ 0

Iteration-1		Cj	2	3	0	0	0
B	CB	XB	X	Y	S1	S2	S3	Min Ratio XB / Y
S1	0	72	4	(9)	1	0	0	72 /9=8→
S2	0	110	10	11	0	1	0	110 /11=10
S3	0	153	17	9	0	0	1	153 /9=17
Z=0		Zj	0	0	0	0	0
		Zj-Cj	-2	-3↑	0	0	0

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

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

∴ The pivot element is 9.

Iteration-2		Cj	2	3	0	0	0
B	CB	XB	X	Y	S1	S2	S3	Min Ratio XB / X
Y	3	8	0.4444	1	0.1111	0	0	8 / 0.4444 = 18
S2	0	22	(5.1111)	0	-1.2222	1	0	22 / 5.1111 = 4.3043→
S3	0	81	13	0	-1	0	1	81 / 13 = 6.2308
Z=24		Zj	1.3333	3	0.3333	0	0
		Zj-Cj	-0.6667↑	0	0.3333	0	0

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

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

∴ The pivot element is 5.1111.

Iteration-3		Cj	2	3	0	0	0
B	CB	XB	X	Y	S1	S2	S3	Min Ratio
Y	3	6.087	0	1	0.2174	-0.087	0
X	2	4.3043	1	0	-0.2391	0.1957	0
S3	0	25.0435	0	0	2.1087	-2.5435	1
Z=26.8696		Zj	2	3	0.1739	0.1304	0
	Zj-Cj	0	0	0.1739	0.1304	0

Since all Zj-Cj≥0

Hence, the optimal solution is:
X=4.3043,

Y=6.087

Max Z=26.8696