La scelta fra le alternative:i metodi Electre

I metodi Electre

• Electre = ELimination Et Choix Traduisant la REalité

• scopo:

mettere a punto un metodo decisionale il più aderente possibile alla realtà

• rifiutano a priori il rigore assiomatico

sono tollerate contraddizioni matematiche

• seguono concretamente il processo decisionale

• assecondano l’irrazionalità del decisore

dipendenza dalle alternative irrilevanti

inconsistenza dei confronti a coppie

incompletezza (= incomparabilità tra 2 alternative)

Perché introdurre l’incompletezza?

in teoria:

assioma di completezza

il decisore, posto di fronte a due alternative A e B, deve essere sempre in grado di esprimere la sua preferenzao indifferenza

non è tollerata l’incertezza

nella realtà:

i sensi umani hanno capacità di discriminazione finita e operano per classi

la compensazione tra due alternative con opportuni pesi non sempre è possibile

la percezione della differenza di prestazione è soggettiva

incompletezza

I metodi Electre: elementi comuni

• ammettono inconsistenza (caduta dell’assioma di transitività)e incomparabilità (caduta dell’assioma di completezza)

• analisi di concordanza

valutazione dei fattori (criteri) che non si oppongono al fatto che un’alternativa sia meglio di un’altra

• analisi di discordanza

misura del rammarico nello scegliere un’alternativa piuttosto che un’altra

• attribuzione di pesi ai criteri secondo le preferenze

• verifica dell’esistenza di relazioni di surclassamento tra coppie di alternative (sulla base di soglie di concordanza e discordanza)

• creazione di un ordinamento delle alternative ed eventuale rappresentazione per mezzo di un grafo dei surclassamenti

Electre I

Il punto di partenza

A1 A2 A3

x1 ux1(A1) ux1

(A2) ux1(A3)

x2 ux2(A1) ux2

(A2) ux2(A3)

x3 ux3(A1) ux3

(A2) ux3(A3)

x4 ux4(A1) ux4

(A2) ux4(A3)

w1

w2

w3

w4

matrice delle prestazioni

vettore dei pesi

A1 A2 A3

x1 1 0.6 0.4

x2 0.7 0.5 1

x3 0.8 1 0.8

x4 0.8 1 0.6

0.3

0.4

0.2

0.1

Il punto di partenza

matrice delle prestazioni

vettore dei pesi

• coefficiente di concordanza:

• tiene conto dell’insieme dei criteri che non si oppongono al fatto che l’alternativa i sia meglio dell’alternativa j

• esprime il grado con cui si concorda sul fatto che i è migliore di j

• rappresenta la soddisfazione che prova il decisore scegliendo i anziché j

Concordanza

cij =

S wkk I+ij U I=ij

S wkk

I+ij =

insieme dei criteri per i quali l’alternativa i è preferita all’alternativa j

I=ij =

insieme dei criteri per i quali l’alternativa i è equivalente all’alternativa j

S wk = 0.3+0.4 = 0.7k I+12 U I=12

I+12A1 A2 A3

x1 1 0.6 0.4

x2 0.7 0.5 1

x3 0.8 1 0.8

x4 0.8 1 0.6

0.3

0.4

0.2

0.1

Concordanza

>

>

<

<

0.7c12 =

S wk = 1k

Matrice di concordanza

A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

cij [0,1]cij + cji = 1 I=ij = Ø

• coefficiente di discordanza:

• tiene conto delle differenze di prestazione tra l’alternativa i e l’alternativa j

• quantifica il grado con cui alternativa i è peggiore della j

• rappresenta il rammarico che prova il decisore scegliendo i anziché j

Discordanza

I-ij =

insieme dei criteri per i quali l’alternativa j è preferita all’alternativa i

dij =max wk |uxk

(Aj) - uxk(Ai)|

max wk |uxk(Aj) - uxk

(Ai)|k I-ij

k

I-12

A1 A2 A3

x1 1 0.6 0.4

x2 0.7 0.5 1

x3 0.8 1 0.8

x4 0.8 1 0.6

0.3

0.4

0.2

0.1

Discordanza

>

>

<

<

0.33d12 =

max wk |uxk(A2) - uxk

(A1)| = w3 |ux3(A2) – ux3

(A1)| = 0.2×|1-0.8| = 0.04 k I-12

max wk |uxk(A2) - uxk

