Operations Research - KSU

1 OperationsResearchAPPLICATIONSAND ALGORITHMSDUXBURY 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 DesignBerk & 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 ScientistsHoerl & Snee, Statistical Thinking: Improving Business PerformanceKao, Introduction to Stochastic ProcessesKenett & 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 ApplicationsLattin, 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 ExcelRamsey, The Elements of Statistics with Applications to Economics SAS Institute Inc.

2 , JMP-IN: Statistical Discovery Software Savage, Decision Making with Insight Schrage, Optimization Modeling Using LINDOS eila, Ceric & Tadikamalla, Applied Simulation ModelingShapiro, Modeling the Supply ChainTa n , 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 Analysis Vining, Statistical Methods for Engineers Waner & Costenoble, Finite MathematicsWinston, Introduction to Probability ModelsWinston, Simulation Modeling Using @Risk Winston & 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: ALGORITHMSFOURTH EDITION Wayne L. WinstonINDIANA UNIVERSITY WITH CASES BYJeffrey B. GoldbergUNIVERSITY OF ARIZONAA ustralia Canada Mexico Singapore Spain United Kingdom United States Publisher: Curt HinrichsAssistant Editor: Ann DayEditorial Assistant: Katherine BraytonTechnology Project Manager: Burke TaftMarketing Manager: Joseph RogoveMarketing Assistant: Jessica PerryAdvertising Project Manager: Tami StrangPrint/Media Buyer: Jessica ReedPermissions Editor: Bob KauserProduction Project Manager: Hal HumphreyProduction Service: Hoyt Publishing ServicesText Designer: Kaelin ChappellCopy Editors: David Hoyt and Erica LeeIllustrator: Electronic Illustrators GroupCover Designer: Lisa LanghoffCover Image:Getty Images, photographer Nick KoudisCover Printer: Transcontinental Printing, LouisevilleCompositor: ATLIS GraphicsPrinter:Transcontinental Printing, LouisevilleCOPYRIGHT 2004 Brooks/Cole, a division of ThomsonLearning, Inc.

3 Thomson LearningTMis a trademark used hereinunder 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, in-formation networks, or information storage and retrieval sys-tems without the written permission of the in Canada 1234567 07 06050403 For more information about our products, contact us at:Thomson Learning Academic Resource Center1-800-423-0563 For permission to use material from this text, contact us by:Phone:1-800-730-2214 Fax:1-800-730-2215 Web: of Congress Control Number 2003105883 Student Edition with InfoTrac College Edition:ISBN 0-534-38058-1 Student Edition without InfoTrac College Edition:ISBN 0-534-42358-2 International Student Edition:ISBN 0-534-52020-0 Brooks/Cole Thomson Learning10 Davis DriveBelmont, CA 94002 USAAsiaThomson Learning5 Shenton Way #01-01 UIC BuildingSingapore 068808 Australia/New ZealandThomson Learning102 Dodds StreetSouthbank, Victoria 3006 AustraliaCanadaNelson1120 Birchmount RoadToronto, Ontario M1K 5G4 CanadaEurope/Middle East/AfricaThomson LearningHigh Holborn House50/51 Bedford RowLondon WC1R 4 LRUnited KingdomLatin AmericaThomson LearningSeneca, 53 Colonia Polanco11560 Mexico Magallanes, 2528015 MadridSpain Brief Contents1An Introduction to Model Building 12 Basic Linear Algebra 113 Introduction to Linear Programming 494 The Simplex Algorithm and Goal Programming 1275 Sensitivity Analysis.

4 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 xvi1An Introduction to Model-Building Introduction to Modeling Seven-Step Model-Building Process 5 Petroleum 6 Francisco Police DepartmentScheduling 7 Capital 9 2 Basic Linear Algebra and Vectors and Systems of Linear Equations Gauss-Jordan Method for SolvingSystems of Linear Equations Independence and LinearDependence Inverse of a

