Decision Making Lab3

Laboratory work №3

Topic: Finding solutions based on binary relations preference.

"ELECTRE" method of thresholds of inequality

Goal of the work:

- study of the features of the application of binary relations of preference for decision-making;

- study of the "ELECTRE" method of inequality thresholds;

- implement the the "ELECTRE" method in the MS Excel environment.

The order of work

1. Study the features of binary relations preferences in decision-making and the decision-making algorithm by the method of "ELECTRE" inequality thresholds.

2. Present initial data and search for the optimal solution using the "ELECTRE" method in the MS Excel environment.

3. Make a graphic representation of the problem. Explain the result by showing the optimal solution on the graph. Demonstrate the process of finding solutions to the teacher.

4. Make a report on laboratory work.

5. 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

According to the individual task (Table 1), find the best solutions by performing the necessary calculations in MS Excel. Set the values of the agreement and disagreement indices yourself.

Table 1

Theoretical material

"ELECTRE" method of thresholds of inequality

The ELECTRE methods (acronym stands for ELimination and ChoiceExpressingREality) is a family of multi-criteria decision analysis (MCDA) methods.

There are two main parts to an ELECTRE application: first, the construction of one or several outranking relations, which aims at comparing in a comprehensive way each pair of actions; second, an exploitation procedure that elaborates on the recommendations obtained in the first phase. The nature of the recommendation depends on the problem being addressed: choosing, ranking or sorting.

Criteria in ELECTRE methods have two distinct sets of parameters: the importance coefficients and the veto thresholds. ELECTRE method cannot determine the weights of the criteria.

Stages of the ELECTRE procedure:

1) for each criterion, a discrete scale of possible values of this criterion and weighting coefficients are assigned;

2) a graph is constructed for each criterion, the vertices of which are individual objects of the set and the arcs indicate the dominance relationship between objects according to this criterion;

3) taking into account the importance of the criteria and the preference of the objects, the matrices of the values of the special coefficients – indices of agreement and disagreement are calculated;

4) for each pair of objects (x_i, x_j) ∈ X, the preference ratio, x_i over x_j, is considered established if the value of the corresponding index of agreement is greater than some threshold value, and the index of disagreement is less than the corresponding threshold value.

5) a generalized preference graph is constructed, the structure of which depends on the selected threshold values.

Example.

Let X be the set of students participating in the scholarship competition.

It is necessary to determine the best candidates based on the conducted examinations.

The number, composition of disciplines and possible ways of evaluating students in disciplines may vary according to the specific features of the higher education institution.

Let's consider the evaluations of three students in three disciplines on a five-point scale (Table 2).

Table 2 - Assessments of the examination session

Notations:

x₁, x₂, x₃ ∈ X the set of evaluated objects (students);

y_i – grade of the object х∈Х according to the criterion i, i =1, m (grade by discipline);

c_ki – weight factor of the criterion k_i, i =1,m (importance of the discipline);

0 < c_ki < 1(10,100, ...).

Let c_k1 = 5, c_k2 = 3, c_k3 = 2. 

For each criterion i we build a graph G_i = (X, V_i), where V_i is a set of graph arcs G_i.

An arc in the graph G_i from vertex х_i to vertex x_j exists if a_i ≥ a_j, equality of grades a_i = a_j in the graph is displayed as two arcs from х_i to x_j and from x_j to х_i.

Let's build graphs of binary relations for the disciplines specified in the problem. 

Figure 1 – Graphs of binary relations in mathematics (a), physics (b) and computer graphics (c).

The combined graph characterizes the complete agreement of the preference of some objects over others.

Let's build a combined graph G₀ = (X, V₀), where   is the intersection of three graphs with arcs V_i.

Figure 2 – Combined graph G₀ = (X, V₀)

In our example, V₀ = {Ø}, since there are no arcs in the three graphs that coincide in direction at the same time. 

Let's build a matrix of agreement indices of preference of objects:

Let's consider a couple of objects (x_i, x_j)∈ X. Regarding them, the set of all criteria can be divided into two "opposite" classes. To the first class C(x_i, x_j) we include all the criteria k_i for which x_i ≥ x_j , i =1,m, j =1,m, that is, the criteria according to which in the graphs G_i there is an arc (x_i, x_j): 

In criterion language, we will determine the advantages of alternatives by performing pairwise comparisons. Alternative x₁ is better than x₂ according to the criteria k₁, k₃; alternative x₁ is better than x₃ according to the criteria k₁, k₃; alternative x₂ is better than x₁ according to the criteria k₁, k₂, etc.:

C(x₁, x₂) = {k₁, k₃}, C(x₁, x₃) = {k₁, k₃},

C(x₂, x₁) = {k₁, k₂}, C(x₂, x₃) = {k₁, k₃},

C(x₃, x₁) = {k₂},      C(x₃, x₂) = {k₂, k₃}. 

Agreement indices express the degree of agreement with the preference of x_i over x_j .

