Introduction to Operations Research

Frederick S. Hillier was born and raised in Aberdeen, Washington, where he was an award winner in statewide high school contents in essay writing, mathematics, debate, and music. As an undergraduate at Stanford University he ranked first in his engineering class of over 300 students. Dr. Hillier's research has extended into a variety of areas, including integer programming, queueing theory and its application, statistical quality control, and the application of operations research to the design of production systems and to capital budgeting. He was the first prize winner of a research contest on "Capital Budgeting of Interrelated Projects" sponsored by The Institute of Management Sciences and the U.S. Office of Naval Research. He and Dr. Lieberman also received the honorable mention award for the 1995 Lanchester Prize (best English-language publication of any kind in the field of operations research) for the 6th edition of IOR. He currently serves as the Series Editor for the International Series in Operations Research and Management Science being published by Kluwer Academic Publishers. SUPPLEMENTS PREFACE CHAPTER 1 Introduction 1.1 The Origins of Operations Research 1.2 The Nature of Operations Research 1.3 The Impact of Operations Research 1.4 Algorithms and OR Courseware Selected References Problems CHAPTER 2 Overview of the OperationsOverview of the Operations Research Modeling Approach 2.1 Defining the Problem and Gathering Data 2.2 Formulating a Mathematical Model 2.3 Deriving Solutions from the Model 2.4 Testing the Model 2.5 Preparing to Apply the Model 2.6 Implementation 2.7 Conclusions Selected References Problems CHAPTER 3 Introduction to Linear Programming 3.1 Prototype Example 3.2 The Linear Programming Model 3.3 Assumptions of Linear Programming 3.4 Additional Examples 3.5 Formulating and Solving Linear Programming Models on a Spreadsheet 3.6 Formulating Very Large Linear Programming Models 3.7 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 3.1 Auto Assembly Previews of Added Cases on Our Website Case 3.2 Cutting Cafeteria Costs Case 3.3 Staffing a Call Center Case 3.4 Promoting a Breakfast CHAPTER 4 Solving Linear Programming Problems: The Simplex Method 4.1 The Essence of the Simplex Method 4.2 Setting Up the Simplex Method 4.3 The Algebra of the Simplex Method 4.4 The Simplex Method in Tabular Form 4.5 Tie Breaking in the Simplex Method 4.6 Adapting to Other Model Forms 4.7 Postoptimality Analysis 4.8 Computer Implementation 4.9 The Interior-Point Approach to Solving Linear Programming Problems 4.10 Conclusions Appendix 4.1 An Introduction to Using LINDO and LINGO Selected References Learning Aids for This Chapter on Our Website Problems Case 4.1 Fabrics and Fall Fashions Previews of Added Cases on Our Website Case 4.2 New Frontiers Case 4.3 Assigning Students to Schools CHAPTER 5 The Theory of the Simplex Method 5.1 Foundations of the Simplex Method 5.2 The Simplex Method in Matrix Form 5.3 A Fundamental Insight 5.4 The Revised Simplex Method 5.5 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 6 Duality Theory and Sensitivity Analysis 6.1 The Essence of Duality Theory 6.2 Economic Interpretation of Duality 6.3 Primal–Dual Relationships 6.4 Adapting to Other Primal Forms 6.5 The Role of Duality Theory in Sensitivity Analysis 6.6 The Essence of Sensitivity Analysis 6.7 Applying Sensitivity Analysis 6.8 Performing Sensitivity Analysis on a Spreadsheet 6.9 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 6.1 Controlling Air Pollution Previews of Added Cases on Our Website Case 6.2 Farm Management Case 6.3 Assigning Students to Schools, Revisited Case 6.4 Writing a Nontechnical Memo CHAPTER 7 Other Algorithms for Linear Programming 7.1 The Dual Simplex Method 7.2 Parametric Linear Programming 7.3 The Upper Bound Technique 7.4 An Interior-Point Algorithm 7.5 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 8 The Transportation and Assignment Problems 8.1 The Transportation Problem 8.2 A Streamlined Simplex Method for the Transportation Problem 8.3 The Assignment Problem 8.4 A Special Algorithm for the Assignment Problem 8.5 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 8.1 Shipping Wood to Market Previews of Added Cases on Our Website Case 8.2 Continuation of the Texago Case Study Case 8.3 Project Pickings CHAPTER 9 Network Optimization Models 9.1 Prototype Example 9.2 The Terminology of Networks 9.3 The Shortest-Path Problem 9.4 The Minimum Spanning Tree Problem 9.5 The Maximum Flow Problem 9.6 The Minimum Cost Flow Problem 9.7 The Network Simplex Method 9.8 A Network Model for Optimizing a Project’s Time-Cost Trade-Off 9.9 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 9.1 Money in Motion Previews of Added Cases on Our Website Case 9.2 Aiding Allies Case 9.3 Steps to Success CHAPTER 10 Dynamic Programming 10.1 A Prototype Example for Dynamic Programming 10.2 Characteristics of Dynamic Programming Problems 10.3 Deterministic Dynamic Programming 10.4 Probabilistic Dynamic Programming 10.5 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 11 Integer Programming 11.1 Prototype Example 11.2 Some BIP Applications 11.3 Innovative Uses of Binary Variables in Model Formulation 11.4 Some Formulation Examples 11.5 Some Perspectives on Solving Integer Programming Problems 11.6 The Branch-and-Bound Technique and Its Application to Binary Integer Programming 11.7 A Branch-and-Bound Algorithm for Mixed Integer Programming 11.8 The Branch-and-Cut Approach to Solving BIP Problems 11.9 The Incorporation of Constraint Programming 11.10 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 11.1 Capacity Concerns Previews of Added Cases on Our Website Case 11.2 Assigning Art Case 11.3 Stocking Sets Case 11.4 Assigning Students to Schools, Revisited Again CHAPTER 12 Nonlinear Programming 12.1 Sample Applications 12.2 Graphical Illustration of Nonlinear Programming Problems 12.3 Types of Nonlinear Programming Problems 12.4 One-Variable Unconstrained Optimization 12.5 Multivariable Unconstrained Optimization 12.6 The Karush-Kuhn-Tucker (KKT) Conditions for Constrained Optimization 12.7 Quadratic Programming 12.8 Separable Programming 12.9 Convex Programming 12.10 Nonconvex Programming (with Spreadsheets) 12.11 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 12.1 Savvy Stock Selection Previews of Added Cases on Our Website Case 12.2 International Investments Case 12.3 Promoting a Breakfast Cereal, Revisited CHAPTER 13 Metaheuristics 13.1 The Nature of Metaheuristics 13.2 Tabu Search 13.3 Simulated Annealing 13.4 Genetic Algorithms 13.5 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 14 Game Theory 14.1 The Formulation of Two-Person, Zero-Sum Games 14.2 Solving Simple Games—A Prototype Example 14.3 Games with Mixed Strategies 14.4 Graphical Solution Procedure 14.5 Solving by Linear Programming 14.6 Extensions 14.7 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 15 Decision Analysis 15.1 A Prototype Example 15.2 Decision Making without Experimentation 15.3 Decision Making with Experimentation 15.4 Decision Trees 15.5 Using Spreadsheets to Perform Sensitivity Analysis on Decision Trees 15.6 Utility Theory 15.7 The Practical Application of Decision Analysis 15.8 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 15.1 Brainy Business Preview of Added Cases on Our Website Case 15.2 Smart Steering Support Case 15.3 Who Wants to be a Millionaire? Case 15.4 University Toys and the Engineering Professor Action Figures CHAPTER 16 Markov Chains 16.1 Stochastic Processes 16.2 Markov Chains 16.3 Chapman-Kolmogorov Equations 16.4 Classification of States of a Markov Chain 16.5 Long-Run Properties of Markov Chains 16.6 First Passage Times 16.7 Absorbing States 16.8 Continuous Time Markov Chains Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 17 Queueing Theory 17.1 Prototype Example 17.2 Basic Structure of Queueing Models 17.3 Examples of Real Queueing Systems 17.4 The Role of the Exponential Distribution 17.5 The Birth-and-Death Process 17.6 Queueing Models Based on the Birth-and-Death Process 17.7 Queueing Models Involving Nonexponential Distributions 17.8 Priority-Discipline Queueing Models 17.9 Queueing Networks 17.10 The Application of Queueing Theory 17.11 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 17.1 Reducing In-Process Inventory Preview of an Added Case on Our Website Case 17.2 Queueing Quandary CHAPTER 18 Inventory Theory 18.1 Examples 18.2 Components of Inventory Models 18.3 Deterministic Continuous-Review Models 18.4 A Deterministic Periodic-Review Model 18.5 Deterministic Multiechelon Inventory Models for Supply Chain Management 18.6 A Stochastic Continuous-Review Model 18.7 A Stochastic Single-Period Model for Perishable Products 18.8 Revenue Management 18.9 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 18.1 Brushing Up on Inventory Control Previews of Added Cases on Our Website Case 18.2 TNT: Tackling Newsboy’s Teachings Case 18.3 Jettisoning Surplus Stock CHAPTER 19 Markov Decision Processes 19.1 A Prototype Example 19.2 A Model for Markov Decision Processes 19.3 Linear Programming and Optimal Policies 19.4 Policy Improvement Algorithm for Finding Optimal Policies 19.5 Discounted Cost Criterion 19.6 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems CHAPTER 20 Simulation 20.1 The Essence of Simulation 20.2 Some Common Types of Applications of Simulation 20.3 Generation of Random Numbers 20.4 Generation of Random Observations from a Probability Distribution 20.5 Outline of a Major Simulation Study 20.6 Performing Simulations on Spreadsheets 20.7 Conclusions Selected References Learning Aids for This Chapter on Our Website Problems Case 20.1 Reducing In-Process Inventory, Revisited Case 20.2 Action Adventures Previews of Added Cases on Our Website Case 20.3 Planning Planers Case 20.4 Pricing under Pressure APPENDIXES 1. Documentation for the OR Courseware 2. Convexity 3. Classical Optimization Methods 4. Matrices and Matrix Operations 5. Table for a Normal Distribution PARTIAL ANSWERS TO SELECTED PROBLEMS INDEXES Author Index Subject Index

For over four decades, Introduction to Operations Research by Frederick Hillier has been the classic text on operations research. While building on the classic strengths of the text, the author continues to find new ways to make the text current and relevant to students. One way is by incorporating a wealth of state-of-the-art, user-friendly software and more coverage of business applications than ever before. The hallmark features of this edition include clear and comprehensive coverage of fundamentals, an extensive set of interesting problems and cases, and state-of-the-practice operations research software used in conjunction with examples from the text.

The ninth edition introduces a new partnership with the Institute for Operations Research and Management (INFORMS). These two pillars of the OR world have come together to showcase some of the award-winning applications of operations research and integrate them with this text.