Текст книги "Effective Methods and Transportation Processes Management Models at the Railway Transport. Textbook"

2.4 Multi-criteria Operations Research Tasks

Despite a number of significant difficulties associated with the uncertainty of the conditions of the operation, we have still considered only the simplest problems of operations research, when the criterion by which the effectiveness is evaluated is clear, and it is necessary to turn into a maximum (or minimum) a single indicator of efficiency W. It is he who is the criterion by which one can judge the effectiveness of the operation and the decisions made.

Finally, let’s make one general remark. When justifying a decision under conditions of uncertainty, no matter what we do, the element of uncertainty remains. Therefore, it is impossible to impose too high demands on the accuracy of solving such problems. Instead of unambiguously indicating a single, exactly «optimal» (from some point of view) solution, it is better to single out a whole area of acceptable solutions that turn out to be insignificantly worse than others, no matter what point of view we use. Within this area, the persons responsible for this should make their final choice.

Despite a number of significant difficulties associated with the uncertainty of the conditions of the operation, we have still considered only the simplest problems of operations research, when the criterion by which the effectiveness is evaluated is clear, and it is necessary to turn into a maximum (or minimum) a single indicator of efficiency W. It is he who is the criterion by which one can judge the effectiveness of the operation and the decisions made.

Unfortunately, in practice, such tasks, where the evaluation criterion is clearly dictated by the target orientation of the operation, are relatively rare, mainly when considering small-scale and modest-value activities. As a rule, the effectiveness of large-scale, complex operations affecting the diverse interests of participants cannot be exhaustively characterized using a single performance indicator W. To help him, he has to attract other, additional ones. Such operations research tasks are called «multi-criteria».

Such a multiplicity of criteria (indicators), of which it is desirable to turn some into a maximum, and others into a minimum, is characteristic of any somewhat complex operation. We suggest the reader to formulate in the form of an exercise a number of criteria (performance indicators) for the operation in which the work of urban transport is organized. Fleet of mobile vehicles (trams, buses, trolleybuses) it is considered set; the solution swings routes and stops. When choosing a system of indicators, think about which of them is the main one (most closely related to the target orientation of the operation), and arrange the rest (additional) in descending order of importance. Using this example, you will see that a) none of the indicators can be chosen as the only one and b) the formulation of the indicator system is not such an easy task as it may seem at first glance.

So, typical for a large-scale task of operations research is multi-criteria – the presence of a number of quantitative indicators W1, W2,…, one of which is desirable to turn into a maximum, and others into a minimum, and others into a minimum («so that the wolves are fed and the sheep are safe»).

The question is, is it possible to find a solution that satisfies all these requirements at the same time? With all frankness, we answer: no. A solution that turns any indicator to a maximum, as a rule, neither turns into a maximum, nor a minimum of others. Therefore, the phrase «achieving maximum effect at minimum cost», which is widely used in everyday life, is nothing more than a phrase and should be discarded in scientific analysis. Another wording will be legitimate: «achieving a given effect at minimal cost» or «achieving the maximum effect at a given cost» (unfortunately, these legal formulations seem to be somehow not «elegant» enough in oral speech).

What if you still have to evaluate the effectiveness of the operation by several indicators?

In practice, the following technique is often used for this: they try to compile one of several indicators and, when choosing a solution, use such a «generalized» indicator. Often it is composed in the form of a fraction, where in the numerator are those values, the increase of which is desirable, and in the denominator – the increase of which is undesirable. For example, the enemy’s losses are in the numerator, own losses and the cost of funds spent are in the denominator, etc.

In practice, another, slightly more intricate method of compiling a «generalized» performance indicator is often used. They take individual private indicators, attribute some «weights» to them (a1, a2,…), multiply each indicator by the corresponding weight and add them up; Those indicators that need to be maximized are with a minus sign.

