Operations research

The construction, elaboration and application of mathematical models for making optimal decisions. The theoretical side of operations research is concerned with the analysis and solution of mathematical problems of choosing from a given set $X$ of feasible decisions an element satisfying some criterion of optimality, called an optimal decision of the problem. Sometimes "generalized" elements of $X$ — subsets or functions with values in $X$ (including random variables with values in $X$) — are chosen. Problems of this kind are called optimization problems. The applied side of operations research is concerned with formulating optimization problems and with realizing their solutions.

Formulating a problem in operations research first of all includes the formal description of the set $X$ of feasible decisions and criteria of optimality. This must reflect an informal representation of the possible and the desired under the conditions given. On the other hand, the verification of the adequacy of the informal representation itself for the objective reality is already beyond the limits of operations research. All decisions (including optimal ones) are made only on the basis of the information that is available to the subject(s) making a decision. Therefore, every problem in operations research must reflect in its formulation the knowledge of the subject(s) making a decision about the set of feasible decisions and optimality criteria. Thus, if the decision is made within a single stage of information that does not change and that is given in advance, then the problem is called static. In this case, the complete process of decision making can be reduced to one instantaneous act. In the alternative case, if the decision is made with several different information stages, then the decision will be arrived upon by establishing correspondences between each information stage and each decision that is feasible in it, i.e. by choosing a function expressing this correspondence. If the information stages do change one another, then the problem is called dynamic. In a dynamic problem it is expedient to make decision step-by-step, "multi-step-wise" , or even to model the decision making by means of a process that is continuous in time.

The information states of a decision maker may characterize its true ( "physical" ) state in various ways. It may happen that one information state of the subject includes the set of its physical states. In this case, the decision problem is called indefinite. Such problems of operations research are considered in the theory of games (cf. Games, theory of). If an information state contains several physical states, and if the subjects also know, from their sets, the (a priori) probability of each of these physical states, the problem is called stochastic. Finally, if the information state consists of a unique physical state, then the problem is called deterministic. It is sometimes of interest to consider a family of problems, depending on a numerical or vectorial value running over some parameter set, and unifying them into a single parametric problem. A parametric problem differs from an indefinite problem in that solving the first consists of solving all problems corresponding to special values of the parameter, while solving the second problem consists of finding a feasible decision that is in a certain sense required, whatever the way in which the indefiniteness was actually realized. Meanwhile, solving a stochastic problem consists of finding an optimal decision that is optimal "on the average" over the entire set of individual problems.

Problems of operations research with an arbitrary set $X$ of feasible solutions and with arbitrary optimality criteria can be imagined theoretically. These criteria may consist of the maximization (or minimization) of the values of some numerical or vector function $f$ on $X$. This function is usually called the objective function. In the first case one speaks of a problem of mathematical programming (optimal programming, which should not be confused with programming of a computer), while in the second case one speaks of a problem of vector optimization, or of a multi-criterion problem. Criteria expressed by a binary preference relation $\prec$ on $X$ have also been considered. This relation need not be a total linear, or even a partial, order relation.

In mathematical programming one most often considers problems in which $X$ is a subset of a finite-dimensional Euclidean space $E^n$. If $X$ is, moreover, a convex polyhedron with a finite number of vertices and if the objective function $f$ is linear, one has a problem of linear programming. If $X$ is an arbitrary convex set and $f$ is a convex function, one has a problem of convex programming. Problems of piecewise-linear programming, quadratic programming, etc., can be naturally defined. The set $X$ of feasible decisions can also be a subset of a function space; hence formal variational calculus, as well as a range of problems related to the Pontryagin maximum principle, may therefore also be considered as a part of mathematical programming. In other cases $X$ may be a finite set; such problems belong to discrete programming. The feasible decisions for them may be the points of an integer lattice in $E^n$ (integer programming) or vectors each component of which takes only two values (Boolean programming). In individual cases, the elements of $X$ are permutations on a finite number of symbols, paths in a given graph, etc. A special case of a problem of mathematical programming is that of finding a maximin, i.e. the maximum of a function of one variable which is obtained by minimizing a two (or more) variable function with respect to another variable (analogously, a minimax).

The theory of solving stochastic problems of linear programming is the subject of stochastic programming. Multi-criterion problems, as well as problems with preference relations, relate to the theory of games; they are classified according to their game-theoretic properties.

