Page 232 -

212 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

MANAGEMENT SCIENCE IN ACTION

Fleet Assignment at Delta Air Lines
elta Air Lines uses linear and integer program- The successful implementation of the Coldstart
D ming in its Coldstart project to solve its fleet model for assigning fleet types to flight legs shows
assignment problem. The problem is to match air- the size of linear programmes that can be solved
craft to flight legs and fill seats with paying passen- today. The typical size of the daily Coldstart model is
gers. Airline profitability depends on being able to about 60 000 variables and 40 000 constraints. The
assign the right size of aircraft to the right leg at the first step in solving the fleet assignment problem is
right time of day. An airline seat is a perishable to solve the model as a linear programme. The
commodity; once a flight takes off with an empty model developers report successfully solving these
seat the profit potential of that seat is gone forever. problems on a daily basis and contend that use of
Primary objectives of the fleet assignment model are the Coldstart model will save Delta Air Lines $300
to minimize operating costs and lost passenger rev- million over a three year period.
enue. Constraints are aircraft availability, balancing
Based on R. Subramanian, R.P. Scheff, Jr., J.D. Quillinan, D.S. Wiper,
arrivals and departures at airports and maintenance and R.E. Marsten, ‘Coldstart: Fleet Assignment at Delta Air Lines’,
requirements. Interfaces (January/February 1994): 104–120.

In Chapter 2 we saw how to solve simple, two variable LP problems using the
graphical method. However, we also saw in Chapter 4 that LP problems are likely
to be more complex than this, involving a large number of decision variables and
constraints. The Management Science in Action, Fleet Management at Delta Airlines,
illustrates an LP problem involving around 60 000 variables and 40 000 constraints.
Clearly a graphical solution approach will not work so a mathematical method of
finding the solution is needed. In this chapter we introduce the Simplex method
which is the most widely used LP solution method and the basis for many LP
The Simplex method was computer software programs. The Simplex method provides a set of step-by-step
developed by George
Dantzig while working for instructions, known as an algorithm, for solving an LP problem of any size. In this
the US Air Force. It was chapter we look at how the Simplex method works and in the next chapter we see
first published in 1949. the sensitivity information that the Simplex method provides.

5.1 An Algebraic Overview of the Simplex Method

We will use a typical business problem to demonstrate the Simplex method. High-
Tech Industries imports electronic components that are used to assemble two differ-
ent models of laptop computers. One model is called the Deskpro, and the other
model is called the UltraPortable. HighTech’s management is currently interested in
developing a weekly production schedule for both products.
The Deskpro generates a profit contribution of E50 per unit, and the UltraPortable
generates a profit contribution of E40 per unit. For next week’s production, a maximum
of 150 hours of assembly time can be made available. Each unit of the Deskpro requires
three hours of assembly time, and each unit of the UltraPortable requires five hours of
assembly time. In addition, HighTech currently has only 20 UltraPortable display
components in inventory; so, no more than 20 units of the UltraPortable may be
assembled. Finally, only 300 square metres of warehouse space can be made available
for new production. Assembly of each Deskpro requires eight square metres of ware-
house space; similarly, each UltraPortable requires five square metres.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.