We will calculate agreement indices using formulas

where  c_ij is the value of the index of agreement with the preference of the alternative x_i over x_j;

c_ki is weight factor of the criterion k_i ; 

с is the sum of the coefficients of the criteria's importance;

m is the number of criteria.

In our example, c_k1=5 – Mathematics, c_k2=3 – Pphysics, c_k3=2 – Computer graphics, respectively, с = c_k1 + c_k2 + c_k3 =5+3+2=10.

We will calculate the values of the agreement index matrix:

c₁₂=( c_k1+с_k3)/( c_k1 + c_k2 + c_k3)=(5+2)/(5+3+2)=7/10=0.7;

c₁₃=( c_k1+с_k3)/( c_k1 + c_k2 + c_k3)=(5+2)/(5+3+2)=7/10=0.7;

c₂₁=( c_k1+с_k2)/( c_k1 + c_k2 + c_k3)=(5+3)/(5+3+2)=8/10=0.8;

c₂₃=( c_k1+с_k3)/( c_k1 + c_k2 + c_k3 k3)=(5+2)/(5+3+2)=7/10=0.7;

c₃₁=( c_k2)/( c_k1 + c_k2 + c_k3)=(3)/(5+3+2)=3/10=0.3;

c₃₂=( c_k2+ c_k3)/( c_k1 + c_k2 + c_k3)=(3+2)/(5+3+2)=5/10=0.5.

Matrix of agreement indices C(x_i, x_j):

Let's build a matrix of indices of disagreement with the preference of objects.

Indices of disagreement express the degree of disagreement with the preference of x_i over x_j.

The second class D(x_i, x_j) includes pairs of objects (x_i, x_j) according to the criteria k_i, for which in the graphs G_i there are no arcs (x_i, x_j):

На критеріальній мові визначимо відсутність переваг альтернатив, виконуючи попарні порівняння. Альтернатива x₁ гірше ніж x₂ за критеріями k₂; альтернатива x₁ гірше ніж x₃ за критерієм k₁₂; альтернатива x₂ гірше ніж x₁ за критерієми k₁₃ і т.д.:

In criterion language, we will determine the lack of advantages of alternatives by performing pairwise comparisons. Alternative x₁ is worse than x₂ according to k₂ criteria; alternative x₁ is worse than x₃ according to the criterion k₁₂; the alternative x₂ is worse than x₁ according to the criteria k₁₃, etc.:

D(x1, x2) = {k2},       D(x1, x3) = {k2},

D(x2, x1) = {k3},       D(x2, x3) = {k2},

D(x3, x1) = {k1, k3},  D(x3, x2) = {k1} 

We will calculate the disagreement indices as follows:

,

where d=2 is the normalizing coefficient, which is equal to the maximum difference of grades on the entire set of criteria. 

In our original table, the maximum score is equal to 5, and minimum is equal to 3, so d=5-3=2.

We will calculate the values of the matrix of disagreement indices:

d₁₂= |y₁₂-y₂₂|/d=|3-4|/ 2 =1/2=0.5 (по предмету k2);

d₁₃= |y₁₂-y₃₂|/d=|3-5|/ 2 =2/2=1 (по предмету k2);

d₂₁= |y₂₃-y₁₃|/d=|3-4|/ 2 =1/2=0.5 (по предмету k3);

d₂₃= |y₂₂-y₃₂|/ d =|4-5|/ 2 =1/2=0.5 (по предмету k2);

d₃₁= max{|y₃₁-y₁₁|;|y₃₃-y₁₃|}/ d =max{|4-5|; |3-4|}/ 2 =1/2=0.5; (by subjects k₁, k₃);

d₃₂= |y₃₁-y₂₁|/d =|4-5|/ 2 =1/2=0.5 (by subject k1).

Matrix of disagreement indices D(x_i, x_j):

Let's introduce the preference ratio on the objects through the threshold values p for the agreement indices (it should be closer to one) and q for the disagreement indices (it should be closer to zero).

The object x_i has precedence over the object x_j, if c(x_i, x_j) ≥ p and d(x_i, x_j) ≤ q, that is, the following conditions are met: 

• set of criteria (taking into account their relative importance) according to which the alternative  has a sufficient advantage (more than the threshold p);

• evaluations according to other criteria do not provide sufficient grounds for rejecting the preference (threshold q), the degree of distrust in this assumption does not exceed the permissible limit q.

Let's build a generalized preference graph for threshold values {1,0}:

For thresholds {1,0} all students are equal, it is impossible to make a choice.

Let's build a generalized preference graph for threshold values {0.8, 0.5}:

In this case, it can be concluded that preference should be given to the student х₂.

Conclusions:

1) the method is designed to solve tasks in which a given number of the best alternatives must be selected from the available set of alternatives, taking into account their evaluations according to several criteria, as well as the importance of these criteria;

2) the application of the method made it possible to choose the best candidate for the scholarship.