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