初级篇 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 Its 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 Deterministic 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 Basic Probability 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 Inventory Models 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