Optimization Modeling with Spreadsheets

by Baker, Kenneth R.

• ISBN13: 9780470928639
• ISBN10: 0470928638
• Edition: 2nd
• Format: Hardcover
• Copyright: 2011-05-24
• Publisher: Wiley

Summary

This introductory book on optimization (mathematical programming) includes coverage on linear programming, nonlinear programming, integer programming and heuristic programming; as well as an emphasis on model building using Excel and Solver. The emphasis on model building (rather than algorithms) is one of the features that makes this book distinctive. Most books devote more space to algorithmic details than to formulation principles. These days, however, it is not necessary to know a great deal about algorithms in order to apply optimization tools, especially when relying on the spreadsheet as a solution platform. The emphasis on spreadsheets is another feature that makes this book distinctive. Few books devoted to optimization pay much attention to spreadsheet implementation of optimization principles, and most books that emphasize model building ignore spreadsheets entirely. Thus, someone looking for a spreadsheet-based treatment would otherwise need to use a book that was designed for some other purpose, like a survey of management science topics, rather than one devoted to optimization. The model building emphasis derives from an attempt to be realistic about what readers need most when learning about optimization. At an introductory level, the most practical and motivating theme is the wide applicability of optimization tools. To apply optimization effectively, readers needs more than a brief exposure to a series of numerical examples, which is the way that most mathematical programming books treat applications. With a systematic modeling emphasis, readers can begin to see the basic structures that appear in optimization models and as a result, develop an appreciation for potential applications well beyond the examples in the book. Formulating optimization models is both an art and a science, and this book pays attention to both. The art can be refined with practice, especially supervised practice, just the way a student would learn sculpture or painting. The science is reflected in the structure that organizes the topics in this book. For example, there are several distinct problem types that lend themselves to linear programming formulations, and it makes sense to study these types systematically. In that spirit, the book builds a library of templates against which new problems can be compared. Analogous structures are developed for the presentation of other topics as well.

Author Biography

Kenneth R. Baker, PHD, is Nathaniel Leverone Professor of Management at the Tuck School of Business and Adjunct Professor of Engineering at Dartmouth College. A Fellow of the Institute for Operations Research and the Management Sciences (INFORMS), Dr. Baker has published extensively in his areas of research interest, which include mathematical modeling, spreadsheet engineering, and scheduling. He is the coauthor of Principles of Sequencing and Scheduling and Management Science: The Art of Modeling with Spreadsheets, Third Edition, both published by Wiley.

Table of Contents