5 Matrix 423 Introduction to Linear Programming Is a Linear Programming Problem? Graphical Solution of Two-VariableLinear Programming Problems Cases Diet Problem Work-Scheduling Problem Capital Budgeting Problem Financial Planning Problems Process Models Linear Programming to SolveMultiperiod Decision Problems: AnInventory Model Financial Models Work Scheduling 1094 The Simplex Algorithm and GoalProgramming to Convert an LP to Standard Form of the Simplex Algorithm of Unboundedness Does an LP Have an Optimal bfs? Simplex Algorithm the Simplex Algorithm to SolveMinimization Problems Optimal Solutions LPs LINDO Computer Package Generators, LINGO, and Scalingof LPs and the Convergence of theSimplex Algorithm Big M Method Two-Phase Simplex Method Variables 's Method for Solving LPs Decision Making in theAbsence of Uncertainty: GoalProgramming the Excel Solver to Solve LPs 2025 Sensitivity Analysis:An Applied Approach Graphical Introduction to SensitivityAnalysis Computer and Sensitivity Analysis Use of Shadow Prices Happens to the Optimal z-Value If the Current Basis Is No LongerOptimal?

6 2486 Sensitivity Analysis and Duality Graphical Introduction to SensitivityAnalysis Important Formulas Analysis Analysis When More ThanOne Parameter Is Changed: The 100%Rule the Dual of an LP Interpretation of the DualProblem Dual Theorem and Its Consequences Prices and Sensitivity Analysis Slackness Dual Simplex Method Envelopment Analysis 3357 Transportation, Assignment, andTransshipment Problems 3607. 1 Formulating Transportation Problems 3607. 2 Finding Basic Feasible Solutions forTransportation Problems 3737. 3 The Transportation Simplex Method 3827. 4 Sensitivity Analysis for TransportationProblems 3907. 5 Assignment Problems 3937. 6 Transshipment Problems 4008 Network Models Definitions Problems Problems and PERT Network Flow Problems Spanning Tree Problems Network Simplex Method 4599 Integer Programming to Integer Programming Integer ProgrammingProblems Branch-and-Bound Method forSolving Pure Integer ProgrammingProblems Branch-and-Bound Method forSolving Mixed Integer ProgrammingProblems Knapsack Problems by theBranch-and-Bound Method Combinatorial OptimizationProblems by the Branch-and-BoundMethod Enumeration Cutting Plane Algorithm 545viiiContents10 Advanced Topics in Linear Programming Revised Simplex Algorithm Product Form of the Inverse Column Generation to SolveLarge-Scale LPs Dantzig-Wolfe DecompositionAlgorithm Simplex Method for Upper-BoundedVariables 's Method for Solving LPs 59711 Nonlinear Programming of Differential Calculus Concepts and Concave Functions NLPs with One Variable Section Search Maximization andMinimization with

7 Several Variables Method of Steepest Ascent Multipliers 663 Kuhn Tucker Conditions Programming Programming Method of Feasible Directions Optimality and Tradeoff Curves 69512 Review of Calculus and Probability of Integral Calculus of Integrals Rules of Probability Rule 713 Variables, Mean, variance ,and Covariance 715 Normal Distribution 722 730 13 Decision Making under Uncertainty Criteria Theory in expected Maximization of Utility: Prospect Theory and Framing Effects Trees Rule and Decision Trees Making with Multiple Objectives Analytic Hierarchy Process 78514 Game Theory Zero-Sum and Constant-SumGames: Saddle Points Zero-Sum Games:Randomized Strategies, Domination, andGraphical Solution Programming and Zero-SumGames Nonconstant-Sum Games to n-Person Game Theory Core of an n-Person Game Shapley Value 83715 Deterministic EOQ Inventory Models to Basic Inventory Models Basic Economic Order Quantity Model the Optimal Order Quantity When Quantity Discounts Are Allowed Continuous Rate EOQ Model EOQ Model with Back Orders Allowed to Use EOQ Models EOQ Models 87316 Probabilistic Inventory Models Decision Models Concept of Marginal Analysis News Vendor Problem: Discrete Demand News Vendor Problem: Continuous Demand One-Period Models EOQ with Uncertain Demand:The (r, q) and (s, S) Models EOQ with Uncertain Demand:The Service Level Approach toDetermining Safety Stock Level (R, S) Periodic Review Policy ABC Inventory Classification System Curves 91317 Markov Chains 92317.

