Operations Research | springerprofessional.de

Springer Professional

nach oben

2022 | Buch

Kapitel lesen Erstes Kapitel lesen

Operations Research

A Model-Based Approach

verfasst von: Prof. Dr. H. A. Eiselt, Prof. Dr. Carl-Louis Sandblom

Verlag: Springer International Publishing

Buchreihe : Springer Texts in Business and Economics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This is the third edition of a textbook that has been used in a number of undergraduate courses and covers the standard models and techniques used in decision-making in organizations. The main emphasis of the book is on modelling business-related scenarios and the generation of decision alternatives. Fully solved examples from many areas are used to illustrate the main concepts without getting bogged down in technical details. The book presents an approach to operations research that is heavily based on modelling and makes extensive use of sensitivity analyses. It is the result of the authors’ many years of combined teaching experience.

The third edition includes new topics such as nonlinear programming and reliability theory, as well as additional material on multi-attribute decision-making. Each chapter includes a number of fully solved problems that allow students to practice or self-study. Additional problems are available on the book’s accompanying website.

Anzeige

Inhaltsverzeichnis

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, Carl-Louis 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, Carl-Louis 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 top 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, Carl-Louis Sandblom

4. Nonlinear Programming

Abstract

In the Introduction to Linear Programming in Sect. 2.1 in this volume, we outlined that the objective function(s) and the constraints in linear programming are assumed to be linear functions in the variables. In this chapter, we drop this assumption and only assume divisibility and the deterministic property. Given that, we can view nonlinear programming as a generalization of linear programming. Another important distinction between linear and nonlinear programming is that in nonlinear programming, constraints are not necessarily needed to ensure finite optima as is the case in linear programming. For instance, the nonlinear objective

H. A. Eiselt, Carl-Louis Sandblom

5. Integer Linear 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 example, 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, Carl-Louis Sandblom

6. Network Models

Abstract

Graph theory, the subject at the root of this chapter, dates back to 1736, when the Swiss mathematician Leonhard 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 Sect. 6.5. 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 advanced by operations researchers in the 1950s, most prominently by L.R. Ford and D.R. Fulkerson to deal with path and network flows. For a more comprehensive treatment of the topics covered in this chapter, readers are referred to the pertinent literature, e.g. Eiselt and Sandblom (2000), or Murty (2006).

H. A. Eiselt, Carl-Louis Sandblom

7. 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. For an in-depth treatment of the models described in this chapter, we refer readers to Eiselt and Sandblom (2004), Eiselt and Marianov (2011), Daskin (2013) and Laporte et al. (2019).

H. A. Eiselt, Carl-Louis Sandblom

8. 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, electricians and plumbers 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.

H. A. Eiselt, Carl-Louis Sandblom

9. 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 audit, 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, Carl-Louis Sandblom

10. 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 first introduces the main elements of decision analysis, and then offers 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, Carl-Louis Sandblom

11. Multiattribute Decision Making

Abstract

The models and methods in this chapter all consider problems, in which the consequences of a decision are no longer one-dimensional, while, in contrast to the scenario in decision analysis, the outcomes are deterministic. In other words, if we were to, say, change the composition of a soft drink we manufacture or change the features on a cell phone, we do not just deal with profit as a result of this decision, but face changing customer acceptance (and demand) for the product, different costs, changing market share, customer satisfaction, and other factors, all of which will influence short- and long-term viability of the firm. The models discussed in this chapter are similar to those in the chapter on multiobjective optimization, except that the models in this chapter are discrete: we face only a finite (and usually fairly small) number of choices.

H. A. Eiselt, Carl-Louis Sandblom

12. 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 and 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 1 day to the next.

H. A. Eiselt, Carl-Louis Sandblom

13. Stochastic Processes and Markov Chains

Abstract

Some of the previous chapters have dealt with random events in an ad hoc fashion. 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, Carl-Louis Sandblom

14. Reliability Models

Abstract

In the previous chapter on stochastic processes, we considered a system, which could be in different states in any one time period, and in which the transition from one state to another can occur randomly. Reliability theory in its simplest form includes a number of independent components, each of which is in exactly one of two states: it functions properly, or it does not. Our task is to calculate the probability that the entire system works. The system under consideration may describe a life-changing or life-saving scenario. Consider, for instance, a passenger elevator in a building. Its proper functioning may determine whether or not the passenger live to tell of their experience. On the other hand, if a hardware or software component of a personal computer crashes, it could probably result in some inconvenience to the user but would not be fatal. In reality, deadly accidents related to elevator malfunctions are quite rare: worldwide, there are about 27 elevator deaths per year. On the other hand, computer crashes are an almost everyday occurrence.

H. A. Eiselt, Carl-Louis Sandblom

15. Waiting Line Models

Abstract

Waiting line or queuing systems 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 systems 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, Carl-Louis Sandblom

16. 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),

H. A. Eiselt, Carl-Louis Sandblom

17. Heuristic Methods

Abstract

In this book, you will read about or even directly encounter a number of solution algorithms. All of these algorithms fall into two broad categories: exact algorithms (sometimes also somewhat misleadingly referred to as optimal algorithms) and heuristic methods usually simply called heuristics. Exact algorithms have the obvious advantage of providing the best possible solution there is, given the user-defined constraints, whereas heuristics do not. Some heuristics do have error bounds, some actually proven, while others are empirical, i.e., they state that a certain heuristic usually (typically on average) finds solutions that have a certain quality. On the other hand, there is computing speed. Some models are such that it takes an exact algorithm exceedingly long to find the optimal solution. Is this relevant? Well, it depends. If the task at hand is to, say, locate a landfill for millions of dollars, you will not care if it takes a laptop 2 or 3 weeks to run, so that it can find a solution that may potentially save hundreds of thousands of dollars. There are limits to this argument, of course: if it takes years or even longer to find a solution, most problems have either solved themselves or have become irrelevant by that time. So, this is not acceptable.

H. A. Eiselt, Carl-Louis Sandblom

Backmatter

Titel: Operations Research
verfasst von: Prof. Dr. H. A. Eiselt
Prof. Dr. Carl-Louis Sandblom
Copyright-Jahr: 2022
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-97162-5
Print ISBN: 978-3-030-97161-8
DOI: https://doi.org/10.1007/978-3-030-97162-5

Premium Partner

Weitere Formate
Fachgebiete
Bücher
Zeitschriften
Themenseiten
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024