OPERATIONS RESEARCH AN INTRODUCTIONPDF电子书下载

初级篇 1

Chapter 1 What Is Operations Research? 1

1.1 Operations Research Models 1

1.2 Solving the OR Model 4

1.3 Queuing and Simulation Models 5

1.4 Art of Modeling 5

1.5 More Than Just Mathematics 7

1.6 Phases of an OR Study 8

1.7 About This Book 10

References 10

Chapter 2 Modeling with Linear Programming 11

2.1 Two-Variable LP Model 12

2.2 Graphical LP Solution 15

2.2.1 Solution of a Maximization Model 16

2.2.2 Solution of a Minimization Model 23

2.3 Selected LP Applications 27

2.3.1 Urban Planning 27

2.3.2 Currency Arbitrage 32

2.3.3 Investment 37

2.3.4 Production Planning and Inventory Control 42

2.3.5 Blending and Refining 51

2.3.6 Manpower Planning 57

2.3.7 Additional Applications 60

2.4 Computer Solution with Solver and AMPL 68

2.4.1 LP Solution with Excel Solver 69

2.4.2 LP Solution with AMPL 73

References 80

Chapter 3 The Simplex Method and Sensitivity Analysis 81

3.1 LP Model in Equation Form 82

3.1.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side 82

3.1.2 Dealing with Unrestricted Variables 84

3.2 Transition from Graphical to Algebraic Solution 85

3.3 The Simplex Method 90

3.3.1 Iterative Nature of the Simplex Method 90

3.3.2 Computational Details of the Simplex Algorithm 93

3.3.3 Summary of the Simplex Method 99

3.4 Artificial Starting Solution 103

3.4.1 M-Method 104

3.4.2 Two-Phase Method 108

3.5 Special Cases in the Simplex Method 113

3.5.1 Degeneracy 113

3.5.2 Alternative Optima 116

3.5.3 Unbounded Solution 119

3.5.4 Infeasible Solution 121

3.6 Sensitivity Analysis 123

3.6.1 Graphical Sensitivity Analysis 123

3.6.2 Algebraic Sensitivity Analysis—Changes in the Right-Hand Side 129

3.6.3 Algebraic Sensitivity Analysis—Objective Function 139

3.6.4 Sensitivity Analysis with TORA, Solver, and AMPL 146

References 150

Chapter 4 Duality and Post-Optimal Analysis 151

4.1 Definition of the Dual Problem 151

4.2 Primal-Dual Relationships 156

4.2.1 Review of Simple Matrix Operations 156

4.2.2 Simplex Tableau Layout 158

4.2.3 Optimal Dual Solution 159

4.2.4 Simplex Tableau Computations 165

4.3 Economic Interpretation of Duality 169

4.3.1 Economic Interpretation of Dual Variables 170

4.3.2 Economic Interpretation of Dual Constraints 172

4.4 Additional Simplex Algorithms 174

4.4.1 Dual Simplex Algorithm 174

4.4.2 Generalized Simplex Algorithm 180

4.5 Post-Optimal Analysis 181

4.5.1 Changes Affecting Feasibility 182

4.5.2 Changes Affecting Optimality 187

References 191

Chapter 5 Transportation Model and Ilts Variants 193

5.1 Definition of the Transportation Model 194

5.2 Nontraditional Transportation Models 201

5.3 The Transportation Algorithm 206

5.3.1 Determination of the Starting Solution 207

5.3.2 Iterative Computations of the Transportation Algorithm 211

5.3.3 Simplex Method Explanation of the Method of Multipliers 220

5.4 The Assignment Model 221

5.4.1 The Hungarian Method 222

5.4.2 Simplex Explanation of the Hungarian Method 228

5.5 The Transshipment Model 229

References 234

Chapter 6 Network Models 235

6.1 Scope and Definition of Network Models 236

6.2 Minimal Spanning Tree Algorithm 239

6.3 Shortest-Route Problem 243

6.3.1 Examples of the Shortest-Route Applications 243

6.3.2 Shortest-Route Algorithms 248

6.3.3 Linear Programming Formulation of the Shortest-Route Problem 257

6.4 Maximal flow model 263

6.4.1 Enumeration of Cuts 263

6.4.2 Maximal Flow Algorithm 264

6.4.3 Linear Programming Formulation of Maximal Flow Mode 273

6.5 CPM and PERT 275

6.5.1 Network Representation 277

6.5.2 Critical Path (CPM) Computations 282

6.5.3 Construction of the Time Schedule 285

6.5.4 Linear Programming Formulation of CPM 292

6.5.5 PERT Networks 293

References 296

Chapter 7 Goal Programming 297

7.1 A Goal Programming Formulation 298

7.2 Goal Programming Algorithms 302

7.2.1 The Weights Method 302

7.2.2 The Preemptive Method 305

References 312

Chapter 8 Integer Linear Programming 313

8.1 Illustrative Applications 314

8.1.1 Capital Budgeting 314

8.1.2 Set-Covering Problem 318

