1 Introduction to Operations Research 1
1.1 The Methodology of Operations Research 1
1.2 Successful Applications of Operations Research 5
1.3 Where to Read More about Operations Research 6
1.4 About This Book 7
2 Introduction to Linear Programming 8
2.1 What Is a Linear Programming Problem? 8
2.2 The Graphical Solution of Two-Variable Linear Programming Problems 15
2.3 Special Cases 23
2.4 A Diet Problem 29
2.5 A Work-Scheduling Problem 32
2.6 A Capital Budgeting Problem 36
2.7 Short-Term Financial Planning 40
2.8 Blending Problems 43
2.9 Production Process Models 53
2.10 Using Linear Programming to Solve Multiperiod Decision Problems:An Inventory Model 58
2.11 Multiperiod Financial Models 63
2.12 Multiperiod Work Scheduling 67
3 The Simplex Algorithm 83
3.1 How to Convert an LP to Standard Form 83
3.2 Preview of the Simplex Algorithm 86
3.3 The Simplex Algorithm 92
3.4 Using the Simplex Algorithm to Solve Minimization Problems 102
3.5 Alternative Optimal Solutions 105
3.6 Unbounded LPs 107
3.7 The LINDO Computer Package 110
3.8 Matrix Generators,LINGO,and Scaling of LPs 114
3.9 Degeneracy and the Convergence of the Simplex Algorithm 119
3.10 The Big M Method 123
3.11 The Two-Phase Simplex Method 129
3.12 Variables That Are Unrestricted in Sign 134
3.13 Karmarkar's Method for Solving LPs 140
3.14 Solving LPs with Spreadsheets 141
4 Sensitivity Analysis and Duality 155
4.1 A Graphical Introduction to Sensitivity Analysis 155
4.2 Some Important Formulas 161
4.3 Sensitivity Analysis 169
4.4 Sensitivity Analysis When More Than One Parameter Is Changed:The 100% Rule 184
4.5 Finding the Dual of an LP 190
4.6 Economic Interpretation of the Dual Problem 197
4.7 The Dual Theorem and Its Consequences 200
4.8 Shadow Prices 210
4.9 Duality and Sensitivity Analysis 220
4.10 Complementary Slackness 223
4.11 The Dual Simplex Method 227
4.12 An Application of Dual Prices:Data Envelopment Analysis(DEA) 233
5 Integer Programming 260
5.1 Introduction to Integer Programming 260
5.2 Formulating Integer Programming Problems 263
5.3 The Branch-and-Bound Method for Solving Pure Integer Programming Problems 298
5.4 The Brand-and-Bound Method for Solving Mixed Programming Problems 311
5.5 Solving Knapsack Problems by the Branch-and-Bound Method 312
5.6 Solving Combinatorial Optimization Problems by the Branch-and-Bound Method 315
5.7 Implicit Enumeration 329
5.8 The Cutting Plane Algorithm 335
6 Advanced Topics in Linear Programming 350
6.1 The Revised Simplex Algorithm 350
6.2 The Product Form of the Inverse 355
6.3 Using Column Generation to Solve Large-Scale LPs 358
6.4 The Dantzig-Wolfe Decomposition Algorithm 365
6.5 The Simplex Method for Upper-Bounded Variables 383
6.6 Karmarkar's Method for Solving LPs 387
7 Nonlinear Programmimg 402
7.1 Introductory Concepts 402
7.2 Convex and Concave Functions 415
7.3 Solving NLPs with One Variable 423
7.4 Golden Section Search 431
7.5 Unconstrained Maximization and Minimization with Several Variables 437
7.6 The Method of Steepest Ascent 443
7.7 Lagrange Multipliers 447
7.8 The Kuhn-Tucker Conditions 454
7.9 Quadratic Programming 464
7.10 Separable Programming 473
7.11 The Method of Feasible Directions 479
8 Deterministic Dynamic Programming 490
8.1 Two Puzzles 490
8.2 A Network Problem 492
8.3 An Inventory Problem 499
8.4 Resource Allocation Problems 505
8.5 Equipment Replacement Problems 517
8.6 Formulating Dynamic Programming Recursions 520
8.7 The Wagner-Whitin Algorithm and the Silver-Meal Heuristic 533
8.8 Forward Recursions 539
8.9 Using Spreadsheets to Solve Dynamic Programming Problems 542