Question

The international man of mystery knew the finest haberdashers the world over and constantly sought to expand his dazzling array of fine suits, ties, and cufflinks. Closet space was at a premium however, so purchases were carefully weighed. Each suit provides 23 units of dazzlement, each tie 14, and a set of cufflinks is worth an easy 8. A suit takes up 0.5 cubic feet of closet space and $900 of budget. A tie costs $135 and cufflinks cost $100 per set. Cufflinks are tiny â even in the original box, they take up only .01 cubic feet while ties occupy a lusty .25 cubic feet. He has budgeted $12,000 for clothes on this trip and has 20 cubic feet of closet space left to fill. Formulate and solve a model for this situation.

Answer 1

Let us assume that the number of Suits = X1

Number of ties = X2

Number of cufflinks = X3

The objective function is the maximization of dazzlement:

Max Z = 23X1 + 14X2+ 8X3

The constraint for Closet space:

0.5X1 + 0.25X2 + 0.1 X3 <= 20

The constraint for budget:

900X1 + 135X2 + 100X3 <= 12000

So, the Linear programming model is as follows:

Max Z = 23X1 + 14X2+ 8X3

subject to

0.5X1 + 0.25X2 + 0.1 X3 <= 20

900X1 + 135X2 + 100X3 <= 12000

X1, X2, X3 >= 0

The problem has to be converted to canonical form by adding Slack, Surplus and Artificial variables as required

1. Constraint-1 is of type <=, Slack variable S1 should be added

2. Constraint-2 is of type <=, Slack variable S2 should be added

Adding Slack variables:

Max Z = 23X1 + 14X2+ 8X3 + 0S1 + 0S2

subject to

0.5X1 + 0.25X2 + 0.1 X3 + S1= 20

900X1 + 135X2 + 100X3 + S2= 12000

X1, X2, X3, S1,S2 >= 0

Iteration 1		Cj	23	14	8	0	0
B	CB	XB	X1	X2	X3	S1	S2	Minimum Ratio: XB / X1
S1	0	20	0.5	0.25	0.1	1	0	20 / 0.5=40
S2	0	12000	(900)	135	100	0	1	12000 / 900=13.3333
Z=0		Zj	0	0	0	0	0
		Zj-Cj	-23	-14	-8	0	0

The negative minimum Zj-Cj is -23 and the column index is 1. So, X1 shall be the entering variable.

The minimum ratio is 13.3333 and the row index is 2. So, S2 shall be the leaving basis variable.

The pivot element shall be 900.

R2(new)=R2(old) / 900

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

Iteration 2		Cj	23	14	8	0	0
B	CB	XB	X1	X2	X3	S1	S2	Minimum Ratio: XB / X2
S1	0	13.3333	0	0.175	0.0444	1	-0.0006	13.3333 / 0.175=76.1905
X1	23	13.3333	1	0.15	0.1111	0	0.0011	13.3333 / 0.15=88.8889
Z=306.6667		Zj	23	3.45	2.5556	0	0.0256
		Zj-Cj	0	-10.55	-5.4444	0	0.0256

The negative minimum Zj-Cj is -10.55 and the column index is 2. So, X2 shall be the entering variable.

The minimum ratio is 76.1905 and the row index is 1. So, S1 shall be the leaving basis variable.

The pivot element shall be 0.175.



R1(new)=R1(old) / 0.175

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

Iteration 3		Cj	23	14	8	0	0
B	CB	XB	X1	X2	X3	S1	S2	Minimum Ratio: XB / X3
X2	14	76.1905	0	1	0.254	5.7143	-0.0032	76.1905 / 0.254=300
X1	23	1.9048	1	0	0.073	-0.8571	0.0016	1.9048 / 0.073=26.087
Z=1110.4762		Zj	23	14	5.2349	60.2857	-0.0079
		Zj-Cj	0	0	-2.7651	60.2857	-0.0079

The negative minimum Zj-Cj is -2.7651 and the column index is 3. So, X3 shall be the entering variable.

The minimum ratio is 26.087 and the row index is 2. So, X1 shall be the leaving basis variable.

The pivot element shall be 0.073.



R2(new)=R2(old) / 0.073

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

Iteration 4		Cj	23	14	8	0	0
B	CB	XB	X1	X2	X3	S1	S2	Min Ratio
X2	14	69.5652	-3.4783	1	0	8.6957	-0.0087
X3	8	26.087	13.6957	0	1	-11.7391	0.0217
Z=1182.6087		Zj	60.8696	14	8	27.8261	0.0522
		Zj-Cj	37.8696	0	0	27.8261	0.0522

Since all value of Zj-Cj are >= 0

Therefore, the optimal solution arrives with the following values of variables :

X1 = 0

X2 = 69.5652 = 70 (Rounding off)

X3 = 26.087 = 26 (Rounding off)

Max Z=1182.6087

So,

The number of suits = 0

The number of ties = 70

The number of cufflinks = 26