8.1.3 Fixed-Charge Problem 324

8.1.4 Either-Or and If-Then Constraints 328

8.2 Integer Programming Algorithms 333

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

8.2.2 Cutting-Plane Algorithm 343

8.2.3 Computational Considerations in ILP 348

8.3 Traveling Salesperson (TSP) Problem 349

8.3.1 Heuristic Algorithms 353

8.3.2 B&B Solution Algorithm 356

8.3.3 Cutting-Plane Algorithm 359

References 361

Chapter 9 Deterministic Dynamic Programming 363

9.1 Recursive Nature of Computations in DP 364

9.2 Forward and Backward Recursion 367

9.3 Selected DP Applications 369

9.3.1 Knapsack/Fly-Away/Cargo-Loading Model 369

9.3.2 Work-Force Size Model 377

9.3.3 Equipment Replacement Model 380

9.3.4 Investment Model 384

9.3.5 Inventory Models 387

9.4 Problem of Dimensionality 388

References 390

Chapter 10 Determiniistic Inventory Models 391

10.1 General Inventory Model 391

10.2 Role of Demand in the Development of Inventory Models 392

10.3 Static Economic-Order-Quantity (EOQ) Models 394

10.3.1 Classic EOQ model 394

10.3.2 EOQ with Price Breaks 400

10.3.3 Multi-Item EOQ with Storage Limitation 404

10.4 Dynamic EOQ Models 407

10.4.1 No-Setup Model 409

10.4.2 Setup Model 413

References 425

Chapter 11 Decision Analysis and Games 427

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

11.2 Decision Making under Risk 438

11.2.1 Decision Tree-Based Expected Value Criterion 438

11.2.2 Variations of the Expected Value Criterion 444

11.3 Decision under Uncertainty 453

11.4 Game Theory 458

11.4.1 Optimal Solution of Two-Person Zero-Sum Games 459

11.4.2 Solution of Mixed Strategy Games 462

References 468

Chapter 12 Queuing Systems 469

12.1 Why Study Queues? 470

12.2 Elements of a Queuing Model 471

12.3 Role of Exponential Distribution 473

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

12.4.1 Pure Birth Model 476

12.4.2 Pure Death Model 480

12.5 Generalized Poisson Queuing Model 483

12.6 Specialized Poisson Queues 488

12.6.1 Steady-State Measures of Performance 489

12.6.2 Single-Server Models 493

12.6.3 Multiple-Server Models 502

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

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

12.8 Other Queuing Models 517

12.9 Queuing Decision Models 517

12.9.1 Cost Models 518

12.9.2 Aspiration Level Model 522

References 524

Appendix A AMPL Modeling Language 525

A.1 Rudimentary AMPL Model 525

A.2 Components of AMPL Model 526

A.3 Mathematical Expressions and Computed Parameters 534

A.4 Subsets and Indexed Sets 537

A.5 Accessing External Files 539

A.5.1 Simple Read Files 539

A.5.2 Using Print or Printf to Retrieve Output 541

A.5.3 Input Table Files 541

A.5.4 Output Table Files 544

A.5.5 Spreadsheet Input/Output Tables 546

A.6 Interactive Commands 546

A.7 Iterative and Conditional Execution of AMPL Commands 548

A.8 Sensitivity Analysis Using AMPL 550

Reference 550

高 级篇 551

Chapter 13 Advanced Linear Programming 551

13.1 Simplex Method Fundamentals 552

13.1.1 From Extreme Points to Basic Solutions 554

13.1.2 Generalized Simplex Tableau in Matrix Form 557

13.2 Revised Simplex Method 560

13.2.1 Development of the Optimality and Feasibility Conditions 561

13.2.2 Revised Simplex Algorithm 563

13.3 Bounded-Variables Algorithm 569

13.4 Duality 575

13.4.1 Matrix Definition of the Dual Problem 576

13.4.2 Optimal Dual Solution 576

13.5 Parametric Linear Programming 580

13.5.1 Parametric Changes in C 581

13.5.2 Parametric Changes in b 584

References 586

Chapter 14 Review of BasicProbability 587

14.1 Laws of Probability 587

14.1.1 Addition Law of Probability 588

14.1.2 Conditional Law of Probability 589

14.2 Random Variables and Probability Distributions 591

14.3 Expectation of a Random Variable 593

14.3.1 Mean and Variance (Standard Deviation) of a Random Variable 594

14.3.2 Mean and Variance of Joint Random Variables 596

14.4 Four Common Probability Distributions 599

14.4.1 Binomial Distribution 599

14.4.2 Poisson Distribution 600

14.4.3 Negative Exponential Distribution 601

14.4.4 Normal Distribution 602

14.5 Empirical Distributions 605

References 612

Chapter 15 Probabilistic InventoryModels 613

15.1 Continuous Review Models 614

15.1.1 “Probabilitized” EOQ Model 614

15.1.2 Probabilistic EOQ Model 616

15.2 Single-Period Models 621

