Operations Research: An Introduction, 9/eis ideal for or junior/senior undergraduate and first-year graduate courses in Operations Research in departments of Industrial Engineering, Business Administration, Statistics, Computer Science, and Mathematics. This text streamlines the coverage of the theory, applications, and computations of operations research. Numerical examples are effectively used to explain complex mathematical concepts. A separate chapter of fully analyzed applications aptly demonstrates the diverse use of OR. The popular commercial and tutorial software AMPL, Excel, Excel Solver, and Tora are used throughout the book to solve practical problems and to test theoretical concepts.

**Chapter 1: What Is Operations Research?**

1.1 Operations Research Models

1.2 Solving the OR Model

1.3 Queuing and Simulation Models

1.4 Art of Modeling

1.5 More Than Just Mathematics …

1.6 Phases of an OR Study

1.7 About This Book

References

**Chapter 2: Modeling with Linear Programming**

2.1 Two-Variable LP Model

2.1.1 Properties of the LP Model

2.2 Graphical LP Solution

2.2.1 Solution of a Maximization Model

2.2.2 Solution of a Minimization Model

2.3 Computer Solution with Excel Solver and AMPL

2.3.1 LP Solution with Excel Solver

2.3.2 LP Solution with AMPL

2.4 Linear Programming Applications

2.4.1 Investment

2.4.2 Production Planning and Inventory Control

2.4.3 Manpower Planning

2.4.4 Urban Development Planning

2.4.5 Blending and Refining

2.4.6 Additional LP Applications

References

**Chapter 3: The Simplex Method and Sensitivity Analysis**

3.1 LP Solution Space in Equation Form

3.2 Transition from Graphical to Algebraic Solution

3.3 The simplex Method

3.3.1 Iterative Nature of the Simplex Method

3.3.2 Computational Details of the Simplex Algorithm

3.4 Artificial Starting Solution

3.4.1 *M*-Method

3.4.2 Two-Phase Method

3.5 Special Cases in Simplex Method Application

3.5.1 Degeneracy

3.5.2 Alternative Optima

3.5.3 Unbounded Solution

3.5.4 Infeasible Solution

3.6 Sensitivity Analysis

3.6.1 Graphical Sensitivity Analysis

3.6.2 Algebraic Sensitivity Analysis–Right-hand Side of the Constraints

3.6.3 Algebraic Sensitivity Analysis–Objective-Function Coefficients

3.6.4 Sensitivity Analysis with TORA, Excel Solver, and AMPL

3.7 Computational Issue in Linear Programming

References

**Chapter 4: Duality and Post-Optimal Analysis**

4.1 Definition of the Dual Problem

4.2 Primal-Dual Relationships

4.2.1 Review of Simple Matrix Operations

4.2.2 Simplex Tableau Layout

4.2.3 Optimal Dual Solution

4.2.4 Simplex Tableau Computations

4.3 Economic Interpretation of Duality

4.3.1 Economic Interpretation of Dual Variables

4.3.2 Economic Interpretation of Dual Constraints

4.4 Additional Simplex Algorithms for LP

4.4.1 Dual Simplex Algorithm

4.4.2 Generalized Simplex Algorithm

4.5 Post-optimal Analysis

4.5.1 Changes Affecting Feasibility

4.5.2 Changes Affecting Optimality

References

**Chapter 5: Transportation Model and Its Variants**

5.1 Definition of the Transportation Model

5.2 Nontraditional transportation models

5.3 The transportation Algorithm

5.3.1 Determination of the Starting Solution

5.3.2 Iterative Computations of the Transportation Algorithm

5.4 The Assignment Model

5.4.1 The Hungarian Method

5.4.2 Simplex Explanation of the Hungarian Method

References

**Chapter 6: Network Models**

6.1 Network definitions

6.2 Minimal Spanning tree Algorithm

6.3 Shortest-Route Problem

6.3.1 Examples of the Shortest-Route Applications

