Operations Research: Pearson New International Edition
An Introduction
9th Edition
Published on 2. August 2013
Book
Paperback/Softback
818 pages
978-1-292-02433-2 (ISBN)
Description
For junior/senior undergraduate and first-year graduate courses in Operations Research in departments of Industrial Engineering, Business Administration, Statistics, Computer Science, and Mathematics.
Theory, applications, and computations.
Operations Research: An Introduction 9/e uses theory, applications, and computations to teach students the basics of OR:
Numerical examples are effectively used to explain complex mathematical concepts, thus avoiding the use of complex notations and theorems.
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.
The book can be used conveniently in a survey course that encompasses all the major tools of operations research, or in two separate courses on deterministic and probabilistic decision-making.
Topics include Markov chains, TSP heuristics, new LP models, a simplex-based approach to LP sensitivity analysis, and more. The ninth edition also includes a dedicated chapter on the traveling salesperson, as well as, for the first time in any OR textbook, a (math-free) Section 3.7 explains how the different linear programming algorithms (simplex, dual simplex, revised simplex, and interior point) are "meshed" together to produce highly-successful commercial codes for solving LP in practice.
The companion Excel, TORA, and AMPL files as well as the additional chapters and appendixes are available on the Taha Companion Website (www.pearsonhighered.com/taha) that includes valuable resources forboth students and instructors. A note about accessing the Companion Website:
Instructors should click the "Register" link and follow the on-screen directions to access the site. Instructors need a Pearson Education account to register, but do not require an additional Access Code.
Students can access the Companion Website by redeeming the Access Code included in the front of their new copy of Operations Research, 9e. Students can also purchase Companion Website access online.
The Instructor Resource Center contains the Solutions Manual and PowerPoints of the art from the book. Instructors can download these resources from www.pearsonhighered.com/irc
Theory, applications, and computations.
Operations Research: An Introduction 9/e uses theory, applications, and computations to teach students the basics of OR:
Numerical examples are effectively used to explain complex mathematical concepts, thus avoiding the use of complex notations and theorems.
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.
The book can be used conveniently in a survey course that encompasses all the major tools of operations research, or in two separate courses on deterministic and probabilistic decision-making.
Topics include Markov chains, TSP heuristics, new LP models, a simplex-based approach to LP sensitivity analysis, and more. The ninth edition also includes a dedicated chapter on the traveling salesperson, as well as, for the first time in any OR textbook, a (math-free) Section 3.7 explains how the different linear programming algorithms (simplex, dual simplex, revised simplex, and interior point) are "meshed" together to produce highly-successful commercial codes for solving LP in practice.
The companion Excel, TORA, and AMPL files as well as the additional chapters and appendixes are available on the Taha Companion Website (www.pearsonhighered.com/taha) that includes valuable resources forboth students and instructors. A note about accessing the Companion Website:
Instructors should click the "Register" link and follow the on-screen directions to access the site. Instructors need a Pearson Education account to register, but do not require an additional Access Code.
Students can access the Companion Website by redeeming the Access Code included in the front of their new copy of Operations Research, 9e. Students can also purchase Companion Website access online.
The Instructor Resource Center contains the Solutions Manual and PowerPoints of the art from the book. Instructors can download these resources from www.pearsonhighered.com/irc
More details
Edition
9th edition
Language
English
Place of publication
Harlow
United Kingdom
Target group
College/higher education
Dimensions
Height: 276 mm
Width: 216 mm
ISBN-13
978-1-292-02433-2 (9781292024332)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Book
10/2010
9th Edition
Pearson
€86.65
Article exhausted; check for reprint
Previous edition
Book
10/2010
9th Edition
Pearson
€86.65
Article exhausted; check for reprint
Content
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: 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 9: 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 10: 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 11: 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 12: 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 13: 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 14: 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 15: 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 16: 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
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 17: 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 18: 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 19: 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
Problems
References
Appendix E: Case Studies
Index
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: 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 9: 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 10: 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 11: 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 12: 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 13: 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 14: 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 15: 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 16: 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
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 17: 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 18: 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 19: 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
Problems
References
Appendix E: Case Studies
Index