Consider an airline companys seat allocation problem. Under this system, the availability of seats belonging to a certain class could be dynamically controlled. For example, a certain low-price class (e.g. non refundable tickets) could be closed (i.e. made unavailable) at a certain date because the same seat had a higher probability of being reserved under a higher-price class (e.g. refundable tickets).

The system is modelled under following assumptions:

1. Over time classes are booked in a certain order

2. Low-valuation before high valuation demand pattern

3. Independent arrivals for different booking classes

4. Absence of no-shows

5. No group reservations

Let the classes be ranked from low valuation to high valuation v1 v2 vN and denote their uncertain demands Di, where i denotes the demand for class i. Consider Di has a discrete probability distribution (between k=1,2,,Mi with probability values Pki probability of observing k demand in class i-). The decision of interest is the capacity xi that should be allocated to class i.

Formulate a recursive dynamic programming model to allocate seats to the classes to maximize expected revenue under following steps:

1. Define the states and stages of the model.

2. Formulate the expected revenue function for class N (final class)

3. Formulate the recursive expected revenue function for any class i.