WIXLIB

OperationsResearchA P P L I C AT I O N SAN D ALGOR ITH MS

D U X B U R Y T I T L E S O F R E L AT E D I N T E R E S TAlbright, Winston & Zappe, Data Analysis and Decision MakingAlbright, VBA for Modelers: Developing Decision Support Systems with Microsoft ExcelBerger & Maurer, Experimental DesignBerk & Carey, Data Analysis with Microsoft ExcelClemen & Reilly, Making Hard Decisions with DecisionToolsDevore, Probability & Statistics for Engineering and the SciencesFourer, Gay & Kernighan, AMPL: A Modeling Language for Mathematical ProgrammingHayter, Probability and Statistics for Engineers and ScientistsHoerl & Snee, Statistical Thinking: Improving Business PerformanceKao, Introduction to Stochastic ProcessesKenett & Zacks, Modern Industrial Statistics: Design of Quality and ReliabilityKirkwood, Strategic Decision Making: Multiobjective Decision Analysis with SpreadsheetsLapin & Whisler, Quantitative Decision Making with Spreadsheet ApplicationsLattin, Carroll & Green, Analyzing Multivariate DataLawson & Erjavec, Engineering and Industrial StatisticsMiddleton, Data Analysis Using Microsoft ExcelMinh, Applied Probability ModelsNeuwirth & Arganbright, Mathematical Modeling with Microsoft ExcelRamsey, The Elements of Statistics with Applications to EconomicsSAS Institute Inc., JMP-IN: Statistical Discovery SoftwareSavage, Decision Making with InsightSchrage, Optimization Modeling Using LINDOSeila, Ceric & Tadikamalla, Applied Simulation ModelingShapiro, Modeling the Supply ChainTan, Finite Mathematics for the Managerial, Life, and Social SciencesTaylor, Excel Essentials: Using Microsoft Excel for Data Analysis and Decision MakingVardeman & Jobe, Basic Engineering Data Collection and AnalysisVining, Statistical Methods for EngineersWaner & Costenoble, Finite MathematicsWinston, Introduction to Probability ModelsWinston, Simulation Modeling Using @RiskWinston & Albright, Practical Management ScienceWinston & Venkataramanan, Introduction to Mathematical ProgrammingTo order copies contact your local bookstore or call 1-800-354-9706.For more information go to: www.duxbury.com

OperationsResearchA P P L I C AT I O N SAN D ALGOR ITH MSFOURTH EDITIONWayne L. WinstonINDIANA UNIVERSITYWITH CASES BYJeffrey B. GoldbergUNIVERSITY OF ARIZONAAustraliaSpain Canada MexicoUnited Kingdom SingaporeUnited States

Publisher: Curt HinrichsProduction Service: Hoyt Publishing ServicesAssistant Editor: Ann DayText Designer: Kaelin ChappellEditorial Assistant: Katherine BraytonCopy Editors: David Hoyt and Erica LeeTechnology Project Manager: Burke TaftIllustrator: Electronic Illustrators GroupMarketing Manager: Joseph RogoveCover Designer: Lisa LanghoffMarketing Assistant: Jessica PerryCover Image: Getty Images, photographer Nick KoudisAdvertising Project Manager: Tami StrangCover Printer: Transcontinental Printing, LouisevillePrint/Media Buyer: Jessica ReedCompositor: ATLIS GraphicsPermissions Editor: Bob KauserPrinter: Transcontinental Printing, LouisevilleProduction Project Manager: Hal HumphreyCOPYRIGHT 2004 Brooks/Cole, a division of ThomsonLearning, Inc. Thomson LearningTM is a trademark used hereinunder license.ALL RIGHTS RESERVED. No part of this work covered by thecopyright hereon may be reproduced or used in any form or byany means—graphic, electronic, or mechanical, including but notlimited to photocopying, recording, taping, Web distribution, information networks, or information storage and retrieval systems—without the written permission of the publisher.Printed in Canada1 2 3 4 5 6 707 06 05 04 03For more information about our products, contact us at:Thomson Learning Academic Resource Center1-800-423-0563For permission to use material from this text, contact us by:Phone: 1-800-730-2214 Fax: 1-800-730-2215Web: http://www.thomsonrights.comLibrary of Congress Control Number 2003105883Student Edition with InfoTrac College Edition:ISBN 0-534-38058-1Student Edition without InfoTrac College Edition:ISBN 0-534-42358-2International Student Edition:ISBN 0-534-52020-0Brooks/Cole—Thomson Learning10 Davis DriveBelmont, CA 94002USAAsiaThomson Learning5 Shenton Way #01-01UIC BuildingSingapore 068808Australia/New ZealandThomson Learning102 Dodds StreetSouthbank, Victoria 3006AustraliaCanadaNelson1120 Birchmount RoadToronto, Ontario M1K 5G4CanadaEurope/Middle East/AfricaThomson LearningHigh Holborn House50/51 Bedford RowLondon WC1R 4LRUnited KingdomLatin AmericaThomson LearningSeneca, 53Colonia Polanco11560 Mexico D.F.MexicoSpain/PortugalParaninfoCalle Magallanes, 2528015 MadridSpain

