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
鄂公网安备 42010302001612号 