Operations research : a practical approach

Operations Research: A Practical Introduction is just that: a hands-on approach to the field of operations research (OR) and a useful guide for using OR techniques in scientific decision making, design, analysis and management. The text accomplishes two goals. First, it provides readers with an introduction to standard mathematical models and algorithms. Second, it is a thorough examination of practical issues relevant to the development and use of computational methods for problem solving. Highlights: - All chapters contain up-to-date topics and summaries - A succinct presentation to fit a one-term course - Each chapter has references, readings, and list of key terms - Includes illustrative and current applications - New exercises are added throughout the text - Software tools have been updated with the newest and most popular software. Many students of various disciplines such as mathematics, economics, industrial engineering and computer science often take one course in operations research. This book is written to provide a succinct and efficient introduction to the subject for these students, while offering a sound and fundamental preparation for more advanced courses in linear and nonlinear optimization, and many stochastic models and analyses. It provides relevant analytical tools for this varied audience and will also serve professionals, corporate managers, and technical consultants 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 Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Table of Contents 6 Preface 14 About the Authors 20 1: Introduction to Operations Research 24 1.1 The Origins and Applications of Operations Research 24 1.2 System Modeling Principles 26 1.3 Algorithm Efficiency and Problem Complexity 28 1.4 Optimality and Practicality 32 1.5 Software for Operations Research 33 1.6 Illustrative Applications 37 1.6.1 Analytical Innovation in the Food and Agribusiness Industries 37 1.6.2 Humanitarian Relief in Natural Disasters 38 1.6.3 Mining and Social Conflicts 40 1.7 Summary 41 Key Terms 42 References and Suggested Readings 43 2: Linear Programming 46 2.1 The Linear Programming Model 46 2.2 The Art and Skill of Problem Formulation 47 2.2.1 Integer and Nonlinear Models 53 2.3 Graphical Solution of Linear Programming Problems 53 2.3.1 General Definitions 53 2.3.2 Graphical Solutions 54 2.3.3 Multiple Optimal Solutions 56 2.3.4 No Optimal Solution 57 2.3.5 No Feasible Solution 58 2.3.6 General Solution Method 59 2.4 Preparation for the Simplex Method 59 2.4.1 Standard Form of a Linear Programming Problem 59 2.4.2 Solutions of Linear Systems 61 2.5 The Simplex Method 62 2.6 Initial Solutions for General Constraints 69 2.6.1 Artificial Variables 69 2.6.2 The Two Phase Method 71 2.7 Information in the Tableau 73 2.7.1 Multiple Optimal Solutions 74 2.7.2 Unbounded Solution (No Optimal Solution) 74 2.7.3 Degenerate Solutions 76 2.7.4 Analyzing the Optimal Tableau: Shadow Prices 78 2.8 Duality and Sensitivity Analysis 79 2.8.1 The Dual Problem 79 2.8.2 Postoptimality and Sensitivity Analysis 83 2.9 Revised Simplex and Computational Efficiency 86 2.10 Software for Linear Programming 87 2.10.1 Extensions to General Simplex Methods 88 2.10.2 Interior Methods 90 2.10.3 Software for Solving Linear Programming 92 2.11 Illustrative Applications 94 2.11.1 Forest Pest Control Program 94 2.11.2 Aircraft and Munitions Procurement 95 2.11.3 Grape Processing: Materials Planning and Production 96 2.12 Summary 97 Key Terms 98 Exercises 99 References and Suggested Readings 108 3: Network Analysis 112 3.1 Graphs and Networks: Preliminary Definitions 113 3.2 Maximum Flow in Networks 115 3.2.1 Maximum Flow Algorithm 116 3.2.2 Extensions to the Maximum Flow Problem 119 3.3 Minimum Cost Network Flow Problems 120 3.3.1 Transportation Problem 120 3.3.1.1 Northwest Corner Rule 122 3.3.1.2 Minimum Cost Method 124 3.3.1.3 Minimum “Row” Cost Method 125 3.3.1.4 Transportation Simplex Method 126 3.3.1.5 Transportation Simplex 130 3.3.2 Assignment Problem and Stable Matching 132 3.3.2.1 Stable Matching 136 3.3.3 Capacitated Transshipment Problem 137 3.4 Network Connectivity 139 3.4.1 Minimum Spanning Trees 139 3.4.2 Shortest Network Problem: A Variation on Minimum Spanning Trees 141 3.5 Shortest Path Problems 142 3.5.1 Shortest Path through an Acyclic Network 143 3.5.2 Shortest Paths from Source to All Other Nodes 144 3.5.3 Problems Solvable with Shortest Path Methods 146 3.6 Dynamic Programming 148 3.6.1 Labeling Method for Multi-Stage Decision Making 149 3.6.2 Tabular Method 150 3.6.3 General Recursive Method 153 3.7 Project Management 155 3.7.1 Project Networks and Critical Paths 156 3.7.2 Cost versus Time Trade-Offs 160 3.7.3 Probabilistic Project Scheduling 162 3.8 Software for Network Analysis 164 3.9 Illustrative Applications 165 3.9.1 DNA Sequence Comparison Using a Shortest Path Algorithm 165 3.9.2 Multiprocessor Network Traffic Scheduling 165 3.9.3 Shipping Cotton from Farms to Gins 166 3.10 Summary 167 Key Terms 168 Exercises 169 References and Suggested Readings 177 4: Integer Programming 180 4.1 Fundamental Concepts 180 4.2 Typical Integer Programming Problems 182 4.2.1 General Integer Problems 182 4.2.2 Zero–One (0–1) Problems 182 4.2.3 Mixed Integer Problems 183 4.3 Zero–One (0–1) Model Formulations 184 4.3.1 Traveling Salesman Model 184 4.3.2 Knapsack Model 185 4.3.3 Bin Packing Model 185 4.3.4 Set Partitioning/Covering/Packing Models 186 4.3.5 Generalized Assignment Model 187 4.4 Branch-and-Bound 188 4.4.1 A Simple Example 188 4.4.2 A Basic Branch-and-Bound Algorithm 192 4.4.3 Knapsack Example 192 4.4.4 From Basic Method to Commercial Code 194 4.4.4.1 Branching Strategies 195 4.4.4.2 Bounding Strategies 197 4.4.4.3 Separation Rules 198 4.4.4.4 The Impact of Model Formulation 198 4.4.4.5 Representation of Real Numbers 200 4.5 Cutting Planes and Facets 200 4.6 Cover Inequalities 203 4.7 Lagrangian Relaxation 210 4.7.1 Relaxing Integer Programming Constraints 210 4.7.2 A Simple Example 211 4.7.3 The Integrality Gap 214 4.7.4 The Generalized Assignment Problem 215 4.7.5 A Basic Lagrangian Relaxation Algorithm 217 4.7.6 A Customer Allocation Problem 217 4.8 Column Generation 220 4.9 Software for Integer Programming 224 4.10 Illustrative Applications 225 4.10.1 Solid Waste Management 225 4.10.2 Timber Harvest Planning 227 4.10.3 Propane Bottling Plants 228 4.11 Summary 229 Key Terms 230 Exercises 231 References and Suggested Readings 236 5: Nonlinear Optimization 240 5.1 Preliminary Notation and Concepts 241 5.2 Unconstrained Optimization 246 5.2.1 One-Dimensional Search 246 5.2.1.1 One-Dimensional Search Algorithm 246 5.2.2 Multivariable Search: Gradient Method 248 5.2.2.1 Multivariable Gradient Search 249 5.2.3 Newton’s Method 251 5.2.4 Quasi-Newton Methods 252 5.3 Constrained Optimization 252 5.3.1 Lagrange Multipliers (Equality Constraints) 252 5.3.2 Karush–Kuhn–Tucker Conditions (Inequality Constraints) 253 5.3.3 Quadratic Programming 254 5.3.4 More Advanced Methods 259 5.4 Software for Nonlinear Optimization 259 5.5 Illustrative Applications 262 5.5.1 Gasoline Blending Systems 262 5.5.2 Portfolio Construction 263 5.5.3 Balancing Rotor Systems 264 5.6 Summary 265 Key Terms 265 Exercises 266 References and Suggested Readings 268 6: Markov Processes 272 6.1 State Transitions 273 6.2 State Probabilities 279 6.3 First Passage Probabilities 282 6.4 Properties of the States in a Markov Process 284 6.5 Steady-State Analysis 286 6.6 Expected First Passage Times 288 6.7 Absorbing Chains 290 6.8 Software for Markov Processes 294 6.9 Illustrative Applications 295 6.9.1 Water Reservoir Operations 295 6.9.2 Markov Analysis of Dynamic Memory Allocation 296 6.9.3 Markov Models for Manufacturing Production Capability 297 6.9.4 Markov Decision Processes in Dairy Farming 298 6.10 Summary 299 Key Terms 299 Exercises 300 References and Suggested Readings 304 7: Queueing Models 308 7.1 Basic Elements of Queueing Systems 308 7.2 Arrival and Service Patterns 311 7.2.1 The Exponential Distribution 311 7.2.2 Birth-and-Death Processes 313 7.3 Analysis of Simple Queueing Systems 314 7.3.1 Notation and Definitions 314 7.3.2 Steady State Performance Measures 315 7.3.3 Practical Limits of Queueing Models 321 7.4 Software for Queueing Models 322 7.5 Illustrative Applications 323 7.5.1 Cost Efficiency and Service Quality in Hospitals 323 7.5.2 Queueing Models in Manufacturing 325 7.5.3 Nurse Staffing Based on Queueing Models 327 7.6 Summary 328 Key Terms 329 Exercises 329 References and Suggested Readings 332 8: Simulation 334 8.1 Simulation: Purposes and Applications 334 8.2 Discrete Simulation Models 337 8.2.1 Event-Driven Models 337 8.2.2 Generating Random Events 340 8.3 Observations of Simulations 344 8.3.1 Gathering Statistics 344 8.3.1.1 Average Time in System 344 8.3.1.2 Average Waiting Time 345 8.3.1.3 Average Number in Queue 345 8.3.1.4 Server Utilization 346 8.3.2 Design of Simulation Experiments 347 8.4 Software for Simulation 348 8.5 Illustrative Applications 351 8.5.1 Finnish Air Force Fleet Maintenance 351 8.5.2 Simulation of a Semiconductor Manufacturing Line 352 8.5.3 Simulation of Eurotunnel Terminals 354 8.5.4 Simulation for NASA’s Space Launch Vehicles Operations 355 8.6 Summary 357 Key Terms 357 Exercises 358 References and Suggested Readings 360 9: Decision Analysis 364 9.1 The Decision-Making Process 364 9.2 An Introduction to Game Theory 368 9.2.1 Maximin Strategy 368 9.2.2 Maximax Strategy 369 9.2.3 Laplace Principle (Principle of Insufficient Reason) 369 9.2.4 Hurwicz Principle 369 9.2.5 Savage Minimax Regret 370 9.3 Decision Trees 373 9.4 Utility Theory 381 9.4.1 The Axioms of Utility Theory 382 9.4.2 Utility Functions 384 9.4.3 The Shape of the Utility Curve 389 9.5 The Psychology of Decision-Making 393 9.5.1 Misconceptions of Probability 393 9.5.2 Availability 395 9.5.3 Anchoring and Adjustment 395 9.5.4 Dissonance Reduction 396 9.5.5 The Framing Effect 397 9.5.6 The Sunk Cost Fallacy 399 9.5.7 Irrational Human Behavior 400 9.5.7.1 What Can We Do about Irrational Behavior? 401 9.6 Software for Decision Analysis 401 9.7 Illustrative Applications 402 9.7.1 Decision Support System for Minimizing Costs in the Maritime Industry 402 9.7.2 Refinery Pricing under Uncertainty 404 9.7.3 Decisions for Radioactive Waste Management 406 9.7.4 Investment Decisions and Risk in Petroleum Exploration 406 9.8 Summary 408 Key Terms 408 Exercises 410 References and Suggested Readings 415 10: Heuristic and Metaheuristic Techniques for Optimization 418 10.1 Greedy Heuristics 420 10.2 Local Improvement Heuristics 421 10.3 Simulated Annealing 423 10.4 Parallel Annealing 430 10.5 Genetic Algorithms 432 10.6 Tabu Search 437 10.7 Constraint Programming and Local Search 440 10.8 Other Metaheuristics 441 10.9 Software for Metaheuristics 442 10.10 Illustrative Applications 443 10.10.1 FedEx Flight Management Using Simulated Annealing 443 10.10.2 Ecosystem Management Using Genetic Algorithm Heuristics 445 10.10.3 Efficient Routing and Delivery of Meals on Wheels 447 10.11 Summary 449 Key Terms 450 Exercises 451 References and Suggested Readings 453 Appendix: Review of Essential Mathematics—Notation, Definitions, and Matrix Algebra 456 Index 462