Chapter 1: What Is Operations Research?
1.1 Operations Research Models 1
1.2 Solving the OR Model 4
1.3 Queuing and Simulation Mode!s 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

Chapter 2: Modeling with Linear Programming
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
12.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 Excel Solver and AMPL 68
2.4.1 lP Solution with Excel Solver 69
2.4.2 LP Solution with AMPl 73

Chapter 3: The Simplex Method and Sensitivity Analysis
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

Chapter 4: Duality and Post-Optimal Analysis
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 Method 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

Chapter 5: Transportation Model and Its Variants
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

Chapter 6: Network Models
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 (PM 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 Calculations 293

Chapter 7: Advanced Linear Programming
7.1 Simplex Method Fundamentals 298
7.1.1 From Extreme Points to Basic Solutions 300
7.1.2 Generalized Simplex Tableau in Matrix Form 303
7.2 Revised Simplex Method 306
7.2.1 Development of the Optimality and Feasibility Conditions 307
7.2.2 Revised Simplex Algorithm 309
7.3 Bounded-Variables Algorithm 315
7.4 Duality 321
7.4.1 Matrix Definition of the Dual Problem 322
1.4.2 Optimal Dual Solution 322
7.5 Parametric Linear Programming 326
7.5.1 Parametric Changes in ( 327
7.5.2 Parametric Changes in b 330

Chapter 8: Goal Programming
8.1 A Goal Programming Formulation 334
8.2 Goal Programming Algorithms 338
8.2.1 The Weights Method 338
8.2.2 The Preemptive Method 341

Chapter 9: Integer Linear Programming
9.1 Illustrative Applications 350
9.1.1 Capital Budgeting 350
9.1.2 Set-Covering Problem 354
9.1.3 Fixed-Charge Problem 360
9.1.4 Either-Or and If-Then Constraints 364
9.2 Integer Programming Algorithms 369
9.2.1 Branch-and-Bound (B&B) Algorithm 370
9.2.2 Cutting-Plane Algorithm 379
9.2.3 Computational Considerations in IlP 384
9.3 Traveling Salesperson Problem (TSP) 385
9.3.1 Heuristic Algorithms 389
9.3.2 B&B Solution Algorithm 392
9.3.3 Cutting-Plane Algorithm 395

Chapter 10: Deterministic Dynamic Programming
10.1 Recursive Nature of Computations in DP 400
10.2 Forward and Backward Recursion 403
10.3 Selected DP Applications 405
10.3.1 KnapsackJFly-Away/Cargo-loading Model 405
10.3.2 Work-Force Size Model 413
10.3.3 Equipment Replacement Model 416
10.3.4 Investment Model 420
10.3.5 Inventory Models 423
10.4 Problem of Dimensionality 424

Chapter 11: Deterministic Inventory Models
11.1 General Inventory Model 427
11.2 Role of Demand in the Development of Inventory Models 428
11.3 Static Ecol1omic-Order-Quantity (EOQ) Models 430
11.3.1 Classic EOQ model 430
11.3.2 EOQ with Price Breaks 436
11.3.3 Multi-Item EOQ with Storage Limitation 440
11.4 Dynamic EOQ Models 443
11.4.1 No-Setup Model 445
11.4.2 Setup Model 449

Chapter 12: Review of Basic: Probability
12.1 laws of Probability 463
12.1.1 Addition Law of Probability 464
12.1.2 Conditional Law of Probability 465
12.2 Random Variables and Probability Distributions 467
12.3 Expectation of a Random Variable 469
12.3.1 Mean and Variance (Standard Deviation) of a Random Variable 470
12.3.2 Mean and Variance of Joint Random Variables 472
12.4 Four Common Probability Distributions 475
12.4.1 Binomial Distribution 475
12.4.2 Poisson Distribution 476
12.4.3 Negative Exponential Distribution 477
12.4.4 Normal Distribution 478
12.5 Empirical Distributions 481

Chapter 13 Decision Analysis and Games
13.1 Decision Making under Certainty-Analytic Hierarchy Process (AHP) 490
13.2 Decision Making under Risk 500
13.2.1 Decision Tree-Based Expected Value Criterion 500
13.2.2 Variations of the Expected Value Criterion 506
13.3 Decision under Uncertainty 515
13.4 Game Theory 520
13.4.1 Optimal Solution of Two-Person Zero-Sum Games 521
13.4.2 Solution of Mixed Strategy Games 524

Chapter 14 Probabilistic: Inventory Models
14.1 Continuous Review Models 532
14.1.1 "Probabilitized" EOQ Model 532
14.1.2 Probabilistic EOQ Model 534
14.2 Single-Period Models 539
14.2.1 No-Setup Model (Newsvendor Model) 539
14.2.2 Setup Model (5-5 Policy) 543
14.3 Multiperiod Model 545

Chapter 15 Queuing Systems
15.1 Why Study Queues? 550
15.2 Elements of a Queuing Model 551
15.3 Role of Exponential Distribution 553
15.4 Pure Birth and Death Models (Relationship Between the Exponential and Poisson Distributions) 556
15.4.1 Pure Birth Model 556
15.4.2 Pure Death Model 560
15.5 Generalized Poisson Queuing Model 563
15.6 Specialized Poisson Queues 568
15.6.1 Steady-State Measures of Performance 569
15.6.2 Single-Server Models 573
15.6.3 Multiple-Server Models 582
15.6.4 Machine Servicing Model-{MIMIR): (GDIKIK). R> K 592
15.7 (M/G/1 ):(GDI 00 100)-Pollaczek-Khintchine (P-K) Formula 595
15.8 Other Queuing Models 597
15.9 Queuing Decision Models 597
15.9.1 Cost Models 598
15.9.2 Aspiration Level Model 602

Chapter 16 Simulation Modeling
16.1 Monte Carlo Simulation 605
16.2 Types of Simulation 610
16.3 Elements of Discrete-Event Simulation 611
16.3.1 Generic Definition of Events 611
16.3.2 Sampling from Probability Distributions 613
16.4 Generation of Random Numbers 622
16.5 Mechanics of Discrete Simulation 624
16.5.1 Manual Simulation of a Single-Server Model 624
16.5.2 Spreadsheet-Based Simulation of the Single-Server Model 630
16.6 Methods for Gathering Statistical Observations 633
16.6.1 Subinterval Method 634
16.6.2 Replication Method 635
16.6.3 Regenerative (Cycle) Method 636
16.7 Simulation Languages 638

Chapter 17: Markov Chains
17.1 Definition of a Markov Chain 641
17.2 Absolute and n-Step Transition Probabilities 644
17.3 Classification of the States in a Markov Chain 646
17.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains 649
17.5 First Passage Time 654
17.6 Analysis of Absorbing States 658

Chapter 18: Classical Optimization Theory.
18.1 Unconstrained Problems 665
18.1.1 Necessary and Sufficient Conditions 676
18.1.2 The Newton-Raphson Method 670
18.2 Constrained Problems 672
18.2.1 Equality Constraints 673
18.2.2 Inequality Constraints-Karush-Kuhn-Tucker (KKT) Conditions 685

Chapter 19: Nonlinear Programming Algorithms
19.1 Unconstrained Algorithms 691
19.1.1 Direct Search Method 691
19.1.2 Gradient Method 695
19.2 Constrained Algorithms 699
19.2.1 Separable Programming 699
19.2.2 Quadratic Programming 708
19.2.3 Chance-Constrained Programming 713
19.2.4 linear Combinations Method 718
19.2.5 SUMT Algorithm 721

Appendix A: AMPL Modeling Language
A.1 A Rudimentary AMPl Model 723
A.2 Components of AMPl Model 724
A.3 Mathematical Expressions and Computed Parameters 732
A.4 Subsets and Indexed Sets 735
A.S Accessing External Files 737
A.S.1 Simple Read Files 737
A.5.2 Using Print and Printf to Retrieve Output 739
A.S.3 Input Table Files 739
A.5.4 Output Table Files 742
A.5.S Spreadsheet Input/Output Tables 744
A.6 Interactive Commands 744
A.7 Iterative and Conditional Execution of AMPl Commands 746
A.8 Sensitivity Analysis Using AMPL 748

Appendix B: Statistical Tables
Appendix C: Partial Solutions to Selected Problems