Top

2010 | Book

Read chapter Read first chapter

Operations Research

A Model-Based Approach

Authors: H. A. Eiselt, Carl-Louis Sandblom

Publisher: Springer Berlin Heidelberg

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

About this book

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. While many texts on the subject emphasize methods, the special 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.

Frontmatter

1. Introduction to Operations Research

Abstract

In its first section, this introductory chapter first introduces operations research as a discipline. It defines its function and then traces its roots to its beginnings. The second section highlights some of the main elements of operations research and discusses a number of potential difficulties and pitfalls. Finally, the third section of this chapter suggests an eight-step procedure for the modeling process.

H. A. Eiselt, C. -L. Sandblom

2. Linear Programming

Abstract

This chapter will introduce linear programming, one of the most powerful tools in operations research. We first provide a short account of the history of the field, followed by a discussion of the main assumptions and some features of linear programming. Thus equipped, we then venture into some of the many applications that can be modeled with linear programming. This is followed by a discussion of the underlying graphical concepts and a discussion of the interpretation of the solution with many examples of sensitivity analyses. Each of the sections in this chapter is really a chapter in its own right. We have kept them under the umbrella of the chapter “Linear Programming” so as to emphasize that they belong together rather than being separate entities.

H. A. Eiselt, C. -L. Sandblom

3. Multiobjective Programming

Abstract

As diverse as the problems in the previous chapters have been, they share one common feature: they all have one single objective function and the result is an optimal solution (or multiple optima, in case of dual degeneracy). However, the concept of optimality applies only in case of a single objective. If we state that something is “the best” or optimal, we always have an objective in mind: the fastest car, the most comfortable vehicle, the automobile that is cheapest to operate, and so forth. Whenever a second or even more objectives are included in a problem, the concept of optimality no longer applies. For instance, if the top speed of a vehicle and its gas mileage are relevant concerns, then the comparison between a car, whose speed may go up to 110 miles per hour and which gives 20 miles to the gallon (highway rating) and a vehicle that can go up to 90 miles per hour and which gives 25 miles to the gallon is no longer a simple one: the former car is faster at the expense of fuel efficiency. It will now depend on the decision maker which of the two criteria is considered more important. In other words, the decision maker will—sooner or later—have to specify a tradeoff between the criteria. This is the type of problems considered in this chapter.

H. A. Eiselt, C. -L. Sandblom

4. Integer Programming

Abstract

Not too long after more and more applications of linear programming were developed, it became apparent that in some of these applications, the variables would not be able to attain just any (nonnegative) value, but should be integers. As a simple applications, if a variable has been defined to denote the number of cans of beans manufactured in the planning period, then surely it would make no sense to make, say, 1,305,557.3 cans: the last 0.3 cans would have to be rounded up or down. While this may be an acceptable practice when dealing with this application (after all, it makes very little difference whether or not we make 0.3 cans more or less), in other applications this may make a huge difference. For instance, assigning airplanes to routes or trucks to deliveries may very well make the difference between gain and loss. Furthermore, simply rounding up or down a noninteger (usually referred to as a continuous solution) will not necessarily result in an optimal integer solution. We will demonstrate this fact below.

H. A. Eiselt, C. -L. Sandblom

5. Network Models

Abstract

Graph theory, the subject at the root of this chapter, dates back to 1736, when the Swiss mathematician Leonard Euler considered the now famed “Königsberg bridge problem.” At that time, there were seven bridges across the River Pregel that ran through the city of Königsberg on the Baltic Sea, and Euler wondered whether or not it would be possible to start somewhere in the city, walk across each of the bridges exactly once, and return to where he came from. (It was not). We will return to Euler’s problem in Section 5.5 of this chapter. Two hundred years later in 1936, the Hungarian mathematician Denès König wrote the seminal book “The Theory of Finite and Infinite Graphs,” that laid the foundations of modern graph theory. The subject was first used by operations researchers in the 1950s, most prominently by L.R. Ford and D.R. Fulkerson.

H. A. Eiselt, C. -L. Sandblom

6. Location Models

Abstract

This chapter introduces the basic ideas of location models. We first provide a short introduction to the subject and enumerate some of its major components. This is followed by a detailed discussion of the major classes of location models.

H. A. Eiselt, C. -L. Sandblom

7. Project Networks

Abstract

Back in the days when projects were dealt with by a single individual or a group of workers working sequentially, there was no need for project networks. As an example, consider the construction of a house. Somewhat simplistically, assume that a single individual wants to build a log cabin. He will first dig a hole in the ground for the foundation, then pour the cement, then lay the logs one by one, and so forth. Each job is completely finished before the next task begins. This is a sequential plan, and there is very little that can be done as far as planning is concerned. Consider, however, some of the issues that have arisen as a result of the division of labor. Nowadays, the plumbers can work at the same time the electrician does, but not before the walls have been established, which is also required for the roof to be put up. Given these interdependencies, planning is necessary in case time is an issue. Clearly, while it is possible that, say, electrician and plumber can work in the building at the same time, it is not necessary to use this parallelism: we can still have the two contractors work one after the other, if we so wish. The project will take longer, but it is possible. Project networks were designed by a number of firms in the

