Operations Research An Introduction - GBV

1 Operations ResearchAn IntroductionNinth EditionHamdy A. TahaUniversity of Arkansas, FayettevilieBoston Columbus Indianapolis New York San Francisco Upper Saddle RiverAmsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal TorontoDelhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei TokyoContentsWhat's Mew in the Ninth Edition 25 Acknowledgments 27 About the Author 29 Trademarks 31 Chapter 1 What Is Operations Research ? Introduction Operations Research Models Solving the OR Model Queuing and Simulation Models Art of Modeling More Than Just Mathematics Phases of an OR Study . About This Book 44 Bibliography 45 Chapter 2 Modeling with Linear Programming Two-Variable LP Model Graphical LP Solution Solution of a Maximization Model Solution of a Minimization Model Computer Solution with Solver and AMPL LP Solution with Excel Solver 61' LP Solution with AMPL Linear Programming Applications Investment Production Planning and Inventory Control Manpower Planning Urban Development Planning Blending and Refining Additional LP Applications 97 Bibliography 102 Chapter 3 The Simplex Method and Sensitivity Analysis LP Model in Equation Form Transition from Graphical to Algebraic Solution 7068 The Simplex Method Iterative Nature of the Simplex Method

2 Computational details of the Simplex algorithm Summary of the Simplex Method Artificial Starting Solution M-Method Two-Phase Method Special Cases in the Simplex Method Degeneracy Alternative Optima Unbounded Solution Infeasible Solution Sensitivity Analysis Graphical Sensitivity Analysis Algebraic Sensitivity Analysis Changes in theRight-hand Side Algebraic Sensitivity Analysis Objectivefunction Sensitivity Analysis with Tora, Solver,and Ampl Computational Issues in Linear Programming 765 Bibliography 770 Chapter 4 Duality and Post-Optimal Analysis Definition of the Dual Problem Primal-Dual Relationships Review of Simple Matrix Operations Simplex Tableau Layout } Optimal Dual Solution SimplexTableau Computations Economic Interpretation of Duality Economic Interpretation of Dual Variables Economic Interpretation of Dual Constraints Additional Simplex Algorithms Dual Simplex Algorithm Generalized Simplex Algorithm Post-optimal Analysis Changes Affecting Feasibility Changes Affecting Optimally 205 Bibliography 208 Contents 9 Chapter 5 Transportation Model and Its Variants Definition of the Transportation Model Nontraditional Transportation

3 Models The Transportation Algorithm Determination of the Starting Solution Iterative Computations of the TransportationAlgorithm Simplex Method Explanation of the Method ofMultipliers The Assignment Model The Hungarian Method Simplex Explanation of the Hungarian Method 240 Bibliography 242 Chapter 6 Network Models 243 Chapter and Definition of NetworkModels Spanning Tree AlgorithmShortest-Route Problem Examples of the Shortest-Route Shortest-Route Algorithms Linear Programming Formulation of the Shortest-RouteProblem 264 Maximal Flow Model Enumeration of Cuts Maximal Flow Algorithm Linear Programming Formulation of Maximal FlowMode 278 CPM and PERT , Network Representation 287 Critical Path Method (CPM) Computations 286 Construction of the Time Schedule 289 Linear Programming Formulation of CPM 295 PERT Networks 299 Advanced Linear Programming Simplex Method Fundamentals From Extreme Points to Basic Solutions Generalized Simplex Tableau in Matrix Form 30610 ContentsChapter 8 Chapter 9 Chapter Revised Simplex Method Development of the Optimality and Feasibilityconditions Revised Simplex Algorithm Bounded-Variables Algorithm Duality Matrix Definition of the Dual Problem Optimal Dual Solution Parametric Linear Programming Parametric Changes in C Parametric Changes in b More Linear Programming Topics 334 Bibliography 334 Goal Programming A Goal Programming Formulation Goal Programming Algorithms The Weights Method The