With the arbitrary assignment of weights attributed to particular indicators, this method is no better than the first. Proponents of this technique refer to the fact that a person, making a compromise decision, also mentally weighs the pros and cons, attributing greater importance to factors that are more important to him. This may be true, but, apparently, the «weighting coefficients» with which different indicators are included in the mental calculation are not constant, but change depending on the situation.

Here we meet with an extremely typical technique for such situations – «the transfer of arbitrariness from one instance to another.» Indeed, the simple choice of a compromise solution in a multi-criteria problem based on a mental comparison of the advantages and disadvantages of each solution seems too arbitrary, not «scientific» enough. But manipulating a formula that includes, albeit equally arbitrarily assigned coefficients, gives the solution the features of some kind of «scientificity». In fact, there is no science here – one transfusion from empty to empty.

It turns out that the mathematical apparatus cannot help us in solving multi-criteria problems? Far from it, it can help, and very significantly. Firstly, with the help of this device, it is possible to successfully solve direct problems of operations research and establish what advantages and disadvantages each of the solutions has according to different criteria. The mathematical model gives us the opportunity to calculate not only the value of the main performance indicator, but also all additional ones, and the complexity of the calculation increases little. Comparison of the results of solving a set of such direct problems provides the decision maker with a certain «accumulated scientific experience». Knowing what he wins and what he sacrifices, a person can evaluate each of the decisions and choose the most acceptable for himself.

A perplexing question may arise: what about the mathematical methods of optimization, about which he heard a lot and which he hoped so much? The trouble is that each of these methods makes it possible to find only an optimal solution for a single, scalar criterion W. Evaluate by the vector criterion (W1, W2,…) Modern mathematics does not yet know how. Indeed, not every «better» or «worse» is directly related to «more» or «less», and mathematical methods so far speak only the language of «more-less». Of all the devices known to us, so far only a person is able to make reasonable decisions not according to the scalar, but according to the vector criterion. How he does this is not clear. Maybe each time he reduces the vector to a scalar, forming some function (linear, nonlinear) from its components? Possibly, but not plausible. Most likely, when choosing a solution, he thinks not formally, but generally, instinctively assessing the situation as a whole, discarding insignificant details, subconsciously using all the experience he has, if not literally such, but similar situations. At the same time, the (informal) choice of a compromise solution can significantly help a person with a mathematical apparatus. In any case, it helps to discard in advance obviously unsuccessful solutions, which are not worth thinking about.

Let’s demonstrate one of these methods of preliminary «rejection» of unsuccessful decisions. Let us have to make a choice between several solutions: X1, X2,…, Xn (each option is a vector, the components of which are the elements of the solution). The effectiveness of the operation is evaluated by two indicators: the productivity of P and the cost of S. The first indicator is desirable to maximize, and the second to minimize.

Similarly, unsuitable options are discarded in the case when there are not two, but more. (With more than three of them, the geometric interpretation loses clarity, but the essence of the matter remains the same: the number of competitive solutions decreases sharply.) As for the final choice of the solution, it still remains the prerogative of man – this unsurpassed «master of compromise».

However, the procedure for choosing the final solution, being repeated repeatedly, in different situations, can serve as the basis for which convenient formalization. We are talking about the construction of so-called «heuristic methods» of decision-making. Such methods are widely used in attempts to automate the solution of some informal tasks. For example, in order to force the automaton to solve difficult-to-formalize tasks (for example, reading handwritten text, recognizing images or sounds of live speech), so-called training automata are created. The program according to which such a machine works is not laid down in it in advance, but is formed gradually, in the process of familiarization with an increasingly wide range of situations. The initial model for the machine is an experienced person who knows how to perform an informal task, say, to make a decision according to a vector criterion. Subsequently, there may be further improvement of the program (already in the order of «self-study»).

When solving multi-criteria problems, some authors use a game approach. The uncertainty of the criterion (incomplete knowledge of the purpose of the operation) is considered by them as another type of uncertainty, in principle no different from the uncertainty of conditions. The choice of solution is based on the same principle of «least favored nation» or «extreme pessimism», which we have already discussed earlier. Along with others, this approach to the justification of decisions in multi-criteria problems also has the «right to vote».

