Introduction to Operations Research – Frederick S. Hillier, Gerald J. Lieberman – 10th Edition

CHAPTER 1
Introduction 1
1.1 The Origins of Operations Research 1
1.2 The Nature of Operations Research 2
1.3 The Impact of Operations Research 3
1.4 Algorithms and OR Courseware 5
Selected References 6
Problems 7

CHAPTER 2
Overview of the Operations Research Modeling Approach 8
2.1 Defining the Problem and Gathering Data 8
2.2 Formulating a Mathematical Model 12
2.3 Deriving Solutions from the Model 15
2.4 Testing the Model 17
2.5 Preparing to Apply the Model 19
2.6 Implementation 21
2.7 Conclusions 22
Selected References 23
Problems 23

CHAPTER 3
Introduction to Linear Programming 25
3.1 Prototype Example 26
3.2 The Linear Programming Model 32
3.3 Assumptions of Linear Programming 37
3.4 Additional Examples 44
3.5 Some Classic Case Studies 60
3.6 Formulating and Solving Linear Programming Models on a Spreadsheet 65
3.7 Formulating Very Large Linear Programming Models 73
3.8 Conclusions 80
Appendix 3.1 The LINGO Modeling Language 81
Selected References 90
Learning Aids for This Chapter on CD-ROM 90
Problems 91
Case 3.1 Auto Assembly 100
Previews of Added Cases on CD-ROM 102
Case 3.2 Cutting Cafeteria Costs 102
Case 3.3 Staffing a Call Center 102
Case 3.4 Promoting a Breakfast Cereal 102

CHAPTER 4
Solving Linear Programming Problems: The Simplex Method 103
4.1 The Essence of the Simplex Method 103
4.2 Setting Up the Simplex Method 108
4.3 The Algebra of the Simplex Method 111
4.4 The Simplex Method in Tabular Form 117
4.5 Tie Breaking in the Simplex Method 121
4.6 Adapting to Other Model Forms 124
4.7 Postoptimality Analysis 142
4.8 Computer Implementation 150
4.9 The Interior-Point Approach to Solving Linear Programming Problems 153
4.10 Conclusions 158
Appendix 4.1 An Introduction to Using LINDO 158
Selected References 161
Learning Aids for This Chapter on CD-ROM 161
Problems 162
Case 4.1 Fabrics and Fall Fashions 170
Previews of Added Cases on CD-ROM 172
Case 4.2 New Frontiers 172
Case 4.3 Assigning Students to Schools 172

CHAPTER 5
The Theory of the Simplex Method 173
5.1 Foundations of the Simplex Method 173
5.2 The Revised Simplex Method 184
5.3 A Fundamental Insight 193
5.4 Conclusions 201
Selected References 201
Learning Aids for This Chapter on CD-ROM 201
Problems 202

CHAPTER 6
Duality Theory and Sensitivity Analysis 209
6.1 The Essence of Duality Theory 210
6.2 Economic Interpretation of Duality 217
6.3 Primal-Dual Relationships 220
6.4 Adapting to Other Primal Forms 225
6.5 The Role of Duality Theory in Sensitivity Analysis 229
6.6 The Essence of Sensitivity Analysis 231
6.7 Applying Sensitivity Analysis 239
6.8 Performing Sensitivity Analysis on a Spreadsheet 259
6.9 Conclusions 275
Selected References 275
Learning Aids for This Chapter on CD-ROM 276
Problems 276
Case 6.1 Controlling Air Pollution 289
Previews of Added Cases on CD-ROM 290
Case 6.2 Farm Management 290
Case 6.3 Assigning Students to Schools (Revisited) 291
Case 6.4 Writing a Nontechnical Memo 291

CHAPTER 7
Other Algorithms for Linear Programming 292
7.1 The Dual Simplex Method 292
7.2 Parametric Linear Programming 295
7.3 The Upper Bound Technique 300
7.4 An Interior-Point Algorithm 303
7.5 Conclusions 314
Selected References 314
Learning Aids for This Chapter on CD-ROM 315
Problems 315

CHAPTER 8
The Transportation and Assignment Problems 320
8.1 The Transportation Problem 321
8.2 A Streamlined Simplex Method for the Transportation Problem 335
8.3 The Assignment Problem 350
8.4 A Special Algorithm for the Assignment Problem 359
8.5 Conclusions 363
Selected References 363
Learning Aids for This Chapter on CD-ROM 364
Problems 364
Case 8.1 Shipping Wood to Market 372
Previews of Added Cases on CD-ROM 373
Case 8.2 Continuation of the Texago Case Study 373
Case 8.3 Project Pickings 373

