Teoria da Decisão - Universidade Federal de Minas Geraislusoba/disciplinas/eee910/slides/lusoba/TD5-metodos... · PROMETHEE I Preference Ranking Organization Method for Enrichment

Teoria da DecisãoMétodos Baseados em Relações de Sobreclassificação

Prof. Lucas S. Batista

[email protected]

www.ppgee.ufmg.br/∼lusoba

Universidade Federal de Minas GeraisPrograma de Pós-Graduação em Engenharia Elétrica, Brasil

Métodos de Sobreclassificação Literatura Especializada

Apresentação

Sumário

1 Métodos de SobreclassificaçãoApresentaçãoMétodos baseados em relações de sobreclassificação

2 / 38


Apresentação

Introdução

Questão crucial em tomada de decisãoComo considerar simultaneamente todos os critérios para a compara-ção das ações possíveis?

Procedimentos de agregação multicritério:

Síntese de critério;

Síntese de sistema de relações de preferência.

3 / 38


Apresentação

Introdução

Síntese de sistema de relações de preferência

Distingue-se da síntese de critério principalmente por não consi-derar cada ação aaa ∈ A separadamente.

Relações de preferência são estabelecidas a partir de compara-ções par a par entre as alternativas.

Não garante uma pré-ordem completa em A.

4 / 38


Apresentação

Introdução

Síntese de sistema de relações de preferência

Esse sistema de preferência pode ser expresso por meio de rela-ções binárias (modelo clássico ou nebuloso).

Algumas dificuldades:

comparações par a par podem gerar intransitividades;

incomparabilidade entre ações podem ocorrer;

uma regra adicional de decisão pode ser necessária.

5 / 38


Apresentação

Introdução

Métodos baseados em síntese de relações de preferência

Escola Francesa (década de 1960)

Métodos baseados em relações de sobreclassificaçãoa.

Multicriteria Decision Aid (MCDA).

Atitude construtiva:

Basea-se em modelos mais reais da preferência humana;

Auxilia o decisor a construir suas preferências.

asurclassement ou outranking

6 / 38


Apresentação

Introdução

Escola Francesa

ELECTRE I Elimination Et Choix Traduisant la RealitéELECTRE IIELECTRE IIIELECTRE IV

ELECTRE TRIPROMETHEE I Preference Ranking Organization Method for

Enrichment EvaluationsPROMETHEE IIPROMETHEE V

Tabela : Principais Métodos da Escola Francesa

7 / 38


Métodos baseados em relações de sobreclassificação

Sumário

1 Métodos de SobreclassificaçãoApresentaçãoMétodos baseados em relações de sobreclassificação

8 / 38



Definições

Notação

Seja um conjunto de ações ou alternativas aaai ∈ A, i = 1, . . . ,n e umconjunto de critérios cj , j = 1, . . . ,nc . A avaliação da ação aaai pelocritério cj é dada por cj(aaai).

Representação da Sobreclassificação

As relações entre diferentes ações podem ser representadas numgrafo direcionado G. Uma seta de aaai para aaaj indica que a ação aaaisobreclassifica (preferência ampla) aaaj .

9 / 38



Definições

Exemplo de Sobreclassificação

Represente o grafo das relações entre as ações.

aaa1 aaa2 aaa3 aaa4 aaa5 aaa6 aaa7aaa1aaa2 Saaa3 Saaa4 S S Saaa5 S S Saaa6aaa7

Tabela : Exemplo de relações de sobreclassificação entre ações

Nota: aaai Saaaj : aaai sobreclassifica aaaj .

10 / 38



Definições

Kernel de um GrafoO kernel de um grafo é composto pelo conjunto das ações tal que:

todas as ações que não pertencem ao kernel são sobreclassifi-cadas por pelo menos uma ação do kernel;

as ações do kernel não sobreclassificam outras ações do kernel.

Qual o kernel do exemplo anterior?

Existem ações incomparáveis nesse exemplo?

11 / 38



Definições

Índice de concordânciaSeja um conjunto de ações ou alternativas aaai , i = 1, . . . ,n e um con-junto de critérios cj , j = 1, . . . ,nc .

O critério cj é compatível com a hipótese “aaai sobreclassifica aaak ” se aaaié pelo menos tão boa quanto aaak : cj(aaai) ≥ cj(aaak ).

Condição de discordância

A condição de discordância permite ao tomador de decisão recusar asobreclassificação de uma ação sobre outra, se uma oposição muitoalta existe em pelo menos um critério.