4 Preemptive Method 342 Bibliography 348 Integer Linear Programming Illustrative Applications Capital Budgeting Set-Covering Problem Fixed-Charge Problem Either-Or and If-Then Constraints Integer Programming Algorithms Branch-and-Bound (B&B) Algorithm Cutting-Plane Algorithm 378 Bibliography 383 Heuristic Programming Introduction Greedy (Local Search) Heuristics Discrete Variable Heuristic Continuous Variable Heuristic Metaheuristic Tabu Search Algorithm Simulated Annealing Algorithm Genetic Algorithm 405 Contents Application of Metaheuristics to Integer LinearPrograms ILP Tabu Algorithm ILP Simulated Annealing Algorithm ILP Genetic Algorithm Introduction to Constraint Programming (CP) 425 Bibliography 425 Chapter 11 Traveling Salesperson Problem (TSP) Example Applications of TSP TSP Mathematical Model Exact TSP Algorithms B&B Algorithm Cutting-Plane Algorithm Local Search Heuristics Nearest-Neighbor Heuristic Reversal Heuristic Metaheuristic TSP Tabu Algorithm TSP Simulated Annealing Algorithm TSP Genetic Algorithm 457 Bibliography 467 Chapter 12 Deterministic Dynamic Programming Recursive Nature of Dynamic Programming (DP)

5 , Computations Forward and Backward Recursion Selected DP Applications 468, Knapsack/Fly-Away Kit/Cargo-Loading Model Workforce Size Model Equipment Replacement Model Investment Model Inventory Models Problem of Dimensionality 487 Bibliography 490 Chapter 13 Deterministic Inventory Models General Inventory Model Role of Demand in the Development of InventoryModels 49212 Static Economic-Order-Quantity (EOQ) Models Classical EOQ Model EOQ with Price Breaks Multi-Item EOQ with Storage Limitation Dynamic EOQ Models No-Setup EOQ Model Setup EOQ Model 570 Bibliography 527 Chapter 14 Review of Basic Probability Laws of Probability Addition Law of Probability Conditional Law of Probability Random Variables and Probability Distributions Expectation of a Random Variable Mean and Variance (Standard Deviation)of a Random Variable Joint Random Variables Four Common Probability Distributions Binomial Distribution Poisson Distribution Negative Exponential Distribution Normal Distribution Empirical Distributions 540 Bibliography 546 Chapter 15 Decision Analysis and Games Decision Making under Certainty Analytic HierarchyProcess (AHP)

6 Decision Making under Risk Decision Tree-Based Expected ValueCriterion Variants of the Expected ValueCriterion Decision under Uncertainty Game Theory Optimal Solution of Two-PersonZero-Sum Games Solution of Mixed Strategy Games 579 Bibliography 585 Contents 13 Chapter 16 Probabilistic Inventory Models Continuous Review Models "Probabilitized" EOQ Model Probabilistic EOQ Model Single-Period Models No-Setup Model (Newsvendor Model) Setup Model (s-S Policy) Multiperiod Model 607 Bibliography 603 Chapter 17 Markov Chains Definition of a Markov Chain Absolute and n-Step TransitionProbabilities Classification of the States in a Markov Chain Steady-State Probabilities and Mean Return Timesof Ergodic Chains First Passage Time Analysis of Absorbing States 627 Bibliography 626 Chapter 18 Queuing Systems Why Study Queues?

7 Elements of a Queuing Model Role of Exponential Distribution 630/ Pure Birth and Death Models (Relationship Betweenthe Exponential and Poisspn Distributions) Pure Birth Model 634' Pure Death Model General Poisson Queuing Model Specialized Poisson Queues Steady-State Measures of Performance Single-Server Models Multiple-Server Models Machine Servicing Model (M/M/R):(GD/K/K), R < K (M/G/1):(GD/oo/oo) Pollaczek-Khintchine(P-K) Formula Other Queuing Models 67214 Queuing Decision Models Cost Models Aspiration Level Model 677 Bibliography 679 Chapter 19 Simulation Modeling Monte Carlo Simulation Types of Simulation Elements of Discrete Event Simulation Generic Definition of Events Sampling from Probability Distributions Generation of Random Numbers Mechanics of Discrete Simulation Manual Simulation of a Single-Server Model Spreadsheet-Based Simulation of the Single-ServerModel Methods for Gathering Statistical Observations Subinterval Method Replication Method Simulation Languages 708 Bibliography 770 Chapter 20 Classical Optimization Theory Unconstrained Problems Necessary and Sufficient Conditions The Newton-Raphson Method Constrained Problems

8 Equality Constraints Inequality Constraints Karush-Kuhn-Tucker (KKT)Conditions 727 Bibliography 732 Chapter 21 Nonlinear Programming Algorithms Unconstrained Algorithms Direct Search Method Gradient Method Constrained Algorithms Separable Programming Quadratic Programming Chance-Constrained Programming 754 Contents Linear Combinations Method SUMT Algorithm 760 Bibliography 767 Appendix A Statistical Tables 763 Appendix B Partial Answers to Selected Problems 767 Index 813