6.3.2 Shortest-Route Algorithms

6.3.3 Linear Programming Formulation of the Shortest-Route Problem

6.4 Maximal flow model

6.4.1 Enumeration of Cuts

6.4.2 Maximal-Flow Algorithm

6.4.3 Linear Programming Formulation of the Maximal Flow Model

6.5 CPM and PERT

6.5.1 Network Representation

6.5.2 Critical Path Computations

6.5.3 Construction of the Time Schedule

6.5.4 Linear Programming Formulation of CPM

6.5.5 PERT Calculations

References

**Chapter 7: Advanced Linear Programming**

7.1 Fundamentals of the Simplex Method

7.1.1 From Extreme Points to Basic Solutions

7.1.2 Generalized Simplex Tableau in Matrix Form

7. 2 Revised Simplex Algorithm

7.3 Bounded-Variables Algorithm

7.4 Duality

7.4.1 Matrix Definition of the Dual Problem

7.4.2 Optimal Dual Solution

7.5 Parametric Linear Programming

7.5.1 Parametric Changes in **C**

7.5.2 Parametric Changes in **b**

7.6 More Linear Programming Topics

References

**Chapter 8: Goal Programming**

8.1 A Goal Programming Formulation

8.2 Goal Programming Algorithms

8.2.1 The Weights Method

8.2.2 The Preemptive Method

References

**Chapter 9: Integer Linear Programming**

9.1 Illustrative Applications

9.2 Integer Programming Algorithms

9.2.1 Branch-and-Bound (B&B) Algorithm

9.2.2 Cutting-Plane Algorithm

References

**Chapter 10: Heuristic and Constraint Programming**

10.1 Introduction

10.2 Greedy (local Search) Heuristics

10.2.1 Discrete Variable Heuristi

10.2.2 Continuous Variable Heuristic

10.3 Metaheuristics

10.3.1 Tabu Search Algorithm

10.3.2 Simulated Annealing Algorithm

10.3.3 Genetic Algorithm

10.4 Application of metaheuristics to Integer Linear Programs

10.4.1 ILP Tabu Algorithm

10.4.2 ILP Simulated Annealing Algorithm

10.4.3 ILP Genetic Algorithm

10.5 Introduction to Constraint Programming

References

**Chapter 11: Traveling Salesperson Problem (TSP)**

11.1 Example Applications of TSP

11.2 TSP Mathematical Model

11.3 Exact TSP Algorithm

11.3.1 B&B Algorithm

11.3.2 Cutting-plane Algorithm

11.4 Local Search Heuristics

11.4.1 Nearest-neighbor Heuristic

11.4.2 Sub-tour Reversal heuristic

11.5 Metaheuristic

11.5.1 TSP Tabu Algorithm

11.5.2 TSP Simulated Annealing Algorithm

11.5.3 TSP Genetic Algorithm

References

**Chapter 12: Deterministic Dynamic Programming**

12.1 Recursive Nature of Computations in DP

12.2 Forward and Backward Recursion

12.3 Selected DP Applications

12.3.1 Knapsack/Flyaway Kit/Cargo-Loading Model

12.3.2 Workforce Size Model

12.3.3 Equipment Replacement Model

12.3.4 Investment Model

12.3.5 Inventory Models

12.4 Problem of Dimensionality

References

**Chapter 13: Deterministic Inventory Models**

13.1 General Inventory Model

13.2 Role of Demand in the Development of Inventory Models

13.3 Static Economic-Order-Quantity (EOQ) Models

13.3.1 Classic EOQ model_{ }

13.3.2 EOQ with Price Breaks

13.3.3 Multi-Item EOQ with Storage Limitation

13.4 Dynamic EOQ Models

13.4.1 No-Setup EOQ Model

13.4.2 Setup EOQ Model

References

**Chapter 14: Review of Basic Probability**

14.1 Laws of Probability

14.1.1 Addition Law of Probability