12 / 38



ELECTRE I

Proposto por B. Roy em 1968.

‘‘Elimination and Choice Expressing the Reality”.

Permite determinar uma pré-ordem total das ações.

Passos1 Defina pesos wj para cada um dos J = {1, . . . ,nc} critérios.

2 Estabeleça comparações entre cada par (aaai ,aaak ) ∈ A, gerando osseguintes conjuntos de índices:

J+(aaai ,aaak ) = {j ∈ J | cj(aaai) > cj(aaak )}

J=(aaai ,aaak ) = {j ∈ J | cj(aaai) = cj(aaak )}

J−(aaai ,aaak ) = {j ∈ J | cj(aaai) < cj(aaak )}

13 / 38



ELECTRE I

Passos3 Converta as relações entre ações em valores numéricos:

P+(aaai ,aaak ) =∑

j

wj , j ∈ J+(aaai ,aaak )

P=(aaai ,aaak ) =∑

j

wj , j ∈ J=(aaai ,aaak )

P−(aaai ,aaak ) =∑

j

wj , j ∈ J−(aaai ,aaak )

14 / 38



ELECTRE I

Passos4 Calcule o índice de concordância:

Cik =P+(aaai ,aaak ) + P=(aaai ,aaak )∑

j∈Jwj

, 0 ≤ Cik ≤ 1

5 Calcule o índice de discordância:

Dik =

