Optimization Modeling with Spreadsheets

by Baker, Kenneth R.

• ISBN13: 9780470949108
• ISBN10: 0470949104
• Edition: 2nd
• Format: eBook
• Copyright: 2011-03-08
• 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 area of research interest, which include mathematical modeling, spreadsheet engineering, and scheduling. He is 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.

Chapter 1. Introduction to Spreadsheet Models for Optimization.

1.1 Elements of Model.

1.2 Spreadsheet Models.

1.3 A Hierarchy for Analysis.

1.4 Optimization Software.

1.5 Using Solver.

Chapter 2. Linear Programming: Allocation, Covering and Blending Models.

2.1 Linear Models.

2.2 Allocation Models.

2.3 Covering Models.

2.4 Blending Models.

2.5 Modeling Errors in Linear Programming.

Chapter 3. Linear Programming Network Models.

3.1 The Transportation Model.

3.2 The Assignment Model.

3.3 The Transshipment Model.

3.4 Features of Special Network Models.

3.5 Building Network Models with Yields.

3.6 General Network Models with Yields.

3.7 General Network Models with Transformed Flows.

Chapter 4. Sensitivity Analysis in Linear Programs.

4.1 Parameter Analysis in the Transportation Example

4.2 Parameter Analysis in the Allocation Example.

4.3 The Sensitivity Report and the Transportation Example.

4.4 The Sensitivity Report and the Allocation Example.

4.5 Degeneracy and Alternative Optima.

4.6 Patterns in Linear Programming Solutions.

Chapter 5. Linear Programming: Data Envelopment Analysis.

5.1 A Graphical Perspective on DEA.

5.2 An Algebraic Perspective on DEA.

5.3 A Spreadsheet Model for DEA.

5.4 Indexing.

5.5 Finding Reference Sets and HSUs.

5.6 Assumptions and Limitations of DEA.

Chapter 6. Integer Programming: Binary Choice Models.

6.1 Using Solver with Integer Requirements.

6.2 The Capital Budgeting Problem.

6.3 Set Covering.

6.4 Set Packing.

6.5 Set Partitioning.

6.6 Solving a Large-Scale Set Partitioning Problem.

Chapter 7. Integer Programming: Logical Constraints.

7.1 Simple Logical Constraints: Contingency and Exclusivity.

7.2 Linking Constraints: The Fixed Cost Problem.

7.3 Linking Constraints: The Threshold Level Problem.

7.4 Linking Constraints: The Facility Location Model.

7.5 Disjunctive Constraints: The Machine Sequencing Problem.

7.6 Tour and Subset Constraints: The Traveling Salesperson Problem.

7.7 The Algorithm for Solving Integer Programs.

Chapter 8. Nonlinear Programming.

8.1 One-Variable Models.

8.2 Local Optima and the Search for an Optimum.

8.3 Two-Variable Models.

8.4 Nonlinear Models with Constraints.

8.5 Linearizations.

Chapter 9. Heuristic Solutions with the Evolutionary Solver.

9.1 Features of the Evolutionary Solver.

9.2 An Illustrative Example: Nonlinear Regression.

9.3 The Machine-Sequencing Problem Revisited.

9.4 The Traveling Salesperson Problem Revisited.

9.5 Multi-Machine Scheduling.

9.6 Two-Dimensional Location.

9.7 Line Balancing.

Appendices.

1. Optimization Software and Supplement Files.

2. Graphical Method for Linear Programming.

3. The Simplex Method.

4. Stochastic Programming.

Index.