In conclusion, we emphasize that the collective nature of the work is especially important when justifying decisions in difficult situations. A mathematical model created by a single person (even a very talented one) will always suffer from some one-sidedness. Collective discussion of the models created, the criteria chosen and the proposed recommendations is the best way to overcome this one-sidedness. The well-known proposition «truth is born in a dispute» is nowhere more clearly confirmed than in the field of operations research.

2.5 Dynamic programming method

The use of mathematical methods for solving problems of railway transport is associated with the names of outstanding scientists: L.V. Kantorovich, academician, Nobel Prize laureate; E.S. Ventzel, Doctor of Physical and Mathematical Sciences, Professor; S.V. Duvolyan, Doctor of Technical Sciences, Professor; T.S. Khachaturov, chief correspondent of the Academy of Sciences and others, whose works served the effective development of railway transport and allowed him to take a leading place in the world development of railways. Let’s take a closer look at one of the methods of the dynamic programming method.

Dynamic programming (otherwise referred to as «dynamic planning») is an optimization method that is most adapted to the tasks of managing multi-step (multi-stage) operations.

Suppose there is some operation Q, which breaks down into a series of «steps» or «steps». Some operations are divided into steps naturally; For example, when planning an economic activity, a natural step would be a financial year. In other cases, the division into steps is introduced artificially (for example, the process of putting a spacecraft into orbit can be conditionally divided into stages, time intervals Δt). It is possible to divide into steps or stages not only operations that develop over time, but also those that are not related to time (for example, when distributing resources across several objects, allocating resources to each object can be considered as another «step»). The criterion or indicator of efficiency W, which needs to be turned into a maximum (or minimum), consists of several terms obtained at individual steps (the gain for the entire operation is equal to the sum of the winnings at all its steps).

Let’s consider a few typical problems for which the natural method of solving is the method of dynamic programming.

1. The activities of the group of industrial enterprises P1, P2, …, Pk are planned for a period of m financial years. At the beginning of the period, some funds were allocated for the development of the enterprise system, which should be somehow distributed among enterprises. In the course of the enterprise’s activities, the funds invested in it are partially spent (depreciated). Each enterprise generates income per year, depending on the invested funds; Part of this income is deducted to the fund of enterprises. At the beginning of each financial year, the available funds are redistributed among the enterprises. The question is raised: how much money at the beginning of each year should be allocated to each enterprise so that the total net income for m years is maximum?

2. A space rocket consists of m+1 stages, and the process of launching it into orbit consists of m stages, as a result of each of which the next stage is dropped. The total weight of the rocket consists of the «useful» weight of the last stage Q, plus the weight of the m stages dropped:

G=G1+G2+ … + Gm,

where Gi is the weight of the i-th stage (i = 1,.., m). The question is, how should the weight be distributed between the individual stages in order for the speed of the rocket at the time of launch into orbit to be maximum?

3. The owner of the machine has been operating it for m years. At the beginning of each year, he can decide whether to sell the car and replace it with a new one, or continue to operate without repair. At the end of the period, the car is sold in any circumstances. What decisions need to be made over the years in order to ensure that the total costs of operating, repairing and purchasing new machines are minimal?

4. A section of railway track is being laid between two points A and B. Different route options require different costs (due to the heterogeneity of the soil, terrain features, natural obstacles, etc.). It is required to draw a road from A to B so that the total cost of constructing the site is minimal.

Note that in the last problem there is no natural division into steps: this division has to be introduced artificially, for which, for example, the distance from A to B can be divided into m parts and considered as a «step» overcoming one such part.

Any multistep task of operations research can be solved in different ways: either to search for all the elements of the solution at once at all m steps, or to build optimal control gradually, step by step (optimizing only one step at each stage of the calculation). Usually, the second optimization method turns out to be easier than the first, especially with a large number of steps. This idea of gradual, step-by-step control optimization is the essence of the dynamic programming method. Optimizing one step is usually easier than optimizing the whole process.; it turns out that it is better to solve a relatively simple task many times than to solve a complex one once.