{0, se J−(aaai ,aaak ) = ∅δj max (cj(aaak )− cj(aaai)) , j ∈ J−(aaai ,aaak ), c.c.

tal que δj é o fator de escala associado ao critério cj e 0 ≤ Dik ≤ 1.

15 / 38



ELECTRE I

Passos6 Obtenha as relações de sobreclassificação e as melhores ações:

aaai Saaak ⇐⇒

{Cik ≥ τcDik ≤ τd

τc: limiar de concordância, em geral ≈ 0.7;

τd : limiar de discordância, em geral ≈ 0.3.

16 / 38



ELECTRE I

Suponha as notas de 5 estudantes em 5 matérias

(i,j) M1 M2 M3 M4 M5E1 7 13 8 12 11E2 8 11 11 12 11E3 20 2 10 3 15E4 16 14 16 14 13E5 12 12 8 8 10

Quem é o melhor estudante?

17 / 38



ELECTRE I

Critérios adotados pelo decisor

1 c1: A nota média de todas as matérias deve ser a maior possível;

2 c2: A nota mínima deve ser maior ou igual a 8;

3 c3: A variação em torno da média deve ser a menor possível.

18 / 38



ELECTRE I

Critérios adotados pelo decisor1 c1: A nota média de todas as matérias deve ser a maior possível;

c1(E) =∑

M nota(E ,M)5


c2(E) =

{10, se minM(nota(E ,M)) ≥ 80, c.c.


c3(E) =

√∑M(nota(E ,M)− c1(E))2

5

19 / 38



ELECTRE I

Critérios adotados pelo decisor1 c1: A nota média de todas as matérias deve ser a maior possível;

c1(E) =∑

M nota(E ,M)5


c2(E) =

{10, se minM(nota(E ,M)) ≥ 80, c.c.


c3(E) =

√∑M(nota(E ,M)− c1(E))2

519 / 38



ELECTRE I

Cálculo dos critérios

c1 c2 c3E1 10.2 0 1.035E2 10.6 10 0.606E3 10 0 3.08E4 14.6 10 0.5366E5 10 10 0.8

Tabela : Valores dos critérios

c′1 c′2 c

′3

E1 0.87 0 16.08E2 2.61 20 19.45E3 0 0 0E4 20 20 20E5 0 20 17.9

Tabela : Critérios escalados [0, 20]

Vale notar que o fator de escala adotado é δj = 1/20.

20 / 38



ELECTRE I

Comparações entre estudantes (ações)

J+ E1 E2 E3 E4 E5E1 ∅ {1, 3} ∅ {1}E2 {1, 2, 3} {1, 2, 3} ∅ {1, 3}E3 ∅ ∅ ∅ ∅E4 {1, 2, 3} {1, 3} {1, 2, 3} {1, 3}E5 {2, 3} ∅ {2, 3} ∅

J= E1 E2 E3 E4 E5E1 ∅ {2} ∅ ∅E2 ∅ ∅ {2} {2}E3 {2} ∅ ∅ {1}E4 ∅ {2} ∅ {2}E5 ∅ {2} {1} {2}

J− E1 E2 E3 E4 E5E1 {1, 2, 3} ∅ {1, 2, 3} {2, 3}E2 ∅ ∅ {1, 3} ∅E3 {1, 3} {1, 2, 3} {1, 2, 3} {2, 3}E4 ∅ ∅ ∅ ∅E5 {1} {1, 3} ∅ {1, 3}

21 / 38



ELECTRE I

Cálculo dos coeficientes P+ e P=

Definição dos pesos dos critérios:

w1 = 0.50, w2 = 0.25, w3 = 0.25

P+ E1 E2 E3 E4 E5E1 0 0.75 0 0.5E2 1 1 0 0.75E3 0 0 0 0E4 1 0.75 1 0.75E5 0.5 0 0.5 0

P= E1 E2 E3 E4 E5E1 0 0.25 0 0E2 0 0 0.25 0.25E3 0.25 0 0 0.5E4 0 0.25 0 0.25E5 0 0.25 0.5 0.25

22 / 38



ELECTRE I

Cálculo dos coeficientes de concordância

Cik E1 E2 E3 E4 E5E1 0 1 0 0.5E2 1 1 0.25 1E3 0.25 0 0 0.5E4 1 1 1 1E5 0.5 0.25 1 0.25

Tabela : Coeficiente de concordância Cik

Dik E1 E2 E3 E4 E5E1 1 0 1 1E2 0 0 0.870 0E3 0.804 1 1 1E4 0 0 0 0E5 0.043 0.130 0 1

Tabela : Coeficiente de discordância Dik

23 / 38



ELECTRE I

Relações de sobreclassificação das ações

Considerando que os testes sejam satisfeitos para Cik ≥ 0.75 eDik ≤ 0.25:

Quais Cik satisfazem o teste de concordância?

Quais Dik não satisfazem o teste de discordância?

Esboce o grafo das relações entre as ações.

Qual a ordem de sobreclassificação entre as ações (estudantes)?

24 / 38



ELECTRE I

Discussão

A classificação obtida é coerente: corresponde ao resultado queseria obtido de maneira convencional;

Assim, este método “imita” o pensar humano;

Possui maior capacidade para lidar com grandes quantidades dedados do que o ser humano.

25 / 38



Métodos ELECTRE (Variações)

ELECTRE IS: método ELECTRE I com lógica fuzzy para os ín-dices de concordância e discordância; reduz sensibilidade aosparâmetros definidos pelo decisor.

ELECTRE II: similar ao ELECTRE I, mas modifica a definição dasrelações de sobreclassificação (forte e fraca); elimina circuitos(paradoxo de Condorcet).

ELECTRE III: similar ao ELECTRE II, mas introduz limiares paraas relações de indiferença e preferência estrita entre ações; alta-mente configurável, sendo esta sua principal limitação.

ELECTRE IV: similar ao ELECTRE III, porém elimina a necessi-dade de definição de pesos pelo decisor.

ELECTRE TRI: permite classificar as ações com relação a “açõesde referência”; possui baixa complexidade computacional.

26 / 38



PROMETHEE I

PROMETHEE – “Preference Ranking Organization Method forEnrichment Evaluations” (Brans et al. 1986).

Permite a construção de uma pré-ordem parcial (admite soluçõesequivalentes).

Utiliza uma abordagem de fluxo num grafo de preferências:

define-se funções de preferência entre cada par de ações, e as re-lações de preferência {P, I, J} são dadas pelo fluxo dessas funçõesde preferência entre os nós do grafo.

27 / 38



PROMETHEE I

Relações de preferência

P(aaai ,aaak ) = 0 indica indiferença ou não preferência entre aaai ,aaak ∈ A;

P(aaai ,aaak )→ 0 indica preferência fraca pela ação aaai em relação a aaak ;

P(aaai ,aaak )→ 1 indica preferência forte pela ação aaai em relação a aaak ;

P(aaai ,aaak ) = 1 indica preferência estrita pela ação aaai em relação a aaak .

28 / 38



PROMETHEE I

Conexão entre relações de preferência e critérios

A conexão entre as relações de preferência e os critérios cj ,j = 1, . . . ,nc , é dada por:

Pj(aaai ,aaak ) = G [cj(aaai)− cj(aaak )]

em que 0 < G(x) < 1 e G(x) = 0 para x ≤ 0. Várias generalizaçõesde critérios G(x) são empregadas.

29 / 38



PROMETHEE I

Critério usual:

G(x) =

{0, se x ≤ 01, se x > 0

Quase-critério:

G(x) =

{0, se x ≤ q1, se x > q

Critério linear:

G(x) =

0, se x ≤ 0x/p, se 0 < x ≤ p1, se x > p

30 / 38



PROMETHEE I

Critério degrau:

G(x) =

0, se x ≤ q0.5, se q < x ≤ p1, se x > p

Critério trapezoidal:

G(x) =

0, se x ≤ qx − qp − q

, se q < x ≤ p

1, se x > p

Critério Gaussiano:

G(x) =

{0, se x ≤ 01− exp

(− x

2

2σ2

), se x > 0

31 / 38



PROMETHEE I

Índice de sobreclassificação multiobjetivo

A relação de preferência P(aaai ,aaak ) é dada por:

P(aaai ,aaak ) =

nc∑j=1

wjPj(aaai ,aaak )

nc∑j=1

wj

P(aaai ,aaak )→ 0 indica preferência fraca global de aaai sobre aaak ∀ j .

P(aaai ,aaak )→ 1 indica preferência forte global de aaai sobre aaak ∀ j .

32 / 38



PROMETHEE I

Representação das relações de preferência

Similar ao ELECTRE, as relações de preferência podem ser re-presentadas num grafo direcionado.

Entretanto, agora considera-se arestas (preferências) bidirecio-nais:

P(aaai ,aaak ) =

nc∑j=1

wjPj(aaai ,aaak )

nc∑j=1

wj

33 / 38



PROMETHEE I

Relação de fluxo de preferência

O fluxo líquido no nó aaai é dado pela diferença entre o fluxo depreferência que sai do nó e o fluxo que entra:

φ(aaai) = φ+(aaai)− φ−(aaai)

φ(aaai) =∑

aaak∈AP(aaai ,aaak )−

∑aaak∈A

P(aaak ,aaai)

34 / 38



PROMETHEE I

Relações de sobreclassificação positiva e negativa

Sobreclassificação positiva (S+ = P+ ∪ I+):

aaai P+ aaak ⇔

{se φ+(aaai) > φ+(aaak )

aaai I+ aaak ⇔

{se φ+(aaai) = φ+(aaak )

Sobreclassificação negativa (S− = P− ∪ I−):

aaai P− aaak ⇔

{se φ−(aaai) < φ−(aaak )

aaai I− aaak ⇔

{se φ−(aaai) = φ−(aaak )

35 / 38



PROMETHEE I

Relação de sobreclassificação final

aaai Paaak ⇔

se aaai P

+ aaak ∧ aaai P− aaakou aaai P

+ aaak ∧ aaai I− aaakou aaai I

+ aaak ∧ aaai P− aaak

aaai Iaaak ⇔{

se aaai I+ aaak ∧ aaai I− aaak

aaai Jaaak ⇔{

caso contrário.

36 / 38



PROMETHEE II

PROMETHEE I versus PROMETHEE II

O método PROMETHEE I fornece ao decisor uma classificaçãodas diversas alternativas, porém algumas alternativas podem serincomparáveis.

O método PROMETHEE II elimina a incomparabilidade definindoo seguinte esquema de sobreclassificação (pré-ordem total):

aaai Paaak ⇔{

se φ(aaai) > φ(aaak )

aaai Iaaak ⇔{

se φ(aaai) = φ(aaak )

37 / 38


Literatura Especializada

Y. Collette, P. Siarry, Multiobjective Optimization: Principles and Case Studies, ser.Decision Engineering, Springer, 2003.

L. Y. Maystre, J. Pictet, J. Simos, Méthodes Multicritères ELECTRE, Presses Poly-techniques et Universitaires Romandes, 1994.

J. Figueira, S. Greco, M. Ehrgott, Multiple Criteria Decision Analysis: State of theArt Surveys, Springer Science, 2005.

B. Roy, Decision-Aid and Decision-Making, European Journal of Operational Re-search, 45, p. 324–331, 1990.

Inicio

38 / 38

Métodos de SobreclassificaçãoApresentaçãoMétodos baseados em relações de sobreclassificação

Documents

Teoria da Decisão - Universidade Federal de Minas Geraislusoba/disciplinas/eee910/slides/lusoba/TD5-metodos... · PROMETHEE I Preference Ranking Organization Method for Enrichment