EBook Problem 8-21 (Algorithmic) Round Tree Manor is a hotel that provides two types of rooms...

Solution

a)

	Super Saver	Deluxe	Business
Type 1	100	5	0
Type 2	0	65	55

b)

Super Saver=100

Delux=70

Business=55

Explanation

a)

MAX Z = 32x1 + 17x2 + 43x3 + 35x4 + 39x5
subject to
x1 + x2 <= 120
x3 + x4 <= 70
x5 <= 55
x1 + x3 <= 105
x2 + x4 + x5 <= 120
and x1,x2,x3,x4,x5 >= 0

Using simplex method,

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate:

MAX Z = 32x1 + 17x2 + 43x3 + 35x4 + 39x5 + 0S1 + 0S2 + 0S3 + 0S4 + 0S5
subject to
x1 + x2 + S1 <= 120
x3 + x4 + S2<= 70
x5 + S3<= 55
x1 + x3 + S4<= 105
x2 + x4 + x5 + S5<= 120
and x1,x2,x3,x4,x5,S1,S2,S3,S4,S5 >= 0

Iteration-1		Cj	32	17	43	35	39	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	S4	S5	MinRatio XBx3
S1	0	120	1	1	0	0	0	1	0	0	0	0	---
S2	0	70	0	0	(1)	1	0	0	1	0	0	0	701=70→
S3	0	55	0	0	0	0	1	0	0	1	0	0	---
S4	0	105	1	0	1	0	0	0	0	0	1	0	1051=105
S5	0	120	0	1	0	1	1	0	0	0	0	1	---
Z=0		Zj	0	0	0	0	0	0	0	0	0	0
		Cj-Zj	32	17	43↑	35	39	0	0	0	0	0

Positive maximum Cj-Zj is 43 and its column index is 3. So, the entering variable is x3.

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

∴ The pivot element is 1.

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

R2(new)=R2(old)

R1(new)=R1(old)

R3(new)=R3(old)

R4(new)=R4(old) - R2(new)

R5(new)=R5(old)

Iteration-2		Cj	32	17	43	35	39	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	S4	S5	MinRatio XBx5
S1	0	120	1	1	0	0	0	1	0	0	0	0	---
x3	43	70	0	0	1	1	0	0	1	0	0	0	---
S3	0	55	0	0	0	0	(1)	0	0	1	0	0	55/1=55
S4	0	35	1	0	0	-1	0	0	-1	0	1	0	---
S5	0	120	0	1	0	1	1	0	0	0	0	1	120/1=120
Z=3010		Zj	0	0	43	43	0	0	43	0	0	0
		Cj-Zj	32	17	0	-8	39↑	0	-43	0	0	0

Positive maximum Cj-Zj is 39 and its column index is 5. So, the entering variable is x5.

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

∴ The pivot element is 1.

Entering =x5, Departing =S3, Key Element =1

R3(new)=R3(old)

R1(new)=R1(old)

R2(new)=R2(old)

R4(new)=R4(old)

R5(new)=R5(old) - R3(new)

Iteration-3		Cj	32	17	43	35	39	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	S4	S5	MinRatio XBx1
S1	0	120	1	1	0	0	0	1	0	0	0	0	120/1=120
x3	43	70	0	0	1	1	0	0	1	0	0	0	---
x5	39	55	0	0	0	0	1	0	0	1	0	0	---
S4	0	35	(1)	0	0	-1	0	0	-1	0	1	0	35/1=35
S5	0	65	0	1	0	1	0	0	0	-1	0	1	---
Z=5155		Zj	0	0	43	43	39	0	43	39	0	0
		Cj-Zj	32↑	17	0	-8	0	0	-43	-39	0	0

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

Minimum ratio is 35 and its row index is 4. So, the leaving basis variable is S4.

∴ The pivot element is 1.

Entering =x1, Departing =S4, Key Element =1

R4(new)=R4(old)

R1(new)=R1(old) - R4(new)

R2(new)=R2(old)

R3(new)=R3(old)

R5(new)=R5(old)

Iteration-4		Cj	32	17	43	35	39	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	S4	S5	MinRatio XBx4
S1	0	85	0	1	0	1	0	1	1	0	-1	0	85/1=85
x3	43	70	0	0	1	1	0	0	1	0	0	0	70/1=70
x5	39	55	0	0	0	0	1	0	0	1	0	0	---
x1	32	35	1	0	0	-1	0	0	-1	0	1	0	---
S5	0	65	0	1	0	(1)	0	0	0	-1	0	1	65/1=65
Z=6275		Zj	32	0	43	11	39	0	11	39	32	0
		Cj-Zj	0	17	0	24↑	0	0	-11	-39	-32	0

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

Minimum ratio is 65 and its row index is 5. So, the leaving basis variable is S5.

∴ The pivot element is 1.

Entering =x4, Departing =S5, Key Element =1

R5(new)=R5(old)

R1(new)=R1(old) - R5(new)

R2(new)=R2(old) - R5(new)

R3(new)=R3(old)

R4(new)=R4(old) + R5(new)

Iteration-5		Cj	32	17	43	35	39	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	S1	S2	S3	S4	S5	MinRatio
S1	0	20	0	0	0	0	0	1	1	1	-1	-1
x3	43	5	0	-1	1	0	0	0	1	1	0	-1
x5	39	55	0	0	0	0	1	0	0	1	0	0
x1	32	100	1	1	0	0	0	0	-1	-1	1	1
x4	35	65	0	1	0	1	0	0	0	-1	0	1
Z=7835		Zj	32	24	43	35	39	0	11	15	32	24
		Cj-Zj	0	-7	0	0	0	0	-11	-15	-32	-24

Since all Cj-Zj≤0

Hence, integer optimal solution is arrived with value of variables as :
x1=100,x2=0,x3=5,x4=65,x5=55

Max Z=7835

b)

Super Saver=100

Delux=70 (65+5)

Business=55