In all areas of everyday life there are situations when conflicting aspects have to be taken into account simultaneously. A problem becomes even more difficult when several decision makers' or interest groups' mutual agreement is needed to find a solution.
Conflict situations are divided in three categories in terms of mathematics:
One decision maker has to make a decision by taking several conflicting aspects into account
Several decision makers have to find a common solution, when every decision maker takes only one criterion into account
Several decision makers look for a common solution, but every decision maker takes several criteria into account
In the first case the problem is a multi-objective optimization problem, where the objective functions make up the various aspects. The second case is a typical problem of the game theory, when the decision makers are the players and the criteria mean the payoff functions. The third case appears as Pareto games in the literature, when the different players only strive to find Pareto optimal solutions instead of optimal ones.
In this chapter we will discuss the basics of this very important and complex topic.
Suppose, that one decision maker wants to find the best decision alternative on the basis of several, usually conflicting criteria. The criteria usually represent decision objectives. At first these are usually defined verbally, such as clean air, cheap maintenance, etc. Before the mathematical model is given, firstly, these objectives have to be described by quantifiable indices. It often occurs that one criterion is described by more than one indices, such as the quality of the air, since the simultaneous presence of many types of pollution have an effect on it. In mathematics it is usually assumed that the bigger value of the certain indices (they will be called objective functions) means favorable value, hence we want to maximize all of the objective functions simultaneously. If we want to minimize one of the objective functions, we can safely multiply its value by , and maximize the resulting new objective function. If in the case of one of the objective functions, the goal is to attain some kind of optimal value, we can maximize the deviation from it by multiplying it by .
If denotes the set of possible decision alternatives, and denotes the th objective function , the problem can be described mathematically as follows:
supposing that .
In the case of a single objective function we look for an optimal solution. Optimal solutions satisfy the following requirements:
(i) An optimal solution is always better than any non-optimal solution.
(ii) There is no such possible solution that provides better objective functions than an optimal solution.
(iii) If more than one optimal solution exist simultaneously, they are equivalent in the meaning that they have the same objective functions.
These properties come from the simple fact that the consequential space,
is a subset of the real number line, which is totally ordered. In the case of multiple objective functions, the
consequential space is a subset of the -dimensional Euclidean space, which is only partially ordered. Another complication results from the fact that a decision alternative that could maximize all of the objective functions simultaneously doesn't usually exist.
the maximum of the th objective function, then the
point is called ideal point. If , then there exits an decision for which . In such special cases satisfies the previously defined (i)-(iii) conditions. However, if , the situation is much more complicated. In that case we look for Pareto optimal solutions instead of optimal ones.
It is not necessary that a multi-purpose optimization problem has Pareto optimal solution, as the case of the
set shows it. Since is open set, for arbitrary and for a small enough positive and .
The following two examples present a discrete and a continuous problem.
Example 27.1 Assume that during the planning of a sewage plant one out of two options must be chosen. The expenditure of the first option is two billion Ft, and its daily capacity is 1500 . The second option is more expensive, three billion Ft with 2000 daily capacity. In this case , , . The following table summarizes the data:
Both options are Pareto optimal, since and .The consequential space consists of two points: and .
Example 27.2 The optimal combination of three technology variants is used in a sewage station. The first variant removes 3,2,1 from one kind of pollution, and 1,3,2 quantity from the another kind of pollution. Let , and denote the percentage composition of the three technology variants.
The restrictive conditions:
the quantity of the removed pollution:
Since the third term is constant, we get the following two objective-function optimum problem:
A consequential space can be determined as follows. From the
and from the restrictive conditions the following conditions arises for the and objective functions:
On the basis of the image of the set, it is clear that the points of the straight section joining to are Pareto optimal. Point isn't better than any possible point of , because in the first objective function it results the worst possible planes. The points of the section are not equivalent to each other, either, going down from the point towards point , the first objective function is increasing, but the second one is continually decreasing. Thus the (ii) and (iii) properties of the optimal solution doesn't remain valid in the case of multi-objection.
As we saw in the previous example, the different Pareto optimal solutions result in different objective function values, so it is primary importance to decide which one should be selected in a particular case. This question is answered by the methodology of the multi-objective programming. Most methods' basis is to substitute some real-valued “value-function” for the objective functions, that is the preference generated by the objective functions is replaced by a single real-valued function. In this chapter the most frequently used methods of multi-objective programming are discussed.
A natural method is the following. We assign one utility function to every objective function. Let denote the utility function of the th objective function. The construction of the function can be done by the usual manner of the theory of utility functions, for example the decision maker can subjectively define the values for the given values, then a continuous function can be interpolated on the resulting point. In the case of additive independent utility function additive, whereas in the case of independent of usefulness utility function additive or multiplicative aggregate utility function can be obtained. That is, the form of the aggregate utility function is either
In such cases the multi-objective optimization problem can be rewrite to one objective-function form:
provided that , and thus means the “value-function”.
Example 27.3 Consider again the decision making problem of the previous example. The range of the first objective function is , while the range of the second one is . Assuming linear utility functions
In addition, suppose that the decision maker gave the
values. Assuming linear utility functions
and in accordance with the given values
By the third equation , and by the second one we obtain , so that
Thus we solve the following one objective-function problem:
Apparently, the optimal solution is: , , that is the first technology must be chosen.
Assume that the number of objective functions is and the decision maker gives vectors: and the related aggregated utility function values. Then the coefficients can be given by the solution of the
equation system. We always suppose that , so that we have at least as many equations as the number of unknown quantities. If the equation system is contradictory, we determine the best fitting solution by the method of least squares. Suppose that
The formal algorithm is as follows:
DO4 the vector of solutions 5
Using this method the value-function is chosen as the linear combination of the original object functions, that is we solve the
problem. If we measure the certain objective functions in different dimensions, the aggregate utility function can't be interpreted, since we add up terms in different units. In this case we generally normalize the objective functions. Let and the minimum and maximum of the objective function on the set . Then the normalized th objective function is given by the
formula, and in the (27.8) problem is replaced by :
It can be shown, that if all of the weights are positive, the optimal solutions of (27.9) are Pareto optimal with regard to the original problem.
Assume that the objective functions are equally important, so we choose equivalent weights: , in this way the aggregate objective function is:
It is easy to see that the optimal solution on set :
that is, only the second technology variant can be chosen.
Suppose that . The formal algorithm is as follows:
DO3 4 5
If we normalize the objective functions, the certain normalized objective functions most favorable value is 1 and the most unfavourable is 0. So that is the ideal point and is the worst yield vector.
In the case of distance-dependent methods we either want to get nearest to the vector or get farthest from the point , so that we solve either the
problem, where denotes some distance function in .
In practical applications the following distance functions are used most frequently:
The distance functions the commonly known Minkowski distance for . The geometric distance doesn't satisfy the usual requirements of distance functions however, it is frequently used in practice. As we will see it later, Nash's classical conflict resolution algorithm uses the geometric distance as well. It is easy to prove that the methods using the distance are equivalent of the weighting method. Notice firstly that
where the first term is constant, while the second term is the objective function of the weighting method. Similarly,
which is the objective function of the weighting method.
Example 27.5 Consider again the problem of the previous example. The normalized consequences are shown by Figure 27.6. The two coordinates are:
Choosing the and the distances, the nearest point of to the ideal point is
that is the optimal decision is:
Therefore only the first two technology must be chosen in 20% and 80% proportion.
Let's choose again equivalent weights () and the distance, but look for the farthest point of from the ideal worst point. We can see from Figure 27.5, that the solution is
Thus the optimal decision is: and
The formal algorithm is as follows:
DO3 4 5 or 6
Assume that we have a point in set , on which we'd like to improve. denotes the present position, on which the decision maker wants to improve, or at design level we can choose the worst point for the starting one. Furthermore, we assume that the decision maker gives an improvement direction vector, which is denoted by . After that, the task is to reach the farthest possible point in set starting from along the direction vector. Thus, mathematically we solve the
optimum task, and the related decision is given by the solution of the
equation under the optimal value. The method is illustrated in Figure 27.7.
Example 27.6 Let's consider again the problem of Example 27.2, and assume that , which contains the worst possible objective function values in its components. If we want to improve the objective functions equally, we have to choose . The graphical solution is illustrated in Figure 27.8, that
so the appropriate values of the decision variables are the following:
A very rarely used variant of the method is when we diminishes the object function values systematically starting from an unreachable ideal point until a possible solution is given. If denotes this ideal point, the (27.18) optimum task is modified as follows:
and the appropriate decision is given by the solution of the
Example 27.7 To return to the previous example, consider again that and , that is we want to diminish the object functions equally. Figure 27.9 shows the graphical solution of the problem, in which we can see that the given solution is the same as the solution of the previous example.
27.1-3 Solve Exercise 27.1-1 using the weighting-method without normalizing the objective functions. Choose the weights.
27.1-5 Solve Exercise 27.1-1with normalized objective functions, weights and minimizing the
27.1-7 Solve Exercise 27.1-1 using the direction-dependent method, choosing and .