What’s New in the Tenth Edition 23 Acknowledgments 25
About the Author 27
Trademarks 29
What Is Operations Research? 31
1.1 Introduction 31
1.2
... [Show More] Operations Research Models 31
1.3 Solving the OR Model 34
1.4 Queuing and Simulation Models 35
1.5 Art of Modeling 36
1.6 More than Just Mathematics 37
1.7 Phases of an OR Study 39
1.8 About this Book 41
Bibliography 41 Problems 42
Modeling with Linear Programming 45
Chapter 2
2.1 Two-Variable LP Model 45
2.2 Graphical LP Solution 47
2.2.1 Solution of a Maximization Model
2.2.2 Solution of a Minimization Model
48 50
2.3 Computer Solution with Solver and AMPL 52
2.3.1 LP Solution with Excel Solver 52
2.3.2 LP Solution with AMPL 56
2.4 Linear Programming Applications 59
2.4.1 Investment 60
2.4.2 Production Planning and Inventory Control 62
2.4.3 Workforce Planning 67
2.4.4 Urban Development Planning 70
2.4.5 Blending and Refining 73
2.4.6 Additional LP Applications 76
Bibliography 76 Problems 76
7
8 Contents Chapter 3
The Simplex Method and Sensitivity Analysis 99
3.1 LP Model in Equation Form 99
3.2 Transition from Graphical to Algebraic Solution 100
3.3 The Simplex Method 103
3.3.1 Iterative Nature of the Simplex Method 103
3.3.2 Computational Details of the Simplex Algorithm 105
3.3.3 Summary of the Simplex Method 111
3.4 Artificial Starting Solution 112 3.4.1 M-Method 112
3.4.2 Two-Phase Method 115
3.5 Special Cases in the Simplex Method 117
3.5.1 Degeneracy 118
3.5.2 Alternative Optima 119
3.5.3 Unbounded Solution 121
3.5.4 Infeasible Solution 122
3.6 Sensitivity Analysis 123
3.6.1 Graphical Sensitivity Analysis 124
3.6.2 Algebraic Sensitivity Analysis—Changes in the
Right-Hand Side 128
3.6.3 Algebraic Sensitivity Analysis—Objective Function 132
3.6.4 Sensitivity Analysis with TORA, Solver,
and AMPL 136
3.7 Computational Issues in Linear Programming 138
Bibliography 142
Case Study: Optimization of Heart Valves Production 142 Problems 145
Duality and Post-Optimal Analysis 169
4.1 Definition of the Dual Problem 169
4.2 Primal–Dual Relationships 172
4.2.1 Review of Simple Matrix Operations 172
4.2.2 Simplex Tableau Layout 173
4.2.3 Optimal Dual Solution 174
4.2.4 Simplex Tableau Computations 177
4.3 Economic Interpretation of Duality 178
4.3.1 Economic Interpretation of Dual Variables 179
4.3.2 Economic Interpretation of Dual Constraints 180
4.4 Additional Simplex Algorithms 182
4.4.1 Dual Simplex Algorithm 182
4.4.2 Generalized Simplex Algorithm 184
Chapter 4
Chapter 5
4.5 Post-Optimal Analysis 185
4.5.1 Changes Affecting Feasibility 186
4.5.2 Changes Affecting Optimality 189
Bibliography 192 Problems 192
Transportation Model and Its Variants 207
5.1 Definition of the Transportation Model 207
5.2 Nontraditional Transportation Models 211
5.3 The Transportation Algorithm 214
5.3.1 Determination of the Starting Solution 216
5.3.2 Iterative Computations of the Transportation
Algorithm 220
5.3.3 Simplex Method Explanation of the Method of
Multipliers 226
5.4 The Assignment Model 227
5.4.1 The Hungarian Method 227
5.4.2 Simplex Explanation of the Hungarian Method 230
Bibliography 231
Case Study: Scheduling Appointments at Australian Tourist Commission Trade Events 232
Problems 236
Network Model 247
6.1 Scope and Definition of Network Models 247
6.2 Minimal Spanning Tree Algorithm 250
6.3 Shortest-Route Problem 251
6.3.1 Examples of the Shortest-Route Applications 252
6.3.2 Shortest-Route Algorithms 255
6.3.3 Linear Programming Formulation of the Shortest-Route Problem 261
6.4 Maximal Flow Model 265
6.4.1 Enumeration of Cuts 266
6.4.2 Maximal Flow Algorithm 267
6.4.3 Linear Programming Formulation of Maximal
Flow Mode 272
6.5 CPM and PERT 273
6.5.1 Network Representation 274
6.5.2 Critical Path Method (CPM) Computations 276
6.5.3 Construction of the Time Schedule 279
Chapter 6
Contents 9
10 Contents
Chapter 7
6.5.4 Linear Programming Formulation of CPM 282
6.5.5 PERT Networks 283
Bibliography 285
Case Study: Saving Federal Travel Dollars 286 Problems 289
Advanced Linear Programming 305
7.1 Simplex Method Fundamentals 305
7.1.1 From Extreme Points to Basic Solutions 306
7.1.2 Generalized Simplex Tableau in Matrix Form 309
7.2 Revised Simplex Method 311
7.2.1 Development of the Optimality and Feasibility
Conditions 311
7.2.2 Revised Simplex Algorithm 312
7.2.3 Computational Issues in the Revised Simplex
Method 315
7.3 Bounded-Variables Algorithm 317
7.4 Duality 322
7.4.1 Matrix Definition of the Dual Problem 322
7.4.2 Optimal Dual Solution 322
7.5 Parametric Linear Programming 325
7.5.1 Parametric Changes in C 325
7.5.2 Parametric Changes in b 327
Chapter 8
Chapter 9
8.1 A Goal Programming Formulation 341
8.2 Goal Programming Algorithms 343
8.2.1 The Weights Method 343
8.2.2 The Preemptive Method 345
Bibliography 350
Case Study: Allocation of Operating Room Time in Mount Sinai Hospital 350
Problems 354
Integer Linear Programming 359
9.1 Illustrative Applications 359
9.1.1 Capital Budgeting 360
9.1.2 Set-Covering Problem 361
7.6 More Linear Programming Topics Bibliography 330
Problems 330
Goal Programming 341
329
Chapter 10
9.1.3 Fixed-Charge Problem 362
9.1.4 Either-Or and If-Then Constraints 364
9.2 Integer Programming Algorithms 366
9.2.1 Branch-and-Bound (B&B) Algorithm 367
9.2.2 Cutting-Plane Algorithm 373
Bibliography 378 Problems 379
Heuristic Programming 397
10.1 Introduction 397
10.2 Greedy (Local Search) Heuristics 398
10.2.1 Discrete Variable Heuristic 399
10.2.2 Continuous Variable Heuristic 401
10.3 Metaheuristic 404
10.3.1 Tabu Search Algorithm 404
Summary of Tabu Search Algorithm 408
10.3.2 Simulated Annealing Algorithm 408 Summary of Simulated Annealing Algorithm 410 10.3.3 Genetic Algorithm 411
Summary of Genetic Algorithm 414
10.4 Application of Metaheuristics to Integer Linear Programs 415
10.4.1 ILP Tabu Algorithm 416
10.4.2 ILP Simulated Annealing Algorithm 418 10.4.3 ILP Genetic Algorithm 420
10.5 Introduction to Constraint Programming (CP) 423 Bibliography 425
Problems 425
Traveling Salesperson Problem (TSP) 435
11.1 Scope of the TSP 435
11.2 TSP Mathematical Model 437
11.3 Exact TSP Algorithms 441
11.3.1 B&B Algorithm 441
11.3.2 Cutting-Plane Algorithm 444
11.4 Local Search Heuristics 445
11.4.1 Nearest-Neighbor Heuristic 445
11.4.2 Reversal Heuristic 446
11.5 Metaheuristics 449
11.5.1 TSP Tabu Algorithm 449
11.5.2 TSP Simulated Annealing Algorithm 452
Chapter 11
Contents 11
12 Contents
Chapter 12
11.5.3 TSP Genetic Algorithm 454 Bibliography 458
Problems 458
Deterministic Dynamic Programming 469
12.1 Recursive Nature of Dynamic Programming (DP) Computations 469
12.2 Forward and Backward Recursion 473
12.3 Selected DP Applications 474
12.3.1 Knapsack/Fly-Away Kit/Cargo-Loading Model 475
12.3.2 Workforce Size Model 480
12.3.3 Equipment Replacement Model 482
12.3.4 Investment Model 485
12.3.5 Inventory Models 488
12.4 Problem of Dimensionality 488 Bibliography 490
Case Study: Optimization of Crosscutting and Log Allocation at Weyerhaeuser 491
Problems 494
Inventory Modeling (with Introduction
to Supply Chains) 501
13.1 Inventory Problem: A Supply Chain Perspective 501
13.1.1 An Inventory Metric in Supply Chains 502
13.1.2 Elements of the Inventory Optimization
Model 504
13.2 Role of Demand in the Development of
Inventory Models 505
13.3 Static Economic-Order-Quantity Models 507
13.3.1 Classical EOQ Model 507
13.3.2 EOQ with Price Breaks 511
13.3.3 Multi-Item EOQ with Storage Limitation 514
13.4 Dynamic EOQ Models 517 13.4.1 No-Setup EOQ Model 518 13.4.2 Setup EOQ Model 521
13.5 Sticky Issues in Inventory Modeling 530 Bibliography 531
Case Study: Kroger Improves Pharmacy Inventory Management 531
Problems 535
Chapter 13
Chapter 14
Review of Basic Probability 543
14.1 Laws of Probability 543
14.1.1 Addition Law of Probability 544 14.1.2 Conditional Law of Probability 544
14.2 Random Variables and Probability Distributions 545
14.3 Expectation of a Random Variable 547
14.3.1 Mean and Variance (Standard Deviation) of a Random Variable 547
14.3.2 Joint Random Variables 548
14.4 Four Common Probability Distributions 551
14.4.1 Binomial Distribution 551
14.4.2 Poisson Distribution 551
14.4.3 Negative Exponential Distribution 552 14.4.4 Normal Distribution 553
14.5 Empirical Distributions 555 Bibliography 560
Problems 560
Decision Analysis and Games 567
15.1 Decision Making Under Certainty—Analytic Hierarchy Process (AHP) 567
15.2 Decision Making Under Risk 574
15.2.1 Decision Tree–Based Expected Value Criterion 574 15.2.2 Variants of the Expected Value Criterion 576
15.3 Decision Under Uncertainty 581
15.4 Game Theory 585
15.4.1 Optimal Solution of Two-Person Zero-Sum Games 585
15.4.2 Solution of Mixed Strategy Games 587
Bibliography 592
Case Study: Booking Limits in Hotel Reservations 593 Problems 595
Probabilistic Inventory Models 611
16.1 Continuous Review Models 611
16.1.1 “Probabilitized” EOQ Model 611 16.1.2 Probabilistic EOQ Model 613
16.2 Single-Period Models 617
16.2.1 No-Setup Model (Newsvendor Model) 618 16.2.2 Setup Model (s-S Policy) 620
Chapter 15
Chapter 16
Contents 13
14 Contents
Chapter 17
16.3 Multiperiod Model 623 Bibliography 625
Problems 625 Markov Chains 629
17.1 Definition of a Markov Chain 629
17.2 Absolute and n-Step Transition Probabilities 632
17.3 Classification of the States in a Markov Chain 633
17.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains 634
17.5 First Passage Time 636
17.6 Analysis of Absorbing States 639
Bibliography 642 Problems 642
Queuing Systems 653
18.1 Why Study Queues? 653
18.2 Elements of a Queuing Model 654
18.3 Role of Exponential Distribution 656
18.4 Pure Birth and Death Models (Relationship Between the Exponential and Poisson Distributions) 657
18.4.1 Pure Birth Model 658
18.4.2 Pure Death Model 661
18.5 General Poisson Queuing Model 662
18.6 Specialized Poisson Queues 665
18.6.1 Steady-State Measures of Performance 667
18.6.2 Single-Server Models 670
18.6.3 Multiple-Server Models 674
18.6.4 Machine Servicing Model—(M/M/R): (GD/K/K), R 6 K 680
18.7 (M/G/1):(GD/H/H)—Pollaczek-Khintchine (P-K) Formula 682
18.8 Other Queuing Models 683
18.9 Queuing Decision Models 684
18.9.1 Cost Models 684
18.9.2 Aspiration Level Model 686 Bibliography 688
Chapter 18
Chapter 19
Contents 15 Case Study: Analysis of an Internal Transport System
in a Manufacturing Plant 688 Problems 690
Simulation Modeling 711
19.1 Monte Carlo Simulation 711
19.2 Types of Simulation 715
19.3 Elements of Discrete Event Simulation 715
19.3.1 Generic Definition of Events 715
19.3.2 Sampling from Probability Distributions 716
19.4 Generation of Random Numbers 720
19.5 Mechanics of Discrete Simulation 722
19.5.1 Manual Simulation of a Single-Server Model 722
19.5.2 Spreadsheet-Based Simulation
of the Single-Server Model 726
19.6 Methods for Gathering Statistical Observations 728
19.6.1 Subinterval Method 729
19.6.2 Replication Method 730
19.7 Simulation Languages 731
Bibliography 733 Problems 733
Classical Optimization Theory 741
20.1 Unconstrained Problems 741
20.1.1 Necessary and Sufficient Conditions 742 20.1.2 The Newton-Raphson Method 744
20.2 Constrained Problems 746
20.2.1 Equality Constraints 747
20.2.2 Inequality Constraints—Karush–Kuhn–Tucker (KKT)
Conditions 754
Bibliography 758
Problems 758
Nonlinear Programming Algorithms 763
21.1 Unconstrained Algorithms 763
Chapter 20
Chapter 21
21.1.1 Direct Search Method
21.1.2 Gradient Method 766 21.2 Constrained Algorithms 769
763
21.2.1 Separable Programming 770 21.2.2 Quadratic Programming 777
16 Contents
21.2.3 Chance-Constrained Programming 781 21.2.4 Linear Combinations Method 785 21.2.5 SUMT Algorithm 787
Bibliography 788
Problems 788 Appendix A Statistical Tables 793
Appendix B Partial Answers to Selected Problems 79 [Show Less]