## Question

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

## Answers

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 >= 0Using 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 Cj32 17 43 35 39 0 0 0 0 0 BCBXBx1x2x3x4x5S1S2S3S4S5MinRatio

XBx3S10 120 1 1 0 0 0 1 0 0 0 0 --- S20 70 0 0 (1)1 0 0 1 0 0 0 701=70 →S30 55 0 0 0 0 1 0 0 1 0 0 --- S40 105 1 0 1 0 0 0 0 0 1 0 1051=105 S50 120 0 1 0 1 1 0 0 0 0 1 --- Z=0Zj0000000000Cj-Zj32 17 43↑ 35 39 0 0 0 0 0

Positive maximumCj-Zjis 43 and its column index is 3. So, the entering variable isx3.

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

∴ 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 Cj32 17 43 35 39 0 0 0 0 0 BCBXBx1x2x3x4x5S1S2S3S4S5MinRatio

XBx5S10 120 1 1 0 0 0 1 0 0 0 0 --- x343 70 0 0 1 1 0 0 1 0 0 0 --- S30 55 0 0 0 0 (1)0 0 1 0 0 55/1=55 S40 35 1 0 0 -1 0 0 -1 0 1 0 --- S50 120 0 1 0 1 1 0 0 0 0 1 120/1=120 Z=3010Zj0043430043000Cj-Zj32 17 0 -8 39↑ 0 -43 0 0 0

Positive maximumCj-Zjis 39 and its column index is 5. So, the entering variable isx5.

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

∴ 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 Cj32 17 43 35 39 0 0 0 0 0 BCBXBx1x2x3x4x5S1S2S3S4S5MinRatio

XBx1S10 120 1 1 0 0 0 1 0 0 0 0 120/1=120 x343 70 0 0 1 1 0 0 1 0 0 0 --- x539 55 0 0 0 0 1 0 0 1 0 0 --- S40 35 (1)0 0 -1 0 0 -1 0 1 0 35/1=35 S50 65 0 1 0 1 0 0 0 -1 0 1 --- Z=5155Zj004343390433900Cj-Zj32↑ 17 0 -8 0 0 -43 -39 0 0

Positive maximumCj-Zjis 32 and its column index is 1. So, the entering variable isx1.

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

∴ 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 Cj32 17 43 35 39 0 0 0 0 0 BCBXBx1x2x3x4x5S1S2S3S4S5MinRatio

XBx4S10 85 0 1 0 1 0 1 1 0 -1 0 85/1=85 x343 70 0 0 1 1 0 0 1 0 0 0 70/1=70 x539 55 0 0 0 0 1 0 0 1 0 0 --- x132 35 1 0 0 -1 0 0 -1 0 1 0 --- S50 65 0 1 0 (1)0 0 0 -1 0 1 65/1=65 Z=6275Zj32043113901139320Cj-Zj0 17 0 24↑ 0 0 -11 -39 -32 0

Positive maximumCj-Zjis 24 and its column index is 4. So, the entering variable isx4.

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

∴ 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 Cj32 17 43 35 39 0 0 0 0 0 BCBXBx1x2x3x4x5S1S2S3S4S5MinRatioS10 20 0 0 0 0 0 1 1 1 -1 -1 x343 5 0 -1 1 0 0 0 1 1 0 -1 x539 55 0 0 0 0 1 0 0 1 0 0 x132 100 1 1 0 0 0 0 -1 -1 1 1 x435 65 0 1 0 1 0 0 0 -1 0 1 Z=7835Zj3224433539011153224Cj-Zj0 -7 0 0 0 0 -11 -15 -32 -24

Since allCj-Zj≤0

Hence, integer optimal solution is arrived with value of variables as :

x1=100,x2=0,x3=5,x4=65,x5=55

MaxZ=7835

b)Super Saver=100

Delux=70 (65+5)

Business=55