《OPERATIONS RESEARCH AN INTRODUCTION》求取 ⇩

初级篇1

Chapter 1What Is Operations Research?1

1.1 Operations Research Models1

1.2 Solving the OR Model4

1.3 Queuing and Simulation Models5

1.4 Art of Modeling5

1.5 More Than Just Mathematics7

1.6 Phases of an OR Study8

1.7 About This Book10

References10

Chapter 2Modeling with Linear Programming11

2.1 Two-Variable LP Model12

2.2Graphical LP Solution15

2.2.1 Solution of a Maximization Model16

2.2.2 Solution of a Minimization Model23

2.3Selected LP Applications27

2.3.1 Urban Planning27

2.3.2 Currency Arbitrage32

2.3.3 Investment37

2.3.4 Production Planning and Inventory Control42

2.3.5 Blending and Refining51

2.3.6 Manpower Planning57

2.3.7 Additional Applications60

2.4Computer Solution with Solver and AMPL68

2.4.1 LP Solution with Excel Solver69

2.4.2 LP Solution with AMPL73

References80

Chapter 3The Simplex Method and Sensitivity Analysis81

3.1LP Model in Equation Form82

3.1.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side82

3.1.2 Dealing with Unrestricted Variables84

3.2 Transition from Graphical to Algebraic Solution85

3.3The Simplex Method90

3.3.1 Iterative Nature of the Simplex Method90

3.3.2 Computational Details of the Simplex Algorithm93

3.3.3 Summary of the Simplex Method99

3.4 Artificial Starting Solution103

3.4.1M-Method104

3.4.2 Two-Phase Method108

3.5 Special Cases in the Simplex Method113

3.5.1Degeneracy113

3.5.2 Alternative Optima116

3.5.3 Unbounded Solution119

3.5.4 Infeasible Solution121

3.6 Sensitivity Analysis123

3.6.1Graphical Sensitivity Analysis123

3.6.2 Algebraic Sensitivity Analysis—Changes in the Right-Hand Side129

3.6.3 Algebraic Sensitivity Analysis—Objective Function139

3.6.4 Sensitivity Analysis with TORA, Solver, and AMPL146

References150

Chapter 4Duality and Post-Optimal Analysis151

4.1 Definition of the Dual Problem151

4.2 Primal-Dual Relationships156

4.2.1Review of Simple Matrix Operations156

4.2.2 Simplex Tableau Layout158

4.2.3 Optimal Dual Solution159

4.2.4 Simplex Tableau Computations165

4.3 Economic Interpretation of Duality169

4.3.1Economic Interpretation of Dual Variables170

4.3.2 Economic Interpretation of Dual Constraints172

4.4 Additional Simplex Algorithms174

4.4.1Dual Simplex Algorithm174

4.4.2 Generalized Simplex Algorithm180

4.5 Post-Optimal Analysis181

4.5.1Changes Affecting Feasibility182

4.5.2 Changes Affecting Optimality187

References191

Chapter 5Transportation Model and Ilts Variants193

5.1 Definition of the Transportation Model194

5.2 Nontraditional Transportation Models201

5.3 The Transportation Algorithm206

5.3.1Determination of the Starting Solution207

5.3.2 Iterative Computations of the Transportation Algorithm211

5.3.3 Simplex Method Explanation of the Method of Multipliers220

5.4 The Assignment Model221

5.4.1The Hungarian Method222

5.4.2 Simplex Explanation of the Hungarian Method228

5.5 The Transshipment Model229

References234

Chapter 6Network Models235

6.1 Scope and Definition of Network Models236

6.2 Minimal Spanning Tree Algorithm239

6.3 Shortest-Route Problem243

6.3.1Examples of the Shortest-Route Applications243

6.3.2 Shortest-Route Algorithms248

6.3.3 Linear Programming Formulation of the Shortest-Route Problem257

6.4 Maximal flow model263

6.4.1Enumeration of Cuts263

6.4.2 Maximal Flow Algorithm264

6.4.3 Linear Programming Formulation of Maximal Flow Mode273

6.5 CPM and PERT275

6.5.1Network Representation277

6.5.2 Critical Path (CPM) Computations282

6.5.3 Construction of the Time Schedule285

6.5.4 Linear Programming Formulation of CPM292

6.5.5 PERT Networks293

References296

Chapter 7Goal Programming297

7.1 A Goal Programming Formulation298

7.2Goal Programming Algorithms302

7.2.1 The Weights Method302

7.2.2 The Preemptive Method305

References312

Chapter 8Integer Linear Programming313

8.1Illustrative Applications314

8.1.1 Capital Budgeting314

8.1.2 Set-Covering Problem318

8.1.3 Fixed-Charge Problem324

