辅导 Laboratory work №2讲解 Python编程

Decision Making Lab2

Laboratory work №2

Topic: Methods of multi-criteria optimization when reducing problems to single-criteria ones

Goal of the work:

- study the possibilities of using multi-criteria optimization methods by reducing problems to single-criteria ones;

- learn how to perform. a graphic presentation of a decision-making task;

- learn how to search for solutions using multi-criteria optimization methods when reducing problems to single-criteria ones.

The order of work

1. Study theoretical information about the task of decision-making with methods of multi-criteria optimization by reducing problems to single-criteria ones.

2. Choose a subject area for decision-making (the same as in laboratory work #1).

3. Perform. a verbal formulation of the decision-making problem in the selected subject area and determine 6 alternatives, evaluating them according to 5 criteria.

4. In the MS Excel environment, create the tables with data for solving the problem.

5. Search for solutions based on various methods.

6. Compare the obtained solutions. Explain the results. Demonstrate the process of finding solutions to the teacher.

7. Make a report on laboratory work.

8. Defend laboratory work.

Content of the report

1. Topic of the work.

2. Goal of the work.

3. Individual task.

4. Description of the work execution.

5. Interpretation of the obtained results.

6. Conclusions.

Individual tasks

Select the problem area according to the ID in the group list. Search for solutions for the given problem area (Table 1).

Table 1

Theoretical material

All methods of solving multi-criteria optimization problems are based on reducing the initial problem with a vector criterion to an optimization problem with a scalar criterion. The methods differ only in the mechanism of implementation of such reduction. Most common of them are the main criterion, convolution criteria – linear and maximum convolution, consequent concessions, ideal point, target programming.

1 The main criterion method

In the method of the main criterion, one of the functionals f_i, for example f₁, is selected as the target function, which most fully reflects the goal of decision-making from the point of view of decision maker. The remaining requirements for the result, described by the functionals f₂, … , f_m, are taken into account with the help of additional restrictions. Thus, the multi-criteria optimization problem turns into a single-criteria optimization:

Formally, we obtain a simple problem of finding the maximum of the functional f₁ on a new admissible set D´. The restriction f₁(х) ≥ t_i shows that the functionals f₂, … , f_m are bounded from below, and it is not necessary to reach their maximum values.

Example 1.

Let’s solve the task of placing the enterprise.

We have seven alternative options х₁ – х₇, where each is evaluated by experts in conventional units according to four criteria:

f₁ – distance to the supplier of raw materials;

f₂ – availability of labor resources;

f₃ – cost of electricity supply;

f₄ - transport connection.

The experts identified the main criterion – availability of labor resources and limitation of assessments according to other criteria (Table 2.1). It is necessary to make the best decision about the location of the enterprise according to the method of the main criterion.

Table 2.1 – Criteria for location of an enterprise

2 The method of linear convolution

This method of "scalarization" (convolution) of the multicriteria optimization problem allows replacing the vector optimality criterion

f=(f₁, … , f_m)

to scalar one

J: D → R.

It is based on the linear association of all private objective functionals f₁, … , f_m into one:

Here, α_i – weighting coefficients, which can be considered as indicators of the relative importance of individual criterion functionals f_i. The more importance given to the criterion f_i, the greater the weighting coefficient assigned to it.

Example 2.

It is necessary to make the best decision about the location of the enterprise using the method of linear convolution.

We have seven alternative variants х₁ – х₇, each of which was evaluated by experts in conditional units according to four criteria (Table 2.4):

f₁ – distance to the supplier of raw materials;

f₂ – availability of labor resources;

f₃ – cost of electricity supply;

f₄ - transport connection.

The experts established weighting coefficients of the importance of the criteria:

a₁=0,3; a₂=0,4; a₃=0,1; a₄=0,2.

Table 2.4 – Criteria for location of an enterprise

3 Maximin convolution method

This method can be formally presented in the form.

Here, the target functional J(x) is affected only by a certain criterion of optimality, which corresponds to the smallest value of the functional f_i(x) at the point x, that is the "worst case". At the same time, by the value of J(x) we can determine the guaranteed lower estimate for all functionals f_i(x). This fact is regarded as an advantage of the maximin criterion over the linear convolution method.

If necessary, we can normalize individual target functions, i.e. bring the measurement scales of individual f_i(x) values into mutual agreement, using the "weighted" form. of the maximin criterion:

The selection of the values of the weighting coefficients α_i based on a priori information allows influencing the optimization process.

Normalization of criteria (reduction to a comparable dimensionless form) can be carried out in various ways, the most common among them are the following: 

where  f_i^max – the maximum value of the criterion f_i(x) on a set of admissible alternatives X, "i є І₁ÈI₂,;

f_i^min – the minimum value of the criterion f_i(x) on a set of admissible alternatives X, "i ϵ І₁ÈI₂,

I₁ – the set of indices for which the objective functions are maximized;

І₂ – the set of indices for which the objective functions are minimized.

The criteria are "collapsed" into one objective function, forming the so-called generalized criterion, in which the relative importance of each of the criteria is taken into account using weighting factors that must satisfy the following ratios:

As a result, the original multi-criteria problem is reduced to an ordinary optimization problem with one criterion.

Example 3.

It is necessary to make the best decision about the location of the enterprise using the method of maximin convolution.

We have seven alternative variants х₁ – х₇, each of which was evaluated by experts in conditional units according to four criteria (Table 2.4):

f₁ – distance to the supplier of raw materials;

f₂ – availability of labor resources;

f₃ – cost of electricity supply;

f₄ - transport connection.

The experts established weighting coefficients of the importance of the criteria:

a₁=0,3; a₂=0,4; a₃=0,1; a₄=0,2 (табл. 2.4).

Find the best solution for placing the enterprise using the maximin convolution method.

4 The method of consequent concessions

The method of consequent concessions belongs to the category of lexicographic optimization. The essence of the method of consequent concessions is that the original multi-criteria problem is replaced by a sequence of single-criteria problems, the area of admissible solutions of which is narrowed from problem to problem with the help of additional restrictions taking into account the criteria requirements. When formulating each problem in relation to a more important criterion, a concession is made, the amount of which depends on the requirements of the problem and the optimal solution according to this criterion.

Solving a multi-criteria problem by the method of consequent concessions consists in performing the following actions:

1) partial criteria are numbered in order of their relative importance;

