Operations Research APPLICATIONS AND ALGORITHMS DUXBURY TITLES OF RELATED INTEREST Albright, Winston & Zappe, Data Analysis and Decision Making Albright, VBA for Modelers: Developing Decision Support Systems with Microsoft Excel Berger & Maurer, Experimental Design Berk & Carey, Data Analysis with Microsoft Excel Clemen & Reilly, Making Hard Decisions with DecisionTools Devore, Probability & Statistics for Engineering and the Sciences Fourer, Gay & Kernighan, AMPL: A Modeling Language for Mathematical Programming Hayter, Probability and Statistics for Engineers and Scientists Hoerl & Snee, Statistical Thinking: Improving Business Performance Kao, Introduction to Stochastic Processes Kenett & Zacks, Modern Industrial Statistics: Design of Quality and Reliability Kirkwood, Strategic Decision Making: Multiobjective Decision Analysis with Spreadsheets Lapin & Whisler, Quantitative Decision Making with Spreadsheet Applications Lattin, Carroll & Green, Analyzing Multivariate Data Lawson & Erjavec, Engineering and Industrial Statistics Middleton, Data Analysis Using Microsoft Excel Minh, Applied Probability Models Neuwirth &Arganbright, Mathematical Modeling with Microsoft Excel Ramsey, The Elements of Statistics with Applications to Economics SAS Institute Inc., JMP-IN: Statistical Discovery Software Savage, Decision Making with Insight Schrage, Optimization Modeling Using LINDO Seila, Ceric & Tadikamalla, Applied Simulation Modeling Shapiro, Modeling the Supply Chain Tan, Finite Mathematics for the Managerial, Life, and Social Sciences Taylor, Excel Essentials: Using Microsoft Excel for Data Analysis and Decision Making Vardeman & Jobe, Basic Engineering Data Collection and Analysis Vining, Statistical Methods for Engineers Waner & Costenoble, Finite Mathematics Winston, Introduction to Probability Models Winston, Simulation Modeling Using @Risk Winston & Albright, Practical Management Science Winston & Venkataramanan, Introduction to Mathematical Programming To order copies contact your local bookstore or call 1-800-354-9706. For more information go to: www.duxbury.com (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) Operations Research AP P LI CATI O N S AN D ALG O R ITH M S F O U RTH E D ITI O N Wayne L. Winston INDIANA UNIVERSITY WITH CASES BY Jeffrey B. Goldberg UNIVERSITY OF ARIZONA Australia (cid:2) Canada (cid:2) Mexico (cid:2) Singapore Spain (cid:2) United Kingdom (cid:2) United States Publisher: Curt Hinrichs Production Service: Hoyt Publishing Services Assistant Editor: Ann Day Text Designer: Kaelin Chappell Editorial Assistant: Katherine Brayton Copy Editors: David Hoyt and Erica Lee Technology Project Manager: Burke Taft Illustrator: Electronic Illustrators Group Marketing Manager: Joseph Rogove Cover Designer: Lisa Langhoff Marketing Assistant: Jessica Perry Cover Image:Getty Images, photographer Nick Koudis Advertising Project Manager: Tami Strang Cover Printer: Transcontinental Printing, Louiseville Print/Media Buyer: Jessica Reed Compositor: ATLIS Graphics Permissions Editor: Bob Kauser Printer:Transcontinental Printing, Louiseville Production Project Manager: Hal Humphrey COPYRIGHT © 2004 Brooks/Cole, a division of Thomson Asia Learning, Inc. Thomson LearningTMis a trademark used herein Thomson Learning under license. 5 Shenton Way #01-01 UICBuilding ALL RIGHTS RESERVED. No part of this work covered by the Singapore 068808 copyright hereon may be reproduced or used in any form or by Australia/New Zealand any means—graphic, electronic, or mechanical, including but not Thomson Learning limited to photocopying, recording, taping, Web distribution, in- 102 Dodds Street formation networks, or information storage and retrieval sys- Southbank, Victoria 3006 tems—without the written permission of the publisher. Australia Printed in Canada Canada Nelson 1 2 3 4 5 6 7 07 06 05 04 03 1120 Birchmount Road Toronto, Ontario M1K 5G4 For more information about our products, contact us at: Canada Thomson Learning Academic Resource Center Europe/Middle East/Africa 1-800-423-0563 Thomson Learning For permission to use material from this text, contact us by: High Holborn House Phone:1-800-730-2214 Fax:1-800-730-2215 50/51 Bedford Row London WC1R 4LR Web:http://www.thomsonrights.com United Kingdom Latin America Library of Congress Control Number 2003105883 Thomson Learning Student Edition with InfoTrac College Edition: Seneca, 53 ISBN 0-534-38058-1 Colonia Polanco 11560 Mexico D.F. Student Edition without InfoTrac College Edition: Mexico ISBN 0-534-42358-2 International Student Edition: Spain/Portugal Paraninfo ISBN 0-534-52020-0 Calle Magallanes, 25 28015 Madrid Brooks/Cole—Thomson Learning Spain 10 Davis Drive Belmont,CA 94002 USA (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) Brief Contents 1 An Introduction to Model Building 1 2 Basic Linear Algebra 11 3 Introduction to Linear Programming 49 4 The Simplex Algorithm and Goal Programming 127 5 Sensitivity Analysis:An Applied Approach 227 6 Sensitivity Analysis and Duality 262 7 Transportation, Assignment, and Transshipment Problems 360 8 Network Models 413 9 Integer Programming 475 10 Advanced Topics in Linear Programming 562 11 Nonlinear Programming 610 12 Review of Calculus and Probability 707 13 Decision Making under Uncertainty 737 14 Game Theory 803 15 Deterministic EOQ Inventory Models 846 16 Probabilistic Inventory Models 880 17 Markov Chains 923 18 Deterministic Dynamic Programming 961 19 Probabilistic Dynamic Programming 1016 20 Queuing Theory 1051 21 Simulation 1145 22 Simulation with Process Model 1191 23 Spreadsheet Simulation with the Excel Add-in @Risk 1212 24 Forecasting Models 1275 v (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) Contents Preface xii 3.3 Special Cases 63 About the Author xvi 3.4 A Diet Problem 68 3.5 A Work-Scheduling Problem 72 3.6 A Capital Budgeting Problem 76 An Introduction to 3.7 Short-Term Financial Planning 82 1 3.8 Blending Problems 85 Model-Building 1 3.9 Production Process Models 95 1.1 An Introduction to Modeling 1 3.10 Using Linear Programming to Solve 1.2 The Seven-Step Model-Building Multiperiod Decision Problems: An Process 5 Inventory Model 100 1.3 CITGO Petroleum 6 3.1l Multiperiod Financial Models 105 1.4 San Francisco Police Department 3.12 Multiperiod Work Scheduling 109 Scheduling 7 1.5 GE Capital 9 The Simplex Algorithm and Goal 4 Programming 127 Basic Linear Algebra 2 11 4.1 How to Convert an LP to Standard 2.1 Matrices and Vectors 11 Form 127 2.2 Matrices and Systems of Linear 4.2 Preview of the Simplex Algorithm 130 Equations 20 4.3 Direction of Unboundedness 134 2.3 The Gauss-Jordan Method for Solving 4.4 Why Does an LP Have an Systems of Linear Equations 22 Optimal bfs? 136 2.4 Linear Independence and Linear 4.5 The Simplex Algorithm 140 Dependence 32 4.6 Using the Simplex Algorithm to Solve 2.5 The Inverse of a Matrix 36 Minimization Problems 149 2.6 Determinants 42 4.7 Alternative Optimal Solutions 152 4.8 Unbounded LPs 154 4.9 The LINDO Computer Package 158 Introduction to Linear Programming 3 49 4.10 Matrix Generators, LINGO, and Scaling of LPs 163 3.1 What Is a Linear Programming Problem? 49 4.11 Degeneracy and the Convergence of the Simplex Algorithm 168 3.2 The Graphical Solution of Two-Variable Linear Programming Problems 56 4.12 The Big M Method 172 vi 4.13 The Two-Phase Simplex Method 178 Transportation, Assignment, and 4.14 Unrestricted-in-Sign Variables 184 7 4.15 Karmarkar's Method for Solving LPs 190 Transshipment Problems 360 4.16 Multiattribute Decision Making in the 7.1 Formulating Transportation Problems 360 Absence of Uncertainty: Goal Programming 191 7.2 Finding Basic Feasible Solutions for Transportation Problems 373 4.l7 Using the Excel Solver to Solve LPs 202 7.3 The Transportation Simplex Method 382 7.4 Sensitivity Analysis for Transportation Sensitivity Analysis: Problems 390 5 7.5 Assignment Problems 393 An Applied Approach 227 7.6 Transshipment Problems 400 5.1 A Graphical Introduction to Sensitivity Analysis 227 5.2 The Computer and Sensitivity 8 Network Models 413 Analysis 232 8.1 Basic Definitions 413 5.3 Managerial Use of Shadow Prices 246 8.2 Shortest-Path Problems 414 5.4 What Happens to the Optimal z-Value If the Current Basis Is No Longer 8.3 Maximum-Flow Problems 419 Optimal? 248 8.4 CPM and PERT 431 8.5 Minimum-Cost Network Flow Problems 450 Sensitivity Analysis and Duality 6 262 8.6 Minimum Spanning Tree Problems 456 8.7 The Network Simplex Method 459 6.1 A Graphical Introduction to Sensitivity Analysis 262 6.2 Some Important Formulas 267 Integer Programming 9 475 6.3 Sensitivity Analysis 275 6.4 Sensitivity Analysis When More Than 9.1 Introduction to Integer Programming 475 One Parameter Is Changed: The 100% 9.2 Formulating Integer Programming Rule 289 Problems 477 6.5 Finding the Dual of an LP 295 9.3 The Branch-and-Bound Method for 6.6 Economic Interpretation of the Dual Solving Pure Integer Programming Problem 302 Problems 5l2 6.7 The Dual Theorem and Its 9.4 The Branch-and-Bound Method for Consequences 304 Solving Mixed Integer Programming 6.8 Shadow Prices 313 Problems 523 6.9 Duality and Sensitivity Analysis 323 9.5 Solving Knapsack Problems by the Branch-and-Bound Method 524 6.10 Complementary Slackness 325 9.6 Solving Combinatorial Optimization 6.11 The Dual Simplex Method 329 Problems by the Branch-and-Bound 6.12 Data Envelopment Analysis 335 Method 527 9.7 Implicit Enumeration 540 9.8 The Cutting Plane Algorithm 545 Contents vii Advanced Topics in Linear Decision Making 10 13 Programming under Uncertainty 562 737 10.1 The Revised Simplex Algorithm 562 13.1 Decision Criteria 737 10.2 The Product Form of the Inverse 567 13.2 Utility Theory 741 10.3 Using Column Generation to Solve 13.3 Flaws in Expected Maximization Large-Scale LPs 570 of Utility:Prospect Theory and 10.4 The Dantzig-Wolfe Decomposition Framing Effects 755 Algorithm 576 13.4 Decision Trees 758 10.5 The Simplex Method for Upper-Bounded 13.5 Bayes’Rule and Decision Trees 767 Variables 593 13.6 Decision Making with 10.6 Karmarkar's Method for Solving LPs 597 Multiple Objectives 773 13.7 The Analytic Hierarchy Process 785 Nonlinear Programming 11 610 Game Theory 14 803 11.1 Review of Differential Calculus 610 11.2 Introductory Concepts 616 14.1 Two-Person Zero-Sum and Constant-Sum 11.3 Convex and Concave Functions 630 Games: Saddle Points 803 11.4 Solving NLPs with One Variable 637 14.2 Two-Person Zero-Sum Games: Randomized Strategies, Domination, and 11.5 Golden Section Search 649 Graphical Solution 807 11.6 Unconstrained Maximization and 14.3 Linear Programming and Zero-Sum Minimization with Several Variables 655 Games 816 11.7 The Method of Steepest Ascent 660 14.4 Two-Person Nonconstant-Sum 11.8 Lagrange Multipliers 663 Games 827 11.9 The Kuhn–Tucker Conditions 670 14.5 Introduction to n-Person Game 11.10 Quadratic Programming 680 Theory 832 11.11 Separable Programming 688 14.6 The Core of an n-Person Game 834 11.12 The Method of Feasible Directions 693 14.7 The Shapley Value 837 11.13 Pareto Optimality and Tradeoff Curves 695 Deterministic EOQ 15 Inventory Models 846 Review of Calculus 12 and Probability 15.1 Introduction to Basic 707 Inventory Models 846 12.1 Review of Integral Calculus 707 15.2 The Basic Economic Order Quantity Model 848 12.2 Differentiation of Integrals 710 15.3 Computing the Optimal Order 12.3 Basic Rules of Probability 710 Quantity When Quantity 12.4 Bayes’Rule 713 Discounts Are Allowed 859 12.5 Random Variables, Mean, Variance, 15.4 The Continuous Rate EOQ Model 865 and Covariance 715 15.5 The EOQ Model with Back 12.6 The Normal Distribution 722 Orders Allowed 868 12.7 z-Transforms 730 viii Contents 15.6 When to Use EOQ Models 872 18.6 Formulating Dynamic 15.7 Multiple-Product EOQ Models 873 Programming Recursions 989 18.7 The Wagner–Whitin Algorithm and the Silver–Meal Heuristic 1001 Probabilistic Inventory Models 18.8 Using Excel to Solve Dynamic 16 880 Programming Problems 1006 16.1 Single-Period Decision Models 880 16.2 The Concept of Marginal Analysis 880 Probabilistic Dynamic 16.3 The News Vendor Problem: 19 Discrete Demand 881 Programming 1016 16.4 The News Vendor Problem: Continuous Demand 886 19.1 When Current Stage Costs Are 16.5 Other One-Period Models 888 Uncertain, but the Next Period’s State Is Certain 1016 16.6 The EOQ with Uncertain Demand: The (r, q) and (s, S) Models 890 19.2 A Probabilistic Inventory Model 1019 16.7 The EOQ with Uncertain Demand: 19.3 How to Maximize the Probability of a The Service Level Approach to Favorable Event Occurring 1023 Determining Safety Stock Level 898 19.4 Further Examples of Probabilistic 16.8 (R, S) Periodic Review Policy 907 Dynamic Programming Formulations 1029 16.9 The ABCInventory 19.5 Markov Decision Processes 1036 Classification System 911 16.10 Exchange Curves 913 Queuing Theory 20 1051 Markov Chains 20.1 Some Queuing Terminology 1051 17 923 20.2 Modeling Arrival and Service 17.1 What Is a Stochastic Process? 923 Processes 1053 17.2 What Is a Markov Chain? 924 20.3 Birth–Death Processes 1053 17.3 n-Step Transition Probabilities 928 20.4 The M/M/1/GD/∞/∞Queuing System and the Queuing Formula L(cid:2) (cid:3)W1072 17.4 Classification of States in a Markov Chain 931 20.5 The M/M/1/GD/c/∞Queuing System 1083 17.5 Steady-State Probabilities and Mean 20.6 The M/M/s/GD/∞/∞Queuing First Passage Times 934 System 1087 17.6 Absorbing Chains 942 20.7 The M/G/∞/GD/∞/∞and GI/G/∞/GD/∞/∞Models 1095 17.7 Work-Force Planning Models 950 20.8 The M/G/1/GD/∞/∞Queuing System 1097 20.9 Finite Source Models:The Machine Repair Model 1099 Deterministic Dynamic 18 20.10 Exponential Queues in Series and Programming 961 Open Queuing Networks 1104 20.11 The M/G/s/GD/s/∞System (Blocked 18.1 Two Puzzles 961 Customers Cleared) 1112 18.2 ANetwork Problem 962 20.12 How to Tell Whether Interarrival Times 18.3 An Inventory Problem 969 and Service Times Are Exponential 1115 18.4 Resource-Allocation Problems 974 20.13 Closed Queuing Networks 1119 18.5 Equipment-Replacement Problems 985 Contents ix 20.14 An Approximation for the G/G/m 23.5 The RISKGENERAL Function 1244 Queuing System 1124 23.6 The RISKCUMULATIVE 20.15 Priority Queuing Models 1126 Random Variable 1248 20.16 Transient Behavior of 23.7 The RISKTRIGEN Random Variable 1249 Queuing Systems 1131 23.8 Creating a Distribution Based on a Point Forecast 1250 23.9 Forecasting the Income of a 21 Simulation 1145 Major Corporation 1252 23.10 Using Data to Obtain Inputs for New 21.1 Basic Terminology 1145 Product Simulations 1256 21.2 An Example of a Discrete-Event 23.11 Simulation and Bidding 1267 Simulation 1146 23.12 Playing Craps with @Risk 1269 21.3 Random Numbers and Monte Carlo 23.13 Simulating the NBAFinals 1271 Simulation 1153 21.4 An Example of Monte Carlo Simulation 1158 Forecasting Models 21.5 Simulations with Continuous 24 1275 Random Variables 1162 24.1 Moving-Average Forecast Methods 1275 21.6 An Example of a Stochastic 24.2 Simple Exponential Smoothing 1281 Simulation 1173 24.3 Holt’s Method:Exponential Smoothing 21.7 Statistical Analysis in Simulations 1180 with Trend 1283 21.8 Simulation Languages 1183 24.4 Winter’s Method:Exponential Smoothing 21.9 The Simulation Process 1184 with Seasonality 1286 24.5 Ad Hoc Forecasting 1292 24.6 Simple Linear Regression 1302 Simulation with Process Model 22 1191 24.7 Fitting Nonlinear Relationships 1312 22.1 Simulating an M/M/1 Queuing 24.8 Multiple Regression 1317 System 1191 22.2 Simulating an M/M/2 System 1195 @Risk Crib Sheet 22.3 Simulating aSeries System 1199 Appendix 1: 1336 22.4 Simulating Open Queuing Networks 1203 22.5 Simulating Erlang Service Times 1207 22.6 What Else Can Process Model Do? 1210 Cases Appendix 2: 1350 Case 1 Help, I’m Not Getting Any Simulation with the Excel Younger 1351 23 Add-in @Risk Case 2 Solar Energy for Your Home 1351 1212 Case 3 Golf-Sport: Managing Operations 1352 23.1 Introduction to @Risk: Case 4 Vision Corporation: Production Planning The News Vendor Problem 1212 and Shipping 1355 23.2 Modeling Cash Flows from Case 5 Material Handling in a General a New Product 1222 Mail-Handling Facility 1356 23.3 Product Scheduling Models 1232 Case 6 Selecting Corporate Training 23.4 Reliability and Warranty Modeling 1238 Programs 1359 x Contents