Operations Research Applications and Algorithms (with CD-ROM and InfoTrac)

by Winston, Wayne L.

• ISBN13: 9780534380588
• ISBN10: 0534380581
• Edition: 4th
• Format: Hardcover
• Copyright: 2003-07-25
• Publisher: Cengage Learning

Summary

The market-leading textbook for the course, Winston's OPERATIONS RESEARCH owes much of its success to its practical orientation and consistent emphasis on model formulation and model building. It moves beyond a mere study of algorithms without sacrificing the rigor that faculty desire. As in every edition, Winston reinforces the book's successful features and coverage with the most recent developments in the field. The Student Suite CD-ROM, which now accompanies every new copy of the text, contains the latest versions of commercial software for optimization, simulation, and decision analysis.

Table of Contents

Preface	xii
About the Author	xvi
An Introduction to Model-Building	1	(10)
An Introduction to Modeling	1	(4)
The Seven-Step Model-Building Process	5	(1)
CITGO Petroleum	6	(1)
San Francisco Police Department Scheduling	7	(2)
GE Capital	9	(2)
Basic Linear Algebra	11	(38)
Matrices and Vectors	11	(9)
Matrices and Systems of Linear Equations	20	(2)
The Gauss-Jordan Method for Solving Systems of Linear Equations	22	(10)
Linear Independence and Linear Dependence	32	(4)
The Inverse of a Matrix	36	(6)
Determinants	42	(7)
Introduction to Linear Programming	49	(78)
What Is a Linear Programming Problem?	49	(7)
The Graphical Solution of Two-Variable Linear Programming Problems	56	(7)
Special Cases	63	(5)
A Diet Problem	68	(4)
A Work-Scheduling Problem	72	(4)
A Capital Budgeting Problem	76	(6)
Short-Term Financial Planning	82	(3)
Blending Problems	85	(10)
Production Process Models	95	(5)
Using Linear Programming to Solve Multiperiod Decision Problems: An Inventory Model	100	(5)
Multiperiod Financial Models	105	(4)
Multiperiod Work Scheduling	109	(18)
The Simplex Algorithm and Goal Programming	127	(100)
How to Convert an LP to Standard Form	127	(3)
Preview of the Simplex Algorithm	130	(4)
Direction of Unboundedness	134	(2)
Why Does an LP Have an Optimal bfs?	136	(4)
The Simplex Algorithm	140	(9)
Using the Simplex Algorithm to Solve Minimization Problems	149	(3)
Alternative Optimal Solutions	152	(2)
Unbounded LPs	154	(4)
The LINDO Computer Package	158	(5)
Matrix Generators, LINGO, and Scaling of LPs	163	(5)
Degeneracy and the Convergence of the Simplex Algorithm	168	(4)
The Big M Method	172	(6)
The Two-Phase Simplex Method	178	(6)
Unrestricted-in-Sign Variables	184	(6)
Karmarkar's Method for Solving LPs	190	(1)
Multiattribute Decision Making in the Absence of Uncertainty: Goal Programming	191	(11)
Using the Excel Solver to Solve LPs	202	(25)
Sensitivity Analysis: An Applied Approach	227	(35)
A Graphical Introduction to Sensitivity Analysis	227	(5)
The Computer and Sensitivity Analysis	232	(14)
Managerial Use of Shadow Prices	246	(2)
What Happens to the Optimal z-Value If the Current Basis Is No Longer Optimal?	248	(14)
Sensitivity Analysis and Duality	262	(98)
A Graphical Introduction to Sensitivity Analysis	262	(5)
Some Important Formulas	267	(8)
Sensitivity Analysis	275	(14)
Sensitivity Analysis When More Than One Parameter Is Changed: The 100% Rule	289	(6)
Finding the Dual of an LP	295	(7)
Economic Interpretation of the Dual Problem	302	(2)
The Dual Theorem and Its Consequences	304	(9)
Shadow Prices	313	(10)
Duality and Sensitivity Analysis	323	(2)
Complementary Slackness	325	(4)
The Dual Simplex Method	329	(6)
Data Envelopment Analysis	335	(25)
Transportation, Assignment, and Transshipment Problems	360	(53)
Formulating Transportation Problems	360	(13)
Finding Basic Feasible Solutions for Transportation Problems	373	(9)
The Transportation Simplex Method	382	(8)
Sensitivity Analysis for Transportation Problems	390	(3)
Assignment Problems	393	(7)
Transshipment Problems	400	(13)
Network Models	413	(62)
Basic Definitions	413	(1)
Shortest-Path Problems	414	(5)
Maximum-Flow Problems	419	(12)
CPM and PERT	431	(19)
Minimum-Cost Network Flow Problems	450	(6)
Minimum Spanning Tree Problems	456	(3)
The Network Simplex Method	459	(16)
Integer Programming	475	(87)
Introduction to Integer Programming	475	(2)
Formulating Integer Programming Problems	477	(35)
The Branch-and-Bound Method for Solving Pure Integer Programming Problems	512	(11)
The Branch-and-Bound Method for Solving Mixed Integer Programming Problems	523	(1)
Solving Knapsack Problems by the Branch-and-Bound Method	524	(3)
Solving Combinatorial Optimization Problems by the Branch-and-Bound Method	527	(13)
Implicit Enumeration	540	(5)
The Cutting Plane Algorithm	545	(17)
Advanced Topics in Linear Programming	562	(48)
The Revised Simplex Algorithm	562	(5)
The Product Form of the Inverse	567	(3)
Using Column Generation to Solve Large-Scale LPs	570	(6)
The Dantzig-Wolfe Decomposition Algorithm	576	(17)
The Simplex Method for Upper-Bounded Variables	593	(4)
Karmarkar's Method for Solving LPs	597	(13)
Nonlinear Programming	610	(97)
Review of Differential Calculus	610	(6)
Introductory Concepts	616	(14)
Convex and Concave Functions	630	(7)
Solving NLPs with One Variable	637	(12)
Golden Section Search	649	(6)
Unconstrained Maximization and Minimization with Several Variables	655	(5)
The Method of Steepest Ascent	660	(3)
Lagrange Multipliers	663	(7)
The Kuhn--Tucker Conditions	670	(10)
Quadratic Programming	680	(8)
Separable Programming	688	(5)
The Method of Feasible Directions	693	(2)
Pareto Optimality and Tradeoff Curves	695	(12)
Review of Calculus and Probability	707	(30)
Review of Integral Calculus	707	(3)
Differentiation of Integrals	710	(1)
Basic Rules of Probability	710	(3)
Bayes' Rule	713	(2)
Random Variables, Mean, Variance, and Covariance	715	(7)
The Normal Distribution	722	(8)
z-Transforms	730	(7)
Decision Making under Uncertainty	737	(66)
Decision Criteria	737	(4)
Utility Theory	741	(14)
Flaws in Expected Maximization of Utility: Prospect Theory and Framing Effects	755	(3)
Decision Trees	758	(9)
Bayes' Rule and Decision Trees	767	(6)
Decision Making with Multiple Objectives	773	(12)
The Analytic Hierarchy Process	785	(18)
Game Theory	803	(43)
Two-Person Zero-Sum and Constant-Sum Games: Saddle Points	803	(4)
Two-Person Zero-Sum Games: Randomized Strategies, Domination, and Graphical Solution	807	(9)
Linear Programming and Zero-Sum Games	816	(11)
Two-Person Nonconstant-Sum Games	827	(5)
Introduction to n-Person Game Theory	832	(2)
The Core of an n-Person Game	834	(3)
The Shapley Value	837	(9)
Deterministic EOQ Inventory Models	846	(34)
Introduction to Basic Inventory Models	846	(2)
The Basic Economic Order Quantity Model	848	(11)
Computing the Optimal Order Quantity When Quantity Discounts Are Allowed	859	(6)
The Continuous Rate EOQ Model	865	(3)
The EOQ Model with Back Orders Allowed	868	(4)
When to Use EOQ Models	872	(1)
Multiple-Product EOQ Models	873	(7)
Probabilistic Inventory Models	880	(43)
Single-Period Decision Models	880	(1)
The Concept of Marginal Analysis	880	(1)
The News Vendor Problem: Discrete Demand	881	(5)
The News Vendor Problem: Continuous Demand	886	(2)
Other One-Period Models	888	(2)
The EOQ with Uncertain Demand: The (r, q) and (s, S) Models	890	(8)
The EOQ with Uncertain Demand: The Service Level Approach to Determining Safety Stock Level	898	(9)
(R, S) Periodic Review Policy	907	(4)
The ABC Inventory Classification System	911	(2)
Exchange Curves	913	(10)
Markov Chains	923	(38)
What Is a Stochastic Process?	923	(1)
What Is a Markov Chain?	924	(4)
n-Step Transition Probabilities	928	(3)
Classification of States in a Markov Chain	931	(3)
Steady-State Probabilities and Mean First Passage Times	934	(8)
Absorbing Chains	942	(8)
Work-Force Planning Models	950	(11)
Deterministic Dynamic Programming	961	(55)
Two Puzzles	961	(1)
A Network Problem	962	(7)
An Inventory Problem	969	(5)
Resource-Allocation Problems	974	(11)
Equipment-Replacement Problems	985	(4)
Formulating Dynamic Programming Recursions	989	(12)
The Wagner--Whitin Algorithm and the Silver--Meal Heuristic	1001	(5)
Using Excel to Solve Dynamic Programming Problems	1006	(10)
Probabilistic Dynamic Programming	1016	(35)
When Current Stage Costs Are Uncertain, but the Next Period's State Is Certain	1016	(3)
A Probabilistic Inventory Model	1019	(4)
How to Maximize the Probability of a Favorable Event Occurring	1023	(6)
Further Examples of Probabilistic Dynamic Programming Formulations	1029	(7)
Markov Decision Processes	1036	(15)
Queuing Theory	1051	(94)
Some Queuing Terminology	1051	(2)
Modeling Arrival and Service Processes	1053	(1)
Birth--Death Processes	1053	(19)
The M/M/1/GD/∞/∞ Queuing System and the Queuing Formula L = λW	1072	(11)
The M/M/1/GD/c/∞ Queuing System	1083	(4)
The M/M/s/GD/∞/∞ Queuing System	1087	(8)
The M/G/∞/GD/∞/∞ and GI/G/∞/GD/∞/∞ Models	1095	(2)
The M/G/∞/GD/∞/∞ Queuing System	1097	(2)
Finite Source Models: The Machine Repair Model	1099	(5)
Exponential Queues in Series and Open Queuing Networks	1104	(8)
The M/G/s/GD/s/∞ System (Blocked Customers Cleared)	1112	(3)
How to Tell Whether Interarrival Times and Service Times Are Exponential	1115	(4)
Closed Queuing Networks	1119	(5)
An Approximation for the G/G/m Queuing System	1124	(2)
Priority Queuing Models	1126	(5)
Transient Behavior of Queuing Systems	1131	(14)
Simulation	1145	(46)
Basic Terminology	1145	(1)
An Example of a Discrete-Event Simulation	1146	(7)
Random Numbers and Monte Carlo Simulation	1153	(5)
An Example of Monte Carlo Simulation	1158	(4)
Simulations with Continuous Random Variables	1162	(11)
An Example of a Stochastic Simulation	1173	(7)
Statistical Analysis in Simulations	1180	(3)
Simulation Languages	1183	(1)
The Simulation Process	1184	(7)
Simulation with Process Model	1191	(21)
Simulating an M/M/1 Queuing System	1191	(4)
Simulating an M/M/2 System	1195	(4)
Simulating a Series System	1199	(4)
Simulating Open Queuing Networks	1203	(4)
Simulating Erlang Service Times	1207	(3)
What Else Can Process Model Do?	1210	(2)
Simulation with the Excel Add-in @Risk	1212	(63)
Introduction to @Risk: The News Vendor Problem	1212	(10)
Modeling Cash Flows from a New Product	1222	(10)
Product Scheduling Models	1232	(6)
Reliability and Warranty Modeling	1238	(6)
The RISKGENERAL Function	1244	(4)
The RISKCUMULATIVE Random Variable	1248	(1)
The RISKTRIGEN Random Variable	1249	(1)
Creating a Distribution Based on a Point Forecast	1250	(2)
Forecasting the Income of a Major Corporation	1252	(4)
Using Data to Obtain Inputs for New Product Simulations	1256	(11)
Simulation and Bidding	1267	(2)
Playing Craps with @Risk	1269	(2)
Simulating the NBA Finals	1271	(4)
Forecasting Models	1275	(61)
Moving-Average Forecast Methods	1275	(6)
Simple Exponential Smoothing	1281	(2)
Holt's Method: Exponential Smoothing with Trend	1283	(3)
Winter's Method: Exponential Smoothing with Seasonality	1286	(6)
Ad Hoc Forecasting	1292	(10)
Simple Linear Regression	1302	(10)
Fitting Nonlinear Relationships	1312	(5)
Multiple Regression	1317	(19)
Appendix 1: @Risk Crib Sheet	1336	(14)
Appendix 2: Cases	1350	(20)
Case 1 Help, I'm Not Getting Any Younger	1351	(1)
Case 2 Solar Energy for Your Home	1351	(1)
Case 3 Golf-Sport: Managing Operations	1352	(3)
Case 4 Vision Corporation: Production Planning and Shipping	1355	(1)
Case 5 Material Handling in a General Mail-Handling Facility	1356	(3)
Case 6 Selecting Corporate Training Programs	1359	(3)
Case 7 Best Chip: Expansion Strategy	1362	(2)
Case 8 Emergency Vehicle Location in Springfield	1364	(1)
Case 9 System Design: Project Management	1365	(1)
Case 10 Modular Design for the Help-You Company	1366	(2)
Case 11 Brite Power: Capacity Expansion	1368	(2)
Appendix 3: Answers to Selected Problems	1370	(32)
Index	1402