8.1.4 Either-Or and If-Then Constraints328

8.2Integer Programming Algorithms333

8.2.1 Branch-and-Bound (BB) Algorithm334

8.2.2 Cutting-Plane Algorithm343

8.2.3 Computational Considerations in ILP348

8.3Traveling Salesperson (TSP) Problem349

8.3.1 Heuristic Algorithms353

8.3.2 BB Solution Algorithm356

8.3.3 Cutting-Plane Algorithm359

References361

Chapter 9Deterministic Dynamic Programming363

9.1 Recursive Nature of Computations in DP364

9.2 Forward and Backward Recursion367

9.3Selected DP Applications369

9.3.1 Knapsack/Fly-Away/Cargo-Loading Model369

9.3.2 Work-Force Size Model377

9.3.3 Equipment Replacement Model380

9.3.4 Investment Model384

9.3.5 Inventory Models387

9.4 Problem of Dimensionality388

References390

Chapter 10Determiniistic Inventory Models391

10.1 General Inventory Model391

10.2 Role of Demand in the Development of Inventory Models392

10.3 Static Economic-Order-Quantity (EOQ) Models394

10.3.1 Classic EOQ model394

10.3.2 EOQ with Price Breaks400

10.3.3 Multi-Item EOQ with Storage Limitation404

10.4 Dynamic EOQ Models407

10.4.1 No-Setup Model409

10.4.2 Setup Model413

References425

Chapter 11Decision Analysis and Games427

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

11.2 Decision Making under Risk438

11.2.1 Decision Tree-Based Expected Value Criterion438

11.2.2 Variations of the Expected Value Criterion444

11.3 Decision under Uncertainty453

11.4 Game Theory458

11.4.1 Optimal Solution of Two-Person Zero-Sum Games459

11.4.2 Solution of Mixed Strategy Games462

References468

Chapter 12Queuing Systems469

12.1 Why Study Queues?470

12.2 Elements of a Queuing Model471

12.3 Role of Exponential Distribution473

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

12.4.1 Pure Birth Model476

12.4.2 Pure Death Model480

12.5 Generalized Poisson Queuing Model483

12.6 Specialized Poisson Queues488

12.6.1 Steady-State Measures of Performance489

12.6.2 Single-Server Models493

12.6.3 Multiple-Server Models502

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

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

12.8 Other Queuing Models517

12.9 Queuing Decision Models517

12.9.1 Cost Models518

12.9.2 Aspiration Level Model522

References524

Appendix A AMPL Modeling Language525

A.1Rudimentary AMPL Model525

A.2 Components of AMPL Model526

A.3 Mathematical Expressions and Computed Parameters534

A.4 Subsets and Indexed Sets537

A.5 Accessing External Files539

A.5.1 Simple Read Files539

A.5.2 Using Print or Printf to Retrieve Output541

A.5.3 Input Table Files541

A.5.4 Output Table Files544

A.5.5 Spreadsheet Input/Output Tables546

A.6 Interactive Commands546

A.7 Iterative and Conditional Execution of AMPL Commands548

A.8 Sensitivity Analysis Using AMPL550

Reference550

高级篇551

Chapter 13Advanced Linear Programming551

13.1 Simplex Method Fundamentals552

13.1.1 From Extreme Points to Basic Solutions554

13.1.2 Generalized Simplex Tableau in Matrix Form557

13.2 Revised Simplex Method560

13.2.1 Development of the Optimality and Feasibility Conditions561

13.2.2 Revised Simplex Algorithm563

13.3 Bounded-Variables Algorithm569

13.4 Duality575

13.4.1 Matrix Definition of the Dual Problem576

13.4.2 Optimal Dual Solution576

13.5 Parametric Linear Programming580

13.5.1 Parametric Changes in C581

13.5.2 Parametric Changes in b584

References586

Chapter 14Review of BasicProbability587

14.1 Laws of Probability587

14.1.1 Addition Law of Probability588

14.1.2 Conditional Law of Probability589

14.2 Random Variables and Probability Distributions591

14.3 Expectation of a Random Variable593

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

14.3.2 Mean and Variance of Joint Random Variables596

14.4 Four Common Probability Distributions599

14.4.1 Binomial Distribution599

14.4.2 Poisson Distribution600

14.4.3 Negative Exponential Distribution601

14.4.4 Normal Distribution602

14.5 Empirical Distributions605

References612

Chapter 15Probabilistic InventoryModels613

15.1 Continuous Review Models614

15.1.1 “Probabilitized” EOQ Model614

15.1.2 Probabilistic EOQ Model616

15.2 Single-Period Models621

15.2.1 No-Setup Model (Newsvendor Model)621