14.1.2 Conditional Law of Probability

14.2 Random Variables and Probability Distributions

14.3 Expectation of a Random Variable

14.3.1 Mean and Variance (Standard Deviation) of a Random Variable

14.3.2 Mean and Variance of Joint Random Variables

14.4 Four Common Probability Distributions

14.4.1 Binomial Distribution

14.4.2 Poisson Distribution

14.4.3 Negative Exponential Distribution

14.4.4 Normal Distribution

14.5 Empirical Distributions

References

**Chapter 15: Decision Analysis and Games**

15.1 Decision Making under Certainty–Analytic Hierarchy Process (AHP)

15.2 Decision Making under Risk

15.2.1 Expected Value Criterion

15.2.2 Variations of the Expected Value Criterion

15.3 Decision under Uncertainty

15.4 Game Theory

15.4.1 Optimal Solution of Two-Person Zero-Sum Games

15.4.2 Solution of Mixed Strategy Games

References

**Chapter 16: Probabilistic Inventory Models**

16.1 Continuous Review Models

16.1.1 “Probabilitized” EOQ Model

16.1.2 Probabilistic EOQ Model

16.2 Single-Period Models

16.2.1 No Setup Model

16.2.2 Setup Model (*s*-*S* Policy)

16.3 Multiperiod Model

References

**Chapter 17: Markov Chains**

17.1 Definition of a Markov Chain

17.2 Absolute and *n*-Step Transition Probabilities

17.3 Classification of the States in a Markov Chain

17.4Steady-State Probabilities and Mean Return Times of Ergodic Chains

17.5 First Passage Time

17.6 Analysis of Absorbing States

References

**Chapter 18: Queuing Systems**

18.1 Why Study Queues?

18.2 Elements of a Queuing Model

18.3 Role of Exponential Distribution

18.4 Pure Birth and Death Models (Relationship Between the Exponential and Poisson Distributions)

18.4.1 Pure Birth Model

18.4.2 Pure Death Model

18.5 Generalized Poisson Queuing Model

18.6 Specialized Poisson Queues

18.6.1 Steady-State Measures of Performance

18.6.2 Single-Server Models

18.6.3 Multiple-Server Models

18.6.4 Machine Servicing Model*–(M/M/R) *:* (GD/K/K)*,*R<K*

18.7 –Pollaczek-Khintchine (P-K) Formula

18.8 Other Queuing Models

18.9 Queuing Decision Models

18.9.1 Cost Models

18.9.2 Aspiration Level Model

References

**Chapter 19: Simulation Modeling**

19.1 Monte Carlo Simulation

19.2 Types of Simulation

19.3 Elements of Discrete-Event Simulation

19.3.1 Generic Definition of Events

19.3.2 Sampling from Probability Distributions

19.4 Generation of Random Numbers

19.5 Mechanics of Discrete Simulation

19.5.1 Manual Simulation of a Single-Server Model

19.5.2 Spreadsheet-Based Simulation of the Single-Server Model

19.6 Methods for Gathering Statistical Observations

19.6.1 Subinterval Method

19.6.2 Replication Method

19.7 Simulation Languages

References

**Chapter 20: Classical Optimization Theory**

20.1 Unconstrained Problems

20.1.1 Necessary and Sufficient Conditions

20.1.2 The Newton-Raphson Method

20.2 Constrained Problems

20.2.1 Equality Constraints

20.2.2 Inequality Constraints*–*Karush-Kuhn-Tucker (KKT) Conditions

References

**Chapter 21: Nonlinear Programming Algorithms**

21.1 Unconstrained Algorithms

21.1.1 Direct Search Method

21.1.2 Gradient Method

21.2 Constrained Algorithms

21.2.1 Separable Programming

21.2.2 Quadratic Programming

21.2.3 Chance-Constrained Programming

21.2.4 Linear Combinations Method

21.2.5 SUMT Algorithm

References