(A1)| = w1 |ux1(A2) – ux1

(A1)| = 0.3×|0.6-1| = 0.12 k I

Matrice di discordanza

A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

dij [0,1]

Soglie di concordanza e discordanza

soglia di concordanza Sc

(0 < Sc < 1)

se cij Sc

i criteri per cui i è preferibile a j (area di non conflitto) sono sufficientemente importanti

se cij < Sc

i non surclassa j perché il conflitto è troppo alto (area di non conflitto troppo piccola)

soglia di discordanza Sd

(0 < Sd < 1)

se dij > Sd

i non surclassa j perché la differenza di prestazione tra i e j (area di conflitto) giustifica un veto alla scelta di i rispetto a j

se dij Sd

i criteri discordanti non sono abbastanza importanti da porre un veto sulla scelta di i rispetto a j

Determinazione delle soglie

• la determinazione delle soglie rappresenta una fase critica del metodo Electre I

• spesso si assumono come soglie i valori medi degli indici di concordanza e di discordanza:

S S ciji=1

n

j=1j i

n1

n(n-1)Sc =

S S diji=1

n

j=1j i

n1

n(n-1)Sd =

La relazione di surclassamento

i surclassa j se e solo se (cij Sc) e (dij Sd)

A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

A1 A2 A3

A1 - 1 1

A2 0 - 0

A3 0 0 -

Sc=0.533Sd=0.717

La relazione di surclassamento

la matrice di surclassamento può essere rappresentata sotto forma di grafo orientato

1 2

3

nodi:alternative

archi:relazioni di surclassamento

A1 A2 A3

A1 - 1 1

A2 0 - 0

A3 0 0 -

La ricerca del nucleo

• nucleo:

• insieme delle alternative tra loro non comparabili (ovvero non surclassate da nessun’altra alternativa)

• identificato a partire dal grafo orientato eliminando le alternative surclassate

• tutte le alternative che appartengono al nucleo sono tra loro non comparabili, mentre quelle che non appartengono al nucleo sono surclassate da almeno una alternativa del nucleo

• le alternative del nucleo rappresentano quelle tra cui il decisore dovrà effettuare una scelta di tipo politico

1 2

4

65

3

Electre I: problematiche

• non genera un ordinamento

• tranne che per grafi completi (nessun nodo isolato) e transitivi (per i quali vale la relazione di transitività tra i nodi)

• elimina solo alcune alternative

• la scelta delle soglie è un fattore critico

• è soggettiva

• l’uso delle medie dei coefficienti di concordanza/discordanza come soglie manca di un preciso significato pratico

• influenza l’ordinamento

Electre II

Grafo forte e grafo debole

• si introducono due coppie di soglie: debole e forte

0 < ScD < Sc

F < 1, 0 < SdF < Sd

D < 1

• si generano due grafi di surclassamento:

• uno forte, più rigido e restrittivo e quindi più povero di surclassamenti, e con molte incomparabilità

• uno debole, meno restrittivo e quindi più ricco di surclassamenti e con poche incomparabilità

1

2

4

65

3

7

9

8

1

2

4

65

3

7

9

8

Ordinamento delle alternative

ordinamento discendente:

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

1

2

4

65

3

7

9

8

1

2

4

65

3

7

9

8

Ordinamento delle alternative

ordinamento discendente:

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

1

2

4

65

3

7

9

8

1

2

4

65

3

7

9

8

Ordinamento delle alternative

ordinamento discendente :

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

1

2

4

65

3

7

9

8

1

2

4

65

3

7

9

8

Ordinamento delle alternative

ordinamento discendente :

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

1

2

4

65

3

7

9

8

1

2

4

65

3

7

9

8

{1,2}

Ordinamento delle alternative

ordinamento discendente :

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

4

65

3

7

9

8

4

65

3

7

9

8

Ordinamento delle alternative

ordinamento discendente :

• si estraggono dal grafo forte tutte le alternative non surclassate

• tra queste, si scartano quelle eventualmente surclassate nel grafo debole

• si assegnano le alternative rimaste alla prima classe di ordinamento

• si eliminano dai grafi le alternative ordinate e i rispettivi archi uscenti

• si reitera il processo assegnando via via le alternative selezionate a classi di ordinamento successive

4

65

3

7

9

8

4

65

3

7

9

8

{3}

Ordinamento delle alternative