15.2.2 Setup Model (s-S Policy)625

15.3 Multiperiod Model627

References630

Chapter 16Simulation Modeling631

16.1 Monte Carlo Simulation631

16.2 Types of Simulation636

16.3 Elements of Discrete-Event Simulation637

16.3.1 Generic Definition of Events637

16.3.2 Sampling from Probability Distributions639

16.4 Generation of Random Numbers648

16.5 Mechanics of Discrete Simulation650

16.5.1 Manual Simulation of a Single-Server Model650

16.5.2 Spreadsheet-Based Simulation of the Single-Server Model656

16.6 Methods for Gathering Statistical Observations659

16.6.1 Subinterval Method660

16.6.2 Replication Method661

16.6.3 Regenerative (Cycle) Method662

16.7 Simulation Languages664

References666

Chapter 17Markov Chains667

17.1 Definition of a Markov Chain667

17.2 Absolute and n-Step Transition Probabilities670

17.3 Classification of the States in a Markov Chain672

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

17.5 First Passage Time680

17.6 Analysis of Absorbing States684

References689

Chapter 18Classical Optimization Theory691

18.1 Unconstrained Problems691

18.1.1 Necessary and Sufficient Conditions692

18.1.2 The Newton-Raphson Method696

18.2 Constrained Problems698

18.2.1 Equality Constraints699

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

References716

Chapter 19Nonlinear Programming Algorithms717

19.1 Unconstrained Algorithms717

19.1.1 Direct Search Method717

19.1.2 Gradient Method721

19.2 Constrained Algorithms725

19.2.1 Separable Programming725

19.2.2 Quadratic Programming734

19.2.3 Chance-Constrained Programming739

19.2.4 Linear Combinations Method744

19.2.5 SUMT Algorithm747

References748

Chapter 20Additional Network and LP Algorithms749

20.1 Minimum-Cost Capacitated Flow Problem749

20.1.1 Network Representation750

20.1.2 Linear Programming Formulation752

20.1.3 Capacitated Network Simplex Algorithm757

20.2 Decomposition Algorithm764

20.3 Karmarkar Interior-Point Method773

20.3.1 Basic Idea of the Interior-Point Algorithm773

20.3.2 Interior-Point Algorithm775

References784

Chapter 21Forecasting Models785

21.1 Moving Average Technique785

21.2 Exponential Smoothing789

21.3 Regression790

References794

Chapter 22Probabilistic Dynamic Programming795

22.1 A Game of Chance795

22.2 Investment Problem798

22.3 Maximization of the Event of Achieving a Goal802

References805

Chapter 23Markovian Decision Process807

23.1 Scope of the Markovian Decision Problem807

23.2 Finite-Stage Dynamic Programming Model809

23.3 Infinite-Stage Model813

23.3.1 Exhaustive Enumeration Method813

23.3.2 Policy Iteration Method Without Discounting816

23.3.3 Policy Iteration Method with Discounting819

23.4 Linear Programming Solution822

References826

Chapter 24Case Analysis827

Case 1: Airline Fuel Allocation Using Optimum Tankering828

Case 2: Optimization of Heart Valves Production835

Case 3: Scheduling Appointments at Australian Tourist Commission Trade Events838

Case 4: Saving Federal Travel Dollars842

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

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

Case 7: Optimizing Trailer Payloads at PFG Building Glass856

Case 8: Optimization of Crosscutting and Log Allocation at Weyerhaeuser862

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

Case 10: Booking Limits in Hotel Reservations874

Case 11: Casey's Problem: Interpreting and Evaluating a New Test877

Case 12: Ordering Golfers on the Final Day of Ryder Cup Matches880

Case 13: Inventory Decisions in Dell's Supply Chain882

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

Case 15: Telephone Sales Manpower Planning at Qantas Airways888

Appendix B Statistical Tables895

Appendix C Partial Solutions to Answers Problems899

Appendix D Review of Vectors and Matrices949

D.1 Vectors949

D.1.1 Definition of a Vector949

D.1.2 Addition (Subtraction) of Vectors949

D.1.3 Multiplication of Vectors by Scalars950

D.1.4 Linearly Independent Vectors950

D.2 Matrices950

D.2.1 Definition of a Matrix950

D.2.2 Types of Matrices950

D.2.3 Matrix Arithmetic Operations951

D.2.4 Determinant of a Square Matrix952

D.2.5 Nonsingular Matrix954

D.2.6 Inverse of a Nonsingular Matrix954

D.2.7 Methods of Computing the Inverse of Matrix955

D.2.8 Matrix Manipulations Using Excel960

D.3 Quadratic Forms961

D.4Convex and Concave Functions963

Problems963

Selected References964

Appendix E Case Studies965