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
Problems 6
CHAPTER 2 Overview of the Operations Research Modeling Approach 7
2.1 Defining the Problem and Gathering Data 7
2.2 Formulating a Mathematical Model 10
2.3 Deriving Solutions from the Model 14
2.4 Testing the Model 16
2.5 Preparing to Apply the Model 18
2.6 Implementation 20
2.7 Conclusions 21
Selected References 22
Problems 22
CHAPTER 3 Introduction to Linear Programming 24
3.1 Prototype Example 25
3.2 The Linear Programming Model 31
3.3 Assumptions of Linear Programming 36
3.4 Additional Examples 44
3.5 Some Case Studies 61
3.6 Displaying and Solving Linear Programming Models on a Spreadsheet 67
3.7 Formulating Very Large Linear Programming Models 73
3.8 Conclusions 79
Appendix 3.1 The LINGO Modeling Language 79
Selected References 89
Learning Aids for This Chapter in Your OR Courseware 90
Problems 90
Case 3.1 Auto Assembly 103
Case 3.2 Cutting Cafeteria Costs 104
Case 3.3 Staffing a Call Center 106
CHAPTER 4 Solving Linear Programming Problems：The Simplex Method 109
4.1 The Essence of the Simplex Method 109
4.2 Setting Up the Simplex Method 114
4.3 The Algebra of the Simplex Method 118
4.4 The Simplex Method in Tabular Form 123
4.5 Tie Breaking in the Simplex Method 128
4.6 Adapting to Other Model Forms 132
4.7 Postoptimality Analysis 152
4.8 Computer Implementation 160
4.9 The Interior-Point Approach to Solving Linear Programming Problems 163
4.10 Conclusions 168
Appendix 4.1 An Introduction to Using LINDO 169
Selected References 171
Learning Aids for This Chapter in Your OR Courseware 172
Problems 172
Case 4.1 Fabrics and Fall Fashions 182
Case 4.2 New Frontiers 185
Case 4.3 Assigning Students to Schools 188
CHAPTER 5 The Theory of the Simplex Method 190
5.1 Foundations of the Simplex Method 190
5.2 The Revised Simplex Method 202
5.3 A Fundamental Insight 212
5.4 Conclusions 220
Selected References 220
Learning Aids for This Chapter in Your OR Courseware 221
Problems 221
CHAPTER 6 Duality Theory and Sensitivity Analysis 230
6.1 The Essence of Duality Theory 231
6.2 Economic Interpretation of Duality 239
6.3 Primal-Dual Relationships 242
6.4 Adapting to Other Primal Forms 247
6.5 The Role of Duality Theory in Sensitivity Analysis 252
6.6 The Essence of Sensitivity Analysis 254
6.7 Applying Sensitivity Analysis 262
6.8 Conclusions 284
Selected References 284
Learning Aids for This Chapter in Your OR Courseware 285
Problems 285
Case 6.1 Controlling Air Pollution 302
Case 6.2 Farm Management 304
Case 6.3 Assigning Students to Schools（Revisited） 307
CHAPTER 7 Other Algorithms for Linear Programming 309
7.1 The Dual Simplex Method 309
7.2 Parametric Linear Programming 312
7.3 The Upper Bound Technique 317
7.4 An Interior-Point Algorithm 320
7.5 Linear Goal Programming and Its Solution Procedures 332
7.6 Conclusions 339
Selected References 340
Learning Aids for This Chapter in Your OR Courseware 340
Problems 341
Case 7.1 A Cure for Cuba 347
CHAPTER 8 The Transportation and Assignment Problems 350
8.1 The Transportation Problem 351
8.2 A Streamlined Simplex Method for the Transportation Problem 365
8.3 The Assignment Problem 381
8.4 Conclusions 391
Selected References 391
Learning Aids for This Chapter in Your OR Courseware 392
Problems 392
Case 8.1 Shipping Wood to Market 401
Case 8.2 Project Pickings 402
CHAPTER 9 Network Optimization Models 405
9.1 Prototype Example 406
9.2 The Terminology of Networks 407
9.3 The Shortest-Path Problem 411
9.4 The Minimum Spanning Tree Problem 415
9.5 The Maximum Flow Problem 420
9.6 The Minimum Cost Flow Problem 429
9.7 The Network Simplex Method 438
9.8 Conclusions 448
Selected References 449
Learning Aids for This Chapter in Your OR Courseware 449
Problems 450
Case 9.1 Aiding Allies 458
Case 9.2 Money in Motion 464
CHAPTER 10 Project Management with PERT/CPM 468
10.1 A Prototype Example—The Reliable Construction Co.Project 469
10.2 Using a Network to Visually Display a Project 470
10.3 Scheduling a Project with PERT/CPM 475
10.4 Dealing with Uncertain Activity Durations 485
10.5 Considering Time-Cost Trade-Offs 492
10.6 Scheduling and Controlling Project Costs 502
10.7 An Evaluation of PERT/CPM 508
10.8 Conclusions 512
Selected References 513
Learning Aids for This Chapter in Your OR Courseware 514
Problems 514
Case 10.1 Steps to Success 524
Case 10.2 “School’s out forever！！” 527
CHAPTER 11 Dynamic Programming 533
11.1 A Prototype Example for Dynamic Programming 533
11.2 Characteristics of Dynamic Programming Problems 538
11.3 Deterministic Dynamic Programming 541
11.4 Probabilistic Dynamic Programming 562
11.5 Conclusions 568
Selected References 568
Learning Aids for This Chapter in Your OR Courseware 568
Problems 569
CHAPTER 12Integer Programming 576
12.1 Prototype Example 577
12.2 Some BIP Applications 580
12.3 Innovative Uses of Binary Variables in Model Formulation 585
12.4 Some Formulation Examples 591
12.5 Some Perspectives on Solving Integer Programming Problems 600
12.6 The Branch-and-Bound Technique and Its Application to Binary Integer Programming 604
12.7 A Branch-and-Bound Algorithm for Mixed Integer Programming 616
12.8 Other Developments in Solving BIP Problems 622
12.9 Conclusions 630
Selected References 631
Learning Aids for This Chapter in Your OR Courseware 631
Problems 632
Case 12.1 Capacity Concerns 642
Case 12.2 Assigning Art 645
Case 12.3 Stocking Sets 649
Case 12.4 Assigning Students to Schools（Revisited Again） 653
CHAPTER 13 Nonlinear Programming 654
13.1 Sample Applications 655
13.2 Graphical Illustration of Nonlinear Programming Problems 659
13.3 Types of Nonlinear Programming Problems 664
13.4 One-Variable Unconstrained Optimization 670
13.5 Multivariable Unconstrained Optimization 673
13.6 The Karush-Kuhn-Tucker （KKT） Conditions for Constrained Optimization 679
13.7 Quadratic Programming 683
13.8 Separable Programming 690
13.9 Convex Programming 697
13.10 Nonconvex Programming 702
13.11 Conclusions 706
Selected References 706
Learning Aids for This Chapter in Your OR Courseware 707
Problems 708
Case 13.1 Savvy Stock Selection 720
CHAPTER 14 Game Theory 726
14.1 The Formulation of Two-Person，Zero-Sum Games 726
14.2 Solving Simple Games—A Prototype Example 728
14.3 Games with Mixed Strategies 733
14.4 Graphical Solution Procedure 735
14.5 Solving by Linear Programming 738
14.6 Extensions 741
14.7 Conclusions 742
Selected References 743
Learning Aids for This Chapter in Your OR Courseware 743
Problems 743
CHAPTER 15 Decision Analysis 749
15.1 A Prototype Example 750
15.2 Decision Making without Experimentation 751
15.3 Decision Making with Experimentation 758
15.4 Decision Trees 764
15.5 Utility Theory 770
15.6 The Practical Application of Decision Analysis 778
15.7 Conclusions 781
Selected References 781
Learning Aids for This Chapter in Your OR Courseware 782
Problems 782
Case 15.1 Brainy Business 795
Case 15.2 Smart Steering Support 798
CHAPTER 16 Markov Chains 802
16.1 Stochastic Processes 802
16.2 Markov Chains 803
16.3 Chapman-Kolmogorov Equations 808
16.4 Classification of States of a Markov Chain 810
16.5 Long-Run Properties of Markov Chains 812
16.6 First Passage Times 818
16.7 Absorbing States 820
16.8 Continuous Time Markov Chains 822
Selected References 827
Learning Aids for This Chapter in Your OR Courseware 828
Problems 828
CHAPTER 17 Queueing Theory 834
17.1 Prototype Example 835
17.2 Basic Structure of Queueing Models 835
17.3 Examples of Real Queueing Systems 840
17.4 The Role of the Exponential Distribution 841
17.5 The Birth-and-Death Process 848
17.6 Queueing Models Based on the Birth-and-Death Process 852
17.7 Queueing Models Involving Nonexponential Distributions 871
17.8 Priority-Discipline Queueing Models 879
17.9 Queueing Networks 885
17.10 Conclusions 889
Selected References 890
Learning Aids for This Chapter in Your OR Courseware 890
Problems 891
Case 17.1 Reducing In-Process Inventory 905
CHAPTER 18 The Application of Queueing Theory 907
18.1 Examples 907
18.2 Decision Making 909
18.3 Formulation of Waiting-Cost Functions 912
18.4 Decision Models 917
18.5 Some Award-Winning Applications of Queueing Theory 923
18.6 Conclusions 926
Selected References 926
Learning Aids for This Chapter in Your OR Courseware 926
Problems 927
Case 18.1 Queueing Quandary 932
CHAPTER 19 Inventory Theory 935
19.1 Examples 936
19.2 Components of Inventory Models 938
19.3 Deterministic Continuous-Review Models 941
19.4 A Deterministic Periodic-Review Model 951
19.5 A Stochastic Continuous-Review Model 956
19.6 A Stochastic Single-Period Model for Perishable Products 961
19.7 Stochastic Periodic-Review Models 975
19.8 Larger Inventory Systems in Practice 983
19.9 Conclusions 987
Selected References 987
Learning Aids for This Chapter in Your OR Courseware 987
Problems 988
Case 19.1 Brushing Up on Inventory Control 1000
Case 19.2 TNT：Tackling Newsboy’s Teachings 1002
Case 19.3 Jettisoning Surplus Stock 1004
CHAPTER 20 Forecasting 1009
20.1 Some Applications of Forecasting 1010
20.2 Judgmental Forecasting Methods 1013
20.3 Time Series 1014
20.4 Forecasting Methods for a Constant-Level Model 1016
20.5 Incorporating Seasonal Effects into Forecasting Methods 1018
20.6 An Exponential Smoothing Method for a Linear Trend Model 1021
20.7 Forecasting Errors 1025
20.8 Box-Jenkins Method 1026
20.9 Causal Forecasting with Linear Regression 1028
20.10 Forecasting in Practice 1036
20.11 Conclusions 1038
Selected References 1038
Learning Aids for This Chapter in Your OR Courseware 1038
Problems 1039
Case 20.1 Finagling the Forecasts 1048
CHAPTER 21 Markov Decision Processes 1053
21.1 A Prototype Example 1053
21.2 A Model for Markov Decision Processes 1056
21.3 Linear Programming and Optimal Policies 1059
21.4 Policy Improvement Algorithm for Finding Optimal Policies 1064
21.5 Discounted Cost Criterion 1069
Selected References 1077
Learning Aids for This Chapter in Your OR Courseware 1078
Problems 1078
CHAPTER 22 Simulation 1084
22.1 The Essence of Simulation 1084
22.2 Some Common Types of Applications of Simulation 1097
22.3 Generation of Random Numbers 1101
22.4 Generation of Random Observations from a Probability Distribution 1105
22.5 Outline of a Major Simulation Study 1110
22.6 Performing Simulations on Spreadsheets 1115
22.7 Variance-Reducing Techniques 1126
22.8 Regenerative Method of Statistical Analysis 1131
22.9 Conclusions 1138
Selected References 1140
Learning Aids for This Chapter in Your OR Courseware 1140
Problems 1141
Case 22.1 Planning Planers 1151
Case 22.2 Pricing under Pressure 1153
APPENDIXES 1156
1.Documentation for the OR Courseware 1156
2.Convexity 1159
3.Classical Optimization Methods 1165
4.Matrices and Matrix Operations 1169
5.Tables 1174
PARTIAL ANSWERS TO SELECTED PROBLEMS 1176
INDEXES 1195
Author Index 1195
Subject Index 1199