CHAPTER SIXTEEN
LINEAR PROGRAMMING
OBJECTIVES
1. To become familiar with the types of problems that linear programming can
solve.
2. To formulate LP problems. (Linear Programs)
3. To solve LP problems using graphs. (Graphing the LP Problem)
4. To relate LP to marginal analysis through the concept of shadow prices.
(Shadow Prices)
5. To interpret the output from LP computer algorithms. (Formulation and
Computer Solution)
TEACHING SUGGESTIONS
I. Introduction and Motivation
The purpose of this chapter is not to make students into experts at solving linear
programming problems. Rather it is to teach them (1) to recognize when a
problem is amenable to solution through linear programming, (2) to be able to
formulate such problems as linear programs and (3) to be able to interpret the
output of computer algorithms that solve linear programs. Of course, all of this
implies that the student must have an intuitive feel for how linear programs are
solved. Besides understanding the meaning of the optimal solution the student
should also understand the meaning of shadow prices.
John Wiley & Sons
17-8
John Wiley & Sons
17-8
II. Teaching the “Nuts and Bolts”
The chapter is quite straightforward and therefore our comments are brief. One
pedagogical issue is how much time to spend on graphical analysis. The easiest
examples using graphical analysis involve putting the decision variables on the
axes such as in our PC example. Of course, this requires having exactly two
decision variables. Still it provides all of the intuition necessary. From here it is
possible to proceed to a discussion of more complex problems for which
graphical solutions are not possible. In other words, you may want to skip the
sections entitled “Production for Maximum Output” and “Production For
Minimum Cost” and go straight to “Computer Solutions.” Although these two
examples provide a graphical analysis for cases where there are only two
constraints but more than two decision variables, they add nothing to the
explanation of larger problems (and they may require an inordinate amount of
class time to explain.) In courses where time is at a premium they can be
dropped. They are included because these standard applications of graphical
analysis are taught in many courses.
Bonus Spreadsheet Problems
1. A manufacturer produces six products from six inputs. Each product
requires different amounts of inputs. The following table shows the profit
and raw materials requirements for each product. The last column shows
the total amounts of raw materials available.
Products
1 2 3 4 5 6
Profits 60 70 48 52 48 60 Total Amounts
Inputs required of Inputs
Aluminum .5 2 2 1 400
Steel 2 2.5 1.5 .5 580
Plastic 1.5 4 .5 890
Rubber 1 .5 1 .5 2.5 525
Glass 1 2 1.5 .4 1 2 650
Chrome .5 2 .5 2 1.5 2 620
a. Formulate the appropriate linear program.
John Wiley & Sons
17-8
b. Find the company’s most profitable production plan using a spreadsheet
optimizer.
Answer
a. The LP formulation is:
maximize = 60x1 + 70x2 + 48x3 + 52x4 + 48x5 + 60x6
subject to: .5x1 + 2x2 + 2x4 + x5≤ 400
2x1 + 2.5x2 + 1.5x3 + .5x5≤ 580
1.5x2 + 4x3 + .5x5≤ 890
x1 + .5x3+ x4 + .5x5 + 2.5x6≤ 525
x1 + 2x2 + 1.5x3+ .4x4 + x5 + 2x6≤ 650
.5x1 + 2x2 + .5x3+ 2x4 + 1.5x5 + 2x6≤ 620
b. From the spreadsheet optimizer, the optimal solution is:
x1 = 120, x2 = 0, x3 = 220, x4 = 160, x5 = 20, and x6 = 50.
2. A refinery processes two types of crude oil, heavy (H) and light (L), into its
final product, fuel oil (F). Two different production processes (which can be
used singly or simultaneously) are available.
Process 1: 1 unit of H and 2 units of L to yield 2 units of F at a cost of
$1.00.
Process 2: 1 unit of H and 1 unit of L to yield 1.5 units of F at a cost of
$.70.
The refinery must determine its production plan for the summer cycle
(May-October) and the winter cycle (November-April). It has contracts to
purchase 100 units of H and 150 units of L in each cycle and to deliver 125 units
of F in the summer and 170 units of F in the winter. (The company is free to sell
more than these contract amounts.) The summer unit fuel price is $1.00, and the
winter price is expected to be $1.20. Finally, the refinery’s goal is to maximize
profit.
John Wiley & Sons
17-8
a. Formulate the refinery’s problem as two separate linear programs one for
the summer cycle and one for the winter cycle. Explain (in a sentence or
two) why this is possible. Solve using a spreadsheet. (Hint: The appropriate
decision variables for the problems are the levels of the two processes used
in production during the two cycles. Denote these variables by s1, s2, w1, and
w2.)
b. Now suppose the refinery has facilities to store crude oil over the course of
the year, but it cannot store the final product, fuel oil. Any excess crude that
is not processed incurs a $.05 per unit charge for storage between cycles.
The refinery only considers storing “summer” crude for winter production
(and not vice versa). Formulate a single linear program by which the firm
can maximize annual profit. Solve using a spreadsheet. (Hint: Introduce the
additional decision variables IH and IL denoting the amounts of crude held in
inventory between summer and winter. With these two new variables,
modify and integrate the twin LP’s in part (a) into a single LP. How do the
inventory variables affect the constraints pertaining to crude supplies in
summer and winter?)
c. How does the refinery benefit from inventory holding, and why does it
benefit? (A general, qualitative answer will suffice.)
Answer
a. If the firm uses processes 1 and 2 at levels s1 and s2 in the summer its
profit is:
= [($1.00)(2) – $1.00]s1 + [($1.00)(1.5) – $.70]s2
= 1s1 + .8s2.
Thus, the LP formulation for the summer is:
Maximize = s1 + .8s2,
subject to 1s1 + 1s2 ≤ 100 (heavy crude),
2s1 + 1s2 ≤ 150 (light crude)
2s1 + 1.5s2 125.
In turn, If the firm uses the processes at levels w1 and w2 in the
John Wiley & Sons
17-8
winter, its profit is:
= [($1.20)(2) – $1.00]w1 + [($1.20)(1.5) – $.70]w2
= 1.40w1 + 1.10w2.
Thus, the LP formulation for the winter is:
Maximize = 1.40w1 + 1.10w2,
subject to 1w1 + 1w2 ≤ 100 (heavy crude)
2w1 + 1w2 ≤ 150 (light crude)
2w1 + 1.5w2 170.
The LP problems are modeled on the spreadsheet below. To solve the
summer problem, one maximizes profit in cell G15 by varying the
process levels in cells C6 and E6, subject to cells I7, I8, and I11 all being
greater or equal to zero. The solution is: s1 = s2 = 50, and = 90. The
corresponding solution for the winter cycle is: w1 = w2 = 50, and = 125.
b. The new formulation is:
Maximize s1 + .8s2 + 1.40w1 + 1.10w2 – .05IH – .05IL,
subject to s1 + s2 + IH = 100,
2s1 + 1s2 + IL = 150,
2s1 + 1.5s2 125,
w1 + w2 ≤ 100 + IH,
2w1 + w2 ≤ 150 + IL,
2w1 + 1.5w2 170.
and all variables non-negative.
Here IH and IL are the inventories of heavy and light crude oil carried
over from summer (when not all crude is processed) to winter (when
fuel oil prices are most profitable). Of course, all decision variables
must be nonnegative. The spreadsheet below already allows for
John Wiley & Sons
17-8
A B C D E F G H I J
1
2
3
4Summer
5Process 1 Process 2 Available Summer Cost of
6Level 62.5 0 Inputs Used Inputs Inventory Inventory
7H 1 1 62.5 100 37.5 0.05
8L 2 1 125 150 25 0.05
9
10 Output Min Output Extra
11 F 2 1.5 125 125 0
12
13 Revenue 1.00 125
14 Cost 1.00 0.70 62.5
15 Profit 62.5
16
17 Winter Available Winter
18 Process 1 Process 2 Inputs Used Inputs Inventory
19 Level 37.5 100
20 H 1 1 137.5 137.5 0
21 L 2 1 175 175 0
22
23 Output Min Output Extra
24 F 2 1.5 225 170 55
25
26 Revenue 1.20 270
27 Cost 1.00 0.70 107.5 Profit/Yr
28 Profit 162.5 221.875
29
inventories. (In the part a solution, the inventories were simply set to
zero to maintain separation between the summer and winter problems.)
Using the optimizer, we maximize total profit in cell J28, by changing
cells C6, E6, C19, E19, subject to I7, I8, I11, I20, I21, and I24 all being
greater or equal to zero. The solution is: s1 = 62.5, s2 = 0, IH = 37.5, IL =
25, w1 = 37.5, w2 = 100, and T = 221.875. Note that the firm barely
meets its fuel oil delivery obligations in the summer and stores crude for
more profitable sales in the winter. As one can confirm, the same
solution applies for a range of inventory costs: $.10 per unit, $.05 per
unit or $0 per unit. (Total profit increases as inventory costs decline.)
John Wiley & Sons
17-8
ADDITIONAL MATERIALS
I. Suggested Readings
R. Fourer, “Linear Programming Software Survey,” OR/MS Today, June 2013,
pp. 44-53.
J. Fallows, “Dirty Coal, Clean Future, The Atlantic, December 2010, pp. 66-78.
V. Postrel, “Operation Everything,” The Boston Globe, June 27, 2004, p. D1.
S. Begley, “Did you Hear the One about the Salesman who Traveled Better?”
The Wall Street Journal, April 23, 2004, p. B2.
L.J. LeBlanc et al, “Nu-kote’s Spreadsheet Linear-Programming Models for
Optimizing Transportation,” Interfaces, 34, March-April 2004, 139-146.
J. L. Higle and S. W. Wallace, “Sensitivity Analysis and Uncertainty in Linear
Programming,” Interfaces, July-August 2003, pp. 53-60.
S. Bollapragada et al, “NBC’s Optimization Systems Increase Revenues and
Productivity,” Interfaces, January-February 2002, pp. 47-60.
G. Brown et al, “The Kellogg Company Optimizes Production, Inventory, and
Distribution,” Interfaces, 31, November-December 2001, 1-15.
T. A. Grossman, “Reversing Tradition: Nonlinear Optimization Deserves More
Emphasis, OR/MS Today, August 2001, pp. 22-25
E. H. Kaplan, “Allocating HIV Resources,” OR/MS Today, February 2001, pp.
26-29
E. W. Schuster and S. J. Allen, “Raw Material Management at Welch’s, Inc,”
Interfaces, September-October 1998, pp. 13-24.
R. A. Bosch, “Big Mac Attack,” OR/MS Today, October 1993. (This article
formulates a linear program for optimizing fast-food meals at McDonalds.)
John Wiley & Sons
17-8
D. Klingman et al, “The Successful Deployment of Management Science
Throughout Citgo Petroleum Corporation,” Interfaces, January-February 1987,
pp. 4-25.
Kimes, S.E. and J.A. Fitzsimmons, “Selecting Profitable Sites at LaQuinta
Motor Inns,” Interfaces, Mar.-April. 1990, pp. 12-20.
II. Cases
Fair Play at Chisolm University, (UVA-QA-0789), Darden Business School,
University of Virginia, 2012.
Timeshare Exchange Fair (A and B), (UVA-QA-0709), Darden Business School,
University of Virginia, 2007.
Australian Motors Ltd. (OIT23), Stanford University, 1998. (Available from
Harvard Business School Publishing.)
MacPherson Refrigeration Ltd. (93D021), Richard Ivey School of Business,
1997. (Available from Harvard Business School Publishing.)
Chase Shipping (9-196-098), Harvard Business School, 1995.
Buckeye Power and Light Company, (UVA-QA-0326), Darden Business School,
University of Virginia, 1991.
III. Quips and Quotes
Has anything witty ever been said about linear programming?
John Wiley & Sons
17-8