Introduction to Operations Research

Contents......Page 3
Website......Page 10
Preface......Page 14
THE ORIGINS OF OPERATIONS RESEARCH......Page 23
THE NATURE OF OPERATIONS RESEARCH......Page 24
THE RISE OF ANALYTICS TOGETHER WITH OPERATIONS RESEARCH......Page 25
THE IMPACT OF OPERATIONS RESEARCH......Page 27
ALGORITHMS AND OR COURSEWARE......Page 29
PROBLEMS......Page 31
DEFINING THE PROBLEM AND GATHERING DATA......Page 32
FORMULATING A MATHEMATICAL MODEL......Page 35
DERIVING SOLUTIONS FROM THE MODEL......Page 37
TESTING THE MODEL......Page 40
PREPARING TO APPLY THE MODEL......Page 41
IMPLEMENTATION......Page 42
SELECTED REFERENCES......Page 43
PROBLEMS......Page 45
Intro to Linear Programming......Page 47
PROTOTYPE EXAMPLE......Page 48
THE LINEAR PROGRAMMING MODEL......Page 54
ASSUMPTIONS OF LINEAR PROGRAMMING......Page 60
ADDITIONAL EXAMPLES......Page 66
FORMULATING AND SOLVING LINEAR PROGRAMMING  MODELS ON A SPREADSHEET......Page 84
FORMULATING VERY LARGE LINEAR PROGRAMMING MODELS......Page 93
SELECTED REFERENCES......Page 101
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 102
PROBLEMS......Page 103
CASES CASE 3.1 Auto Assembly......Page 112
CASE 3.4 Promoting a Breakfast Cereal......Page 114
THE ESSENCE OF THE SIMPLEX METHOD......Page 115
SETTING UP THE SIMPLEX METHOD......Page 120
THE ALGEBRA OF THE SIMPLEX METHOD......Page 123
THE SIMPLEX METHOD IN TABULAR FORM......Page 129
TIE BREAKING IN THE SIMPLEX METHOD......Page 134
ADAPTING TO OTHER MODEL FORMS......Page 137
POSTOPTIMALITY ANALYSIS......Page 155
COMPUTER IMPLEMENTATION......Page 163
THE INTERIOR-POINT APPROACH TO SOLVING LINEAR PROGRAMMING PROBLEMS......Page 165
APPENDIX 4.1 AN INTRODUCTION TO USING LINDO AND LINGO......Page 169
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 173
PROBLEMS......Page 174
CASES......Page 182
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 184
FOUNDATIONS OF THE SIMPLEX METHOD......Page 185
THE SIMPLEX METHOD IN MATRIX FORM......Page 196
A FUNDAMENTAL INSIGHT......Page 205
THE REVISED SIMPLEX METHOD......Page 208
SELECTED REFERENCES......Page 211
PROBLEMS......Page 212
THE ESSENCE OF DUALITY THEORY......Page 219
ECONOMIC INTERPRETATION OF DUALITY......Page 227
PRIMAL–DUAL RELATIONSHIPS......Page 230
ADAPTING TO OTHER PRIMAL FORMS......Page 235
THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS......Page 239
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 242
PROBLEMS......Page 243
Linear Programming under Uncertainty......Page 247
THE ESSENCE OF SENSITIVITY ANALYSIS......Page 248
APPLYING SENSITIVITY ANALYSIS......Page 255
PERFORMING SENSITIVITY ANALYSIS ON A SPREADSHEET......Page 272
ROBUST OPTIMIZATION......Page 286
CHANCE CONSTRAINTS......Page 290
STOCHASTIC PROGRAMMING WITH RECOURSE......Page 293
SELECTED REFERENCES......Page 298
PROBLEMS......Page 299
CASES......Page 310
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 311
THE DUAL SIMPLEX METHOD......Page 312
PARAMETRIC LINEAR PROGRAMMING......Page 316
THE UPPER BOUND TECHNIQUE......Page 321
AN INTERIOR-POINT ALGORITHM......Page 323
CONCLUSIONS......Page 334
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 335
PROBLEMS......Page 336
Transportation & Assignment Problems......Page 340
THE TRANSPORTATION PROBLEM......Page 341
A STREAMLINED SIMPLEX METHOD  FOR THE TRANSPORTATION PROBLEM......Page 355
THE ASSIGNMENT PROBLEM......Page 370
A SPECIAL ALGORITHM FOR THE ASSIGNMENT PROBLEM......Page 378
CONCLUSIONS......Page 382
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 383
PROBLEMS......Page 384
CASES......Page 392
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 393
Network Optimization Models......Page 394
PROTOTYPE EXAMPLE......Page 395
THE TERMINOLOGY OF NETWORKS......Page 396
THE SHORTEST-PATH PROBLEM......Page 399
THE MINIMUM SPANNING TREE PROBLEM......Page 404
THE MAXIMUM FLOW PROBLEM......Page 409
THE MINIMUM COST FLOW PROBLEM......Page 417
THE NETWORK SIMPLEX METHOD......Page 425
A NETWORK MODEL FOR OPTIMIZING A PROJECT’S  TIME-COST TRADE-OFF......Page 435
CONCLUSIONS......Page 446
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 447
PROBLEMS......Page 448
CASES......Page 456
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 459
A PROTOTYPE EXAMPLE FOR DYNAMIC PROGRAMMING......Page 460
CHARACTERISTICS OF DYNAMIC PROGRAMMING PROBLEMS......Page 465
DETERMINISTIC DYNAMIC PROGRAMMING......Page 467
PROBABILISTIC DYNAMIC PROGRAMMING......Page 484
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 490
PROBLEMS......Page 491
Integer Programming......Page 496
PROTOTYPE EXAMPLE......Page 497
SOME BIP APPLICATIONS......Page 500
INNOVATIVE USES OF BINARY VARIABLES  IN MODEL FORMULATION......Page 505
SOME FORMULATION EXAMPLES......Page 511
SOME PERSPECTIVES ON SOLVING INTEGER  PROGRAMMING PROBLEMS......Page 519
THE BRANCH-AND-BOUND TECHNIQUE AND ITS APPLICATION  TO BINARY INTEGER PROGRAMMING......Page 523
A BRANCH-AND-BOUND ALGORITHM FOR MIXED  INTEGER PROGRAMMING......Page 535
THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS......Page 541
THE INCORPORATION OF CONSTRAINT PROGRAMMING......Page 547
CONCLUSIONS......Page 553
SELECTED REFERENCES......Page 554
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 555
PROBLEMS......Page 556
CASES......Page 565
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 567
Nonlinear Programming......Page 569
SAMPLE APPLICATIONS......Page 570
GRAPHICAL ILLUSTRATION OF NONLINEAR  PROGRAMMING PROBLEMS......Page 574
TYPES OF NONLINEAR PROGRAMMING PROBLEMS......Page 578
ONE-VARIABLE UNCONSTRAINED OPTIMIZATION......Page 584
MULTIVARIABLE UNCONSTRAINED OPTIMIZATION......Page 589
THE KARUSH-KUHN-TUCKER (KKT) CONDITIONS  FOR CONSTRAINED OPTIMIZATION......Page 595
QUADRATIC PROGRAMMING......Page 599
SEPARABLE PROGRAMMING......Page 605
CONVEX PROGRAMMING......Page 612
NONCONVEX PROGRAMMING (WITH SPREADSHEETS)......Page 620
CONCLUSIONS......Page 624
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 625
PROBLEMS......Page 626
CASES......Page 637
PREVIEWS OF ADDED CASES ON OUR WEBSITE, (www.mhhe.com/hillier)......Page 638
Metaheuristics......Page 639
THE NATURE OF METAHEURISTICS......Page 640
TABU SEARCH......Page 647
SIMULATED ANNEALING......Page 658
GENETIC ALGORITHMS......Page 667
CONCLUSIONS......Page 677
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 678
PROBLEMS......Page 679
THE FORMULATION OF TWO-PERSON, ZERO-SUM GAMES......Page 683
SOLVING SIMPLE GAMES—A PROTOTYPE EXAMPLE......Page 685
GAMES WITH MIXED STRATEGIES......Page 690
GRAPHICAL SOLUTION PROCEDURE......Page 692
SOLVING BY LINEAR PROGRAMMING......Page 694
EXTENSIONS......Page 698
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 699
PROBLEMS......Page 700
Decision Analysis......Page 704
A PROTOTYPE EXAMPLE......Page 705
DECISION MAKING WITHOUT EXPERIMENTATION......Page 706
DECISION MAKING WITH EXPERIMENTATION......Page 712
DECISION TREES......Page 718
USING SPREADSHEETS TO PERFORM SENSITIVITY  ANALYSIS ON DECISION TREES......Page 722
UTILITY THEORY......Page 730
THE PRACTICAL APPLICATION OF DECISION ANALYSIS......Page 738
SELECTED REFERENCES......Page 739
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 740
PROBLEMS......Page 741
CASES......Page 751
PREVIEW OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 753
Queueing Theory......Page 754
BASIC STRUCTURE OF QUEUEING MODELS......Page 755
EXAMPLES OF REAL QUEUEING SYSTEMS......Page 760
THE ROLE OF THE EXPONENTIAL DISTRIBUTION......Page 762
THE BIRTH-AND-DEATH PROCESS......Page 768
QUEUEING MODELS BASED ON THE BIRTH-AND-DEATH PROCESS......Page 773
QUEUEING MODELS INVOLVING  NONEXPONENTIAL DISTRIBUTIONS......Page 785
PRIORITY-DISCIPLINE QUEUEING MODELS......Page 793
QUEUEING NETWORKS......Page 798
THE APPLICATION OF QUEUEING THEORY......Page 802
SELECTED REFERENCES......Page 807
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 808
PROBLEMS......Page 809
CASES......Page 821
PREVIEW OF AN ADDED CASE ON OUR WEBSITE (www.mhhe.com/hillier)......Page 822
Inventory Theory......Page 823
EXAMPLES......Page 824
COMPONENTS OF INVENTORY MODELS......Page 826
DETERMINISTIC CONTINUOUS-REVIEW MODELS......Page 828
A DETERMINISTIC PERIODIC-REVIEW MODEL......Page 838
DETERMINISTIC MULTIECHELON INVENTORY MODELS FOR SUPPLY CHAIN MANAGEMENT......Page 843
A STOCHASTIC CONTINUOUS-REVIEW MODEL......Page 861
A STOCHASTIC SINGLE-PERIOD MODEL  FOR PERISHABLE PRODUCTS......Page 865
REVENUE MANAGEMENT......Page 877
SELECTED REFERENCES......Page 885
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 886
PROBLEMS......Page 887
CASES......Page 897
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 899
Markov Decision Processes......Page 900
A PROTOTYPE EXAMPLE......Page 901
A MODEL FOR MARKOV DECISION PROCESSES......Page 903
LINEAR PROGRAMMING AND OPTIMAL POLICIES......Page 906
CONCLUSIONS......Page 910
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 911
PROBLEMS......Page 912
THE ESSENCE OF SIMULATION......Page 915
SOME COMMON TYPES OF APPLICATIONS OF SIMULATION......Page 927
GENERATION OF RANDOM NUMBERS......Page 931
GENERATION OF RANDOM OBSERVATIONS  FROM A PROBABILITY DISTRIBUTION......Page 935
OUTLINE OF A MAJOR SIMULATION STUDY......Page 940
PERFORMING SIMULATIONS ON SPREADSHEETS......Page 944
CONCLUSIONS......Page 962
SELECTED REFERENCES......Page 964
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)......Page 965
PROBLEMS......Page 966
CASES......Page 973
PREVIEWS OF ADDED CASES ON OUR WEBSITE (www.mhhe.com/hillier)......Page 974
Documentation for OR Courseware......Page 975
Convexity......Page 977
Classical Optimization Methods......Page 982
Matrices & Matrix Operations......Page 985
Normal Distribution Table......Page 990
Art of Modeling with Spreadsheets......Page 1080
A  CASE  STUDY:  THE  EVERGLADE  GOLDEN  YEARS  COMPANY  CASH  FLOW  PROBLEM......Page 1081
OVERVIEW  OF  THE  PROCESS  OF  MODELING  WITH  SPREADSHEETS......Page 1082
SOME  GUIDELINES  FOR  BUILDING  “GOOD”  SPREADSHEET  MODELS......Page 1092
DEBUGGING A SPREADSHEET MODEL......Page 1098
CONCLUSIONS......Page 1100
LEARNING  AIDS  FOR  THIS  CHAPTER  ON  THIS WEBSITE......Page 1101
PROBLEMS......Page 1102
CASES......Page 1104
Project Management with PERT/CPM......Page 1106
A PROTOTYPE EXAMPLE—THE RELIABLE  CONSTRUCTION CO. PROJECT......Page 1107
USING A NETWORK TO VISUALLY DISPLAY A PROJECT......Page 1108
SCHEDULING A PROJECT WITH PERT/CPM......Page 1110
DEALING WITH UNCERTAIN ACTIVITY DURATIONS......Page 1120
CONSIDERING TIME-COST TRADE-OFFS......Page 1126
SCHEDULING AND CONTROLLING PROJECT COSTS......Page 1135
AN EVALUATION OF PERT/CPM......Page 1142
CONCLUSIONS......Page 1146
CASE......Page 1155
Additional Special Types of Linear Programming Problems......Page 1159
THE TRANSSHIPMENT PROBLEM......Page 1160
MULTIDIVISIONAL  PROBLEMS......Page 1165
THE DECOMPOSITION PRINCIPLE FOR  MULTIDIVISIONAL PROBLEMS......Page 1169
MULTITIME PERIOD PROBLEMS......Page 1177
MULTIDIVISIONAL MULTITIME PERIOD PROBLEMS......Page 1180
SELECTED REFERENCES PROBLEMS......Page 1182
Probability Theory......Page 1186
RANDOM VARIABLES......Page 1188
PROBABILITY AND PROBABILITY DISTRIBUTIONS......Page 1189
CONDITIONAL PROBABILITY AND INDEPENDENT EVENTS......Page 1193
DISCRETE PROBABILITY DISTRIBUTIONS......Page 1195
CONTINUOUS PROBABILITY DISTRIBUTIONS......Page 1199
EXPECTATION......Page 1205
MOMENTS......Page 1207
BIVARIATE PROBABILITY DISTRIBUTION......Page 1208
MARGINAL AND CONDITIONAL PROBABILITY DISTRIBUTIONS......Page 1212
EXPECTATIONS FOR BIVARIATE DISTRIBUTIONS......Page 1215
INDEPENDENT RANDOM VARIABLES AND RANDOM SAMPLES......Page 1217
CENTRAL LIMIT THEOREM......Page 1219
FUNCTIONS OF RANDOM VARIABLES......Page 1220
SELECTED REFERENCES......Page 1223
PROBLEMS......Page 1224
STRUCTURE FUNCTION OF A SYSTEM......Page 1227
SYSTEM RELIABILITY......Page 1229
CALCULATION OF EXACT SYSTEM RELIABILITY......Page 1231
BOUNDS ON SYSTEM RELIABILITY......Page 1235
BOUNDS ON RELIABILITY BASED UPON FAILURE TIMES......Page 1236
SELECTED REFERENCES......Page 1239
PROBLEMS......Page 1240
EXAMPLES......Page 1242
DECISION  MAKING......Page 1244
FORMULATION OF WAITING-COST FUNCTIONS......Page 1247
DECISION  MODELS......Page 1251
THE EVALUATION OF TRAVEL TIME......Page 1256
CONCLUSIONS......Page 1261
SELECTED REFERENCES LEARNING AIDS FOR THIS CHAPTER ON THIS WEBSITE PROBLEMS......Page 1262
Forecasting......Page 1267
SOME  APPLICATIONS  OF  FORECASTING......Page 1268
JUDGMENTAL FORECASTING METHODS......Page 1270
TIME SERIES......Page 1271
FORECASTING METHODS FOR A CONSTANT-LEVEL MODEL......Page 1272
INCORPORATING SEASONAL EFFECTS INTO FORECASTING METHODS......Page 1275
AN EXPONENTIAL SMOOTHING METHOD FOR A LINEAR TREND MODEL......Page 1278
FORECASTING ERRORS......Page 1281
BOX-JENKINS METHOD......Page 1282
CAUSAL FORECASTING WITH LINEAR REGRESSION......Page 1284
FORECASTING IN PRACTICE......Page 1292
CONCLUSIONS SELECTED REFERENCES......Page 1294
LEARNING AIDS FOR THIS CHAPTER ON THIS WEBSITE PROBLEMS......Page 1295
CASE......Page 1304
BIDDING FOR A CONSTRUCTION PROJECT......Page 1308
PROJECT MANAGEMENT......Page 1313
CASH FLOW MANAGEMENT......Page 1319
FINANCIAL RISK ANALYSIS......Page 1325
REVENUE MANAGEMENT IN THE TRAVEL INDUSTRY......Page 1329
CHOOSING THE RIGHT DISTRIBUTION......Page 1335
DECISION MAKING WITH PARAMETER ANALYSIS REPORTS AND TREND CHARTS......Page 1348
SUMMARY......Page 1351
PROBLEMS......Page 1352
ACKNOWLEDGMENT......Page 1354
STOCHASTIC PROCESSES......Page 1355
MARKOV CHAINS......Page 1357
CHAPMAN-KOLMOGOROV EQUATIONS......Page 1363
CLASSIFICATION OF STATES OF A MARKOV CHAIN......Page 1366
LONG-RUN PROPERTIES OF MARKOV CHAINS......Page 1369
FIRST PASSAGE TIMES......Page 1375
ABSORBING STATES......Page 1377
CONTINUOUS TIME MARKOV CHAINS......Page 1380
LEARNING AIDS FOR THIS CHAPTER ON THIS WEBSITE......Page 1385
PROBLEMS......Page 1386