Simple recourse

Simple recourse problems feature a very special form of the recourse matrix. Deviations from a target value are penalized by a linear penalty. We illustrate the use of this feature with one of the first stochastic linear programs ever formulated, an airline fleet allocation problem due to Ferguson and Dantzig [1]. In this problem a fleet of airplanes must be assigned to different routes so as to minimize the operating costs. The demands along the routes are stochastic, and penalties are incurred for lost sales due to insufficient capacity.

The algebraic formulation of this problem is as follows:

where I is the set of aircraft to be used,

R is the set of routes to be serviced,

R(i) is the set of routes within R that can be serviced by aircraft of type I,

b_i is the number of aircraft available of type i,

c_ir is the cost of operating an aircraft of type i along route r,

t_ir is the passenger capacity of aircraft i on route r,

h_rs is the passenger demand on route r under scenario s,

q_r is the revenue lost per passenger turned away on route r,

x_ir is the number of aircraft of type i assigned to route r,

y_rs is the number of passengers turned away on route r under scenario s,

z_rs is the number of empty seats on route r under scenario s,

p_s is the probability of scenario s.

Time file

Core file

Stoch file

Reference

1. A.R. Ferguson and G.B. Dantzig, “The allocation of aircraft to routes—an example of linear programming under uncertain demand”, Management Science 3 (1956) 45–73.