Preface	p. xi
Introduction to Spreadsheet Models for Optimization	p. 1
Elements of a Model	p. 2
Spreadsheet Models	p. 4
A Hierarchy for Analysis	p. 7
Optimization Software	p. 8
Using Solver	p. 10
Summary	p. 17
Exercises	p. 18
References	p. 20
Linear Programming: Allocation, Covering, and Blending Models	p. 21
Linear Models	p. 22
Linear Constraints	p. 24
Formulation	p. 25
Layout	p. 26
Results	p. 28
Allocation Models	p. 29
The Product Mix Problem	p. 35
Covering Models	p. 39
The Staff-Scheduling Problem	p. 43
Blending Models	p. 47
Modeling Errors in Linear Programming	p. 53
Exceptions	p. 53
Debugging	p. 55
Logic	p. 56
Summary	p. 57
Exercises	p. 57
Case: JetGreen	p. 68
Linear Programming: Network Models	p. 71
The Transportation Model	p. 72
The Assignment Model	p. 77
The Transshipment Model	p. 81
Features of Special Network Models	p. 85
Building Network Models with Balance Equations	p. 86
General Network Models with Yields	p. 91
Models with Yield Losses	p. 91
Models with Yield Gains	p. 93
General Network Models with Transformed Flows	p. 98
Summary	p. 103
Exercises	p. 103
Case: Casey's Famous Roast Beef	p. 113
Case: Hollingsworth Paper Company	p. 114
Production and Distribution Facilities	p. 115
Patterns of Distribution	p. 115
Expansion Proposals	p. 116
Sensitivity Analysis in Linear Programs	p. 119
Parameter Analysis in the Transportation Example	p. 120
Parameter Analysis in the Allocation Example	p. 127
The Sensitivity Report and the Transportation Example	p. 135
The Sensitivity Report and the Allocation Example	p. 138
Degeneracy and Alternative Optima	p. 140
Patterns in Linear Programming Solutions	p. 144
The Transportation Model	p. 145
The Product Portfolio Model	p. 149
The Investment Model	p. 152
The Allocation Model	p. 154
The Refinery Model	p. 155
Summary	p. 159
Exercises	p. 160
Case: Cox Cable and Wire Company	p. 171
Background	p. 171
The Contract	p. 172
The Analysis	p. 173
Linear Programming: Data Envelopment Analysis	p. 175
A Graphical Perspective on DEA	p. 177
An Algebraic Perspective on DEA	p. 181
A Spreadsheet Model for DEA	p. 183
Indexing	p. 188
Finding Reference Sets and HCUs	p. 190
Assumptions and Limitations of DEA	p. 193
Summary	p. 196
Exercises	p. 196
Case: Branch Performance at Nashville National Bank	p. 205
Branch Growth at Nashville National Bank	p. 205
Assessing Branch Productivity	p. 206
Branch Managers Revolt	p. 206
Measuring Branches: Available Techniques	p. 207
The DEA Study	p. 207
Integer Programming: Binary Choice Models	p. 211
Using Solver with Integer Requirements	p. 213
The Capital Budgeting Problem	p. 217
Set Covering	p. 221
Set Packing	p. 224
Set Partitioning	p. 227
Playoff Scheduling	p. 229
Solving a Large-Scale Set Partitioning Problem	p. 234
The Algorithm for Solving Integer Programs	p. 237
Summary	p. 243
Exercises	p. 243
Case: Motel Location for Nature's Inn	p. 249
Integer Programming: Logical Constraints	p. 251
Simple Logical Constraints: Exclusivity and Contingency	p. 253
Linking Constraints: The Fixed Cost Problem	p. 255
Linking Constraints: The Threshold Level Problem	p. 260
Linking Constraints: The Facility Location Model	p. 261
Capacitated Version	p. 263
Uncapacilated Version	p. 267
Disjunctive Constraints: The Machine Sequencing Problem	p. 270
Tour and Subset Constraints: The Traveling Salesperson Problem	p. 274
Summary	p. 282
Exercises	p. 283
Case: Hornby Products Company	p. 291
History	p. 291
Alternatives	p. 293
Nonlinear Programming	p. 297
One-variable Models	p. 298
An Inventory Example	p. 300
A Quantity Discount Example	p. 302
Local Optima and the Search for an Optimum	p. 304
Two-Variable Models	p. 307
Curve Fitting	p. 307
Two-dimensional Location	p. 310
Nonlinear Models with Constraints	p. 312
A Pricing Example	p. 313
Sensitivity Analysis for Nonlinear Programs	p. 315
The Portfolio Optimization Model	p. 316
Linearizations	p. 320
Linearizing the Maximum	p. 320
Linearizing the Absolute Value	p. 324
Summary	p. 327
Exercises	p. 328
Case: Delhi Foods	p. 335
Heuristic Solutions with the Evolutionary Solver	p. 337
Features of the Evolutionary Solver	p. 338
An Illustrative Example: Nonlinear Regression	p. 339
The Machine-Sequencing Problem Revisited	p. 346
The Traveling Salesperson Problem Revisited	p. 349
Two-dimensional Location	p. 352
Line Balancing	p. 354
Group Assignment	p. 358
Summary	p. 362
Exercises	p. 362
Case: Colgate Wave (Abridged)	p. 370
Introduction	p. 370
The Study	p. 370
Case Appendix: Market Share Simulation Model (CoIgate.xls)	p. 373
Data	p. 373
Calculations	p. 373
Simulation	p. 374
Appendices
Optimization Software and Supplemental Files	p. 375
Risk Solver Platform	p. 375
Supplemental Excel Files	p. 376
Graphical Methods in Linear Programming	p. 377
An Example	p. 377
Generalities	p. 382
The Simplex Method	p. 385
An Example	p. 385
Variations of the Algorithm	p. 390
References	p. 393
Stochastic Programming	p. 395
One-Stage Decisions with Uncertainty	p. 395
Two-Stage Decisions with Uncertainty	p. 399
Using Solver	p. 402
Index	p. 407
Table of Contents provided by Ingram. All Rights Reserved.