(a) Show that this is a two-stage stochastic program with first-stage integer decision 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 integer. Assume that Northam revises its seating policy every year. Is a multistage program needed?

(b) Assume that the data in Exercise 1 correspond to the demand for seat reservations. Assume 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. Model this situation as a three-stage program, with first-stage decisions as before, second-stage decisions corresponding to the number of accepted reservations, and third-stage decisions corresponding to effective seat occupation. Show that the third stage is a simple recourse program with a reward for each occupied seat and a penalty for each denied reservation.

(c) 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. 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 the corresponding problem as a recourse program. Find the optimal acceptance policy with the data of Exercise 1 in Section 1.6 and no-shows as in (b) of the current exercise. To simplify, assume that passengers with a denied reservation are not seated in a higher class even if a seat is available there.