Problem 1: Airline Seat Allocation and Yield Management (a) Two-stage SP problem: Seat allocation and passenger acceptance policy Northam Airlines is trying to decide how to partition a new plane for its Chicago- Detroit route. The plane can seat 200 economy class passengers. A section can be partitioned off for first class seats but each of these seats takes the space of 2 economy class seats. A business class section can also be included, but each of these seats takes as much space as 1.5 economy class seats. The profit on a first class ticket is, however, three times the profit of an economy ticket. A business class ticket has a profit of two times of an economy tickets profit. Once the plane is partitioned into these seating classes, it cannot be changed. Northam knows, however, that the plane will not always be full in each section. They have decided that three scenarios will occur with about the same frequency: (1) weekday morn- ing and evening traffic, (2) weekend traffic, and (3) weekday midday traffic. Under Scenario 1, they think they can sell as many as 20 first class tickets, 50 business class tickets, and 200 economy tickets. Under Scenario 2, these figures are 10, 25, and 175. Under Scenario 3, they are 5, 10, and 150. You can assume they cannot sell more tickets than seats in each of the sections (i.e., overbooking is not allowed in part (a). But we consider overbooking in parts (b)-(d) because some passengers do not appear to the flight). Show that this is a two-stage stochastic program with first-stage integer deci- sion variables. (Observe that, for a random variable with integer realizations, the second-stage variables can be assumed continuous because the optimal second- stage decisions are automatically integers).

(b) Three-stage SP problem: Seat allocation, passenger acceptance policy, and seat occupation Assume that the data in (a) correspond to the demand for seat reservations. As- sume that there is a 50% probability that all clients with a reservation effectively show up and that 10% or 20% no-shows occur with equal probability. Assume the top management estimates the reward of an occupied seat to be 4, 2, and 1 in the first class, business class, and economy class, respectively, and the penalty for a denied reservation is 1.5 times the reward. Model this situation as a three-stage program, with first-stage decisions as be- fore, second-stage decisions corresponding to the number of accepted reserva- 1tions, and third-stage decisions corresponding to effective seat occupation (Please note that the third stage is a recourse program with a reward for each occupied seat and a penalty for each denied reservation).

(c) Two-Stage SP problem: passenger acceptance policy and seat occupation (no upgrade) Consider now the situation where the number of seats has been fixed to 12, 24, and 140 for the first class, business class, and economy class, respectively. Model the corresponding problem as a recourse program. Find the optimal acceptance policy with the data of part (b). To simplify, assume that passengers with a denied reservation are not seated in a higher class even if a seat is available there. (d) Two-Stage SP problem: passenger acceptance policy and seat occupation (upgrade is possible) It is the same as part (c) except that passengers with a denied reservation are seated in a higher class if a seat is available there.