Question

eBook Problem 8-21 (Algorithmic) Round Tree Manor is a hotel that provides two types of rooms with three rental classes: Super Saver, Deluxe, and Business. The profit per night for each type of room and rental class is as follows: Rental Class Super Saver $32 $17 Deluxe $43 $35 Business Type I Room Type II $39 Type I rooms do not have wireless Internet access and are not available for the Business rental dass. Round Tree's management makes a forecast of the demand by rental class for each night in the future. A linear programming model developed to maximize profit is used to determine how many reservations to accept for each rental class. The demand forecast for a particular night is 120 rentals in the Super Saver class, 70 rentals in the Deluxe class, and 55 rentals in the Business dlass. Round Tree has 105 Type I rooms and 120 Type II rooms. a. Use linear programming to determine how many reservations to accept in each rental class and how the reservations should be allocated to roorm types. Variable SuperSaver rentals allocated to room type I SuperSaver rentals allocated to room type II Deluxe rentals allocated to room type I Deluxe rentals allocated to room type II Business rentals allocated to room type II Of reservations

Answer 1

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