Page 54 -

34 CHAPTER 2 AN INTRODUCTION TO LINEAR PROGRAMMING

We saw in Chapter 1 that management science makes extensive use of mathemat-
ical models. One of the first types of model to be developed – and since used
extensively – is that of linear programming. In fact, linear programming (LP) is
sufficiently important to management science that we shall be spending the next
five chapters looking at LP and its developments. Linear programming is a manage-
ment science technique used in many countries and by many different types of
organization – manufacturing companies, service organizations, government agencies,
not-for-profit organizations. Delta Airlines facing a decision problem in deciding
George B. Dantzig which type of aircraft in its fleet should be allocated to different flight routes; health
(1914–2005) is the care planners in Rome planning the home care service provided to patients with
American mathematician
generally credited with AIDS; the Arabian Light Metals Company in Kuwait trying to decide on the mixture
suggesting linear of aluminium-based products to manufacture; London Underground trying to decide
programming in 1947, on crew rostering for its services. Managers are often in a situation where they are
although it was looking to make the best decision possible but where the options they face limit – or
independently suggested
some years earlier by constraint – what they are actually able to do. In such situations, LP can often prove a
Soviet economist and very useful model to apply. To illustrate some of the properties that all LP problems
mathematician Leonid have in common, let us consider the following typical applications:
Kantorovich.
1 A manufacturer of mobile phones is looking at the production schedule for the
next few months and trying to decide how many of each phone model to
manufacture in order to meet demand forecasts for different sales regions.
Clearly, the production schedule will need to ensure that enough phones are
produced to meet projected demand in each sales region but at the same time
minimize production costs.
2 A financial analyst must select an investment portfolio for a high-value client
from a variety of investment alternatives. The analyst would like to establish
the portfolio that maximizes the return on investment. At the same time,
though, the analyst also has to satisfy certain client requirements in terms of
the mix of investments and the risk associated with each.
3 A marketing manager wants to determine how best to allocate a fixed advertising
budget among alternative advertising media such as Internet, television,
newspaper and magazine. The manager would like to determine the media mix
that maximizes advertising effectiveness but within the budget constraint faced.
4 A regional health centre collects and stores blood donations that are used in
the region’s hospitals. The transportation manger has to ensure that each
hospital receives the supply of blood it needs to treat patients and at the same
time minimize the time taken to transport blood supplies from the centre to
the various hospitals.
In this chapter we shall introduce the basic concepts of linear programming and see
how to formulate and solve linear programming problems. In subsequent chapters
we shall expand on the basic model.
Linear programming was These examples are only a few of the situations in which linear programming has
initially referred to as been used successfully, but they illustrate the diversity of linear programming
‘programming in a linear
structure’. In 1948 applications. A close scrutiny reveals one basic property they all have in common.
Tjalling Koopmans In each example, we were concerned with maximizing or minimizing some quantity.
suggested to George In example 1, the manufacturer wanted to minimize costs; in example 2, the financial
Dantzig that the name analyst wanted to maximize return on investment; in example 3, the marketing
was much too long;
Koopmans suggested manager wanted to maximize advertising effectiveness; and in example 4, the com-
shortening it to linear pany wanted to minimize total transportation time. In all linear programming prob-
programming. George lems, the maximization or minimization of some quantity is the objective.
Dantzig agreed and the All linear programming problems also have a second property: restrictions or con-
field we now know as
linear programming was straints that limit the degree to which the objective can be pursued. In example 1, the
named. manufacturer is restricted by constraints requiring product demand to be satisfied and

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.