Introduction to Operations Research

by Hillier, Frederick S.; Lieberman, Gerald J.

• ISBN13: 9780078414473
• ISBN10: 0078414474
• Edition: 6th
• Format: Hardcover
• Copyright: 1995-03-01
• Publisher: McGraw-Hill College

Summary

Textbook providing a rigorous treatment in a stimulating manner. Includes realistic examples, illustrations, and exercises. 3 1/2 inch disk included. DLC: Operations research.

Table of Contents

Preface	xv
1 INTRODUCTION	1	(7)
1.1 The Origins of Operations Research	1	(2)
1.2 The Nature of Operations Research	3	(1)
1.3 The Impact of Operations Research	4	(1)
1.4 Algorithms and OR Courseware	4	(4)
2 OVERVIEW OF THE OPERATIONS RESEARCH MODELING APPROACH	8	(17)
2.1 Defining the Problem and Gathering Data	9	(2)
2.2 Formulating a Mathematical Model	11	(4)
2.3 Deriving Solutions from the Model	15	(2)
2.4 Testing the Model	17	(2)
2.5 Preparing to Apply the Model	19	(2)
2.6 Implementation	21	(1)
2.7 Conclusions	22	(3)
3 INTRODUCTION TO LINEAR PROGRAMMING	25	(56)
3.1 Prototype Example	26	(6)
3.2 The Linear Programming Model	32	(6)
3.3 Assumptions of Linear Programming	38	(7)
3.4 Additional Examples	45	(17)
3.5 Some Case Studies	62	(5)
3.6 Conclusions	67	(14)
4 SOLVING LINEAR PROGRAMMING PROBLEMS: THE SIMPLEX METHOD	81	(72)
4.1 The Essence of the Simplex Method	82	(5)
4.2 Setting Up the Simplex Method	87	(3)
4.3 The Algebra of the Simplex Method	90	(5)
4.4 The Simplex Method in Tabular Form	95	(5)
4.5 The Breaking in the Simplex Method	100	(3)
4.6 Adapting to Other Model Forms	103	(19)
4.7 Post-Optimality Analysis	122	(7)
4.8 Computer Implementation	129	(2)
4.9 The Interior-Point Approach to Solving Linear Programming Problems	131	(5)
4.10 Conclusions	136	(17)
5 THE THEORY OF THE SIMPLEX METHOD	153	(43)
5.1 Foundations of the Simplex Method	153	(12)
5.2 The Revised Simplex Method	165	(9)
5.3 A Fundamental Insight	174	(8)
5.4 Conclusions	182	(14)
6 DUALITY THEORY AND SENSITIVITY ANALYSIS	196	(67)
6.1 The Essence of Duality Theory	197	(7)
6.2 Economic Interpretation of Duality	204	(2)
6.3 Primal-Dual Relationships	206	(4)
6.4 Adapting to Other Primal Forms	210	(5)
6.5 The Role of Duality Theory in Sensitivity Analysis	215	(2)
6.6 The Essence of Sensitivity Analysis	217	(6)
6.7 Applying Sensitivity Analysis	223	(15)
6.8 Conclusions	238	(25)
7 OTHER ALGORITHMS FOR LINEAR PROGRAMMING	263	(40)
7.1 The Dual Simplex Method	264	(2)
7.2 Parametric Linear Programming	266	(5)
7.3 The Upper Bound Technique	271	(3)
7.4 An Interior-Point Algorithm	274	(11)
7.5 Linear Goal Programming and Its Solution Procedures	285	(7)
7.6 Conclusions	292	(11)
8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS	303	(50)
8.1 The Transportation Problem	304	(11)
8.2 A Streamlined Simplex Method for the Transportation Problem	315	(14)
8.3 The Assignment Problem	329	(9)
8.4 Conclusions	338	(15)
9 NETWORK ANALYSIS, INCLUDING PERT-CPM	353	(71)
9.1 Prototype Example	355	(1)
9.2 The Terminology of Networks	356	(3)
9.3 The Shortest-Path Problem	359	(3)
9.4 The Minimum Spanning Tree Problem	362	(4)
9.5 The Maximum Flow Problem	366	(6)
9.6 The Minimum Cost Flow Problem	372	(6)
9.7 The Network Simplex Method	378	(11)
9.8 Project Planning and Control with PERT-CPM	389	(15)
9.9 Conclusions	404	(20)
10 DYNAMIC PROGRAMMING	424	(46)
10.1 A Prototype Example for Dynamic Programming	425	(5)
10.2 Characteristics of Dynamic Programming Problems	430	(3)
10.3 Deterministic Dynamic Programming	433	(20)
10.4 Probabilistic Dynamic Programming	453	(5)
10.5 Conclusions	458	(12)
11 GAME THEORY	470	(24)
11.1 The Formulation of Two-Person, Zero-Sum Games	471	(1)
11.2 Solving Simple Games-A Prototype Example	472	(5)
11.3 Games With Mixed Strategies	477	(2)
11.4 Graphical Solution Procedure	479	(3)
11.5 Solving by Linear Programming	482	(3)
11.6 Extensions	485	(1)
11.7 Conclusions	486	(8)
12 INTERGER PROGRAMMING	494	(64)
12.1 Prototype Example	495	(2)
12.2 Some Other Formulation Possibilities with Binary Variables	497	(6)
12.3 Some Formulation Examples	503	(8)
12.4 Some Perspectives on Solving Integer Programming Problems	511	(4)
12.5 The Branch-and-Bound Technique and Its Application to Binary Integer Programming	515	(12)
12.6 A Branch-and-Bound Algorithm for Mixed Integer Programming	527	(6)
12.7 Recent Developments in Solving BIP Problems	533	(8)
12.8 Conclusions	541	(17)
13 NONLINEAR PROGRAMMING	558	(70)
13.1 Sample Applications	559	(4)
13.2 Graphical Illustration of Nonlinear Programming Problems	563	(5)
13.3 Types of Nonlinear Programming Problems	568	(6)
13.4 One-Variable Unconstrained Optimization	574	(3)
13.5 Multivariable Unconstrained Optimization	577	(5)
13.6 The Karush-Kuhn-Tucker (KKT) Conditions for Constrained Optimization	582	(4)
13.7 Quadratic Programming	586	(5)
13.8 Separable Programming	591	(7)
13.9 Convex Programming	598	(5)
13.10 Nonconvex Programming	603	(3)
13.11 Conclusions	606	(22)
14 MARKOV CHAINS	628	(33)
14.1 Stochastic Processes	629	(1)
14.2 Markov Chains	630	(3)
14.3 Chapman-Kolmogorov Equations	633	(2)
14.4 Classification of States of a Markov Chain	635	(3)
14.5 First Passage Times	638	(2)
14.6 Long-Run Properties of Markov Chains	640	(6)
14.7 Absorption States	646	(2)
14.8 Continuous-Time Markov Chains	648	(13)
15 QUEUEING THEORY	661	(72)
15.1 Prototype Example	662	(1)
15.2 Basic Structure of Queueing Models	662	(5)
15.3 Examples of Real Queueing Systems	667	(1)
15.4 The Role of the Exponential Distribution	668	(6)
15.5 The Birth-and-Death Process	674	(5)
15.6 Queueing Models Based on the Birth-and-Death Process	679	(17)
15.7 Queueing Models Involving Nonexponential Distributions	696	(8)
15.8 Priority-Discipline Queueing Models	704	(5)
15.9 Queueing Networks	709	(4)
15.10 Conclusions	713	(20)
16 THE APPLICATION OF QUEUEING THEORY	733	(23)
16.1 Examples	734	(1)
16.2 Decision Making	735	(3)
16.3 Formulation of Waiting-Cost Functions	738	(4)
16.4 Decision Models	742	(6)
16.5 Conclusions	748	(8)
17 INVENTORY THEORY	756	(50)
17.1 Examples	757	(2)
17.2 Components of Inventory Models	759	(2)
17.3 Deterministic Models	761	(11)
17.4 Stochastic Models	772	(25)
17.5 Conclusions	797	(9)
18 FORECASTING	806	(27)
18.1 Judgemental Techniques	807	(1)
18.2 Time Series	808	(1)
18.3 Forecasting Procedures for a Constant-Level Model	809	(3)
18.4 A Forecasting Procedure for a Linear Trend Model	812	(2)
18.5 A Forecasting Procedure for a Constant Level with Seasonal Effects Model	814	(3)
18.6 Forecasting Errors	817	(1)
18.7 Box-Jenkins Method	818	(1)
18.8 Linear Regression	819	(7)
18.9 Conclusions	826	(7)
19 MARKOV DECISION PROCESSES	833	(31)
19.1 A Prototype Example	834	(2)
19.2 A Model for Markov Decision Processes	836	(3)
19.3 Linear Programming and Optimal Policies	839	(4)
19.4 A Policy Improvement Algorithm for Finding Optimal Policies	843	(5)
19.5 Discounted Cost Criterion	848	(7)
19.6 Conclusions	855	(9)
20 DECISION ANALYSIS	864	(36)
20.1 A Prototype Example	865	(1)
20.2 Decision Making without Experimentation	865	(4)
20.3 Decision Making with Experimentation	869	(5)
20.4 Decision Trees	874	(3)
20.5 Utility Theory	877	(6)
20.6 Conclusions	883	(17)
21 SIMULATION	900	(45)
21.1 Illustrative Examples	902	(7)
21.2 Formulating and Implementing a Simulation Model	909	(10)
21.3 Experimental Design for Simulation	919	(7)
21.4 Regenerative Method of Statistical Analysis	926	(6)
21.5 Conclusions	932	(13)
APPENDIXES	945	(27)
1 Documentation for the OR Courseware	947	(4)
2 Convexity	951	(8)
3 Classical Optimization Methods	959	(4)
4 Matrices and Matrix Operations	963	(7)
5 Tables	970	(2)
Answers to Selected Problems	972	(10)
Indexes	982
Author Index	982	(4)
Subject Index	986