OPERATIONS RESEARCH \"< I 'TRODl!C'1l0'- !:,ICIITll 1~l)lTro" I lAM DY A. TAl IA Operations Research: An Introduction Eighth Edition Hamdy A. Taha University of Arkansas, Fayetteville Upper Saddle River, New Jersey 07458 Library of Congress Calaloging.in-Publicalion Data Taha, Hamdy A. Operations research: an introduction I Hamdy A. Taha.~8th ed. p. ern. Includes bibliographical references and index_ ISBN 0-13-188923·0 1. Operations research. 2. Programming (Mathematics) 1. Title. T57.6.T3 199796-37160 003 -dc21 96-37160 Vice President and Editorial Director, ECS: Marcia J. Horton Senior Editor: Holly Stark Executive Managing Editor: Vince O'Brien Managing Editor: David A. George Production Editor: Craig Little Director of Creative Services: Paul Belfanti Art Director: Jayne Conte Cover Designer: Bruce Kenselaar Art Editor: Greg Dulles Manufacturing Manager: Alexis HeydJ-Long Manufacturing Buyer: Lisa McDowell _ © 2007 by Pearson Education, Inc. Pearson Prentice Hall _ • - . Pearson Education, Inc. . Upper Saddle River, NJ 07458 All rights reserved. No part of this book may be reproduced, in any form or by any means, without permis- sion in writing from the publisher. Pearson Prentice Hall"" is a trademark of Pearson Education, Inc. Preliminary edition, first, and second editions © 1968,1971 and 1976, respectively, by Hamdy A. Taha. Third, fourth, and fifth editions © 1982,1987, and 1992, respectively, by Macmillan Publishing Company. Sixth and seventh editions © 1997 and 2003, respectively, by Pearson Education, Inc. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effective- ness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, perfor- mance, or use of these programs. Printed in the United States of America 10 9 8 7 6 5 4 3 2 ISBN 0-13-188923-0 Pearson Education Ltd., London Pearson Education Australia Pty. Ltd., Sydney Pearson Education Singapore, Pte. Ltd. Pearson Education North Asia Ltd., Hong Kong Pearson Education Canada, Inc., Toronto Pearson Educaci6n de Mexico, S.A. de C. V. Pearson Education-Japan, Tokyo Pearson Education Malaysia, Pte. Ltd. Pearson Education, Inc., Upper Saddle River, New Jersey To Karen Los rios no llevan agua, el sallas fuentes sec6 ... jYo se donde hay una fuente que no ha de secar el sol! La fuente que no se agota es mi propio coraz6n ... -li: RuizAguilera (1862) Contents Preface xvii About the Author xix Trademarks xx Chapter 1 What Is Operations Research? 1 1.1 Operations Research Models 1 1.2 Solving the OR Model 4 1.3 Queuing and Simulation Mode!s 5 1.4 Art of Modeling 5 1.5 More Than Just Mathematics 7 1.6 Phases of an OR Study 8 1.7 About This Book 10 References 10 Chapter 2 Modeling with Linear Programming 11 2.1 Two-Variable LP Model 12 2.2 Graphical LP Solution 15 2.2.1 Solution of a Maximization Model 16 2.2.2 Solution of a Minimization Model 23 12.3 Selected LP Applications 27 2.3.1 Urban Planning 27 2.3.2 Currency Arbitrage 32 2.3.3 Investment 37 2.3.4 Production Planning and Inventory Control 42 2.3.5 Blending and Refining 51 2.3.6 Manpower Planning 57 2.3.7 Additional Applications 60 2.4 Computer Solution with Excel Solver and AMPL 68 2.4.1 lP Solution with Excel Solver 69 2.4.2 LP Solution with AMPl 73 References 80 Chapter 3 The Simplex Method and Sensitivity Analysis 81 3.1 LP Model in Equation Form 82 3.1.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side 82 3.1.2 Dealing with Unrestricted Variables '84 3.2 Transition from Graphical to Algebraic Solution 85 vii viii Contents 3.3 The Simplex Method 90 3.3.1 Iterative Nature of the Simplex Method 90 3.3.2 Computational Details of the Simplex Algorithm 93 3.3.3 Summary of the Simplex Method 99 3.4 Artificial Starting Solution 103 3.4.1 M-Method 104 3.4.2 Two-Phase Method 108 3.5 Special Cases in the Simplex Method 113 3.5.1 Degeneracy 113 3.5.2 Alternative Optima 116 3.5.3 Unbounded Solution 119 3.5.4 Infeasible Solution 121 3.6 Sensitivity Analysis 123 3.6.1 Graphical Sensitivity Analysis 123 3.6.2 Algebraic Sensitivity Analysis-Changes in the Right- Hand Side 129 3.6.3 Algebraic Sensitivity Analysis-Objective Function 139 3.6.4 Sensitivity Analysis with TORA, Solver, and AMPL 146 References 150 Chapter 4 Duality and Post-Optimal Analysis 151 4.1 Definition of the Dual Problem 151 4.2 Primal-Dual Relationships 156 4.2.1 Review of Simple Matrix Operations 156 4.2.2 Simplex Tableau Layout 158 4.2.3 Optimal Dual Solution 159 4.2.4 Simplex Tableau Computations 165 4.3 Economic Interpretation of Duality 169 4.3.1 Economic Interpretation of Dual Variables 170 4.3.2 Economic Interpretation of Dual Constraints 172 4.4 Additional Simplex Algorithms 174 4.4.1 Dual Simplex Method 174 4.4.2 Generalized Simplex Algorithm 180 4.5 Post-Optimal Analysis 181 4.5.1 Changes Affecting Feasibility 182 4.5.2 Changes Affecting Optimality 187 References 191 Chapter 5 Transportation Model and Its Variants 193 5.1 Definition of the Transportation Model 194 5.2 Nontraditional Transportation Models 201 5.3 The Transportation Algorithm 206 5.3.1 Determination of the Starting Solution 207 5.3.2 Iterative Computations of the Transportation Algorithm 211 Contents ix 5.3.3 Simplex Method Explanation of the Method of Multipliers 220 5.4 The Assignment Model 221 5.4.1 The Hungarian Method 222 5.4.2 Simplex Explanation of the Hungarian Method 228 5.5 The Transshipment Model 229 References 234 Chapter 6 Network Models 235 6.1 Scope and Definition of Network Models 236 6.2 Minimal Spanning Tree Algorithm 239 6.3 Shortest-Route Problem 243 6.3.1 Examples of the Shortest-Route Applications 243 6.3.2 Shortest-Route Algorithms 248 6.3.3 Linear Programming Formulation of the Shortest-Route Problem 257 6.4 Maximal flow model 263 6.4.1 Enumeration of Cuts 263 6.4.2 Maximal-Flow Algorithm 264 6.4.3 Linear Programming Formulation of Maximal Flow Mode 273 6.5 (PM and PERT 275 6.5.1 Network Representation 277 6.5.2 Critical Path (CPM) Computations 282 6.5.3 Construction of the Time Schedule 285 6.5.4 Linear Programming Formulation of CPM 292 6.5.5 PERT Calculations 293 References 296 Chapter 7 Advanced Linear Programming 297 7.1 Simplex Method Fundamentals 298 7.1.1 From Extreme Points to Basic Solutions 300 7.1.2 Generalized Simplex Tableau in Matrix Form 303 7.2 Revised Simplex Method 306 7.2.1 Development of the Optimality and Feasibility Conditions 307 7.2.2 Revised Simplex Algorithm 309 7.3 Bounded-Variables Algorithm 315 7.4 Duality 321 7.4.1 Matrix Definition of the Dual Problem 322 1.4.2 Optimal Dual Solution 322 7.5 Parametric Linear Programming 326 7.5.1 Parametric Changes in ( 327 7.5.2 Parametric Changes in b 330 References 332 x Contents Chapter 8 Goal Programming 333 8.1 A Goal Programming Formulation 334 8.2 Goal Programming Algorithms 338 8.2.1 The Weights Method 338 8.2.2 The Preemptive Method 341 References 348 Chapter 9 Integer Linear Programming 349 9.1 Illustrative Applications 350 9.1.1 Capital Budgeting 350 9.1.2 Set-Covering Problem 354 9.1.3 Fixed-Charge Problem 360 9.1.4 Either-Or and If-Then Constraints 364 9.2 Integer Programming Algorithms 369 9.2.1 Branch-and-Bound (B&B) Algorithm 370 9.2.2 Cutting-Plane Algorithm 379 9.2.3 Computational Considerations in IlP 384 9.3 Traveling Salesperson Problem (TSP) 385 9.3.1 Heuristic Algorithms 389 9.3.2 B&B Solution Algorithm 392 9.3.3 Cutting-Plane Algorithm 395 References 397 Chapter 10 Deterministic Dynamic Programming 399 10.1 Recursive Nature of Computations in DP 400 10.2 Forward and Backward Recursion 403 10.3 Selected DP Applications 405 10.3.1 KnapsackJFly-Away/Cargo-loading Model 405 10.3.2 Work-Force Size Model 413 10.3.3 Equipment Replacement Model 416 10.3.4 Investment Model 420 10.3.5 Inventory Models 423 10.4 Problem of Dimensionality 424 References 426 Chapter 11 Deterministic Inventory Models 427 11.1 General Inventory Model 427 11.2 Role of Demand in the Development of Inventory Models 428 11.3 Static Ecol1omic-Order-Quantity (EOQ) Models 430 11.3.1 Classic EOQ model 430 11.3.2 EOQ with Price Breaks 436 11.3.3 Multi-Item EOQ with Storage Limitation 440 11.4 Dynamic EOQ Models 443 11.4.1 No-Setup Model 445 11.4.2 Setup Model 449 References 461