$2.$ The Reserve Crew Allocation Program is a linear program used by American Airlines to allocate and utilize reserve crews at a minimum cost. The program sclects a set of erews to meet the daily demand for reserve crews. The number of reserves required on any particular day is forecast by using experienee to establish probabilities. The simplex tableau is presented below.

$[$ In the tableas, a$\_1,=\{[1$ if erew z $,$ is on duey on day; $0$ otherwise $].$; b$\_4=$ minimum number of reserve crews; required an dayi; $]$

The constraints are given by

a$\_11$ x$\_1+$a$\_12$ x$\_2+$a$\_13$ x$\_3+$a$\_14$ x$\_4++$a$\_1$ n x$\_$n$>=$ b$\_1$

For example, the first row of the tableau corresponds to the constraint

x$\_1+$x$\_4+>=8,$

while the second row corresponds to

x$\_1+$x$\_2+>=7$

The cost function to be minimized is

w$=$c$\_1$ x$\_1+$c$\_2$ x$\_2+$c$\_3$ x$\_3++$c$\_$n x$\_$n

The linear programming example of reserve crew allocation discussed above is American Airline's own program. They also use a standard linear program to schedule their flight crews on aircraft and for training assignments. This is a considerably larger and more complicated program. Exercises $1.$ Suppose there are $4$ crews available. Crew $1$ is on duty days $1$ and $2.$ Crew $2$ is on duty days $1$ and $3.$ Cret is on duty days $2$ and $3.$ Crew $4$ is on duty days $1,2,$ and $3.$ A minimum of $2$ crews is required on days $1$ :$1.$ Suppose there are $4$ crews available. Crew $1$ is on duty days $1$ and $2.$ Crew $2$ is on duty days $1$ and $3.$ Crew $3$ is on duty days $2$ and $3.$ Crew $4$ is on duty days $1,2,$ and $3.$ A minimum of $2$ crews is required on days $1$ and$2,$ and $3$ crews on day $3.$ Use the simplex method to determine which crews should be selected and what the cost is$.2.$ For this application, x$\_$i$=1$ if i is used and x$\_$i$=0$ if crew i is not used. What happens if the simplex method returns a value of $2$ or $1/2$ for one of the variables? T Example supplied by D$.$ R$.$ Bomemann, Manager, Operations Research, American Airlines.