Question

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 Deluxe Business Type I $30 $35 -- Room Type II $20 $30 $40 Type I rooms do not have Internet access and are not available for the Business rental class. 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 130 rentals in the Super Saver class, 60 rentals in the Deluxe class, and 50 rentals in the Business class. Round Tree has 100 Type I rooms and 120 Type II rooms. Use linear programming to determine how many reservations to accept in each rental class and how the reservations should be allocated to room types. Summarize the model in algebraic form by defining the decision variables, the objective function and all the constraints. PLEASE DO NOT USE EXCEL TO SOLVE.

Answer 1

This is a transportation problem. First, create the transportation matrix as follows:

	Super Saver	Deluxe	Business	Total Capacity
Type-I	$30	$35	-	100
Type-II	$20	$30	$40	120
Total Demand	130	60	50

Let Xjk be the number of Type-j rooms assigned for the k-th rental class for j=1,2 and k=1,2,3

Maximize Z = 30 X11 + 35 X12 + 0 X13 + 20 X21 + 30 X22 + 40 X23

Subject to,

X11 + X12 + X13 <= 100
X21 + X22 + X23 <= 120

X11 + X21 <= 130
X12 + X22 <= 60
X13 + X23 <= 50

Xjk >= 0

Use simplex method to solve the bove LP. For this, first write the LP in standard form of Simplex and create the initial tabluae.

Maximize Z = 30 X11 + 35 X12 + 0 X13 + 20 X21 + 30 X22 + 40 X23

Subject to,

X11 + X12 + X13 + s1 = 100
X21 + X22 + X23 + s2 = 120

X11 + X21 + s3 = 130
X12 + X22 + s4 = 60
X13 + X23 + s5 = 50

Xjk >= 0

Initial Simplex Tableau
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution	Ratio
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
0	s1	1	1	1	0	0	0	1	0	0	0	0	100	-
0	s2	0	0	0	1	1	1	0	1	0	0	0	120	120
0	s3	1	0	0	1	0	0	0	0	1	0	0	130	-
0	s4	0	1	0	0	1	0	0	0	0	1	0	60	-
0	s5	0	0	1	0	0	1	0	0	0	0	1	50	50
Zj		0	0	0	0	0	0	0	0	0	0	0	0
Cj - Zj		30	35	0	20	30	40	0	0	0	0	0
First iteration
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution	Ratio
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
0	s1	1	1	1	0	0	0	1	0	0	0	0	100	100
0	s2	0	0	-1	1	1	0	0	1	0	0	-1	70	-
0	s3	1	0	0	1	0	0	0	0	1	0	0	130	-
0	s4	0	1	0	0	1	0	0	0	0	1	0	60	60
40	X23	0	0	1	0	0	1	0	0	0	0	1	50	-
Zj		0	0	40	0	0	40	0	0	0	0	40	2000
Cj - Zj		30	35	-40	20	30	0	0	0	0	0	-40
Second iteration
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution	Ratio
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
0	s1	1	0	1	0	-1	0	1	0	0	-1	0	40	40
0	s2	0	0	-1	1	1	0	0	1	0	0	-1	70	-
0	s3	1	0	0	1	0	0	0	0	1	0	0	130	130
35	X12	0	1	0	0	1	0	0	0	0	1	0	60	-
40	X23	0	0	1	0	0	1	0	0	0	0	1	50	-
Zj		0	35	40	0	35	40	0	0	0	35	40	4100
Cj - Zj		30	0	-40	20	-5	0	0	0	0	-35	-40
Third iteration
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution	Ratio
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
30	X11	1	0	1	0	-1	0	1	0	0	-1	0	40	-40
0	s2	0	0	-1	1	1	0	0	1	0	0	-1	70	70
0	s3	0	0	-1	1	1	0	-1	0	1	1	0	90	90
35	X12	0	1	0	0	1	0	0	0	0	1	0	60	60
40	X23	0	0	1	0	0	1	0	0	0	0	1	50	-
Zj		30	35	70	0	5	40	30	0	0	5	40	5300
Cj - Zj		0	0	-70	20	25	0	-30	0	0	-5	-40
Fourth iteration
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution	Ratio
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
30	X11	1	1	1	0	0	0	1	0	0	0	0	100	-
0	s2	0	-1	-1	1	0	0	0	1	0	-1	-1	10	10
0	s3	0	-1	-1	1	0	0	-1	0	1	0	0	30	30
30	X22	0	1	0	0	1	0	0	0	0	1	0	60	-
40	X23	0	0	1	0	0	1	0	0	0	0	1	50	-
Zj		30	60	70	0	30	40	30	0	0	30	40	6800
Cj - Zj		0	-25	-70	20	0	0	-30	0	0	-30	-40
Fifth iteration
CBi	Cj	30	35	0	20	30	40	0	0	0	0	0	Solution
	Basic	X11	X12	X13	X21	X22	X23	s1	s2	s3	s4	s5
30	X11	1	1	1	0	0	0	1	0	0	0	0	100
20	X21	0	-1	-1	1	0	0	0	1	0	-1	-1	10
0	s3	0	0	0	0	0	0	-1	-1	1	1	1	20
30	X22	0	1	0	0	1	0	0	0	0	1	0	60
40	X23	0	0	1	0	0	1	0	0	0	0	1	50
Zj		30	40	50	20	30	40	30	20	0	10	20	7000
Cj - Zj		0	-5	-50	0	0	0	-30	-20	0	-10	-20

Note that at fifth iteration, all Cj - Zj values are <= 0. So, this is an optimal solution. At the optimality, X11=100, X21=10, X22=60, and X23=50 and the total profit is $7,000.

Assignments	Super Saver	Deluxe	Business	Total utilized capacity
Type-I	100	0	0	100
Type-II	10	60	50	120
Total Fulfilled	110	60	50