初级篇

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.2 Graphical LP Solution

2.2.1 Solution of a Maximization Model

2.2.2 Solution of a Minimization Model

2.3 Selected LP Applications

2.3.1 Urban Planning

2.3.2 Currency Arbitrage

2.3.3 Investment

2.3.4 Production Planning and Inventory Control

2.3.5 Blending and Refining

2.3.6 Manpower Planning

2.3.7 Additional Applications

2.4 Computer Solution with Solver and AMPL

2.4.1 LP Solution with Excel Solver

2.4.2 LP Solution with AMPL

References

Chapter 3 The Simplex Method and Sensitivity Analysis

3.1 LP Model in Equation Form

3.1.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side

3.1.2 Dealing with Unrestricted Variables

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.3.3 Summary of the Simplex Method

3.4 Artificial Starting Solution

3.4.1 M-Method

3.4.2 Two-Phase Method

3.5 Special Cases in the Simplex Method

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—Changes in the Right-Hand Side

3.6.3 Algebraic Sensitivity Analysis—Objective Function

3.6.4 Sensitivity Analysis with TORA, Solver, and AMPL

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

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 Ilts 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.3.3 Simplex Method Explanation of the Method of Multipliers

5.4 The Assignment Model

5.4.1 The Hungarian Method

5.4.2 Simplex Explanation of the Hungarian Method

5.5 The Transshipment Model

References

Chapter 6 Network Models

6.1 Scope and Definition of Network Models

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 Maximal Flow Mode

6.5 CPM and PERT

6.5.1 Network Representation

6.5.2 Critical Path (CPM) Computations

6.5.3 Construction of the Time Schedule

6.5.4 Linear Programming Formulation of CPM

6.5.5 PERT Networks

References

Chapter 7 Goal Programming

7.1 A Goal Programming Formulation

7.2 Goal Programming Algorithms

7.2.1 The Weights Method

7.2.2 The Preemptive Method

References

Chapter 8 Integer Linear Programming

8.1 Illustrative Applications

8.1.1 Capital Budgeting

8.1.2 Set-Covering Problem

8.1.3 Fixed-Charge Problem

8.1.4 Either-Or and If-Then Constraints

8.2 Integer Programming Algorithms

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

8.2.2 Cutting-Plane Algorithm

8.2.3 Computational Considerations in ILP

8.3 Traveling Salesperson (TSP) Problem

8.3.1 Heuristic Algorithms

8.3.2 B&B Solution Algorithm

8.3.3 Cutting-Plane Algorithm

References

Chapter 9 Deterministic Dynamic Programming

9.1 Recursive Nature of Computations in DP

9.2 Forward and Backward Recursion

9.3 Selected DP Applications

9.3.1 Knapsack/Fly-Away/Cargo-Loading Model

9.3.2 Work-Force Size Model

9.3.3 Equipment Replacement Model

9.3.4 Investment Model

9.3.5 Inventory Models

9.4 Problem of Dimensionality

References

Chapter 10 Determiniistic Inventory Models

10.1 General Inventory Model

10.2 Role of Demand in the Development of Inventory Models

10.3 Static Economic-Order-Quantity (EOQ) Models

10.3.1 Classic EOQ model

10.3.2 EOQ with Price Breaks

10.3.3 Multi-Item EOQ with Storage Limitation

10.4 Dynamic EOQ Models

10.4.1 No-Setup Model

10.4.2 Setup Model

References

Chapter 11 Decision Analysis and Games

11.1 Decision Making under Certainty—Analytic Hierarchy Process (AHP)

11.2 Decision Making under Risk

11.2.1 Decision Tree-Based Expected Value Criterion

11.2.2 Variations of the Expected Value Criterion

11.3 Decision under Uncertainty

11.4 Game Theory

11.4.1 Optimal Solution of Two-Person Zero-Sum Games

11.4.2 Solution of Mixed Strategy Games

References

Chapter 12 Queuing Systems

12.1 Why Study Queues?

12.2 Elements of a Queuing Model

12.3 Role of Exponential Distribution

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

12.4.1 Pure Birth Model

12.4.2 Pure Death Model

12.5 Generalized Poisson Queuing Model

12.6 Specialized Poisson Queues

12.6.1 Steady-State Measures of Performance

12.6.2 Single-Server Models

12.6.3 Multiple-Server Models

12.6.4 Machine Servicing Model—(M/M/R): (GD/K/K),R＜K

12.7 (M/G/1) : (GD/∞/∞)—Pollaczek-Khintchine (P-K) Formula

12.8 Other Queuing Models