Brief Contents1 An Introduction to Model Building 12 Basic Linear Algebra 113 Introduction to Linear Programming 494 The Simplex Algorithm and Goal Programming 1275 Sensitivity Analysis: An Applied Approach 2276 Sensitivity Analysis and Duality 2627 Transportation, Assignment, and Transshipment Problems 3608 Network Models 4139 Integer Programming 47510 Advanced Topics in Linear Programming 56211 Nonlinear Programming 61012 Review of Calculus and Probability 70713 Decision Making under Uncertainty 73714 Game Theory 80315 Deterministic EOQ Inventory Models 84616 Probabilistic Inventory Models 88017 Markov Chains 92318 Deterministic Dynamic Programming 96119 Probabilistic Dynamic Programming 101620 Queuing Theory 105121 Simulation 114522 Simulation with Process Model 119123 Spreadsheet Simulation with the Excel Add-in @Risk 121224 Forecasting Models 1275v

ContentsPreface xiiAbout the Author xvi1Special Cases 63A Diet Problem 683.5 A Work-Scheduling Problem 723.6 A Capital Budgeting Problem 763.7 Short-Term Financial Planning 823.8 Blending Problems 853.9 Production Process Models 953.10 Using Linear Programming to SolveMultiperiod Decision Problems: AnInventory Model 1003.1l Multiperiod Financial Models 1053.12 Multiperiod Work Scheduling 1093.33.4An Introduction toModel-Building 11.11.21.31.41.5An Introduction to Modeling 1The Seven-Step Model-BuildingProcess 5CITGO Petroleum 6San Francisco Police DepartmentScheduling 7GE Capital 942Basic Linear Algebra 112.12.22.32.42.52.63Introduction to Linear Programming 493.13.2viMatrices and Vectors 11Matrices and Systems of LinearEquations 20The Gauss-Jordan Method for SolvingSystems of Linear Equations 22Linear Independence and LinearDependence 32The Inverse of a Matrix 36Determinants 42What Is a Linear ProgrammingProblem? 49The Graphical Solution of Two-VariableLinear Programming Problems 56The Simplex Algorithm and GoalProgramming 127How to Convert an LP to StandardForm 1274.2 Preview of the Simplex Algorithm 1304.3 Direction of Unboundedness 1344.4 Why Does an LP Have anOptimal bfs? 1364.5 The Simplex Algorithm 1404.6 Using the Simplex Algorithm to SolveMinimization Problems 1494.7 Alternative Optimal Solutions 1524.8 Unbounded LPs 1544.9 The LINDO Computer Package 1584.10 Matrix Generators, LINGO, and Scalingof LPs 1634.11 Degeneracy and the Convergence of theSimplex Algorithm 1684.12 The Big M Method 1724.1

