Introduction to Operations Research Third Edition Joseph G. Ecker and Michael Kupferschmid Krieger, 2004 1 Introduction 1.1 Operations Research 1.2 Nature and Scope of Operations Research 1.3 History and Development of Operations Research 1.4 Overview of Operations Research Methods 1.5 Perspective of This Text 1.6 Organization of This Text Selected References Exercises Part 1: Linear Programming 2 Linear Programming Models and Applications 2.1 Formulating Linear Programming Models An Introductory Resource Allocation Problem Assumption of Continuity Sensitivity of the Optimal Solution Algebraic Statement of Linear Programming Problems 2.2 Further Linear Programming Formulation Examples Brewery Problem Oil Refinery Problem Warehouse Problem Chicken and Egg Problem Nurse Scheduling Problem 2.3 Some Scientific Applications of Linear Programming Curve Fitting Inconsistent Systems of Equations Feasibility Problem Selected References Exercises 3 The Simplex Algorithm for Linear Programming 3.1 Standard Form and Pivoting Standard Form The Simplex Tableau Pivoting on a Simplex Tableau 3.2 Canonical Form Canonical Form Finding a Better Basic Feasible Solution The Simplex Rule for Pivoting The Geometry of a Pivot 3.3 Optimal, Unbounded, and Infeasible Forms Optimal Form Unbounded Form Two Infeasible Forms 3.4 Solving Linear Programs in Canonical Form Pivoting to Optimal Form What Can Go Wrong: Degeneracy and Cycling Ways to Prevent Cycling Convergence in the Nondegenerate Case Convergence in the Degenerate Case 3.5 Obtaining Canonical Form from Standard Form Getting an Identity The Subproblem Technique Pivoting to Form a Subproblem Summary of the Subproblem Technique 3.6 The Simplex Algorithm The Simplex Algorithm 3.7 Reformulating Any Linear Program into Standard Form Maximization Problems Inequality Constraints Free Variables 3.8 The Method of Artificial Variables Getting b Nonnegative The Artificial Problem Feasibility of the Original Problem Canonical Form for the Original Problem 3.9 Pivot Matrices and the Revised Simplex Method Pivot Matrices The Revised Simplex Method Tableaus with the Same Basic Sequence 3.10 Computer Solution of Linear Programs Computer Cycling Controlling Roundoff Errors Tolerances and Errors Other Practical Considerations Selected References Exercises 4 Geometry of the Simplex Algorithm 4.1 Geometry of Pivoting Graphical Representation of the Feasible Set Extreme Points and Basic Feasible Solutions The General Case Alternative Representations of the Feasible Set Graphical Interpretation of Canonical Form Tableaus 4.2 Convex Sets Definition of a Convex Set Convexity of the Feasible Set 4.3 Multiple Optimal Solutions Finding All Optimal Solutions Convexity of the Set of Optimal Solutions Optimal Rays Selected References Exercises 5 Duality in Linear Programming 5.1 The Standard Dual Pair Duality Relations 5.2 Getting the Dual Solution from a Primal Solution Relationships between Optimal Tableaus Constructing an Optimal Dual Vector 5.3 Economic Interpretation of Dual Variables The Complementary Slackness Conditions 5.4 Finding the Dual of Any Linear Program Dual of a Linear Program in Standard Form A More Complicated Example Dual of the Transportation Problem 5.5 The Dual Simplex Method Another Example of Dual Simplex Pivoting 5.6 Using the Dual to Computational Advantage A Difficult Primal Problem Having an Easy Dual 5.7 Theorems of the Alternative Selected References Exercises 6 Sensitivity Analysis in Linear Programming 6.1 The Brewery Problem 6.2 Changes in Production Requirements Changes in Nonbasic Variables Increasing Basic Variables Decreasing Basic Variables When a Nonbasic Variable Exceeds Its Minimum Ratio 6.3 Changes in Available Resources Changes in One Resource Simultaneous Changes in Several Resources Computing Shadow Prices 6.4 Changes in Selling Prices Simultaneous Changes in Prices 6.5 Adding New Products or Constraints New Products Technology Changes New Constraints Selected References Exercises 7 Linear Programming Models for Network Flow Problems 7.1 The Transportation Problem The Transportation Tableau 7.2 Using the Dual to Improve the Current Solution Obtaining an Optimal Transportation Tableau A Final Comparison with the Simplex Algorithm 7.3 The Transportation Algorithm 7.4 Finding an Initial Basic Feasible Solution 7.5 Variations of the Transportation problem Unequal Supply and Demand The Transshipment Problem Multiple Optimal Solutions 7.6 The Assignment Problem 7.7 General Network Models The General Network Flow Model Spanning Trees and Basic Feasible Solutions Solving a General Network Flow Problem Summary of the General Network Flow Algorithm Finding an Initial Feasible Spanning Tree Selected References Exercises Part 2: Integer, Nonlinear and Dynamic Programming 8 Integer Programming 8.1 The Integer Programming Problem 8.2 Implicit Enumeration 8.3 Solution by Branch and Bound The Branch-and-Bound Algorithm A Branch-and-Bound Example in Detail The Order of Selecting Unfathomed Nodes Practical Considerations in Using Branch and Bound 8.4 0-1 Integer Programs A 0-1 Example Looking Ahead How Far to Look Ahead Getting Nonnegative, Increasing Cost Coefficients The Branch-and-Bound Algorithm for 0-1 Programs 8.5 Integer Programming Formulation Examples The Oakwood Furniture Problem Revisited The Knapsack Problem Capital Budgeting Facility Location The Traveling Salesman Problem A Scheduling Problem 8.6 Integer Programming Formulation Techniques Writing General Integer Programs as 0-1 Programs Mixed-Integer Programs Enforcing Logical Conditions Selected References Exercises 9 Nonlinear Programming 9.1 A Nonlinear Programming Problem Contour Plots Assumption of Continuity Algorithms for Nonlinear Programming 9.2 Unconstrained Minimization Maxima and Minima in One Dimension Maxima and Minima in n Dimensions 9.3 Equality Constraints Parametric Representation of Equality Constraints Several Equality Constraints Several Parameters The Method of Lagrange Classifying Lagrange Points An Important Use of the Lagrange Multiplier Theorem 9.4 Inequality Constraints Active and Inactive Constraints The Orthogonality Condition The Karush-Kuhn-Tucker Conditions 9.5 Convexity Convex Functions Convexity and Minima Checking Whether a Function is Convex 9.6 Karush-Kuhn-Tucker Theory of Nonlinear Programming The KKT Method Strategy in Solving the KKT Conditions 9.7 Numerical Methods of Nonlinear Programming Line Searching The Method of Steepest Descent The Generalized Reduced-Gradient Method The Ellipsoid Algorithm Conclusion 9.8 Nonlinear Programs with Special Structure Quadratic Programming Geometric Programming Separable Programming Other Theoretical Aspects of Nonlinear Programming Selected References Exercises 10 Dynamic Programming 10.1 An Introductory Example The Stagecoach Problem The Backward Recursive Relations The Forward Recursive Relations Basic Features of a Dynamic Programming Formulation 10.2 A Loading Problem 10.3 The Boxes Problem 10.4 The Equipment Replacement Problem 10.5 Problems with Several State Variables The Curse of Dimensionality 10.6 Continuous State Dynamic Programming Problems A Simple Example A More Complicated Example Selected References Exercises Part 3: Probabilistic Models 11 Queueing Models 11.1 A Simple Example and Basic Terminology 11.2 A Simple Model Suggested by Observation Consequences of Exponentially Distributed Interarrival Times Special Case 1: Arrivals But No Departures Special Case 2: Departures But No Arrivals 11.3 A More General Arrivals and Departures Model 11.4 Steady-State Queueing Systems 11.5 A Single-Server System with Constant Rates 11.6 Operating Characteristics from Basic Principles 11.7 Multiple-Server Queues 11.8 Finite Queues 11.9 Limited-Source Queues 11.10 Optimization in Queues Optimizing over the Number of Servers, s Optimizing over the Mean Service Rate, mu Optimizing over the Mean Arrival Rate, lambda 11.11 Queueing Models Involving Nonexponential Distributions The Kendall Notation Selected References Exercises 12 Inventory Models 12.1 Economic Order-Quantity Models Economic Order-Quantity Models with No Shortages Allowed Economic Order-Quantity Models with Shortages Allowed Economic Order-Quantity Models with Price Breaks Economic Order-Quantity Models with Several Inventories 12.2 Dynamic Inventory Models with Periodic Review Concave Cost Functions Convex Cost Functions 12.3 Stochastic Inventory Models A Single-Period Model A Two-Period Model Selected References Exercises 13 Simulation 13.1 Next-Event Simulation Observing a Queueing System Constructing an Event List 13.2 Statistical Analysis of Simulation Results Estimating L and L_q Estimating W and W_q Estimating Server Utilization Estimating Probability Distributions Checking Random Interevent Times 13.3 Generating Pseudorandom Numbers Random and Pseudorandom Number Sequences Random-Number Generators The Multiplicative Congruential Algorithm Other Uniform Random-Number Generators Nonuniform Distributions 13.4 Monte Carlo Simulations Evaluation of an Integral The Metropolis Algorithm 13.5 Practical Considerations in Simulation Modeling Computer Programs for Simulation Logical and Statistical Validity Selected References Exercises Appendix: Notational Conventions for Matrix Algebra A.1 Matrices Equality of Two Matrices Multiplying Two Matrices A.2 Systems of Linear Equations A.3 The Sum of Two Matrices A.4 Multiplying a Matrix by a Real Number A.5 The Transpose of a Matrix A.6 Some Simple Matrix Identities Selected References Answers to Selected Exercises Index