H. A. Eiselt, C. -L. Sandblom

8. Machine Scheduling

Abstract

The subject of this chapter is the allocation of jobs (or tasks) to processors (or machines). These terms should be understood in the widest possible sense: in the case of a doctor treating patients the doctor is the processor and the patients represent the tasks, in the case of a tax auditor the auditor is the processor (or the “machine”), while the individual cases are the tasks to be processed. This allocation is to be made so as to optimize some objective. We will discuss a number of these objectives below.

H. A. Eiselt, C. -L. Sandblom

9. Decision Analysis

Abstract

Everywhere in the world, at each moment, millions of people make their own decentralized decisions: when to get up in the morning, what tie to wear, what to eat for lunch or dinner, what to do in the evening (go to the theater or watch television), where to vacation, and many more. Similarly, firms will decide which mode of transportation to use when routing their products to customers, where to locate regional distribution centers, what new product lines to develop, etc. This chapter will first introduce the main elements of decision analysis, and then offer some visualizations of decision analysis problem. This is followed by a discussion of some simple decision rules, sensitivity analyses, and a discussion of the value of information. The chapter wraps up the discussion by some thoughts on utility theory.

H. A. Eiselt, C. -L. Sandblom

10. Inventory Models

Abstract

Worldwide, companies hold billions of dollars in inventories. The main reason is to create a buffer that balances the differences between the inflow and outflow of goods. Inventories can be thought of as water tanks: there may be a constant inflow of water that is pumped into the tank by a pump, while the outflow is low at night, high in the morning (when people get up, take a shower, etc), it then decreases significantly until the demand again increases in the evening (when people come home, do laundry, etc), just to fall off again for the night. Other, popular, examples include grocery stores whose inventories consist of various foodstuffs awaiting sale to its customers. Here, the delivery of the goods is in bulk whenever a delivery truck arrives, while the demand is unknown and erratic. In the case of hospitals, they have in stock medical supplies, bed linen and blood plasma. Again, the demand for these items is uncertain and may differ widely from one day to the next.

H. A. Eiselt, C. -L. Sandblom

11. Stochastic Processes and Markov Chains

Abstract

Some of the previous chapter have dealt with random events. This chapter will deal with such events in a systematic way. In general, in stochastic processes, events occur over time. Time can be dealt with either in continuous fashion, or in discrete fashion. In the continuous case, we may look at the speed of an automobile at any given point in time or at the inventory level of a product in a supermarket at any time. In the discrete case, speed or inventory level are observed only during specific points in time, e.g., each minute, once a week or at similar intervals. In this chapter, we only deal with discrete-time models. The following three sections will introduce some of the basic ideas of stochastic processes and Markov chains.

H. A. Eiselt, C. -L. Sandblom

12. Waiting Line Models

Abstract

Waiting line or queuing system are pervasive. Many of us remember the long lineups in front of stores in the Soviet Union and Vietnam, and we have all experienced lineups in banks and supermarkets, but there are many more instances with waiting lines: think, for instance, about traffic lights, where drivers line up and wait, files that wait for processing in the inbox at a clerk’s workstation, or telephone calls that are put in a queue. Queuing system were first examined by Agner Krarup Erlang (1878–1929). Erlang was a Danish mathematician, who worked for the Copenhagen Telephone Company. One of the questions he faced during this time was to determine the number of telephone circuits that are required to provide an acceptable level of service.

H. A. Eiselt, C. -L. Sandblom

13. Simulation

Abstract

Simulation is one of the major devices in an operations researcher’s toolkit, and there is little doubt that it is among the most flexible and commonly used techniques. In the words of Budnick et al. (1988), “Simulation is primarily concerned with experimentally predicting the behavior of a real system for the purpose of designing the system or modifying behavior.”

H. A. Eiselt, C. -L. Sandblom

Backmatter

Title: Operations Research
Authors: H. A. Eiselt
Carl-Louis Sandblom
Publisher: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-10326-1
Print ISBN: 978-3-642-10325-4
DOI: https://doi.org/10.1007/978-3-642-10326-1

Springer Professional

About this book

Table of Contents

Frontmatter

1. Introduction to Operations Research

2. Linear Programming

3. Multiobjective Programming

4. Integer Programming

5. Network Models

6. Location Models

7. Project Networks

8. Machine Scheduling

9. Decision Analysis

10. Inventory Models

11. Stochastic Processes and Markov Chains

12. Waiting Line Models

13. Simulation

Backmatter