Computer Solutions
Solving LP problems graphically is impractical for settings in which there
are three or more decision variables and constraints. Fortunately, many com-
puter programs are available to solve large-scale LP problems. Indeed, a
major airline routing its aircraft can find itself facing a linear programming
problem involving thousands of decision variables and hundreds of con-
straints. Computers can efficiently solve even problems this large. In its
broad description, the computer solution is much the same, however large
the problem. Typically, the user inputs a mathematical formulation of the
problem, that is, the objective function and all constraints. The computer
program then produces optimal values of all decision variables, the optimal
value of the objective function, and the shadow prices associated with
the constraints.
The last 25 years have seen the development of dozens of spreadsheet-based
linear programming packages.^8 The user enters basic data, including con-
straints, directly into a spreadsheet. The program then carries out all arith-
metic calculations and displays the optimal solution and shadow prices in the
original spreadsheet. A key advantage is that this output can be used as inputs
into larger, related spreadsheets. The following examples illustrate a typical
spreadsheet-based LP program.A STAFFING PROBLEM A major city has minimum requirements for the num-
ber of police officers on duty during each 4-hour period (see the following
table). Because split shifts are prohibited, each officer must work eight con-
secutive hours.
Officers receive standard pay rates for shifts 1 and 2, time and a quarter for
shifts 3 and 4, and time and a half for shifts 5 and 6. How can the police depart-
ment find a daily work schedule that will minimize its total wage cost?Required Number
Shift Time of Police Officers
18 A.M.–12P.M. 150
2 12–4P.M. 100
3 4–8P.M. 250
48 P.M.–12A.M. 400
5 12–4A.M. 500
6 4–8A.M. 175730 Chapter 17 Linear Programming(^8) For a review of these software packages, see R. Fourer, “Linear Programming Survey,” OR/MS
Today(June 2011): 60–69. (An updated version of this comprehensive survey of LP software pack-
ages is available online at http://lionhrtpub.com/orms. Click on “software surveys.”)
c17LinearProgramming.qxd 9/26/11 11:05 AM Page 730