Product Cover Image

Operations Research: An Introduction, 9th Edition

By Hamdy A. Taha

Published by Pearson

Published Date: Aug 29, 2010


Operations Research: An Introduction, 9/e is 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.

Table of Contents

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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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



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 ConstraintsKarush-Kuhn-Tucker (KKT) Conditions



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


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



Chapter 23-CD:  Forecasting Models

23.1 Moving Average Technique

23.2 Exponential Smoothing

23.3 Regression



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



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



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



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




Appendix E: Case Studies