4.13 The Two-Phase Simplex Method 178Unrestricted-in-Sign Variables 1844.15 Karmarkar's Method for Solving LPs 1904.16 Multiattribute Decision Making in theAbsence of Uncertainty: GoalProgramming 1914.l7 Using the Excel Solver to Solve LPs 2024.147Transportation, Assignment, andTransshipment Problems 3607.17.27.37.45Sensitivity Analysis:An Applied Approach 2275.15.25.35.4A Graphical Introduction to SensitivityAnalysis 227The Computer and SensitivityAnalysis 232Managerial Use of Shadow Prices 246What Happens to the Optimal z-ValueIf the Current Basis Is No LongerOptimal? 2487.57.68Network Models 4138.18.28.38.48.56Sensitivity Analysis and Duality 262A Graphical Introduction to SensitivityAnalysis 2626.2 Some Important Formulas 2676.3 Sensitivity Analysis 2756.4 Sensitivity Analysis When More ThanOne Parameter Is Changed: The 100%Rule 2896.5 Finding the Dual of an LP 2956.6 Economic Interpretation of the DualProblem 3026.7 The Dual Theorem and ItsConsequences 3046.8 Shadow Prices 3136.9 Duality and Sensitivity Analysis 3236.10 Complementary Slackness 3256.11 The Dual Simplex Method 3296.12 Data Envelopment Analysis 3358.68.76.19Formulating Transportation Problems 360Finding Basic Feasible Solutions forTransportation Problems 373The Transportation Simplex Method 382Sensitivity Analysis for TransportationProblems 390Assignment Problems 393Transshipment Problems 400Basic Definitions 413Shortest-Path Problems 414Maximum-Flow Problems 419CPM and PERT 431Minimum-Cost Network FlowProblems 450Minimum Spanning Tree Problems 456The Network Simplex Method 459Integer Programming 4759.19.29.39.49.59.69.79.8Introduction to Integer Programming 475Formulating Integer ProgrammingProblems 477The Branch-and-Bound Method forSolving Pure Integer ProgrammingProblems 5l2The Branch-and-Bound Method forSolving Mixed Integer ProgrammingProblems 523Solving Knapsack Problems by theBranch-and-Bound Method 524Solving Combinatorial OptimizationProblems by the Branch-and-BoundMethod 527Implicit Enumeration 540The Cutting Plane Algorithm 545Contentsvii

10Advanced Topics in LinearProgramming 56213Decision Makingunder Uncertainty 73710.1 The Revised Simplex Algorithm 56213.1 Decision Criteria 73710.2 The Product Form of the Inverse 56713.2 Utility Theory 74110.3 Using Column Generation to Solve13.3 Flaws in Expected MaximizationLarge-Scale LPs 57010.4 The Dantzig-Wolfe DecompositionAlgorithm 57610.5 The Simplex Method for Upper-BoundedVariables 59310.6 Karmarkar's Method for Solving LPs 59713.413.513.613.711Nonlinear Programming 61011.1 Review of Differential Calculus 6101411.2 Introductory Concepts 616Game Theory 80314.111.3 Convex and Concave Functions 63014.211.4 Solving NLPs with One Variable 63711.5 Golden Section Search 64911.6 Unconstrained Maximization n with Several Variables 655The Method of Steepest Ascent 660Lagrange Multipliers 663The Kuhn–Tucker Conditions 670Quadratic Programming 680Separable Programming 688The Method of Feasible Directions 693Pareto Optimality and TradeoffCurves 69514.414.514.614.71512Review of Calculusand Probability 70712.1 Review of Integral Calculus 70715.1 Introduction to Basic15.215.312.4 Bayes’ Rule 71312.5 Random Variables, Mean, Variance,and Covariance 71512.6 The Normal Distribution 72212.7 z-Transforms 730viiiContentsTwo-Person Zero-Sum and Constant-SumGames: Saddle Points 803Two-Person Zero-Sum Games:Randomized Strategies, Domination, andGraphical Solution 807Linear Programming and Zero-SumGames 816Two-Person Nonconstant-SumGames 827Introduction to n-Person GameTheory 832The Core of an n-Person Game 834The Shapley Value 837Deterministic EOQInventory Models 84612.2 Differentiation of Integrals 71012.3 Basic Rules of Probability 710of Utility: Prospect Theory andFraming Effects 755Decision Trees 758Bayes’ Rule and Decision Trees 767Decision Making withMultiple Objectives 773The Analytic Hierarchy Process 78515.415.5Inventory Models 846The Basic Economic OrderQuantity Model 848Computing the Optimal OrderQuantity When QuantityDiscounts Are Allowed 859The Continuous Rate EOQ Model 865The EOQ Model with BackOrders Allowed 868