Operations Research: A Practical Approach

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
Preface......Page 14
About the Authors......Page 20
1.1 The Origins and Applications of Operations Research......Page 24
1.2 System Modeling Principles......Page 26
1.3 Algorithm Efficiency and Problem Complexity......Page 28
1.4 Optimality and Practicality......Page 32
1.5 Software for Operations Research......Page 33
1.6.1 Analytical Innovation in the Food and Agribusiness Industries......Page 37
1.6.2 Humanitarian Relief in Natural Disasters......Page 38
1.6.3 Mining and Social Conflicts......Page 40
1.7 Summary......Page 41
Key Terms......Page 42
References and Suggested Readings......Page 43
2.1 The Linear Programming Model......Page 46
2.2 The Art and Skill of Problem Formulation......Page 47
2.3.1 General Definitions......Page 53
2.3.2 Graphical Solutions......Page 54
2.3.3 Multiple Optimal Solutions......Page 56
2.3.4 No Optimal Solution......Page 57
2.3.5 No Feasible Solution......Page 58
2.4.1 Standard Form of a Linear Programming Problem......Page 59
2.4.2 Solutions of Linear Systems......Page 61
2.5 The Simplex Method......Page 62
2.6.1 Artificial Variables......Page 69
2.6.2 The Two Phase Method......Page 71
2.7 Information in the Tableau......Page 73
2.7.2 Unbounded Solution (No Optimal Solution)......Page 74
2.7.3 Degenerate Solutions......Page 76
2.7.4 Analyzing the Optimal Tableau: Shadow Prices......Page 78
2.8.1 The Dual Problem......Page 79
2.8.2 Postoptimality and Sensitivity Analysis......Page 83
2.9 Revised Simplex and Computational Efficiency......Page 86
2.10 Software for Linear Programming......Page 87
2.10.1 Extensions to General Simplex Methods......Page 88
2.10.2 Interior Methods......Page 90
2.10.3 Software for Solving Linear Programming......Page 92
2.11.1 Forest Pest Control Program......Page 94
2.11.2 Aircraft and Munitions Procurement......Page 95
2.11.3 Grape Processing: Materials Planning and Production......Page 96
2.12 Summary......Page 97
Key Terms......Page 98
Exercises......Page 99
References and Suggested Readings......Page 108
3: Network Analysis......Page 112
3.1 Graphs and Networks: Preliminary Definitions......Page 113
3.2 Maximum Flow in Networks......Page 115
3.2.1 Maximum Flow Algorithm......Page 116
3.2.2 Extensions to the Maximum Flow Problem......Page 119
3.3.1 Transportation Problem......Page 120
3.3.1.1 Northwest Corner Rule......Page 122
3.3.1.2 Minimum Cost Method......Page 124
3.3.1.3 Minimum “Row” Cost Method......Page 125
3.3.1.4 Transportation Simplex Method......Page 126
3.3.1.5 Transportation Simplex......Page 130
3.3.2 Assignment Problem and Stable Matching......Page 132
3.3.2.1 Stable Matching......Page 136
3.3.3 Capacitated Transshipment Problem......Page 137
3.4.1 Minimum Spanning Trees......Page 139
3.4.2 Shortest Network Problem: A Variation on Minimum Spanning Trees......Page 141
3.5 Shortest Path Problems......Page 142
3.5.1 Shortest Path through an Acyclic Network......Page 143
3.5.2 Shortest Paths from Source to All Other Nodes......Page 144
3.5.3 Problems Solvable with Shortest Path Methods......Page 146
3.6 Dynamic Programming......Page 148
3.6.1 Labeling Method for Multi-Stage Decision Making......Page 149
3.6.2 Tabular Method......Page 150
3.6.3 General Recursive Method......Page 153
3.7 Project Management......Page 155
3.7.1 Project Networks and Critical Paths......Page 156
3.7.2 Cost versus Time Trade-Offs......Page 160
3.7.3 Probabilistic Project Scheduling......Page 162
3.8 Software for Network Analysis......Page 164
3.9.2 Multiprocessor Network Traffic Scheduling......Page 165
3.9.3 Shipping Cotton from Farms to Gins......Page 166
3.10 Summary......Page 167
Key Terms......Page 168
Exercises......Page 169
References and Suggested Readings......Page 177
4.1 Fundamental Concepts......Page 180
4.2.2 Zero–One (0–1) Problems......Page 182
4.2.3 Mixed Integer Problems......Page 183
4.3.1 Traveling Salesman Model......Page 184
4.3.3 Bin Packing Model......Page 185
4.3.4 Set Partitioning/Covering/Packing Models......Page 186
4.3.5 Generalized Assignment Model......Page 187
4.4.1 A Simple Example......Page 188
4.4.3 Knapsack Example......Page 192
4.4.4 From Basic Method to Commercial Code......Page 194
4.4.4.1 Branching Strategies......Page 195
4.4.4.2 Bounding Strategies......Page 197
4.4.4.4 The Impact of Model Formulation......Page 198
4.5 Cutting Planes and Facets......Page 200
4.6 Cover Inequalities......Page 203
4.7.1 Relaxing Integer Programming Constraints......Page 210
4.7.2 A Simple Example......Page 211
4.7.3 The Integrality Gap......Page 214
4.7.4 The Generalized Assignment Problem......Page 215
4.7.6 A Customer Allocation Problem......Page 217
4.8 Column Generation......Page 220
4.9 Software for Integer Programming......Page 224
4.10.1 Solid Waste Management......Page 225
4.10.2 Timber Harvest Planning......Page 227
4.10.3 Propane Bottling Plants......Page 228
4.11 Summary......Page 229
Key Terms......Page 230
Exercises......Page 231
References and Suggested Readings......Page 236
5: Nonlinear Optimization......Page 240
5.1 Preliminary Notation and Concepts......Page 241
5.2.1.1 One-Dimensional Search Algorithm......Page 246
5.2.2 Multivariable Search: Gradient Method......Page 248
5.2.2.1 Multivariable Gradient Search......Page 249
5.2.3 Newton’s Method......Page 251
5.3.1 Lagrange Multipliers (Equality Constraints)......Page 252
5.3.2 Karush–Kuhn–Tucker Conditions (Inequality Constraints)......Page 253
5.3.3 Quadratic Programming......Page 254
5.4 Software for Nonlinear Optimization......Page 259
5.5.1 Gasoline Blending Systems......Page 262
5.5.2 Portfolio Construction......Page 263
5.5.3 Balancing Rotor Systems......Page 264
Key Terms......Page 265
Exercises......Page 266
References and Suggested Readings......Page 268
6: Markov Processes......Page 272
6.1 State Transitions......Page 273
6.2 State Probabilities......Page 279
6.3 First Passage Probabilities......Page 282
6.4 Properties of the States in a Markov Process......Page 284
6.5 Steady-State Analysis......Page 286
6.6 Expected First Passage Times......Page 288
6.7 Absorbing Chains......Page 290
6.8 Software for Markov Processes......Page 294
6.9.1 Water Reservoir Operations......Page 295
6.9.2 Markov Analysis of Dynamic Memory Allocation......Page 296
6.9.3 Markov Models for Manufacturing Production Capability......Page 297
6.9.4 Markov Decision Processes in Dairy Farming......Page 298
Key Terms......Page 299
Exercises......Page 300
References and Suggested Readings......Page 304
7.1 Basic Elements of Queueing Systems......Page 308
7.2.1 The Exponential Distribution......Page 311
7.2.2 Birth-and-Death Processes......Page 313
7.3.1 Notation and Definitions......Page 314
7.3.2 Steady State Performance Measures......Page 315
7.3.3 Practical Limits of Queueing Models......Page 321
7.4 Software for Queueing Models......Page 322
7.5.1 Cost Efficiency and Service Quality in Hospitals......Page 323
7.5.2 Queueing Models in Manufacturing......Page 325
7.5.3 Nurse Staffing Based on Queueing Models......Page 327
7.6 Summary......Page 328
Exercises......Page 329
References and Suggested Readings......Page 332
8.1 Simulation: Purposes and Applications......Page 334
8.2.1 Event-Driven Models......Page 337
8.2.2 Generating Random Events......Page 340
8.3.1.1 Average Time in System......Page 344
8.3.1.3 Average Number in Queue......Page 345
8.3.1.4 Server Utilization......Page 346
8.3.2 Design of Simulation Experiments......Page 347
8.4 Software for Simulation......Page 348
8.5.1 Finnish Air Force Fleet Maintenance......Page 351
8.5.2 Simulation of a Semiconductor Manufacturing Line......Page 352
8.5.3 Simulation of Eurotunnel Terminals......Page 354
8.5.4 Simulation for NASA’s Space Launch Vehicles Operations......Page 355
Key Terms......Page 357
Exercises......Page 358
References and Suggested Readings......Page 360
9.1 The Decision-Making Process......Page 364
9.2.1 Maximin Strategy......Page 368
9.2.4 Hurwicz Principle......Page 369
9.2.5 Savage Minimax Regret......Page 370
9.3 Decision Trees......Page 373
9.4 Utility Theory......Page 381
9.4.1 The Axioms of Utility Theory......Page 382
9.4.2 Utility Functions......Page 384
9.4.3 The Shape of the Utility Curve......Page 389
9.5.1 Misconceptions of Probability......Page 393
9.5.3 Anchoring and Adjustment......Page 395
9.5.4 Dissonance Reduction......Page 396
9.5.5 The Framing Effect......Page 397
9.5.6 The Sunk Cost Fallacy......Page 399
9.5.7 Irrational Human Behavior......Page 400
9.6 Software for Decision Analysis......Page 401
9.7.1 Decision Support System for Minimizing Costs in the Maritime Industry......Page 402
9.7.2 Refinery Pricing under Uncertainty......Page 404
9.7.4 Investment Decisions and Risk in Petroleum Exploration......Page 406
Key Terms......Page 408
Exercises......Page 410
References and Suggested Readings......Page 415
10: Heuristic and Metaheuristic Techniques for Optimization......Page 418
10.1 Greedy Heuristics......Page 420
10.2 Local Improvement Heuristics......Page 421
10.3 Simulated Annealing......Page 423
10.4 Parallel Annealing......Page 430
10.5 Genetic Algorithms......Page 432
10.6 Tabu Search......Page 437
10.7 Constraint Programming and Local Search......Page 440
10.8 Other Metaheuristics......Page 441
10.9 Software for Metaheuristics......Page 442
10.10.1 FedEx Flight Management Using Simulated Annealing......Page 443
10.10.2 Ecosystem Management Using Genetic Algorithm Heuristics......Page 445
10.10.3 Efficient Routing and Delivery of Meals on Wheels......Page 447
10.11 Summary......Page 449
Key Terms......Page 450
Exercises......Page 451
References and Suggested Readings......Page 453
Appendix: Review of Essential Mathematics—Notation, Definitions, and Matrix Algebra......Page 456
Index......Page 462