• si ripete poi la procedura per generare un ordinamento ascendente (in modo analogo ma invertendo i versi delle frecce)

• si ottengono quindi due ordinamenti che in generale possono essere differenti:

ordinamento discendente

classe: I II III IV V

alternative: {1,2} {3} {5} {4,6} {7,8,9}

ordinamento ascendente

classe: V IV III II I

alternative: {7,8,9} {3,6} {4} {1,5} {2}

Ordinamento medio

• poiché i due ordinamenti possono essere differenti, un metodo per generare un ordinamento finale consiste nel calcolare la posizione media delle alternative:

• tuttavia:• l’ordinamento è comunque parziale

• operare una media tra ordinamenti contraddittori è un’operazione quanto meno discutibile

1 2 3 4 5 6 7 8 9

1 1 2 4 3 4 5 5 5

2 1 4 3 2 4 5 5 5

1.5 1 3 3.5 2.5 4 5 5 5

alternativa

ordinamento disc.

ordinamento asc.

ordinamento medio

Il metodo della dominanza debole

• secondo l’approccio basato sulle soglie,i surclassa j se e solo se (cij Sc) e (dij Sd)

• nel caso in cui Sc = 1 e Sd = 0 ci si riconduce al concetto di dominanza di Pareto: i domina j se è migliore per almeno un criterio senza essere peggiore per gli altri

• nel caso in cui Sc<1 e Sd>0 si passa da un concetto di dominanza assoluta (paretiana) a un concetto di dominanza debole (surclassamento)

• al variare dei valori di Sc e Sd è possibile esplorare come varia la dominanza di un’alternativa sulle altre

i surclassa j se e solo se (cij Sc) e (dij Sd)

ad esempio, per Sc = 0.5 e Sd = 0.5

A1 surclassa A2 (c12=0.7>0.5 e d12=0.33<0.5)

A3 non surclassa A2 (c23=0.4<0.5 e d23=0.3<0.5)

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

L’area di dominanza

A2 è surclassata da A1 per Sc 0.7 e Sd 0.33

L’area di dominanza

0

0

1

1

Sd

Sc

A2 è surclassata da A3 per Sc 0.4 e Sd 0.3

i surclassa j se e solo se (cij Sc) e (dij Sd)

A2A2

l’area rappresenta l’area di dominanza

per l’alternativa A2, ovvero l’insieme delle coppie

di valori Sc-Sd per cui A2 è surclassata da almeno

un’altra alternativa

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

Ordinamento

• è possibile ordinare le alternative in base alle dimensioni delle aree di dominanza:

infatti, quanto più è ampia la zona del piano Sc-Sd in cui un’alternativa è surclassata, tanto meno l’alternativa è soddisfacente

A1 A3 A2

0

0

1

1

Sd

Sc

A2

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

A3

A1

Il metodo degli indici di concordanza/discordanza

• date le matrici C e D si ricavano un indice assoluto di concordanza e un indice assoluto di discordanza per ogni alternativa:

ICi = S cij - S cjij=1

n

j=1

n

IDi = S dij - S djij=1

n

j=1

n

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

D A1 A2 A3

A1 - 0.33 0.67

A2 1 - 1

A3 1 0.3 -

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

C A1 A2 A3

A1 - 0.7 0.6

A2 0.3 - 0.6

A3 0.6 0.4 -

IC1 = = 0.4(0.7+0.6) - (0.3+0.6)

= -1 ID1 = (0.33+0.67) - (1+1)

Ordinamento

• le alternative vengono ordinate in senso discendente rispetto all’indice assoluto di concordanza e in senso ascendente rispetto all’indice assoluto di discordanza:

IC1 = 0.4; IC2 = -0.2; IC3 = -0.2 A1 A2, A3

ID1 = -1; ID2 = 1.37; ID3 = -0.37 A1 A2 A3

• i due ordinamenti non coincidono!

Electre III

Funzione di concordanza per criterio

• per ogni criterio k vengono introdotte una soglia di indifferenzaqk e una soglia di preferenza stretta pk

• entrambe hanno un significato fisico e sono legate alla differenza di prestazioni tra due alternative rispetto al criterio considerato

cij,k

uxk(Aj) – uxk

(Ai)

0

1

0 qk pk

niente in contrario al fatto che Ai sia preferita a Aj

Aj è debolmente preferita a Ai

Aj è decisamente preferita a Ai