12.9 Queuing Decision Models

12.9.1 Cost Models

12.9.2 Aspiration Level Model

References

Appendix A AMPL Modeling Language

A.1 Rudimentary AMPL Model

A.2 Components of AMPL Model

A.3 Mathematical Expressions and Computed Parameters

A.4 Subsets and Indexed Sets

A.5 Accessing External Files

A.5.1 Simple Read Files

A.5.2 Using Print or Printf to Retrieve Output

A.5.3 Input Table Files

A.5.4 Output Table Files

A.5.5 Spreadsheet Input/Output Tables

A.6 Interactive Commands

A.7 Iterative and Conditional Execution of AMPL Commands

A.8 Sensitivity Analysis Using AMPL

Reference

高 级篇

Chapter 13 Advanced Linear Programming

13.1 Simplex Method Fundamentals

13.1.1 From Extreme Points to Basic Solutions

13.1.2 Generalized Simplex Tableau in Matrix Form

13.2 Revised Simplex Method

13.2.1 Development of the Optimality and Feasibility Conditions

13.2.2 Revised Simplex Algorithm

13.3 Bounded-Variables Algorithm

13.4 Duality

13.4.1 Matrix Definition of the Dual Problem

13.4.2 Optimal Dual Solution

13.5 Parametric Linear Programming

13.5.1 Parametric Changes in C

13.5.2 Parametric Changes in b

References

Chapter 14 Review of BasicProbability

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 Probabilistic InventoryModels

15.1 Continuous Review Models

15.1.1 “Probabilitized” EOQ Model

15.1.2 Probabilistic EOQ Model

15.2 Single-Period Models

15.2.1 No-Setup Model (Newsvendor Model)

15.2.2 Setup Model (s-S Policy)

15.3 Multiperiod Model

References

Chapter 16 Simulation Modeling

16.1 Monte Carlo Simulation

16.2 Types of Simulation

16.3 Elements of Discrete-Event Simulation

16.3.1 Generic Definition of Events

16.3.2 Sampling from Probability Distributions

16.4 Generation of Random Numbers

16.5 Mechanics of Discrete Simulation

16.5.1 Manual Simulation of a Single-Server Model

16.5.2 Spreadsheet-Based Simulation of the Single-Server Model

16.6 Methods for Gathering Statistical Observations

16.6.1 Subinterval Method

16.6.2 Replication Method

16.6.3 Regenerative (Cycle) Method

16.7 Simulation Languages

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.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains

17.5 First Passage Time

17.6 Analysis of Absorbing States

References

Chapter 18 Classical Optimization Theory

18.1 Unconstrained Problems

18.1.1 Necessary and Sufficient Conditions

18.1.2 The Newton-Raphson Method

18.2 Constrained Problems

18.2.1 Equality Constraints

18.2.2 Inequality Constraints—Karush-Kuhn-Tucker (KKT) Conditions

References

Chapter 19 Nonlinear Programming Algorithms

19.1 Unconstrained Algorithms

19.1.1 Direct Search Method

19.1.2 Gradient Method

19.2 Constrained Algorithms

19.2.1 Separable Programming

19.2.2 Quadratic Programming

19.2.3 Chance-Constrained Programming

19.2.4 Linear Combinations Method

19.2.5 SUMT Algorithm

References

Chapter 20 Additional Network and LP Algorithms

20.1 Minimum-Cost Capacitated Flow Problem

20.1.1 Network Representation

20.1.2 Linear Programming Formulation

20.1.3 Capacitated Network Simplex Algorithm

20.2 Decomposition Algorithm

20.3 Karmarkar Interior-Point Method

20.3.1 Basic Idea of the Interior-Point Algorithm

20.3.2 Interior-Point Algorithm

References

Chapter 21 Forecasting Models

21.1 Moving Average Technique

21.2 Exponential Smoothing

21.3 Regression

References

Chapter 22 Probabilistic Dynamic Programming

22.1 A Game of Chance

22.2 Investment Problem

22.3 Maximization of the Event of Achieving a Goal

References

Chapter 23 Markovian Decision Process

23.1 Scope of the Markovian Decision Problem

23.2 Finite-Stage Dynamic Programming Model

23.3 Infinite-Stage Model

23.3.1 Exhaustive Enumeration Method

23.3.2 Policy Iteration Method Without Discounting

23.3.3 Policy Iteration Method with Discounting

23.4 Linear Programming Solution

References

Chapter 24 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 12: 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 B Statistical Tables

Appendix C Partial Solutions to Answers Problems

Appendix D 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

Selected References

Appendix E Case Studies