CHAPTER 9
Network Optimization Models 374
9.1 Prototype Example 375
9.2 The Terminology of Networks 376
9.3 The Shortest-Path Problem 380
9.4 The Minimum Spanning Tree Problem 384
9.5 The Maximum Flow Problem 388
9.6 The Minimum Cost Flow Problem 396
9.7 The Network Simplex Method 404
9.8 A Network Model for Optimizing a Projects Time-Cost Trade-Off 414
9.9 Conclusions 426
Selected References 427
Learning Aids for This Chapter on CD-ROM 427
Problems 428
Case 9.1 Money in Motion 437
Previews of Added Cases on CD-ROM 439
Case 9.2 Aiding Allies 439
Case 9.3 Steps to Success 439

CHAPTER 10
Dynamic Programming 440
10.1 A Prototype Example for Dynamic Programming 440
10.2 Characteristics of Dynamic Programming Problems 445
10.3 Deterministic Dynamic Programming 447
10.4 Probabilistic Dynamic Programming 466
10.5 Conclusions 471
Selected References 472
Learning Aids for This Chapter on CD-ROM 472
Problems 472

CHAPTER 11
Integer Programming 478
11.1 Prototype Example 479
11.2 Some BIP Applications 482
11.3 Innovative Uses of Binary Variables in Model Formulation 487
11.4 Some Formulation Examples 493
11.5 Some Perspectives on Solving Integer Programming Problems 501
11.6 The Branch-and-Bound Technique and Its Application to Binary Integer Programming 505
11.7 A Branch-and-Bound Algorithm for Mixed Integer Programming 515
11.8 The Branch-and-Cut Approach to Solving BIP Problems 521
11.9 The Incorporation of Constraint Programming 527
11.10 Conclusions 533
Selected References 533
Learning Aids for This Chapter on CD-ROM 534
Problems 534
Case 11.1 Capacity Concerns 544
Previews of Added Cases on CD-ROM 546
Case 11.2 Assigning Art 546
Case 11.3 Stocking Sets 546
Case 11.4 Assigning Students to Schools (Revisited Again) 546

CHAPTER 12
Nonlinear Programming 547
12.1 Sample Applications 548
12.2 Graphical Illustration of Nonlinear Programming Problems 552
12.3 Types of Nonlinear Programming Problems 556
12.4 One-Variable Unconstrained Optimization 561
12.5 Multivariable Unconstrained Optimization 567
12.6 The Karush-Kuhn-Tucker (KKT) Conditions for Constrained Optimization 572
12.7 Quadratic Programming 576
12.8 Separable Programming 583
12.9 Convex Programming 589
12.10 Nonconvex Programming (with Spreadsheets) 597
12.11 Conclusions 602
Selected References 603
Learning Aids for This Chapter on CD-ROM 603
Problems 604
Case 12.1 Savvy Stock Selection 615
Previews of Added Cases on CD-ROM 616
Case 12.2 International Investments 616
Case 12.3 Promoting a Breakfast Cereal (Revisited) 616

CHAPTER 13
Metaheuristics 617
13.1 The Nature of Metaheuristics 618
13.2 Tabu Search 625
13.3 Simulated Annealing 635
13.4 Genetic Algorithms 644
13.5 Conclusions 652
Selected References 654
Learning Aids for This Chapter on CD-ROM 654
Problems 655

CHAPTER 14
Game Theory 659
14.1 The Formulation of Two-Person, Zero-Sum Games 659
14.2 Solving Simple Games?A Prototype Example 661
14.3 Games with Mixed Strategies 666
14.4 Graphical Solution Procedure 667
14.5 Solving by Linear Programming 670
14.6 Extensions 673
14.7 Conclusions 674
Selected References 674
Learning Aids for This Chapter on CD-ROM 675
Problems 675

CHAPTER 15
Decision Analysis 680
15.1 A Prototype Example 681
15.2 Decision Making without Experimentation 682
15.3 Decision Making with Experimentation 687
15.4 Decision Trees 693
15.5 Using Spreadsheets to Perform Sensitivity Analysis on Decision Trees 698
15.6 Utility Theory 708
15.7 The Practical Application of Decision Analysis 715
15.8 Conclusions 718
Selected References 718
Learning Aids for This Chapter on CD-ROM 719
Problems 719
Case 15.1 Brainy Business 729
Preview of an Added Case on CD-ROM 731
Case 15.2 Smart Steering Support 731