One of the contemporary (since the 1970's) trends in operations research is the transition from the consideration of individual problems to the study of systems, spaces, calculi of such problems, and to the study of relations between various problems or the reduction of some problems to others that have a simpler structure. The mathematical apparatus intended for and developed with the aim of solving problems of operations research is conveniently called the mathematics of operations research. The methods in question do, in principle, not differ by their nature from the mathematical methods of any other mathematical discipline with informal applications or, at least, interpretations. The stages of elaboration of mathematical methods for various problems of operations research and their classes differ. The theories of linear and convex programming are the most well developed.

Some parametric problems of operations research, distinguished by specific informal interpretations, problems and terminology, bear the name of models of operations research. Usually, each model has an intrinsic method for solving it. The range of models of operations research is great: from specific problems, differing only by the numerical values of their parameters (examples are the assignment and the transportation problem, some more difficult cutting problems, the allocation problem, and the theory of networks), to such specified disciplines as the theory of inventory control, allotation or reliability theory. The theory of games provides a large number of models of operations research (games of timing, Blotto-type games, poker-type games, differential pursuit games, etc.). Some advanced problems in queueing theory are also considered as models of operations research, although the majority of problems in queueing theory do not as yet have an optimization character.

The solution of such problems of operations research starts with the choice of an optimality principle. If one has a problem of mathematical programming this is a trivial matter: The optimality principle consists of the maximization (respectively, minimization) of the objective function. Thus, in this case the optimality principle of the problem formally coincides with its optimality criterion. In other cases the discovery of the optimality principle is an essential stage in the solution of the problem and it can be realized in various ways. Means for reducing a vector criterion or preference relation to numerical criteria have been used. E.g., in the case of a multi-criterion problem the optimality principle may consist in giving the individual components of the vector criterion some weights and by considering the weighted sum as objective function. Another optimality principle may consist of the maximization of the minimal component of the vector criterion (the maximin principle), etc. Optimality principles in problems with a preference relation can be extremely varied (cf., e.g., Games, theory of). The possibility and ways of replacing preference relations by numerical criteria constitute one of the basic problems in utility theory. Thus, the criterion of a problem of operations research is part of its conditions, while the optimality principle is part of its answer. In the majority of models of operations research the optimality principle is fixed.

After the choice of the optimality principle, the next stage in the solution of a problem of operations research is that of proving its realizability (i.e. the existence of a solution of the problem in the sense of this principle). The non-realizability of an optimality principle in the class of feasible decisions given by the conditions of the problem can sometimes be overcome by way of introducing decisions that are generalized in some sense or other; subsets of the set of feasible decisions or functions with values in this set.

Since the existence of optimal decisions for a problem of operations research often turns out to be non-constructive (e.g. based on some fixed-point theorem), while it is sometimes constructive but provides its indication only potentially (and not practically), the third stage of evaluating a problem of operations research is that of obtaining the optimal solution.

Problems of operations research possess a number of features, brought about by the method of formulating and solving them. First, even for the simplest parameter classes of problems it is usually not possible to express the solutions as an analytic expression in the corresponding parameters. Therefore, problems of operations research can, in the majority of cases, not be solved analytically and must be solved numerically. Secondly, the majority of problems of practical interest contain in their formulation a very large amount of numerical material, not reducible to analytic expressions; thus, the numerical solution of these problems can only be accomplished on a computer. Thirdly, the process of solving a lot of problems of operations research consists of performing simple single-type operations over large collections of numbers. Therefore, the problems of operations research impose demands on the computer involving, to a great extent, both the computer memory and its speed of operation. The actual demands of operations research have shown a great influence on the development of computers and their memory.

The range of applications of operations research is very broad. Operations research is used in the solution of technical (both constructive and technological), technico-economic and socio-economic problems, as well as in problems of control in various media and on various levels, thereby slowly solidifying the traditional "intuitive" methods of decision making.

The practical introduction of results of operations research can be found at various levels of scholarship. The first issue which was overcome relatively early is related to the construction of conceptual structures of models of real problems of decision making (or with the selection of a model of already given structure). This establishes a possibility in principle of modelling a class of real problems, including the problem under consideration, by a certain class of problems of operations research. The next issue consists in the choice of precisely that problem in this class that models the specific problem of interest. For this choice one must, in particular, measure the values of the parameters determining the problem to be solved. Now, since these parameters need not have a physical or technological character, but are often of an economic or even socio-economic character, their measurement with a required precision may pose a problem in itself. This problem in the choice of information for the construction of a specific model can be considered as the basic obstacle on the way of elaborating the optimal decision. Next, after the construction of the model, there arise the purely mathematical, including computational, difficulties of its analysis and solution. In essence, the contents of operations research consists precisely of overcoming these difficulties. Finally, after the solution has been found, the last issue arises, which is often of an organizational and psychological nature: the solution found quite often differs from traditional solutions and hence is regarded with disbelief. All this restricts the applicability of operations research. In order to overcome these difficulties more successfully, teams working in the field of operations research are often combined into inter-disciplinary groups; these are formed by, apart from mathematicians, usually also engineers, economists and specialists in the domain of the concrete discipline, and sometimes even psychologists, managers, etc.

References

[1]	P.M. Morse, G.E. Kimball, "Methods of operations research" , M.I.T. (1952)
[2]	T.L. Saaty, "Mathematical methods of operations research" , McGraw-Hill (1959)
[3]	A. Kaufmann, R. Faure, "Invitation à la récherche opérationelle" , Dunod (1963)
[4]	A. Kaufmann, "Methods and models of operations research" , Prentice-Hall (1963) (Translated from French)
[5]	W. Churchmen, R.L. Ackoff, E.L. Arnoff, "Introduction to operations research" , Wiley (1957)
[6]	Yu.V. Chuev, "Operations research in a military case" , Moscow (1970) (In Russian)
[7]	Yu.B. Germeier, "Introduction to the theory of operations research" , Moscow (1971) (In Russian)
[8]	R. Ackoff, M. Sasieni, "Fundamentals of operations research" , Wiley (1968)
[9]	E.S. Venttsel', "Operations research" , Moscow (1972) (In Russian)
[10]	H. Wagner, "Principles of operations research" , Prentice-Hall (1975)
[11]	, Operations research. Methodological aspects , Moscow (1972) (In Russian)
[12]	, Mathematische Standardmodelle der Operationsforschung. Mathematische Grundlagen, Methoden und Modelle , 1 , Berlin (1971)
[13]	, Mathematische Standardmodelle der Operationsforschung. Mathematische Grundlagen, Methoden und Modelle , 1–3 , Berlin (1971–1973)

References

[a1]	E.M.L. Beall, "Introduction to optimization" , Wiley (1987)
[a2]	F.S. Hillier, G.J. Lieberman, "Introduction to operations research" , Holden-Day (1967)