Since the 1960s, operations research (or, alternatively, management science) has
become an indispensable tool in scientific management. In simple words, its goal on
the strategic and tactical levels is to aid in decision making and, on the operational
level, automate decision making. Its tools are algorithms, procedures that create and
improve solutions to a point at which optimal or, at least, satisfactory solutions have
been found.
Whilemany texts on the subject emphasizemethods, the focus of this book is on the
applications of operations research in practice. Typically, a topic is introduced by
means of a description of its applications, a model is formulated, and its solution is
presented. Then the solution is discussed and its implications for decision making are
outlined. We have attempted to maximize the understanding of the topics by using
intuitive reasoning while keeping mathematical notation and the description of
techniques to a minimum. The exercises are designed to fully explore the material
covered in the chapters, without resorting to mind-numbing repetitions and
trivialization.
The book is designed for (typically second year) students of business manage-
ment and industrial engineering.With the appropriate deletions, the material can be
used for a one-semester course in the subject, while the complete material will be
sufficient for a full-year course. The reasoning and explanations are intuitive
throughout. Each algorithm is followed by a numerical example that shows in detail how the method progresses. After presenting the applications and the
techniques, each chapter ends with a number of fully solved examples that review
the concepts covered in the chapter. Some more technical material has been taken
out and is available at http://esor.ie.dal.ca/. The second edition adds new material
on multicriteria optimization, postman problems, Lagrangian relaxation, cutting
planes, machine scheduling, and Markov chains.
It is our pleasure to thank all the people who have made this volume possible.
Special thanks are due to Mr. Rauscher of Springer-Verlag for his encouragement
and support in our writing of the second edition of this book, as well as Sina Raeisi for his help with the production of the figures, and the Buddha Man for his
meticulous typing. Without the help of all of these individuals, this book would
not have seen the light of day. We like to thank all of them.
H.A. Eiselt
C.-L. 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 ................ 3
1.3 The Modeling Process . . . ............................. 9
2 Linear Programming .................................... 13
2.1 Introduction to Linear Programming . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Applications of Linear Programming . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Production Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Diet Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Allocation Problems ............................ 26
2.2.4 Employee Scheduling ........................... 30
2.2.5 Dynamic Production – Inventory Models ............. 33
2.2.6 Blending Problems ............................. 37
2.2.7 Transportation and Assignment Problems . . . ......... 40
2.3 Graphical Representation and Solution .................... 57
2.3.1 The Graphical Solution Method .................... 57
2.3.2 Special Cases . ................................ 66
2.4 Postoptimality Analyses ............................... 73
2.4.1 Graphical Sensitivity Analyses . . . . . . . . . . . . . . . . . . . . 74
2.4.2 Economic Analysis of an Optimal Solution . . . ........ 84
2.5 Duality . .......................................... 96
3 Multiobjective Programming .............................. 105
3.1 Vector Optimization ................................. 106
3.2 Solution Approaches to Vector Optimization Problems . . . . .... 110
3.3 Goal Programming . . . ............................... 113
4 Integer Programming ................................... 123
4.1 Definitions and Basic Concepts ......................... 123
4.2 Applications of Integer Programming . . . . . . . . . . . . . . . . . . . . . 130
4.2.1 Cutting Stock Problems . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.2.2 Diet Problems Revisited . . . ...................... 136
4.2.3 Land Use .................................... 137
4.2.4 Modeling Fixed Charges . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.2.5 Workload Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.3 Solution Methods for Integer Programming Problems ......... 144
4.3.1 Cutting Plane Methods . . . ....................... 144
4.3.2 Branch-and-Bound Methods . . . . . . . . . . . . . . . . . . . . . . 149
4.3.3 Heuristic Methods . ............................ 154
5 Network Models ........................................ 175
5.1 Definitions and Conventions . . . . . . . . . . ................. 175
5.2 Network Flow Problems .............................. 177
5.3 Shortest Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.4 Spanning Tree Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.5 Routing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.5.1 Arc Routing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.5.2 Node Routing Problems . . ....................... 204
6 Location Models ....................................... 221
6.1 The Major Elements of Location Problems ................. 221
6.2 Covering Problems .................................. 224
6.2.1 The Location Set Covering Problem . . .............. 225
6.2.2 The Maximal Covering Location Problem ............ 230
6.3 Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.3.1 1-Center Problems ............................. 234
6.3.2 p-Center Problems ............................. 235
6.4 Median Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.4.1 Minisum Problems in the Plane .................... 237
6.4.2 Minisum Problems in Networks ................... 241
6.5 Other Location Problems . ............................. 245
7 Project Networks ....................................... 257
7.1 The Critical Path Method . . ............................ 258
7.2 Project Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
7.3 Project Planning with Resources ......................... 269
7.4 The PERT Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8 Machine Scheduling ..................................... 283
8.1 Basic Concepts of Machine Scheduling ................... 284
8.2 Single Machine Scheduling Models . . . . .................. 285
8.3 Parallel Machine Scheduling Models . . . . . . . . . . . . . . . . . . . . . 289
8.4 Dedicated Machine Scheduling Models . .................. 294
9 Decision Analysis ....................................... 303
9.1 Introduction to Decision Analysis . . ...................... 303
9.2 Visualizations of Decision Problems ...................... 305
9.3 Decision Rules Under Uncertainty and Risk . . . . . . . . . . . . . . . . 308
9.4 Sensitivity Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
9.5 Decision Trees and the Value of Information . . . . . . . . . . . . . . . 315
9.6 Utility Theory . . . . . . . . . . . ........................... 322
10 Multicriteria Decision Making ............................. 333
10.1 The General Model and a Generic Solution Method . . . . . . . . . 333
10.2 The Analytic Hierarchy Process . . ...................... 336
11 Inventory Models ....................................... 343
11.1 Basic Concepts in Inventory Planning . . . . . . . . . . . . . . . . . . . . 343
11.2 The Economic Order Quantity (EOQ) Model .............. 346
11.3 The Economic Order Quantity with Positive Lead Time . . . . . . 350
11.4 The Economic Order Quantity with Backorders ............. 352
11.5 The Economic Order Quantity with Quantity Discounts . . . . . . . 354
11.6 The Production Lot Size Model . . . . . . . . . . . . . . . . . . . . . . . . 357
11.7 The Economic Order Quantity with Stochastic Lead
Time Demand ..................................... 359
11.7.1 A Model That Optimizes the Reorder Point . . ....... 360
11.7.2 A Stochastic Model with Simultaneous Computation
of Order Quantity and Reorder Point . . ............ 362
11.8 Extensions of the Basic Inventory Models . . . . . . . . . . . . . . . . . 363
12 Stochastic Processes and Markov Chains ..................... 369
12.1 Basic Ideas and Concepts ............................. 369
12.2 Steady-State Solutions ............................... 374
12.3 Decision Making with Markov Chains . . . ................ 376
13 Waiting Line Models .................................... 381
13.1 Basic Queuing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
13.2 Optimization in Queuing ............................. 389
14 Simulation ............................................ 397
14.1 Introduction to Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
14.2 Random Numbers and Their Generation .................. 399
14.3 Examples of Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
14.3.1 Simulation of a Waiting Line System . . . ........... 403
14.3.2 Simulation of an Inventory System ............... 406
Appendix A: Heuristic Algorithms ............................. 417
Appendix B: Vectors and Matrices ............................. 425
Appendix C: Systems of Simultaneous Linear Equations ............ 427
Appendix D: Probability and Statistics .......................... 431
Bibliography .............................................. 439
Index .................................................... 441