![]()
CHAPTER 1
INTRODUCTION TO OPERATIONS RESEARCH
1.1 WHAT IS DETERMINISTIC OPERATIONS RESEARCH?
Today, many âoperationsâ problems are routinely solved throughout business and industry. These include determining work shifts for large departments, designing production facilities to maximize the throughput, allocating scarce resources (such as raw materials and labor) to meet demands at a minimum cost, or determining which investments to place available funds. Such problems are very different from the traditional problems that students of mathematics, science, and engineering often face, because there are no physical laws that can be used; for example, knowing how to use Newtonâs second law or Ohmâs law will not help solve these industrial problems. To handle such problems, different mathematical models must be used.
Mathematical Model A mathematical model is a collection of variables and the relationships needed to describe important features of a given problem.
Until World War II, most businesses and industries did not worry about such operations problems. This was partly because no formal mathematical discipline directly handled these problems, and partly because there was no urgent need for them. During World War II, military planners began working with scientists and mathematicians in order to apply a scientific approach to the management of the war effort, in which they began to devise mathematical models to deal with such issues. After the war, others began to look at these techniques for industry, which brought about the beginning of Operations Research.
Operations Research Operations research (OR) is the study of how to form mathematical models of complex science, engineering, industrial, and management problems and how to analyze them using mathematical techniques.
Operations research is the name most often used to describe the mathematical study of such problems. In business, it is also known as Management Science or Operations Management. Typically, OR is divided into two areas: deterministic operations research, where all parameters are fixed, and stochastic operations research, where we assume some of the problem parameters are random. This book deals exclusively with deterministic operations research.
There have been many successful and interesting applications of operations research techniques since the 1940s. In fact, operations research has been used to solve many diverse problems.
1. Scheduling ACC Basketball. Nemhauser and Trick [67] discussed how they used OR techniques to determine successful schedules for the Atlantic Coast Conference basketball season, which consists of a round-robin schedule among 10 teams stretching from Maryland to Florida.
2. Designing Communication Networks. Balakrishnan, Magnanti, and Mirchandani [4] look at the problem of designing survivable networks with high bandwidth in order to minimize costs. These problems have great importance due to the explosion of phone, cable, and video services.
3. Scheduled Aircraft Maintenance. Gopalan and Talluri [51] studied how to schedule aircraft maintenance when there are many operating restrictions in place, such as making sure the aircraft is at the correct maintenance location within a certain amount of time.
4. Truck Dispatching for Oil Pickup. Bixby and Lee [16] look at the vehicle routing and scheduling problem that arise from an oil companyâs desire to better utilize truck fleets and drivers.
5. Component Assignment in Printed Circuit Board Manufacturing. Hillier and Brandeau [58] consider the problem of determining the minimum cost assignment of various components to insertion machines that are used in the automated assembly of printed circuit boards.
OR is much more than the formation of mathematical models of problems; it also deals with the solution of these models and the evaluation of their solutions with regard to the real-world problem. In deterministic OR models, we typically formulate the problem as an optimization problem, where we want to minimize or maximize a function (such as costs, profits, time, etc.) given that the solution must satisfy certain restrictions and requirements (demand met, scarce resources, etc.). Such optimization problems are often referred to as Mathematical Programs.
Mathematical Program A mathematical program or Optimization Model is a mathematical structure where problem choices are represented by decision variables. Using these decision variables, mathematical programs look to optimize some objective function of the decision variables subject to certain constraints that limit the possible choices (values of decision variables). It can be written in the most general form (assuming maximization problem)
where x is a vector of decision variables, f (x) is the objective function, and the set S is the set of values for the decision variables satisfying all of the constraints.
The three highlighted terms in the above definition, decision variables, objective function, and constraints, represent the fundamental concerns of any OR model. In fact, it is the objective function that makes a model an optimization model. This was fairly revolutionary in 1947, when George Dantzig used an objective function to determine which decisions were better than others. Before that, there was not much thought given in modeling toward objective functions; instead, basic ground rules given by those in authority were used to guide the search for the âbest answer.â1
But how do we create a mathematical model? That is the real question in any study of operations research. The whole modeling process involves a four-stage cycle:
1. Problem Definition and Data Gathering. Here is where the real work begins. Actually knowing what problem we wish to model is more important than most people realize. If we have no idea what we want to determine, how do we know if we have a reasonable solution or not? Next, a modeler must observe the system and collect data to estimate any parameters of the model.
2. Creating the Mathematical Model. Once the problem is defined and data have been collected, it is now time to develop a model of the situation. This involves determining decision variables, constraints, and objectives that are needed in the problem. Sometimes it involves only determining which formula we need to use. Models can be either deterministic, as studied in this book, or stochastic, in which case our data are more important because we need them to verify assumptions on probability distributions, means, and so on.
3. Solving the Mathematical Model. This can have many different forms. If we have a deterministic optimization model, we try to find the values of the decision variables that give the best objective function value. Sometimes, however, this is not tractable. For example, in the infamous traveling salesperson problem, a person has to travel to many different locations and wants to determine the shortest route to visit them all before returning home. For many instances, this problem cannot be solved to optimality. In that case, when a problem is that difficult or intractable, operations researchers often try to develop heuristics that find a reasonable solution in a short amount of time. For stochastic problems, a âsolutionâ is not always easy to find. In many instances, simulation is used to approximate a good solution. Here, we simulate the system many times by generating random numbers for each random variable and determine from these simulations which alternative is best.
4. Using the Mathematical Model to Make Real-World Predictions. Once we have a solution to a mathematical model, we must use that answer to solve the real-world problem. While it is often the case that the values of our decision variables are what we will use, that is not always the case. For example, if we solve a mathematical program and get fractional values, and we wanted an integral solution, we may want to âfudgeâ the values a little, perhaps by rounding up or down, to get integers. However, this is not always a good idea, because we may end up with a solution that does not satisfy all the constraints.
Once weâve gone through these four steps, we are done, right? Not quite. Often the model gives answers that we know cannot work in the real problem, which means the model is not quite right. In this case, we may have to start all over again. Mathematical modeling is a very cyclical process, as illustrated in Figure 1.1.
Even when the model seems correct, we are often interested in scenarios where our parameters change. These âWhat Ifâ scenarios are important, because often our data do not generate the absolutely correct parameters. Therefore, we want to know what small changes to our parameters do to our solutions.
Sensitivity Analysis Sensitivity analysis is the determination of the effect of small changes of parameter values on the solutions to a mathematical model.
FIGURE 1.1 Cyclical nature of mathematical modeling.
Sometimes this is very easy to do, and sometimes it is not. For one important model weâll study, sensitivity analysis is both straightforward and informative.
In this book we deal with three important parts of operations research: finding a mathematical model, solving it, and analyzing the results obtained and the solution technique itself. To do this, we first spend time on obtaining models, including some common models found in OR applications. This includes doing sensitivity analysis on certain models and ...
