Operations research an introduction

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Contents......Page 8
What’s New in the Tenth Edition......Page 24
Acknowledgments......Page 26
About the Author......Page 28
Trademarks......Page 30
 1.2 Operations Research Models......Page 32
 1.3 Solving the OR Model......Page 35
 1.4 Queuing and Simulation Models......Page 36
 1.5 Art of Modeling......Page 37
 1.6 More than Just Mathematics......Page 38
 1.7 Phases of an OR Study......Page 40
 Bibliography......Page 42
 Problems......Page 43
 2.1 Two-Variable LP Model......Page 46
 2.2 Graphical LP Solution......Page 48
  2.2.1 Solution of a Maximization Model......Page 49
  2.2.2 Solution of a Minimization Model......Page 51
  2.3.1 LP Solution with Excel Solver......Page 53
  2.3.2 LP Solution with AMPL......Page 57
 2.4 Linear Programming Applications......Page 60
  2.4.1 Investment......Page 61
  2.4.2 Production Planning and Inventory Control......Page 63
  2.4.3 Workforce Planning......Page 68
  2.4.4 Urban Development Planning......Page 71
  2.4.5 Blending and Refining......Page 74
 Problems......Page 77
 3.1 LP Model in Equation Form......Page 100
 3.2 Transition from Graphical to Algebraic Solution......Page 101
  3.3.1 Iterative Nature of the Simplex Method......Page 104
  3.3.2 Computational Details of the Simplex Algorithm......Page 106
  3.3.3 Summary of the Simplex Method......Page 112
  3.4.1 M-Method......Page 113
  3.4.2 Two-Phase Method......Page 116
 3.5 Special Cases in the Simplex Method......Page 118
  3.5.1 Degeneracy......Page 119
  3.5.2 Alternative Optima......Page 120
  3.5.3 Unbounded Solution......Page 122
  3.5.4 Infeasible Solution......Page 123
 3.6 Sensitivity Analysis......Page 124
  3.6.1 Graphical Sensitivity Analysis......Page 125
  3.6.2 Algebraic Sensitivity Analysis—Changes in the Right-Hand Side......Page 129
  3.6.3 Algebraic Sensitivity Analysis—Objective Function......Page 133
  3.6.4 Sensitivity Analysis With Tora, Solver, and AMPL......Page 137
   3.7 Computational Issues In Linear Programming13......Page 139
 Bibliography......Page 143
 Problems......Page 146
 4.1 Definition of the Dual Problem......Page 170
  4.2.1 Review of Simple Matrix Operations......Page 173
  4.2.2 Simplex Tableau Layout......Page 174
  4.2.3 Optimal Dual Solution......Page 175
  4.2.4 Simplex Tableau Computations......Page 178
 4.3 Economic Interpretation of Duality......Page 179
 4.3.1 Economic Interpretation of Dual Variables......Page 180
 4.3.2 Economic Interpretation of Dual Constraints......Page 181
  4.4.1 Dual Simplex Algorithm......Page 183
  4.4.2 Generalized Simplex Algorithm......Page 185
 4.5 Post-Optimal Analysis......Page 186
  4.5.1 Changes Affecting Feasibility......Page 187
  4.5.2 Changes Affecting Optimality......Page 190
 Problems......Page 193
 5.1 Definition of the Transportation Model......Page 208
 5.2 Nontraditional Transportation Models......Page 212
 5.3 The Transportation Algorithm......Page 215
  5.3.1 Determination of the Starting Solution......Page 217
  5.3.2 Iterative Computations of the Transportation Algorithm......Page 221
  5.3.3 Simplex Method Explanation of the Method of Multipliers......Page 227
  5.4.1 The Hungarian Method......Page 228
  5.4.2 Simplex Explanation of the Hungarian Method......Page 231
 Bibliography......Page 232
 Problems......Page 237
 6.1 Scope and Definition of Network Models......Page 248
 6.2 Minimal Spanning Tree Algorithm......Page 251
 6.3 Shortest-route Problem......Page 252
  6.3.1 Examples of the Shortest-Route Applications......Page 253
  6.3.2 Shortest-Route Algorithms......Page 256
  6.3.3 Linear Programming Formulation of the Shortest-Route Problem......Page 262
 6.4 Maximal Flow Model......Page 266
  6.4.1 Enumeration of Cuts......Page 267
  6.4.2 Maximal Flow Algorithm......Page 268
  6.4.3 Linear Programming Formulation of Maximal Flow Mode......Page 273
 6.5 CPM and Pert......Page 274
  6.5.1 Network Representation......Page 275
  6.5.2 Critical Path Method (CPM) Computations......Page 277
  6.5.3 Construction of the Time Schedule......Page 280
  6.5.4 Linear Programming Formulation of CPM......Page 283
  6.5.5 Pert Networks......Page 284
 Bibliography......Page 286
 Problems......Page 290
 7.1 Simplex Method Fundamentals......Page 306
  7.1.1 From Extreme Points to Basic Solutions......Page 307
  7.1.2 Generalized Simplex Tableau in Matrix Form......Page 310
  7.2.1 Development of the Optimality and Feasibility Conditions......Page 312
  7.2.2 Revised Simplex Algorithm......Page 313
  7.2.3 Computational Issues in the Revised Simplex Method......Page 316
 7.3 Bounded-Variables Algorithm......Page 318
  7.4.2 Optimal Dual Solution......Page 323
  7.5.1 Parametric Changes in C......Page 326
  7.5.2 Parametric Changes in B......Page 328
 7.6 More Linear Programming Topics......Page 330
 Problems......Page 331
 8.1 A Goal Programming Formulation......Page 342
  8.2.1 The Weights Method......Page 344
  8.2.2 The Preemptive Method......Page 346
 Case Study: Allocation of Operating Room Time in Mount Sinai Hospital......Page 351
 Problems......Page 355
 9.1 Illustrative Applications......Page 360
  9.1.1 Capital Budgeting......Page 361
  9.1.2 Set-Covering Problem......Page 362
  9.1.3 Fixed-Charge Problem......Page 363
  9.1.4 Either-Or and If-Then Constraints......Page 365
 9.2 Integer Programming Algorithms......Page 367
  9.2.1 Branch-and-Bound (B&B) Algorithm......Page 368
  9.2.2 Cutting-Plane Algorithm......Page 374
 Bibliography......Page 379
 Problems......Page 380
 10.1 Introduction......Page 398
 10.2 Greedy (Local Search) Heuristics......Page 399
  10.2.1 Discrete Variable Heuristic......Page 400
  10.2.2 Continuous Variable Heuristic......Page 402
  10.3.1 Tabu Search Algorithm......Page 405
  10.3.2 Simulated Annealing Algorithm......Page 409
  10.3.3 Genetic Algorithm......Page 412
 10.4 Application of Metaheuristics to Integer Linear Programs......Page 416
  10.4.1 ILP Tabu Algorithm......Page 417
  10.4.2 ILP Simulated Annealing Algorithm......Page 419
  10.4.3 ILP Genetic Algorithm......Page 421
 10.5 Introduction To Constraint Programming (CP)......Page 424
 Problems......Page 426
 11.1 Scope of the TSP......Page 436
 11.2 TSP Mathematical Model......Page 438
  11.3.1 B&B Algorithm......Page 442
  11.3.2 Cutting-Plane Algorithm......Page 445
  11.4.1 Nearest-Neighbor Heuristic......Page 446
  11.4.2 Reversal Heuristic......Page 447
  11.5.1 TSP Tabu Algorithm......Page 450
  11.5.2 TSP Simulated Annealing Algorithm......Page 453
  11.5.3 TSP Genetic Algorithm......Page 455
 Problems......Page 459
 12.1 Recursive Nature of Dynamic Programming (DP) Computations......Page 470
 12.2 Forward and Backward Recursion......Page 474
 12.3 Selected DP Applications......Page 475
  12.3.1 Knapsack/Fly-Away Kit/cargo-Loading Model......Page 476
  12.3.2 Workforce Size Model......Page 481
  12.3.3 Equipment Replacement Model......Page 483
  12.3.4 Investment Model......Page 486
 12.4 Problem of Dimensionality......Page 489
 Bibliography......Page 491
 Case Study: Optimization of Crosscutting and Log Allocation at Weyerhaeuser......Page 492
 Problems......Page 495
 13.1 Inventory Problem: A Supply Chain Perspective......Page 502
  13.1.1 An Inventory Metric in Supply Chains......Page 503
  13.1.2 Elements of the Inventory Optimization Model......Page 505
 13.2 Role of Demand In the Development of Inventory Models......Page 506
  13.3.1 Classical EOQ Model......Page 508
  13.3.2 EOQ with Price Breaks......Page 512
  13.3.3 Multi-Item EOQ With Storage Limitation......Page 515
 13.4 Dynamic EOQ Models......Page 518
  13.4.1 No-Setup EOQ Model......Page 519
  13.4.2 Setup EOQ Model......Page 522
 13.5 Sticky Issues in Inventory Modeling......Page 531
 Case Study: Kroger Improves Pharmacy Inventory Management......Page 532
 Problems......Page 536
 14.1 Laws of Probability......Page 544
  14.1.2 Conditional Law of Probability......Page 545
 14.2 Random Variables and Probability Distributions......Page 546
  14.3.1 Mean and Variance (Standard Deviation) of a Random Variable......Page 548
  14.3.2 Joint Random Variables......Page 549
  14.4.2 Poisson Distribution......Page 552
  14.4.3 Negative Exponential Distribution......Page 553
  14.4.4 Normal Distribution......Page 554
 14.5 Empirical Distributions......Page 556
 Problems......Page 561
 15.1 Decision Making Under Certainty—Analytic Hierarchy Process (AHP)......Page 568
  15.2.1 Decision Tree–Based Expected Value Criterion......Page 575
  15.2.2 Variants of the Expected Value Criterion......Page 577
 15.3 Decision Under Uncertainty......Page 582
  15.4.1 Optimal Solution of Two-Person Zero-Sum Games......Page 586
  15.4.2 Solution of Mixed Strategy Games......Page 588
 Bibliography......Page 593
 Case Study: Booking Limits in Hotel Reservations......Page 594
 Problems......Page 596
  16.1.1 “Probabilitized” EOQ Model......Page 612
  16.1.2 Probabilistic EOQ Model......Page 614
 16.2 Single-Period Models......Page 618
  16.2.1 No-Setup Model (Newsvendor Model)......Page 619
  16.2.2 Setup Model (s-S Policy)......Page 621
 16.3 Multiperiod Model......Page 624
 Problems......Page 626
 17.1 Definition of a Markov Chain......Page 630
 17.2 Absolute and n-Step Transition Probabilities......Page 633
 17.3 Classification of the States in a Markov Chain......Page 634
 17.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains......Page 635
 17.5 First Passage Time......Page 637
 17.6 Analysis of Absorbing States......Page 640
 Problems......Page 643
 18.1 Why Study Queues?......Page 654
 18.2 Elements of a Queuing Model......Page 655
 18.3 Role of Exponential Distribution......Page 657
 18.4 Pure Birth and Death Models (Relationship Between the Exponential and Poisson Distributions)......Page 658
  18.4.1 Pure Birth Model......Page 659
  18.4.2 Pure Death Model......Page 662
 18.5 General Poisson Queuing Model......Page 663
 18.6 Specialized Poisson Queues......Page 666
  18.6.1 Steady-State Measures of Performance......Page 668
  18.6.2 Single-Server Models......Page 671
  18.6.3 Multiple-Server Models......Page 675
  18.6.4 Machine Servicing Model—(M/M/R):(GD/K/K), R 18.7 (M/G/1):(GD/∞/∞)—Pollaczek–Khintchine (P–K) Formula......Page 683
 18.8 Other Queuing Models......Page 684
  18.9.1 Cost Models......Page 685
  18.9.2 Aspiration Level Model......Page 687
 Case Study: Analysis of an Internal Transport System in a Manufacturing Plant......Page 689
 Problems......Page 691
 19.1 Monte Carlo Simulation......Page 712
  19.3.1 Generic Definition of Events......Page 716
  19.3.2 Sampling From Probability Distributions......Page 717
 19.4 Generation of Random Numbers......Page 721
  19.5.1 Manual Simulation of a Single-Server Model......Page 723
  19.5.2 Spreadsheet-Based Simulation of the Single-Server Model......Page 727
 19.6 Methods for Gathering Statistical Observations......Page 729
  19.6.1 Subinterval Method......Page 730
  19.6.2 Replication Method......Page 731
 19.7 Simulation Languages......Page 732
 Problems......Page 734
 20.1 Unconstrained Problems......Page 742
  20.1.1 Necessary and Sufficient Conditions......Page 743
  20.1.2 The Newton–Raphson Method......Page 745
 20.2 Constrained Problems......Page 747
  20.2.1 Equality Constraints......Page 748
  20.2.2 Inequality Constraints—Karush–Kuhn–Tucker (KKT) Conditions......Page 755
 Problems......Page 759
  21.1.1 Direct Search Method......Page 764
  21.1.2 Gradient Method......Page 767
 21.2 Constrained Algorithms......Page 770
  21.2.1 Separable Programming......Page 771
  21.2.2 Quadratic Programming......Page 778
  21.2.3 Chance-Constrained Programming......Page 782
  21.2.4 Linear Combinations Method......Page 786
  21.2.5 Sumt Algorithm......Page 788
 Problems......Page 789
Appendix A Statistical Tables......Page 794
Appendix B Partial Answers to Selected Problems......Page 798
Index......Page 834