8 1 What Is a Stochastic Process? 92317. 2 What Is a Markov Chain? 92417. 3n-Step Transition Probabilities 92817. 4 Classification of States in a Markov Chain 93117. 5 Steady-State Probabilities and Mean First Passage Times 93417. 6 Absorbing Chains 94217. 7 Work-Force Planning Models 95018 Deterministic Dynamic Programming Puzzles Network Problem Inventory Problem Problems Problems Dynamic Programming Recursions Wagner Whitin Algorithm and the Silver Meal Heuristic Excel to Solve DynamicProgramming Problems 100619 Probabilistic Dynamic Programming Current Stage Costs AreUncertain, but the Next Period s State Is Certain Probabilistic Inventory Model to Maximize the Probability of aFavorable Event Occurring Examples of ProbabilisticDynamic Programming Formulations Decision Processes 103620 Queuing Theory Queuing Terminology Arrival and Service Processes Death Processes M/M/1/GD/ / Queuing Systemand the Queuing Formula L M/M/1/GD/c/ Queuing System M/M/s/GD/ / Queuing System M/G/ /GD/ / andGI/G/ /GD/ / Models M/G/1/GD/ / Queuing System Source Models.

9 The MachineRepair Model Queues in Series and Open Queuing Networks M/G/s/GD/s/ System (BlockedCustomers Cleared) to Tell Whether Interarrival Timesand Service Times Are Exponential Queuing Networks RISKGENERAL Function RISKCUMULATIVE Random Variable RISKTRIGEN Random Variable a Distribution Based on a Point Forecast the Income of a Major Corporation Data to Obtain Inputs for NewProduct Simulations and Bidding Craps with @Risk the NBA Finals 127124 Forecasting Models Forecast Methods Exponential Smoothing s Method: Exponential Smoothingwith Trend s Method: Exponential Smoothingwith Seasonality Hoc Forecasting Linear Regression Nonlinear Relationships Regression 1317 Appendix 1:@Risk Crib Sheet 1336 Appendix 2:Cases 1350 Case 1 Help, I m Not Getting Any Younger 1351 Case 2 Solar Energy for Your Home 1351 Case 3 Golf-Sport: Managing Operations 1352 Case 4 Vision Corporation: Production Planningand Shipping 1355 Case 5 Material Handling in a General Mail-Handling Facility 1356 Case 6 Selecting Corporate Training Programs Approximation for the G/G/mQueuing System Queuing Models Behavior of Queuing Systems 113121 Simulation Terminology Example of a Discrete-EventSimulation Numbers and Monte CarloSimulation Example of Monte Carlo Simulation with Continuous Random Variables Example of a Stochastic Simulation Analysis in Simulations Languages Simulation Process 118422 Simulation with Process Model an M/M/1 Queuing System an M/M/2 System a Series System Open Queuing Networks Erlang Service Times Else Can Process Model Do?

10 121023 Simulation with the Excel Add-in @Risk to @Risk:The News Vendor Problem Cash Flows from a New Product Scheduling Models and Warranty Modeling 1238 Case 7 Best Chip: Expansion Strategy 1362 Case 8 Emergency Vehicle Location inSpringfield 1364 Case 9 System Design: Project Management 1365 Case 10 Modular Design for the Help-YouCompany 1366 Case 11 Brite Power: Capacity Expansion 1368 Appendix 3:Answers to SelectedProblems 1370 Index 14 0 2 Contentsxi PrefaceIn recent years, Operations Research software has be-come widely available. Its use is illustrated throughoutthis book. Like most tools, however, it is of little valueunless the user understands its application and pur-pose. Users must ensure that the mathematical inputaccurately reflects the real-life problems to be solvedand that the numerical results are correctly applied tosolve them. With this in mind, this book emphasizesmodel formulation and model building as well as theinterpretation of software Audience and PrerequisitesThis book is intended as an advanced beginning or in-termediate text in Operations Research or managementscience.