2) maximize the first, most important criterion:

f₁(x) → max,  x є X,

and we get the optimal value of the first criterion f₁^max ;

3) assign the value of the permissible decrease in the value Δ₁ of this criterion and maximize the second most important partial criterion, provided that the value of the first criterion must differ from the maximum by no more than the value of the established decrease (concession):

f₂(x) → max,  f₁(x) ≥ f₁^max — Δ₁,  x є X;

as a result of solving the problem, we get the optimal value of the criterion f₂^max ;

4) assign the value of the concession again, but already to the second criterion and find the maximum of the third most important criterion, provided that the values of the first two criteria do not differ from the previously found maximum values by more than the amount of the corresponding concessions;

5) similarly, other partial criteria are used in turn;

6) if the problem is solved for k criteria, then we have:

f_k+1(x) ® max,  

f₁(x) ≥ f₁^max — Δ₁,

f₂(x) ≥ f₂^max — Δ₂,

. . .

f_k(x) ≥ f _k ^max,

x є X;

the problem is solved when all criteria are considered;

7) any strategy obtained when solving the problem of finding the conditional maximum of the last criterion in terms of importance is usually considered optimal.

Example 4.

It is necessary to make the best decision about the location of the enterprise. We have seven alternative options х₁ – х₇, each of which is evaluated in conditional units according to four criteria f₁, f₂, f₃, f₄ (table 2.1). The criteria are arranged in order of decreasing importance for decision maker. We solve the problem f(x) → max.

Table 2.10 – Evaluations of criteria in conventional units