Introduction to Operations Research

by Hillier, Frederick S.

• ISBN13: 9780072462395
• ISBN10: 0072462396
• Edition: 7th
• Format: Hardcover
• Copyright: 2000-06-01
• Publisher: McGraw Hill College Div

Table of Contents

Preface	xxiii
Introduction	1	(6)
The Origins of Operations Research	1	(1)
The Nature of Operations Research	2	(1)
The Impact of Operations Research	3	(2)
Algorithms and OR Courseware	5	(2)
Problems	6	(1)
Overview of the Operations Research Modeling Approach	7	(17)
Defining the Problem and Gathering Data	7	(3)
Formulating a Mathematical Model	10	(4)
Deriving Solutions from the Model	14	(2)
Testing the Model	16	(2)
Preparing to Apply the Model	18	(2)
Implementation	20	(1)
Conclusions	21	(3)
Selected References	22	(1)
Problems	22	(2)
Introduction to Linear Programming	24	(85)
Prototype Example	25	(6)
The Linear Programming Model	31	(5)
Assumptions of Linear Programming	36	(8)
Additional Examples	44	(17)
Some Case Studies	61	(6)
Displaying and Solving Linear Programming Models on a Spreadsheet	67	(6)
Formulating Very Large Linear Programming Models	73	(6)
Conclusions	79	(30)
The LINGO Modeling Language	79	(10)
Selected References	89	(1)
Learning Aids for This Chapter in Your Or Courseware	90	(1)
Problems	90	(13)
Auto Assembly	103	(1)
Cutting Cafeteria Costs	104	(2)
Staffing a Call Center	106	(3)
Solving Linear Programming Problems: The Simplex Method	109	(81)
The Essence of the Simplex Method	109	(5)
Setting Up the Simplex Method	114	(4)
The Algebra of the Simplex Method	118	(5)
The Simplex Method in Tabular Form	123	(5)
Tie Breaking in the Simplex Method	128	(4)
Adapting to Other Model Forms	132	(20)
Postoptimality Analysis	152	(8)
Computer Implementation	160	(3)
The Interior-Point Approach to Solving Linear Programming Problems	163	(5)
Conclusions	168	(22)
An Introduction to Using LINDO	169	(2)
Selected References	171	(1)
Learning Aids for This Chapter in Your OR Courseware	172	(1)
Problems	172	(10)
Fabrics and Fall Fashions	182	(3)
New Frontiers	185	(3)
Assigning Students to Schools	188	(2)
The Theory of the Simplex Method	190	(40)
Foundations of the Simplex Method	190	(12)
The Revised Simplex Method	202	(10)
A Fundamental Insight	212	(8)
Conclusions	220	(10)
Selected References	220	(1)
Learning Aids for This Chapter in Your OR Courseware	221	(1)
Problems	221	(9)
Duality Theory and Sensitivity Analysis	230	(79)
The Essence of Duality Theory	231	(8)
Economic Interpretation of Duality	239	(3)
Primal-Dual Relationships	242	(5)
Adapting to Other Primal Forms	247	(5)
The Role of Duality Theory in Sensitivity Analysis	252	(2)
The Essence of Sensitivity Analysis	254	(8)
Applying Sensitivity Analysis	262	(22)
Conclusions	284	(25)
Selected References	284	(1)
Learning Aids for This Chapter in Your OR Courseware	285	(1)
Problems	285	(17)
Controlling Air Pollution	302	(2)
Farm Management	304	(3)
Assigning Students to Schools (Revisited)	307	(2)
Other Algorithms for Linear Programming	309	(41)
The Dual Simplex Method	309	(3)
Parametric Linear Programming	312	(5)
The Upper Bound Technique	317	(3)
An Interior-Point Algorithm	320	(12)
Linear Goal Programming and Its Solution Procedures	332	(7)
Conclusions	339	(11)
Selected References	340	(1)
Learning Aids for This Chapter in Your OR Courseware	340	(1)
Problems	341	(6)
A Cure for Cuba	347	(3)
The Transportation and Assignment Problems	350	(55)
The Transportation Problem	351	(14)
A Streamlined Simplex Method for the Transportation Problem	365	(16)
The Assignment Problem	381	(10)
Conclusions	391	(14)
Selected References	391	(1)
Learning Aids for This Chapter in Your OR Courseware	392	(1)
Problems	392	(9)
Shipping Wood to Market	401	(1)
Project Pickings	402	(3)
Network Optimization Models	405	(63)
Prototype Example	406	(1)
The Terminology of Networks	407	(4)
The Shortest-Path Problem	411	(4)
The Minimum Spanning Tree Problem	415	(5)
The Maximum Flow Problem	420	(9)
The Minimum Cost Flow Problem	429	(9)
The Network Simplex Method	438	(10)
Conclusions	448	(20)
Selected References	449	(1)
Learning Aids for This Chapter in Your OR Courseware	449	(1)
Problems	450	(8)
Aiding Allies	458	(6)
Money in Motion	464	(4)
Project Management with PERT/CPM	468	(65)
A Prototype Example--The Reliable Construction Co. Project	469	(1)
Using a Network to Visually Display a Project	470	(5)
Scheduling a Project with PERT/CPM	475	(10)
Dealing with Uncertain Activity Durations	485	(7)
Considering Time-Cost Trade-Offs	492	(10)
Scheduling and Controlling Project Costs	502	(6)
An Evaluation of PERT/CPM	508	(4)
Conclusions	512	(21)
Selected References	513	(1)
Learning Aids for This Chapter in Your OR Courseware	514	(1)
Problems	514	(10)
Steps to Success	524	(3)
School's out forever...''	527	(6)
Dynamic Programming	533	(43)
A Prototype Example for Dynamic Programming	533	(5)
Characteristics of Dynamic Programming Problems	538	(3)
Deterministic Dynamic Programming	541	(21)
Probabilistic Dynamic Programming	562	(6)
Conclusions	568	(8)
Selected References	568	(1)
Learning Aids for This Chapter in Your OR Courseware	568	(1)
Problems	569	(7)
Integer Programming	576	(78)
Prototype Example	577	(3)
Some BIP Applications	580	(5)
Innovative Uses of Binary Variables in Model Formulation	585	(6)
Some Formulation Examples	591	(9)
Some Perspectives on Solving Integer Programming Problems	600	(4)
The Branch-and-Bound Technique and Its Application to Binary Integer Programming	604	(12)
A Branch-and-Bound Algorithm for Mixed Integer Programming	616	(6)
Other Developments in Solving BIP Problems	622	(8)
Conclusions	630	(24)
Selected References	631	(1)
Learning Aids for This Chapter in Your OR Courseware	631	(1)
Problems	632	(10)
Capacity Concerns	642	(3)
Assigning Art	645	(4)
Stocking Sets	649	(4)
Assigning Students to Schools (Revisited Again)	653	(1)
Nonlinear Programming	654	(72)
Sample Applications	655	(4)
Graphical Illustration of Nonlinear Programming Problems	659	(5)
Types of Nonlinear Programming Problems	664	(6)
One-Variable Unconstrained Optimization	670	(3)
Multivariable Unconstrained Optimization	673	(6)
The Karush-Kuhn-Tucker (KKT) Conditions for Constrained Optimization	679	(4)
Quadratic Programming	683	(7)
Separable Programming	690	(7)
Convex Programming	697	(5)
Nonconvex Programming	702	(4)
Conclusions	706	(20)
Selected References	706	(1)
Learning Aids for This Chapter in Your OR Courseware	707	(1)
Problems	708	(12)
Savvy Stock Selection	720	(6)
Game Theory	726	(23)
The Formulation of Two-Person, Zero-Sum Games	726	(2)
Solving Simple Games--A Prototype Example	728	(5)
Games with Mixed Strategies	733	(2)
Graphical Solution Procedure	735	(3)
Solving by Linear Programming	738	(3)
Extensions	741	(1)
Conclusions	742	(7)
Selected References	743	(1)
Learning Aids for This Chapter in Your OR Courseware	743	(1)
Problems	743	(6)
Decision Analysis	749	(53)
A Prototype Example	750	(1)
Decision Making without Experimentation	751	(7)
Decision Making with Experimentation	758	(6)
Decision Trees	764	(6)
Utility Theory	770	(8)
The Practical Application of Decision Analysis	778	(3)
Conclusions	781	(21)
Selected References	781	(1)
Learning Aids for This Chapter in Your OR Courseware	782	(1)
Problems	782	(13)
Brainy Business	795	(3)
Smart Steering Support	798	(4)
Markov Chains	802	(32)
Stochastic Processes	802	(1)
Markov Chains	803	(5)
Chapman-Kolmogorov Equations	808	(2)
Classification of States of a Markov Chain	810	(2)
Long-Run Properties of Markov Chains	812	(6)
First Passage Times	818	(2)
Absorbing States	820	(2)
Continuous Time Markov Chains	822	(12)
Selected References	827	(1)
Learning Aids for This Chapter in Your OR Courseware	828	(1)
Problems	828	(6)
Queueing Theory	834	(73)
Prototype Example	835	(1)
Basic Structure of Queueing Models	835	(5)
Examples of Real Queueing Systems	840	(1)
The Role of the Exponential Distribution	841	(7)
The Birth-and-Death Process	848	(4)
Queueing Models Based on the Birth-and-Death Process	852	(19)
Queueing Models Involving Nonexponential Distributions	871	(8)
Priority-Discipline Queueing Models	879	(6)
Queueing Networks	885	(4)
Conclusions	889	(18)
Selected References	890	(1)
Learning Aids for This Chapter in Your OR Courseware	890	(1)
Problems	891	(14)
Reducing In-Process Inventory	905	(2)
The Application of Queueing Theory	907	(28)
Examples	907	(2)
Decision Making	909	(3)
Formulation of Waiting-Cost Functions	912	(5)
Decision Models	917	(6)
Some Award-Winning Applications of Queueing Theory	923	(3)
Conclusions	926	(9)
Selected References	926	(1)
Learning Aids for This Chapter in Your OR Courseware	926	(1)
Problems	927	(5)
Queueing Quandary	932	(3)
Inventory Theory	935	(74)
Examples	936	(2)
Components of Inventory Models	938	(3)
Deterministic Continuous-Review Models	941	(10)
A Deterministic Periodic-Review Model	951	(5)
A Stochastic Continuous-Review Model	956	(5)
A Stochastic Single-Period Model for Perishable Products	961	(14)
Stochastic Periodic-Review Models	975	(8)
Larger Inventory Systems in Practice	983	(4)
Conclusions	987	(22)
Selected References	987	(1)
Learning Aids for This Chapter in Your OR Courseware	987	(1)
Problems	988	(12)
Brushing Up on Inventory Control	1000	(2)
TNT: Tackling Newsboy's Teachings	1002	(2)
Jettisoning Surplus Stock	1004	(5)
Forecasting	1009	(44)
Some Applications of Forecasting	1010	(3)
Judgmental Forecasting Methods	1013	(1)
Time Series	1014	(2)
Forecasting Methods for a Constant-Level Model	1016	(2)
Incorporating Seasonal Effects into Forecasting Methods	1018	(3)
An Exponential Smoothing Method for a Linear Trend Model	1021	(4)
Forecasting Errors	1025	(1)
Box-Jenkins Method	1026	(2)
Causal Forecasting with Linear Regression	1028	(8)
Forecasting in Practice	1036	(2)
Conclusions	1038	(15)
Selected References	1038	(1)
Learning Aids for This Chapter in Your OR Courseware	1038	(1)
Problems	1039	(9)
Finagling the Forecasts	1048	(5)
Markov Decision Processes	1053	(31)
A Prototype Example	1053	(3)
A Model for Markov Decision Processes	1056	(3)
Linear Programming and Optimal Policies	1059	(5)
Policy Improvement Algorithm for Finding Optimal Policies	1064	(5)
Discounted Cost Criterion	1069	(15)
Selected References	1077	(1)
Learning Aids for This Chapter in Your OR Courseware	1078	(1)
Problems	1078	(6)
Simulation	1084	(92)
The Essence of Simulation	1084	(13)
Some Common Types of Applications of Simulation	1097	(4)
Generation of Random Numbers	1101	(4)
Generation of Random Observations from a Probability Distribution	1105	(5)
Outline of a Major Simulation Study	1110	(5)
Performing Simulations on Spreadsheets	1115	(11)
Variance-Reducing Techniques	1126	(5)
Regenerative Method of Statistical Analysis	1131	(7)
Conclusions	1138	(18)
Selected References	1140	(1)
Learning Aids for This Chapter in Your OR Courseware	1140	(1)
Problems	1141	(10)
Planning Planers	1151	(2)
Pricing under Pressure	1153	(3)
APPENDIXES
1. Documentation for the OR Courseware	1156	(3)
2. Convexity	1159	(6)
3. Classical Optimization Methods	1165	(4)
4. Matrices and Matrix Operations	1169	(5)
5. Tables	1174	(2)
PARTIAL ANSWERS TO SELECTED PROBLEMS	1176	(19)
INDEXES
Author Index	1195	(4)
Subject Index	1199