15.2.1 No-Setup Model (Newsvendor Model) 621

15.2.2 Setup Model (s-S Policy) 625

15.3 Multiperiod Model 627

References 630

Chapter 16 Simulation Modeling 631

16.1 Monte Carlo Simulation 631

16.2 Types of Simulation 636

16.3 Elements of Discrete-Event Simulation 637

16.3.1 Generic Definition of Events 637

16.3.2 Sampling from Probability Distributions 639

16.4 Generation of Random Numbers 648

16.5 Mechanics of Discrete Simulation 650

16.5.1 Manual Simulation of a Single-Server Model 650

16.5.2 Spreadsheet-Based Simulation of the Single-Server Model 656

16.6 Methods for Gathering Statistical Observations 659

16.6.1 Subinterval Method 660

16.6.2 Replication Method 661

16.6.3 Regenerative (Cycle) Method 662

16.7 Simulation Languages 664

References 666

Chapter 17 Markov Chains 667

17.1 Definition of a Markov Chain 667

17.2 Absolute and n-Step Transition Probabilities 670

17.3 Classification of the States in a Markov Chain 672

17.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains 675

17.5 First Passage Time 680

17.6 Analysis of Absorbing States 684

References 689

Chapter 18 Classical Optimization Theory 691

18.1 Unconstrained Problems 691

18.1.1 Necessary and Sufficient Conditions 692

18.1.2 The Newton-Raphson Method 696

18.2 Constrained Problems 698

18.2.1 Equality Constraints 699

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

References 716

Chapter 19 Nonlinear Programming Algorithms 717

19.1 Unconstrained Algorithms 717

19.1.1 Direct Search Method 717

19.1.2 Gradient Method 721

19.2 Constrained Algorithms 725

19.2.1 Separable Programming 725

19.2.2 Quadratic Programming 734

19.2.3 Chance-Constrained Programming 739

19.2.4 Linear Combinations Method 744

19.2.5 SUMT Algorithm 747

References 748

Chapter 20 Additional Network and LP Algorithms 749

20.1 Minimum-Cost Capacitated Flow Problem 749

20.1.1 Network Representation 750

20.1.2 Linear Programming Formulation 752

20.1.3 Capacitated Network Simplex Algorithm 757

20.2 Decomposition Algorithm 764

20.3 Karmarkar Interior-Point Method 773

20.3.1 Basic Idea of the Interior-Point Algorithm 773

20.3.2 Interior-Point Algorithm 775

References 784

Chapter 21 Forecasting Models 785

21.1 Moving Average Technique 785

21.2 Exponential Smoothing 789

21.3 Regression 790

References 794

Chapter 22 Probabilistic Dynamic Programming 795

22.1 A Game of Chance 795

22.2 Investment Problem 798

22.3 Maximization of the Event of Achieving a Goal 802

References 805

Chapter 23 Markovian Decision Process 807

23.1 Scope of the Markovian Decision Problem 807

23.2 Finite-Stage Dynamic Programming Model 809

23.3 Infinite-Stage Model 813

23.3.1 Exhaustive Enumeration Method 813

23.3.2 Policy Iteration Method Without Discounting 816

23.3.3 Policy Iteration Method with Discounting 819

23.4 Linear Programming Solution 822

References 826

Chapter 24 Case Analysis 827

Case 1: Airline Fuel Allocation Using Optimum Tankering 828

Case 2: Optimization of Heart Valves Production 835

Case 3: Scheduling Appointments at Australian Tourist Commission Trade Events 838

Case 4: Saving Federal Travel Dollars 842

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

Case 6: Allocation of Operating Room Time in Mount Sinai Hospital 852

Case 7: Optimizing Trailer Payloads at PFG Building Glass 856

Case 8: Optimization of Crosscutting and Log Allocation at Weyerhaeuser 862

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

Case 10: Booking Limits in Hotel Reservations 874

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

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

Case 13: Inventory Decisions in Dell's Supply Chain 882

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

Case 15: Telephone Sales Manpower Planning at Qantas Airways 888

Appendix B Statistical Tables 895

Appendix C Partial Solutions to Answers Problems 899

Appendix D Review of Vectors and Matrices 949

D.1 Vectors 949

D.1.1 Definition of a Vector 949

D.1.2 Addition (Subtraction) of Vectors 949

D.1.3 Multiplication of Vectors by Scalars 950

D.1.4 Linearly Independent Vectors 950

D.2 Matrices 950

D.2.1 Definition of a Matrix 950

D.2.2 Types of Matrices 950

D.2.3 Matrix Arithmetic Operations 951

D.2.4 Determinant of a Square Matrix 952

D.2.5 Nonsingular Matrix 954

D.2.6 Inverse of a Nonsingular Matrix 954

D.2.7 Methods of Computing the Inverse of Matrix 955

D.2.8 Matrix Manipulations Using Excel 960

D.3 Quadratic Forms 961

D.4 Convex and Concave Functions 963

Problems 963

Selected References 964

Appendix E Case Studies 965