CHAPTER 16
Markov Chains 732
16.1 Stochastic Processes 732
16.2 Markov Chains 734
16.3 Chapman-Kolmogorov Equations 739
16.4 Classification of States of a Markov Chain 742
16.5 Long-Run Properties of Markov Chains 744
16.6 First Passage Times 750
16.7 Absorbing States 752
16.8 Continuous Time Markov Chains 755
Selected References 759
Learning Aids for This Chapter on CD-ROM 760
Problems 760

CHAPTER 17
Queueing Theory 765
17.1 Prototype Example 766
17.2 Basic Structure of Queueing Models 766
17.3 Examples of Real Queueing Systems 771
17.4 The Role of the Exponential Distribution 774
17.5 The Birth-and-Death Process 780
17.6 Queueing Models Based on the Birth-and-Death Process 784
17.7 Queueing Models Involving Nonexponential Distributions 796
17.8 Priority-Discipline Queueing Models 804
17.9 Queueing Networks 809
17.10 The Application of Queueing Theory 813
17.11 Conclusions 817
Selected References 818
Learning Aids for This Chapter on CD-ROM 818
Problems 819
Case 17.1 Reducing In-Process Inventory 831
Preview of an Added Case on CD-ROM 832
Case 17.2 Queueing Quandary 832

CHAPTER 18
Inventory Theory 833
18.1 Examples 834
18.2 Components of Inventory Models 836
18.3 Deterministic Continuous-Review Models 838
18.4 A Deterministic Periodic-Review Model 848
18.5 Deterministic Multiechelon Inventory Models for Suply Chain Management 852
18.6 A Stochastic Continuous-Review Model 870
18.7 A Stochastic Single-Period Model for Perishable Products 875
18.8 Larger Inventory Systems in Practice 886
18.9 Conclusions 889
Selected References 890
Learning Aids for This Chapter on CD-ROM 891
Problems 891
Case 18.1 Brushing Up on Inventory Control 900
Previews of Added Cases on CD-ROM 902
Case 18.2 TNT: Tackling Newsboy?s Teachings 902
Case 18.3 Jettisoning Surplus Stock 902

CHAPTER 19
Markov Decision Processes 903
19.1 A Prototype Example 903
19.2 A Model for Markov Decision Processes 906
19.3 Linear Programming and Optimal Policies 908
19.4 Policy Improvement Algorithm for Finding Optimal Policies 912
19.5 Discounted Cost Criterion 917
19.6 Conclusions 924
Selected References 925
Learning Aids for This Chapter on CD-ROM 925
Problems 926

CHAPTER 20
Simulation 930
20.1 The Essence of Simulation 930
20.2 Some Common Types of Applications of Simulation 942
20.3 Generation of Random Numbers 946
20.4 Generation of Random Observations from a Probability Distribution 950
20.5 Outline of a Major Simulation Study 954
20.6 Performing Simulations on Spreadsheets 959
20.7 Optimizing with OptQuest 978
20.8 Conclusions 991
Selected References 993
Learning Aids for This Chapter on CD-ROM 993
Problems 994
Case 20.1 Reducing In-Process Inventory (Revisited) 1001
Case 20.2 Action Adventures 1001
Previews of Added Cases on CD-ROM 1002
Case 20.3 Planning Planers 1002
Case 20.4 Pricing under Pressure 1002
APPENDIXES
1. Documentation for the OR Courseware 1003
2. Convexity 1006
3. Classical Optimization Methods 1011
4. Matrices and Matrix Operations 1014
5. Table for a Normal Distribution 1019
PARTIAL ANSWERS TO SELECTED PROBLEMS 1021
INDEXES
Author Index 1035
Subject Index 1038
SUPPLEMENTS ON THE CD-ROM AND THE
ONLINE LEARNING CENTER
ADDITIONAL CASES
Case 3.2 Cutting Cafeteria Costs
Case 3.3 Staffing a Call Center
Case 3.4 Promoting a Breakfast Cereal
Case 4.2 New Frontiers
Case 4.3 Assigning Students to Schools
Case 6.2 Farm Management
Case 6.3 Assigning Students to Schools (Revisited)
Case 6.4 Writing a Nontechnical Memo
Case 8.2 Continuation of the Texago Case Study
Case 8.3 Project Pickings
Case 9.2 Aiding Allies
Case 9.3 Steps to Success
Case 11.2 Assigning Art
Case 11.3 Stocking Sets
Case 11.4 Assigning Students to Schools (Revisited Again)
Case 12.2 International Investments
Case 12.3 Promoting a Breakfast Cereal (Revisited)
Case 15.2 Smart Steering Support
Case 17.2 Queueing Quandary
Case 18.2 TNT: Tackling Newsboy?s Teachings
Case 18.3 Jettisoning Surplus Stock
Case 20.3 Planning Planers
Case 20.4 Pricing under Pressure
SUPPLEMENT TO APPENDIX 3.1
More about LINGO
SUPPLEMENT TO CHAPTER 7
Linear Goal Programming and Its Solution Procedures
Problems
Case 7S.1 A Cure for Cuba
Case 7S.2 Airport Security
SUPPLEMENT TO CHAPTER 8
A Case Study with Many Transportation Problems
SUPPLEMENT 1 TO CHAPTER 18
Derivation of the Optimal Policy for the Stochastic Single-Period Model for Perishable
Products
Problems
SUPPLEMENT 2 TO CHAPTER 18
Stochastic Periodic-Review Models
Problems
SUPPLEMENT 1 TO CHAPTER 20
Variance-Reducing Techniques
Problems
SUPPLEMENT 2 TO CHAPTER 20
Regenerative Method of Statistical Analysis
Problems

