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