Operations Research: A Model-Based Approach, Third Edition
By H A Eiselt and Carl-Louis Sandblom
Contents:
1 Introduction to Operations Research . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 The Nature and History of Operations Research . . . . . . . . . . . 1
1.2 The Main Elements of Operations Research . . . . . . . . . . . . . . 4
1.3 The Modeling Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1 Introduction to Linear Programming . . . . . . . . . . . . . . . . . . . . 15
2.2 Applications of Linear Programming . . . . . . . . . . . . . . . . . . . 20
2.2.1 Production Planning . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Diet Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Allocation Problems . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.4 Blending Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.5 Transportation and Assignment Problems . . . . . . . . . . 38
2.2.6 Dynamic Production-Inventory Models . . . . . . . . . . . 45
2.2.7 Employee Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.8 Cutting Stock Problems . . . . . . . . . . . . . . . . . . . . . . 52
2.3 Graphical Representation and Solution . . . . . . . . . . . . . . . . . . 70
2.3.1 The Graphical Solution Method . . . . . . . . . . . . . . . . . 71
2.3.2 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.4 Postoptimality Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.4.1 Graphical Sensitivity Analyses . . . . . . . . . . . . . . . . . 90
2.4.2 Optimal Solution and Sensitivity Analyses on a Printout . . . . . . . . . . . . . . . . . . . . . . 101
2.5 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3 Multiobjective Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.1 Vector Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.2 Solution Approaches to Vector Optimization Problems . . . . . . 131
3.3 Goal Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4 Nonlinear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.2 Applications of Nonlinear Programming . . . . . . . . . . . . . . . . . 146
4.2.1 Forestry Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.2.2 Maximizing Tax Revenues . . . . . . . . . . . . . . . . . . . . 147
4.2.3 Optimizing Inventory and Queuing Models . . . . . . . . 148
4.3 Properties of Nonlinear Programming Problems . . . . . . . . . . . 149
4.4 Solution Methods for Nonlinear Optimization . . . . . . . . . . . . . 152
4.4.1 Newton’s Method for Unconstrained Optimization . . . 153
4.4.2 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . 154
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5 Integer Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.1 Definitions and Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . 162
5.2 Applications of Integer Programming . . . . . . . . . . . . . . . . . . . 170
5.2.1 Diet Problems Revisited . . . . . . . . . . . . . . . . . . . . . . 172
5.2.2 Land Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.2.3 Modeling Fixed Charges . . . . . . . . . . . . . . . . . . . . . . 175
5.2.4 Workload Balancing . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.2.5 Political Districting . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.3 Solution Methods for Integer Programming Problems . . . . . . . 183
5.3.1 Cutting Plane Methods . . . . . . . . . . . . . . . . . . . . . . . 183
5.3.2 Branch-and-Bound Methods . . . . . . . . . . . . . . . . . . . 188
5.3.3 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6 Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
6.1 Definitions and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 215
6.2 Social Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
6.3 Network Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.4 Shortest Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
6.5 Spanning Tree Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.6 Routing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
6.6.1 Arc Routing Problems . . . . . . . . . . . . . . . . . . . . . . . 241
6.6.2 Node Routing Problems . . . . . . . . . . . . . . . . . . . . . . 249
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
7 Location Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
7.1 The Major Elements of Location Problems . . . . . . . . . . . . . . . 267
7.2 Covering Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
7.2.1 The Location Set Covering Problem . . . . . . . . . . . . . 271
7.2.2 The Maximal Covering Location Problem . . . . . . . . . 274
7.3 Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
7.3.1 1-Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 278
7.3.2 p-Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 280
7.4 Median Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.4.1 Minisum Problems in the Plane . . . . . . . . . . . . . . . . . 281
7.4.2 Minisum Problems in Networks . . . . . . . . . . . . . . . . 285
7.5 Other Location Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
8 Project Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
8.1 The Critical Path Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
8.2 Project Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
8.3 Project Planning with Resources . . . . . . . . . . . . . . . . . . . . . . 317
8.4 The PERT Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
9 Machine Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
9.1 Basic Concepts of Machine Scheduling . . . . . . . . . . . . . . . . . 334
9.2 Single-Machine Scheduling Models . . . . . . . . . . . . . . . . . . . . 336
9.3 Parallel Machine Scheduling Models . . . . . . . . . . . . . . . . . . . 340
9.4 Dedicated Machine Scheduling Models . . . . . . . . . . . . . . . . . 345
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
10 Decision Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.1 Introduction to Decision Analysis . . . . . . . . . . . . . . . . . . . . . . 353
10.2 Visualizations of Decision Problems . . . . . . . . . . . . . . . . . . . . 355
10.3 Decision Rules Under Uncertainty and Risk . . . . . . . . . . . . . . 357
10.4 Sensitivity Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
10.5 Decision Trees and the Value of Information . . . . . . . . . . . . . 366
10.6 Utility Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
11 Multiattribute Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . 385
11.1 The General Model and a Generic Solution Method . . . . . . . . 385
11.2 TOPSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
11.3 The Analytic Hierarchy Process . . . . . . . . . . . . . . . . . . . . . . . 391
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
12 Inventory Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
12.1 Basic Concepts in Inventory Planning . . . . . . . . . . . . . . . . . . 401
12.2 The Economic Order Quantity (EOQ) Model . . . . . . . . . . . . . 404
12.3 The Economic Order Quantity with Positive Lead Time . . . . . 407
12.4 The Economic Order Quantity with Backorders . . . . . . . . . . . 410
12.5 The Economic Order Quantity with Quantity Discounts . . . . . . 412
12.6 The Production Lot Size Model . . . . . . . . . . . . . . . . . . . . . . . 414
12.7 The Economic Order Quantity with Stochastic Lead Time
Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
12.7.1 A Model that Optimizes the Reorder Point . . . . . . . . . 418
12.7.2 A Stochastic Model with Simultaneous
Computation of Order Quantity and Reorder Point . . . 419
12.8 Extensions of the Basic Inventory Models . . . . . . . . . . . . . . . 420
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
13 Stochastic Processes and Markov Chains . . . . . . . . . . . . . . . . . . . 425
13.1 Basic Ideas and Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
13.2 Steady-State Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
13.3 Decision Making with Markov Chains . . . . . . . . . . . . . . . . . . 431
14 Reliability Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
14.1 Fundamentals of Reliability Systems . . . . . . . . . . . . . . . . . . . 440
14.2 Time Aspects of Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . 445
14.3 Failure Rates and the Hazard Function . . . . . . . . . . . . . . . . . . 447
14.4 Redundancy and Standby Systems . . . . . . . . . . . . . . . . . . . . . 450
14.5 Estimating Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
15 Waiting Line Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
15.1 Basic Queuing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
15.2 Optimization in Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
16 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
16.1 Introduction to Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
16.2 Random Numbers and Their Generation . . . . . . . . . . . . . . . . . 475
16.3 Examples of Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
16.3.1 Simulation of a Waiting Line System . . . . . . . . . . . . . 480
16.3.2 Simulation of an Inventory System . . . . . . . . . . . . . . 483
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
17 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Appendix A: Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Appendix B: Systems of Simultaneous Linear Equations . . . . . . . . . . 506
Appendix C: Probability and Statistics . . . . . . . . . . . . . . . . . . . . . . . 509
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517