CHAPTER 21
The Art of Modeling with Spreadsheets
21.1 A Case Study: The Everglade Golden Years Company Cash Flow Problem
21.2 Overview of the Process of Modeling with Spreadsheets
21.3 Some Guidelines for Building ?Good? Spreadsheet Models
21.4 Debugging a Spreadsheet Model
21.5 Conclusions
Selected References
Learning Aids for This Chapter on CD-ROM
Problems
Case 21.1 Prudent Provisions for Pensions

CHAPTER 22
Project Management with PERT/CPM
22.1 A Prototype Example?The Reliable Construction Co. Project
22.2 Using a Network to Visually Display a Project
22.3 Scheduling a Project with PERT/CPM
22.4 Dealing with Uncertain Activity Durations
22.5 Considering Time-Cost Trade-Offs
22.6 Scheduling and Controlling Project Costs
22.7 An Evaluation of PERT/CPM
22.8 Conclusions
Selected References
Learning Aids for This Chapter on CD-ROM
Problems
Case 22.1 ?School?s out forever . . .?

CHAPTER 23
Additional Special Types of Linear Programming Problems
23.1 The Transshipment Problem
23.2 Multidivisional Problems
23.3 The Decomposition Principle for Multidivisional Problems
23.4 Multitime Period Problems
23.5 Multidivisional Multitime Period Problems
23.6 Stochastic Programming
23.7 Chance-Constrained Programming
23.8 Conclusions
Selected References
Problems

CHAPTER 24
Probability Theory
24.1 Sample Space
24.2 Random Variables
24.3 Probability and Probability Distributions
24.4 Conditional Probability and Independent Events
24.5 Discrete Probability Distributions
24.6 Continuous Probability Distributions
24.7 Expectation
24.8 Moments
24.9 Bivariate Probability Distribution
24.10 Marginal and Conditional Probability Distributions
24.11 Expectations for Bivariate Distributions
24.12 Independent Random Variables and Random Samples
24.13 Law of Large Numbers
24.14 Central Limit Theorem
24.15 Functions of Random Variables
Selected References
Problems

CHAPTER 25
Reliability
25.1 Structure Function of a System
25.2 System Reliability
25.3 Calculation of Exact System Reliability
25.4 Bounds on System Reliability
25.5 Bounds on Reliability Based upon Failure Times
25.6 Conclusions
Selected References
Problems

CHAPTER 26
The Application of Queueing Theory
26.1 Examples
26.2 Decision Making
26.3 Formulation of Waiting-Cost Functions
26.4 Decision Models
26.5 The Evaluation of Travel Time
26.6 Conclusions
Selected References
Learning Aids for This Chapter on CD-ROM
Problems

CHAPTER 27
Forecasting
27.1 Some Applications of Forecasting
27.2 Judgmental Forecasting Methods
27.3 Time Series
27.4 Forecasting Methods for a Constant-Level Model
27.5 Incorporating Seasonal Effects into Forecasting Methods
27.6 An Exponential Smoothing Method for a Linear Trend Model
27.7 Times Series Forecasting with CB Predictor
27.8 Forecasting Errors
27.9 Box-Jenkins Method
27.10 Causal Forecasting with Linear Regression
27.11 Forecasting in Practice
27.12 Conclusions
Selected References
Learning Aids for This Chapter on CD-ROM
Problems
Case 27.1 Finagling the Forecasts

CHAPTER 28
Examples of Performing Simulations on Spreadsheets with Crystal Ball
28.1 Bidding for a Construction Project
28.2 Project Management
28.3 Cash Flow Management
28.4 Financial Risk Analysis
28.5 Revenue Management in the Travel Industry
28.6 Choosing the Right Distribution
28.7 Decision Making with Decision Tables
28.8 Conclusions