Funzione di discordanza per criterio

• per ogni criterio k viene introdotta una soglia di veto vk

oltre alla soglia di preferenza stretta pk

dij,k

uxk(Aj) – uxk

(Ai)

0

1

0 pk vk

nessun rammarico scegliendo Ai

anziché Aj

la scelta di Ai invece di Aj è causa di rammarico

Aj è incomparabile con Ai

Matrice di concordanza

• sulla base delle concordanze viene generata una matrice di concordanza per ogni criterio

• si ricava poi una matrice generale di concordanza come somma pesata delle matrici per criterio:

n

cij =

S wk cij,kk =1

S wkk =1

n

Matrice di credibilità dei surclassamenti

• i livelli di concordanza vengono poi attenuati sulla base dei valori di discordanza

• si ottiene così una matrice di credibilità dei surclassamenti D

• se fra tutti i criteri ve n’è almeno uno per cui la discordanza è 1, dij=0 la credibilità del surclassamento è nulla

• se per nessun criterio dij,k > cij allora dij= cij

la credibilità del surclassamento coincide con la concordanza

• in tutti gli altri casi dij< cij

la credibilità del surclassamento è inferiore alla concordanza

dij = cij ×1- dij,k

k F 1- cij

P con F = {k | dij,k > cij }

Soglia di discriminazione

• ottenuta la matrice D, si definisce una soglia di discriminazioneSd sulla base della quale effettuare la scelta tra due alternative:

• l’alternativa i surclassa l’alternativa j se

• la soglia di discriminazione non è costante, ma è funzione di dij

• ovvero, tanto maggiore è il livello di conflitto nella scelta tra le alternative (dij piccolo) tanto più alta è la soglia da superare per accettare il surclassamento di i su j

dij > dji

dij - dji > Sdij{

Sdij = a - b × dij

Distillazione delle alternative

• definite le soglie di discriminazione, un algoritmo di distillazione consente di ricavare un ordinamento discendente e un ordinamento ascendente delle alternative

• un’alternativa sta tanto più in alto nell’ordinamento quanto maggiore è la credibilità con cui surclassa le altre alternative

Algoritmo di distillazione

ordinamento discendente:

1) nella matrice D si determina l = max(dij)

2) si calcola la soglia di discriminazione Sl = a - b × l

3) si determina un livello a di credibilità come a = l - Sl

4) si attribuisce a ogni alternativa Ai un a-punteggio così definito:

• +1 per ogni alternativa surclassata da Ai con credibilità a

• -1 per ogni alternativa che surclassa Ai con credibilità a

5) si selezionano le alternative con a-punteggio massimo:

• se è una sola, la si inserisce in classifica, la si elimina da D e si itera l’algoritmo fino ad esaurimento delle alternative

• se sono più di una, si estrae da D la sottomatrice che le contiene e si applica l’algoritmo alla sottomatrice

Ordinamento complessivo

ordinamento ascendente:

• si sviluppa in modo analogo all’algoritmo di ordinamento discendente, ma selezionando via via le alternative cona-punteggio minimo

• sulla base dei due ordinamenti discendente e ascendente si ottiene infine un ordinamento complessivo (parziale) che tiene conto delle incomparabilità

ord. discendente: A4 A7 A3 A1 A2 A5, A6

ord. ascendente: A4 A3 A5 A1 A2 A6, A7

4 3 1 2 6

7

5

4 3 1 2 6

7

5

Electre IV

• l’attribuzione dei pesi ai criteri rappresenta una fase critica dei metodi Electre precedenti Electre IV non attribuisce pesi ai criteri

• utilizza• soglie di indifferenza, preferenza stretta e veto

• contatori di preferenze (per quanti criteri i è preferita a j?)

• categorie di surclassamento (quasi dominanza, dominanza canonica, pseudo-dominanza, veto-dominanza)

• genera una matrice di credibilità dei surclassamenti sulla base della quale vengono generati due ordinamenti

• l’ordinamento finale è ricavato con la stessa procedura utilizzata in Electre III è parziale e tiene conto delle incomparabilità

• Electre IV è applicabile solo in casi in cui i criteri hanno importanza simile (nessun criterio predominante e nessun criterio trascurabile)

Metodi Electre: ma si usano davvero?

DPR 554/1999(Regolamento di attuazione della legge Merloni sui Lavori Pubblici)