At first glance, the idea may seem quite trivial. In fact, what would seem to be simpler: if it is difficult to optimize the operation as a whole, break it into a number of steps. Each such step will be a separate, small operation, which is no longer difficult to optimize. It is necessary to choose such management at each step so that the effectiveness of this step is maximized.

The principle of dynamic programming does not imply that each step is optimized separately, independently of the others. On the contrary, step-by-step management should be chosen far-sightedly, taking into account all its consequences in the future. What is the point if we choose a control at this step, in which the effectiveness of this step is maximum, and the effect on subsequent steps is not optimal?

Suppose, for example, the work of a group of industrial enterprises, some of which are engaged in the production of consumer goods, while others produce machines for this. The task is to obtain the maximum volume of output of consumer goods in m years. Let the investment be planned for the first year. Proceeding from the narrow interests of this step (year), we would have to invest all available funds in the production of consumer goods, put the existing machines at full capacity and achieve the maximum volume of production by the end of the year. But would such a decision be correct from the point of view of the operation as a whole? Obviously not. Bearing in mind the future, it is necessary to allocate a certain share of funds for the production of machines. At the same time, the volume of production for the first year, of course, will decrease, but conditions will be created to increase it in subsequent years.

When planning a multi-step operation, it is necessary to choose control at each step, taking into account its future consequences in the upcoming steps.

However, there is an exception to this rule. Among all the steps, there is one that can be planned simply, without regard to the future. What is this step? Obviously, the latter. This step, the only one of all, can be planned so that it itself, as such, brings the greatest benefit. Therefore, the process of dynamic programming unfolds from end to beginning: the last, m-th step is planned first.

And how to plan it if we do not know how the penultimate one ended? Very simple: you need to make different assumptions about how the penultimate, (m-1) step ended, and for each of these assumptions find a conditional optimal control at the m-th step («conditional» because it is chosen based on the condition that the penultimate step ended in this and that). Let’s assume that this is done, and for each of the outcomes of the penultimate step, we know the conditional optimal control at the last step and the corresponding optimal gain at this step. Now we can optimize the control in the penultimate, (m-1) -th step. Again, we will make all the assumptions about how the previous, (m-2) step ended, and for each of these assumptions we will find such a control at the (m-1) step in which the gain for the last two steps (of which the last one has already been optimized) is maximum. So we will find for each outcome of the (m-2) -th step a conditional optimal control on the (m-1) -m and a conditional optimal gain on the remaining two steps. Next, we optimize the control at the (m-2) step, etc., until we get to the first one.

Let’s assume that we know all the conditional optimal controls at all steps: we know what to do, how to manage at any next step, no matter what state the process is in at its beginning. Now we can build not conditionally optimal, but simply optimal process control. Indeed, let us know what state S0 the managed system (control object) was in at the beginning of the first step. Then we can choose the optimal control of U1 in the first step. By applying it, we will change the state of the system to some S1; In this state, we came to the second step. For him, we also know the conditional optimal control U2, which by the end of the second step puts the system in the S2 state, and so on.

As for the optimal gain for the entire operation, we already know it: after all, it was on the basis of its maximum that we chose control in the first step.

Thus, in the process of optimizing the control of the dynamic programming method, the multi-step process is «passed» twice. The first time is from the end to the beginning, resulting in conditional optimal controls and conditional optimal wins to the end for all steps. The second time is from beginning to end, as a result of which there are (no longer conditional) step controls and, therefore, optimal management of operations as a whole.

The first stage – finding conditional optimal controls and winnings – is incomparably more difficult and time-consuming than the second. On the second, it remains only to «read» the recommendations received on the first. Note that the concepts of «end» and «beginning» can be swapped and the optimization process can be deployed in a different direction. This is quite equivalent to the described method in the sense of calculation, but somewhat less convenient for verbal explanation of the idea of the method.