Appendix A: Statistical Tables

Appendix B: Partial Answers to Selected Problems

**On the CD-ROM**

**Chapter 22-CD: Additional Network and LP algorithms**

22.1 Minimum-Cost Capacitated Flow Problem

22.1.1 Network Representatio

22.1.2 Linear Programming Formulation

22.1.3 Capacitated Network Simplex Algorithm Model

22.2 Decomposition Algorithm

22.3 Karmarkar Interior-Point Method

22.3.1 Basic Idea of the Interior-Point Algorithm

22.3.2 Interior-Point Algorithm

References

**Chapter 23-CD: Forecasting Models**

23.1 Moving Average Technique

23.2 Exponential Smoothing

23.3 Regression

References

**Chapter 24-CD: Probabilistic Dynamic Programming**

24.1 A Game of Chance

24.2 Investment Problem

24.3 Maximization of the Event of Achieving a Goal

References

**Chapter 25-CD: Markovian Decision Process**

25.1 Scope of the Markovian Decision Problem

25.2 Finite-Stage Dynamic Programming Model

25.3 Infinite-Stage Model

25.3.1 Exhaustive Enumeration Method

25.3.2 Policy Iteration Method Without Discounting

25.3.3 Policy Iteration Method with Discounting

25.4 Linear Programming Solution

References

**Chapter 26-CD: Case Analysis**

Case 1: Airline Fuel Allocation Using Optimum Tankering

Case 2: Optimization of Heart Valves Production

Case 3: Scheduling Appointments at Australian Tourist Commission Trade Events

Case 4: Saving Federal Travel Dollars

Case 5: Optimal Ship Routing and Personnel Assignment for Naval Recruitment in Thailand

Case 6: Allocation of Operating Room Time in Mount Sinai Hospital

Case 7: Optimizing Trailer Payloads at PFG Building Glass

Case 8: Optimization of Crosscutting and Log Allocation at Weyerhaeuser

Case 9: Layout Planning for a Computer Integrated Manufacturing (CIM) Facility

Case 10: Booking Limits in Hotel Reservations

Case 11: Casey’s Problem: Interpreting and Evaluating a New Test

Case 14: Ordering Golfers on the Final Day of Ryder Cup Matches

Case 13: Inventory Decisions in Dell’s Supply Chain

Case 14: Analysis of an Internal Transport System in a Manufacturing Plant

Case 15: Telephone Sales Manpower Planning at Qantas Airways

Appendix C-CD: AMPL Modeling Language

C.1 Rudimentary AMPL Model

C.2 Components of AMPL Model

C.3 Mathematical Expressions and Computed Parameters

C.4 Subsets and Indexed Sets

C.5 Accessing External Files

C.5.1 Simple Read Files

C.5.2 Using Print or Printf to Retrieve Output

C.5.3 Input Table Files

C.5.4 Output Table Files

C.5.5 Spreadsheet Input/Output Tables

C.6 Interactive Commands

C.7 Iterative and Conditional Execution of AMPL Commands

C.8 Sensitivity Analysis using AMPL

C.9 Selected AMPL Models

Reference

**Appendix D-CD: Review of Vectors and Matrices**

D.1 Vectors

D.1.1 Definition of a Vector

D.1.2 Addition (Subtraction) of Vectors

D.1.3 Multiplication of Vectors by Scalars

D.1.4 Linearly Independent Vectors

D.2 Matrices

D.2.1 Definition of a Matrix

D.2.2 Types of Matrices

D.2.3 Matrix Arithmetic Operations

D.2.4 Determinant of a Square Matrix

D.2.5 Nonsingular Matrix

D.2.6 Inverse of a Nonsingular Matrix

D.2.7 Methods of Computing the Inverse of Matrix

D.2.8 Matrix Manipulations Using Excel

D.3 Quadratic Forms

D.4 Convex and Concave Functions

** **Problems

References

Appendix E: Case Studies

Index