Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi...

55
1 Metodi Decisionali Metodi Decisionali Multi Criterio Multi Criterio Massimo Paolucci ([email protected]) DIST – Università di Genova 2 Metodi Metodi Multicriterio Multicriterio - Introduzione Introduzione Decisione Multicriterio: scelta di una azione o alternativa tra un insieme di alternative ammissibili effettuata sulla base di due o più criteri. Multiple Criteria Decision Making (MCDM) “Processo decisionale in presenza di più criteri” Criterio: indicazione su come valutare un tipo di prestazione misurata per le diverse alternative,ovvero su come deve essere scelta l'alternativa più efficiente rispetto quella prestazione (e.g., il calcolatore meno costoso, la moto più maneggevole, l'auto con i minori consumi) Nel caso del MCDM i criteri in generale sono contrastanti

Transcript of Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi...

Page 1: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

11

Metodi Decisionali Metodi Decisionali Multi CriterioMulti Criterio

Massimo Paolucci([email protected])

DIST – Università di Genova

2

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzioneDecisione Multicriterio: scelta di una azione o alternativa tra un insieme di alternative ammissibili effettuata sulla base di due o più criteri.

Multiple Criteria Decision Making (MCDM)“Processo decisionale in presenza di più criteri”

Criterio: indicazione su come valutare un tipo di prestazione misurata per le diverse alternative,ovvero su come deve essere scelta l'alternativa più efficiente rispetto quella prestazione (e.g., il calcolatore meno costoso, la moto più maneggevole, l'auto con i minori consumi)

Nel caso del MCDM i criteri in generale sono contrastanti

Page 2: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

22

3

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzioneLe alternative considerate possono essere:

• discrete e finite (enumerabili)• continue ed infinite (non enumerabili)

Attributo: misura (valore) di una prestazione di una alternativa; è un parametro; è fornito nel caso di alternative discrete.

Obiettivo: una funzione che misura una prestazione per un'alternativa definita come punto nello spazio delle variabili decisionali; utilizzata nel caso di alternative di tipo continuo.

4

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzioneUn attributo (obiettivo) può fornire direttamente indicazioni sul livello di un criterio (e.g., attributo "il profitto netto in lire" rispetto il criterio "massimizzare il profitto“)

In altri casi un criterio può non avere un attributo (obiettivo)direttamente corrispondente (e.g., criterio "migliorare la qualità di un sistema di trasporto pubblico urbano")

Può esistere in questi casi un attributo (o un insieme di attributi), detto Proxy Attribute, che indirettamente fornisce indicazioni su tale criterio (e.g., attributi "il rapporto tra il tempo medio di percorrenza e la lunghezza del tragitto", "il numero di utenti medi sui mezzi nelle ore di punta")

Page 3: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

33

5

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzionePassi generali di un processo decisionale:1. Inizializzazione (definizione del problema)2. Formulazione del problema (specifica degli attributi o

obiettivi e dei criteri)3. Costruzione del modello (identificazione delle variabili

decisionali, vincoli, formalizzazione di proprietà strutturali, uso di tecniche di rappresentazione come grafi)

4. Analisi, valutazione e decisione (generazione dell'insieme delle alternative ammissibili e stima dei valori degli attributio obiettivi; raccolta di informazioni sullo stato (state of nature) e dei giudizi di preferenza del decisore(i); definizione di una decisione

5. Implementazione (attuazione) della decisione e rivalutazione della decisione (eventuale iterazione del processo)

6

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

Caratteristiche generali di un problema MCDM:• molti criteri

• molti attributi/obiettivi

• conflitto tra i criteri

• incommensurabilità tra attributi/obiettivi

• scelta tra un insieme finito di alternative definite esplicitamente oppure un insieme infinito di alternative definite implicitamente

Page 4: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

44

7

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

Approccio generale al MCDM:• Utilizzare le informazioni note (factual elements) ed i

giudizi espressi dal decisore (value elements) per determinare una decisione di compromesso

• Ovvero, aiutare il decisore a selezionare l’alternativa più coerente con la sua struttura di preferenza

• Tipi di regole decisionali (Decision Rules):Optimizing rule(stabilire un ordinamento completo tra tutte le alternative -l'ottimo)Satisficing rule(determinare un'alternativa soddisfacente senza ottimizzare globalmente)

8

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

Formulazione dei problemi MCDM

x = vettore delle variabili decisionali

fj(.) = j-mo obiettivo

X= insieme delle alternative ammissibili

[ ]n

Tk1

Xx.t.s

)x(f),...,x(f)x(Fmax

R⊆∈

=

Page 5: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

55

9

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

Formulazione dei problemi MCDM• X può essere infinito ⇒ alternative definite

implicitamente per mezzo di relazioni (vincoli) matematici

• X può essere finito ⇒ 'insieme discreto delle alternative ammissibili A=F(x): x∈X; le funzioni fj(.) rappresentano la misura della prestazione j-ma di una alternativa

• Per una alternativa i-ma Ai corrispondente al punto xi, xij=fj(xi) è il valore dell'attributo j-mo. Nel caso di alternative discrete, nella fase di analisi vengono individuati gli attributi e le alternative. Queste vengono distinte tra loro per i diversi valori assunti dagli attributi (Ai=[ xij, j=1,...,k] con k numero degli attributi).

10

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

I problemi di MCDM si distinguono in:• Problemi Multiattributo (MultiAttribute Decision

Making, MADM) (selezione tra un numero finito di alternative discrete)

• Problemi Multiobiettivo (MultiObjective DecisionMaking, MODM) (progettazione della miglior alternativa, alternative infinite conosciute in maniera implicita)

Page 6: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

66

11

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzioneNel caso dei problemi MCDM verrà considerato un contesto di tipo deterministico e la presenza di un singolo decisore

Una regola decisionale molto generale applicata per i problemi MCDM consiste nei seguenti due passi:

1. individuare l'insieme delle alternative efficienti (non dominate, Pareto ottimali);

2. selezionare l'alternativa efficiente di compromesso utilizzando le informazioni di preferenza che il decisore mette a disposizione.

A volte i passi non sono completamente distinti.

12

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

Alternative efficienti

DefinizioneUna soluzione (alternativa) ammissibile x0∈X èefficiente (non dominata, Pareto ottima) se e solo se non esiste x∈X tale che fj(x)≥ fj(x0) per ogni j∈K=1,...,k e fj(x)≠fj(x0) per almeno un j∈K

Le alternative efficienti sono quelle per cui non esiste un’altra alternativa ammissibile in grado di produrre un miglioramento rispetto un obiettivo/attributo senza peggiorarne almeno un altro.

Page 7: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

77

13

Metodi Metodi MulticriterioMulticriterio -- IntroduzioneIntroduzione

I metodi decisionali multicriterio (fase di analisi e valutazione delle alternative e decisione) hanno tutti una struttura comune

Metodo MCDM(decision rule, ipotesi

sulla struttura di preferenza del decisore)

Formulazione del problema

(obiettivi e alternative)

Informazioni fornite dal decisore

(giudizi di preferenza)

Decisione(Alternativa scelta,

ordinamento trale alternative)

14

Metodi Metodi MulticriterioMulticriterio –– Metodi MADMMetodi MADM

Metodi Decisionali Multiattributo (MADM)• Un problema MADM è definito dalla Matrice delle

Decisioni che descrive le alternative (finite) da considerare

• In generale sono presenti m alternative Ai, i=1,...,m, definite per mezzo di n attributi xj, j=1,..,n

• Il valore assunto dall'attributo xj di un'alternativa Ai èindicato con xij

• L'alternativa Ai è definita come Ai=[xi1,...,xin]• La matrice delle decisioni D è una matrice mxn tale

cheD=[xij, i=1,...,m; j=1,...,n]

Page 8: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

88

15

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi Decisionali Multiattributo (MADM)

• L'insieme delle alternative (la matrice D) èdeterminato dall'analisi del problema decisionale:

individuazione dei criteri ed attributi

selezione di un insieme di alternative candidate

valutazione dei valori degli attributi per le alternative

16

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Un esempio• Una compagnia aerea vuole scegliere quale tipo di

aereo da trasporto acquistare tra 4 possibili candidati

• Vengono individuati 6 attributi rilevanti:

x1 Velocità massima (mach)x2 Raggio di azione (km)x3 Carico massimo trasportabile (Kg)x4 Costo (M$)x5 Affidabilità (qualitativo)x6 Manovrabilità (qualitativo)

Page 9: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

99

17

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

La matrice delle decisioni D

• Non c'è un'alternativa che è chiaramente la migliore

• Non tutti gli attributi sono numerici

x1 x2 x3 x4 x5 x6

A1 2.0 1500 20000 5.5 Media Molto Alta

A2 2.5 2700 18000 6.5 Bassa Media

A3 1.8 2000 21000 4.5 Alta Alta

A4 2.2 1800 20000 5.0 Media Media

18

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Scalarizzazione degli attributi qualitativi• In generale i valori di un attributo possono essere

forniti in una delle seguenti scale:

scala nominale (identificatori)

scala ordinale (ordinamento tra gli identificatori)

scala di intervalli (significativa la differenza tra i valori)

scala di rapporti (invarianza rispetto il rapporto tra valori di scale diverse per la stessa misura; origine)

Page 10: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1010

19

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Scalarizzazione degli attributi qualitativi• Gli attributi qualitativi dell'esempio possono essere

scalarizzati associandoli ad una scala di intervalli arbitraria che ne conservi l'ordine

• Una possibilità è assegnare ai valori qualitativi degli intervalli fuzzy centrati nel punto medio:

Molto Basso = [0,2]; Basso = [2,4]; Medio = [4,6];Alto = [6,8]; Molto Alto = [8,10]

In generale su tali intervalli può essere definita una funzione di appartenenza (membership) che specifica la corrispondenza tra numero e valore qualitativo(e.g., 6,3 potrebbe avere 0.2 di appartenenza a Medio e 0.8 ad

Alto)

20

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

La matrice scalarizzata

• Non esistono nell'esempio alternative dominate

• Dominanza (alternative discrete)

Date due alternative distinte Ai e Ak, Ai domina Ak

(Ai≥Ak) se e solo se xij≥xkj per ogni j=1,...,n (gli attributi misurano tutti dei benefici)

x1 x2 x3 x4 x5 x6

A1 2.0 1500 20000 5.5 5 9

A2 2.5 2700 18000 6.5 3 5

A3 1.8 2000 21000 4.5 7 7

A4 2.2 1800 20000 5.0 5 5

Page 11: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1111

21

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Il concetto di compensazione• Compensazione tra attributi:

la possibilità nella valutazione di un'alternativa di compensare un valore "non buono" di un attributo con un valore "buono" di un altro attributo

• Quando un decisore accetta la compensazione tra due attributi è possibile definire un trade-off tra di essi, ovvero una misura dello scambio

• Esempio: sono disposto a rinunciare in capacità di memoria per un calcolatore per ridurre il costo dello stesso

22

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Il concetto di compensazione• I metodi MADM possono essere classificati come:

non compensatori (non permettono di esprimere trade-off tra gli attributi)compensatori (costruzione di una valutazione globale dell'alternativa); tre modelli generali:– Scoring models (definiscono un punteggio

globale)– Compromizing models (valutano la prossimità

rispetto l'ideale)– Concordance models (valutano in base alla

concordanza con i giudizi del decisore)

Page 12: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1212

23

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMClassificazione dei metodi MADM in funzione del tipo di informazione di preferenza fornita dal DM1. Nessuna informazione [Dominanza, Maximin,

Maximax]2. Informazione sugli attributi

2.1 Livelli standard [Disgiuntivo, Congiuntivo]2.2. Informazione ordinale [Lessicografico]2.3. Informazione cardinale [Simple Additive Weighting

(SAW), Analytic Hierachy Process (AHP)]2.4. Tasso marginale di sostituzione [Trade-off gerarchici]

3. Informazione sulle alternative3.1 Preferenza tra coppie [LINMAP]

24

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore

• Analisi di dominanza

Si eliminano dalla matrice delle decisioni le alternative dominate e si propongono al decisore le rimanenti

Page 13: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1313

25

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore• MAXIMIN

Ciascuna alternativa viene rappresentata dal valore dell'attributo peggiore (caratteristica piùdebole) e si seleziona l'alternativa (le alternative) con il migliore tra tali valori (approccio pessimista)

⎭⎬⎫

⎩⎨⎧

==⎥⎦

⎤⎢⎣

⎡== n,...,1j;m,...,1i,xminmaxargi:AA ij

jii

*

26

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore• MAXIMIN - caratteristiche

Gli attributi devono essere commensurabili (misurati rispetto una scala comune)

Utilizza un sottoinsime delle informazioni disponibili

Non esiste la possibilità di compensare tra loro i valori degli attributi

Page 14: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1414

27

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore• La normalizzazione degli attributi• Trasformare xij, misurato in una scala particolare, in

rij con 0≤rij≤1

a. (beneficio)

b. (costo)

c. (costo)

maxj

ijij

x

xr = ij

imaxj xmaxx =

maxj

ijij

x

x1r −=

ijij x

1x ←ij

minj

ij x

xr = ij

iminj xminx =

28

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore

d. (beneficio)

e. (costo)

f. (costo)

minj

maxj

minjij

ijxx

xxr

−=

minj

maxj

ijmaxj

ijxx

xxr

−=

∑=

=m

1i

2ij

ijij

x

xr

Page 15: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1515

29

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore

• Esempio: la scelta tra gli aerei da trasporto usando (a) e (c)

r1 r2 r3 r4 r5 r6

A1 0.8 0.56 0.95 0.82 0.71 1.0

A2 1.0 1.0 0.86 0.69 0.43 0.56

A3 0.72 0.74 1.0 1.0 1.0 0.78

A4 0.88 0.67 0.95 0.9 0.71 0.56

30

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore

• Esempio: MAXIMIN

r1 r2 r3 r4 r5 r6

A1 0.8 0.56 0.95 0.82 0.71 1.0

A2 1.0 1.0 0.86 0.69 0.43 0.56

A3 0.72 0.74 1.0 1.0 1.0 0.78

A4 0.88 0.67 0.95 0.9 0.71 0.56

0.56

0.43

0.72

0.56

A3

Page 16: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1616

31

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore• MAXIMAX

Ciascuna alternativa viene rappresentata dal valore dell'attributo migliore (caratteristica piùforte) e si seleziona l'alternativa (le alternative) con il migliore tra tali valori (approccio ottimista)

stesse caratteristiche del MAXIMIN

⎭⎬⎫

⎩⎨⎧

==⎥⎦

⎤⎢⎣

⎡== n,...,1j;m,...,1i,xmaxmaxargi:AA ijji

i*

32

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore

• Esempio: MAXIMAX

r1 r2 r3 r4 r5 r6

A1 0.8 0.56 0.95 0.82 0.71 1.0

A2 1.0 1.0 0.86 0.69 0.43 0.56

A3 0.72 0.74 1.0 1.0 1.0 0.78

A4 0.88 0.67 0.95 0.9 0.71 0.56

1.0 (x6)

1.0 (x1,x2)

1.0 (x3,x4,x5)

0.95 (x3)

A3

A2

A1

Page 17: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1717

33

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM senza informazione dal decisore• La procedura di Hurwicz

Un compromesso tra MAXIMIN e MAXIMAX

• con 0≤α≤1 α=0 MAXIMAX, α=1 MAXIMIN

⎭⎬⎫

⎩⎨⎧

⎥⎦

⎤⎢⎣

⎡α−+⋅α== ij

jij

jii

* xmax)1(xminmaxargi:AA

34

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM con informazione sugli attributiLivelli StandardIl decisore indica un insieme di livelli di accettabilità per gli attributi

• Metodo CongiuntivoLivelli standard: xj

0, per j∈S⊆1,...,nAi è considerata accettabile se e solo se xij≥xj

0, per j∈S (ipotesi: tutti gli attributi sono benefici)

Caratteristiche:– Attributi non normalizzati– Scale almeno ordinali

Page 18: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1818

35

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - livelli standard• Metodo congiuntivo: esempio

Livelli standard per gli aerei da trasportox0=(2.1, 1500, 20000, 6.0, MEDIA, MEDIA)

⇒ A4 è la sola alternativa accettabile.

x1 x2 x3 x4 x5 x6

A1 2.0 1500 20000 5.5 Media Molto Alta

A2 2.5 2700 18000 6.5 Bassa Media

A3 1.8 2000 21000 4.5 Alta Alta

A4 2.2 1800 20000 5.0 Media Media

36

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - livelli standard

• Metodo disgiuntivoLivelli standard: xj

0, per j∈S⊆1,...,nAi è considerata accettabile se e solo se per almeno un j∈S xij≥xj

0 (ipotesi: tutti gli attributi sono benefici)

Esempio: Livelli standard per gli aerei da trasportox0=(2.4, 2500, 21000, 4.5, MOLTO ALTA, MOLTO ALTA)

⇒ A1, A2, A3 le alternative accettabili.

Page 19: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

1919

37

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMMetodi MADM con informazione sugli attributi

Informazione ordinaleIl decisore indica l'importanza relativa degli attributi. Non è un'informazione quantitativa

• Metodo Lessicografico– Il decisore ordina gli attributi in funzione della

loro importanza– Gli attributi ordinati: x1, x2, ... , xn

– Le alternative: A=A1,...,Am e l'insieme degli indici delle alternative: I=1,...,m

– Il metodo procede iterativamente restringendo l'insieme delle alternative, considerando un attributo alla volta secondo l'ordine fissato.

38

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione ordinale• Metodo Lessicografico

Passo 0: k=0, I0=I

Passo 1: k=1,

Se |I1|=1 fine, altrimenti vai al passo 2

Passo r-mo (generico): k=r,

Se |Ir|=1 fine, altrimenti vai al passo r+1

L'iterazione termina comunque quando k=n.

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

==∈

1hIh

1 xmaxargi:iI0

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

==−∈

hrIh

r xmaxargi:iI1r

Page 20: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2020

39

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione ordinale• Metodo Lessicografico - osservazioni • Se |In|>1 le alternative Ai, i∈In sono considerate equivalenti

• Gli attributi non devono essere commensurabili

• Limitato uso dell'informazione disponibile

• Variante: intervalli di indifferenza ±∆

Esempio: tre alternative e due attributiGli attributi sono benefici.x1 più importante di x2.L'intervallo di indifferenza è ∆=1

con x1 si conclude che A3≈A2; quindi con x2 è scelta A2.

x1 x2

A1 2 6

A2 3 4

A3 4 2

40

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM con informazione sugli attributiInformazione cardinaleIl decisore fornisce una misura dell'importanza degli attributi (pesi). Informazione quantitativa

• Metodo del Simple Additive Weighting (SAW)– Il decisore fornisce un peso wj, j=1,...,n, per

indicare l'importanza di ciascun attributo– Viene costruito un punteggio (score) per ogni

alternativa– Viene scelta l'alternativa con il punteggio più alto

Page 21: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2121

41

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione cardinale• Metodo del Simple Additive Weighting (SAW)

w=[w1,...,wn] vettore dei pesi tali che

Gli attributi devono essere commensurabili (normalizzati)

Il punteggio dell'alternativa i-ma:

1wn

1jj =∑

=

∑=

=n

1jijji xwR

42

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione cardinale• Metodo del Simple Additive Weighting (SAW)

L'insieme delle alternative selezionate (preferite):

E' un metodo molto semplice che appartiene alla classe dei metodi decisionali che utilizzano "funzioni valore" (ValueFunction)

⎭⎬⎫

⎩⎨⎧

== ii

i* Rmaxargi:AA

Page 22: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2222

43

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione cardinale• Analytic Hierarchy Process (AHP) - concetti base

Il metodo SAW costruisce un peso con cui valutare le alternative come

dove di solito

=

== n

1jj

n

1jijj

iw

xw

S

1wn

1jj =∑

=

44

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’idea di base• I valori xij si possono interpretare come il punteggio di Ai in

base al criterio j• xj=(x1j, x2j, ..., xmj) fornisce quindi l’importanza delle

alternative rispetto al criterio j• w rappresenta il vettore dei pesi che misurano l’importanza

relativa dei criteri• L’idea di AHP sta nel derivare (o valutare) l’importanza

relativa delle alternative rispetto ad i singoli criteri, ossia

j1xm

1iij ∀=∑

=

Page 23: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2323

45

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’idea di base• La decisione può essere strutturata secondo una gerarchia

Goal

Crit 1 Crit 2 Crit n

A1 A2 Am. . . . . . . . .

. . . . . . .

w1 w2 wn

x11x12 x1n xmn

1

46

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMAHP - L’idea di base

• Scopo del metodo:definire le priorità relative delle alternative rispetto il goal (il nodo al più alto livello della gerarchia)

• Il metodo procede bottom-up:si comparano le alternative (livello più basso) tra loro in relazione ad ogni singolo criterio del livello immediatamente superiore e si determina la loro prioritàrelativasi sale di un livello e si comparano tra loro i criteri (sub-criteri) rispetto al goal (ad ogni singolo criterio) a livello superiore e si determina il loro peso relativosi aggregano tutte le priorità della gerarchia calcolando la priorità delle alternative rispetto al goal (decisione)

Page 24: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2424

47

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - Passi formali• Dati k livelli (k livello delle alternative):

Elementi al livello k (alternative): x1,...,xk

Elementi al livello k-1 (criteri o subcriteri): y1,...,yk-1

Elementi al livello k-2 (criteri, subcriteri o goal): z1,...,zk-2

Wyj=[wyj(xi)] matrice dei pesi relativi delle alternative rispetto al criterio yj al livello superiore

Wzh=[wzh(yj)] matrice dei pesi relativi dei criteri a livello k-1 rispetto al criterio (goal) zh al livello superiore

• La priorità di xi rispetto a zh

∑−

=⋅=

1k

1jiyjziz )x(w)y(w)x(w jhh

48

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - Passi formali• In forma matriciale:

Nel caso di 3 livelli (Goal, Criteri, Alternative)

dove:– W è il vettore dei pesi dei criteri (al primo livello) rispetto

l’unico elemento del livello superiore, il goal

– P2 è la matrice (alternative x criteri) le cui colonne sono i vettori dei pesi relativi delle alternative rispetto ai criteri

– Wz è il vettore dei pesi (importanza) delle alternative rispetto al goal (la preferenza)

]1k,...,1j),y(w[P]k,...,1i),x(w[ jz1kiz hh −=⋅== −

WPW 2z ⋅=

Page 25: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2525

49

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - Passi formali• In generale:

Ad esempio su 4 livelli:

WPPPW 21nnz ⋅⋅⋅⋅⋅= −

Goal

SC1 SC2 SCn

A1 A2 Am. . . . . . . . .

. . . . .

w1 w2 wk

x11x12 x1n

xmn

1

C1 C2 Ck. . . . .

y11 y1k

⎥⎥⎥

⎢⎢⎢

⎡=

k

1

w

wW M

⎥⎥⎥

⎢⎢⎢

⎡=

nk1n

k111

2yy

yyP

L

MM

L

⎥⎥⎥

⎢⎢⎢

⎡=

nm1m

n111

3xx

xxP

L

MM

L

50

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - Informazioni assolute e relative• Informazioni assolute

viene fornita la matrice delle decisioni

i pesi dei criteri rispetto ai subcriteri ed al goal sono misure oggettive

• Informazioni relativenon si conoscono misure oggettive ma si comparano le alternative in relazione ad i singoli criteri ed i criteri in relazione al goal o ai sottocriteri

possono verificarsi inconsistenze

Page 26: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2626

51

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’indice di consistenza (CI)• In caso di informazioni assolute il CI=0 (consistenza

totale)

• Come viene calcolato?

]n,...,1j,m,...,1i,x[D ij ===

[ ]ke

ekkekj

ejej

kj

ej

kjj a

1aa

1

1xx

xx

1

xx

MC =⇒=

⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢

=⎥⎥⎦

⎢⎢⎣

⎡=

Matrice delle decisioni

Matrice di comparazione rispetto al criterio j

52

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’indice di consistenza (CI)• Così costruita la matrice MCj è perfettamente consistente• Il più grande autovalore della matrice MCj è pari al numero

delle alternative, mentre gli altri autovalori sono nulli

• Nel caso di informazioni relative i rapporti xkj/xej sono stimati (soggettivi) quindi la matrice di comparazione può non risultare completamente consistente

• In questi casi il massimo autovalore si discosta da m (ed i restanti possono essere non nulli)

mmax =λ

m~max ≠λ

Page 27: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2727

53

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’indice di consistenza (CI)• L’indice di consistenza è calcolato come

quindi CI=0 ⇒ consistenza completa

• L’indice misura quanto il DM si discosta con i propri giudizi da una situazione di consistenza completa

• Lo scostamento dovrebbe essere causato da limitate violazioni alla transitività dei giudizi e non da giudizi espressi in maniera del tutto casuale

1mm~

CI max−

−λ=

54

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - L’indice di consistenza (CI)• Per verificare che un CI non corrisponde a giudizi totalmente

randomici si confronta il CI con un Random Index (RI)• Gli RI sono misure random tabulate e generate per numeri

fissati di alternative• Per lo stesso numero m di alternative si calcola il Rapporto di

Consistenza (CR)

• Empiricamente una soglia di accettabilità per CR è 0.1• Per valori superiori si suggerisce al DM di verificare i propri

giudizi

RICICR =

Page 28: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2828

55

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

AHP - CR - implementazioni• Poichè il calcolo degli autovalori delle matrici di

comparazione risulta non risolubile in maniera esatta per m≥5 si adottano dei metodi numerici per la stima di del massimo autovalore

56

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione sugli attributiTasso marginale di sostituzione (MRS)

• Metodi che usano esplicitamente l'informazione circa la possibilità di compensazione tra (coppie) di attributi

Dati due attributi x1 ed x2 ed una alternativa corrispondente ad un punto (x°1,x°2) nel sottospazio di x1 ed x2, il tasso marginale di sostituzione λ(x°1,x°2) misura la disponibilitàdel DM a peggiorare il valore di x1 dell'alternativa considerata per ottenere un miglioramento unitario del valore di x2

)x,x(21

02

12

01

110

201 0

201

xx

xx

xx)x,x(

∆∆=

−=λ

Page 29: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

2929

57

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - Tasso marginale di sostituzioneTasso marginale di sostituzione (MRS)

• E' una proprietà locale• E' definito solo per attributi non indipendenti

∆λa

∆λb

∆λc

∆λe ∆λd

a

b

c

de

Andamento caratteristico del tasso marginale di sostituzione tra due attributi

λb <λa< λc

λe <λa< λd

58

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - Tasso marginale di sostituzioneTasso marginale di sostituzione (MRS)

• Le curve di isopreferenza (indifferenza):Luogo delle punti nel piano associato a due attributi non indipendenti formato da alternative indifferenti nel senso delle preferenze

x1 (beneficio)

x2 (beneficio)

preferenzacrescente

Page 30: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3030

59

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - Tasso marginale di sostituzione• Metodo dei trade-off gerarchici (o dell'aggregazione

gerarchica)Note le curve di isopreferenza per il DM, riduce il numero degli attributi aggregando coppie di attributi non indipendenti.

Esempio:Tre alternative, A1, A2, A3, descritte da 4 attributi x1, x2, x3, x4

Per x1, x2, attributi non indipendenti sono note le curve di isopreferenzaSi può eliminare dalla matrice delle decisioni l'attributo x2

60

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - Tasso marginale di sostituzione• Metodo dei trade-off gerarchici - esempio

x2

A1

A2

A3A'2A'1

x21x31x'21x'11

x12

x22

x32

x11

x1

Page 31: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3131

61

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - Tasso marginale di sostituzione• Metodo dei trade-off gerarchici - esempio

In linea di principio è possibile iterare sino ad avere un solo attributo aggregato sulla cui base decidereIl metodo riduce la dimensione del problema

⎥⎥⎥

⎢⎢⎢

⎡=⇒

⎥⎥⎥

⎢⎢⎢

⎡→

⎥⎥⎥

⎢⎢⎢

⎡=

343331

242321

141311

34333231

24233221

14133211

34333231

24232221

14131211

xx'xxx'xxx'x

'D

xxx'xxxx'xxxx'x

xxxxxxxxxxxx

D

62

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM - informazione sulle alternativePreferenze tra coppie di alternative

• Il DM specifica la sua preferenza tra coppie di alternative

• Questa informazione è rappresentata da un insieme di coppie ordinate Ω=(Ak,Al): Ak è preferita ad Al

• In generale Ω è un sottinsieme dell'insieme di tutte le possibili coppie tra le alternative disponibili

Page 32: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3232

63

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMMetodi MADM – preferenze tra coppie di alternative• Metodo LINMAP (LINear Programming techniques for

Multimensional Analysis of Preference)Sono date m alternative descritte da n attributi ed un insieme Ω di coppie di preferenza espresse dal decisore

Principio:Si ipotizza l'esistenza di una alternativa "ideale" per il DM, si identifica tale alternativa e si ordinano le alternative sulla base della distanza pesata da quella ideale nello spazio degli attributi

il DM può anche indicare un insieme di preferenze non transitivegli output del metodo sono l'alternativa ideale A*=(x*), il vettore dei pesi ideali w*, l'ordinamento (parziale) tra le alternative

64

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMMetodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Distanza euclidea pesata dell'alternativa Ai=(xij) dall'alternativa ideale A*=(xj

*)

l’ordinamento è in base al quadrato della distanza si=di2

a minori valori di si corrispondono le alternative migliori

ProblemaDeterminare i valori di x* e w* in modo che siano il più possibile congruenti con i giudizi forniti dal DMSe il DM indica una coppia (Ak,Al)∈Ω (per comodità la coppia si può indicare con (k,l)), si ha congruenza se sk≤sl

21n

1j

2*jij

*ji )xx(wd

⎟⎟

⎜⎜

⎛−= ∑

=

Page 33: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3333

65

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMMetodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Incongruenza della soluzione rispetto (k,l) ∈Ω

Livello di incongruenza (poorness of fit)(B≥0)

Il problema consiste nell'identificare x* e w* in modo che B sia minimoPer evitare la soluzione banale wj

*=0 (B=0) viene imposto che la congruenza della soluzione rispetto i giudizi del DM sia piùgrande dell'incongruenza

[ ]lkkllk

klkl ss,0max

sssessssse0

)ss( −=⎩⎨⎧

<−≥

=− −

∑Ω∈

−−=)l,k(

kl )ss(B

66

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Congruenza della soluzione rispetto (k,l) ∈Ω

Livello di congruenza (goodness of fit)

Il problema:min Bs.t.G>B ovvero G-B=h>0 per h arbitrario

∑Ω∈

+−=)l,k(

kl )ss(G

[ ]klkl

klklkl ss,0max

ssse0sssess

)ss( −=⎩⎨⎧

<≥−

=− +

Page 34: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3434

67

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

s.t.

Le incognite sono le variabili nei vettori x* e w*

Il problema non è lineare: si introducono delle variabili ausiliarie zkl, ∀(k,l)∈Ω

[ ]∑Ω∈

−=)l,k(

lk ss,0maxminBmin

h)ss(BG)l,k(

kl =−=− ∑Ω∈

68

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Scrivendo i vincoli in funzione delle x* e w* si evidenzia un’ulteriore non linearità ...

Ω∈∀≥

=−

Ω∈∀≥+−

Ω∈

Ω∈

)l,k(0z)3(

h)ss()2()l,k(0zss)1(

.t.s

zmin

kl

)l,k(kl

klkl

)l,k(kl

Page 35: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3535

69

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Si sostituisce ottenendo un problema

lineare.

∑ ∑

∑∑

= =

==

−−−=

=−−−=−

n

1j

n

1jkjlj

*j

*j

2kj

2*j

n

1j

2*jkj

*j

n

1j

2*jlj

*jkl

)xx(xw2)xx(w

)xx(w)xx(wss

lj

*j

*j

*j vxw ←

70

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADMMetodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

n,...,1jliberav0w)4(

)l,k(0z)3(

0h)xx(v2)xx(w)2(

)l,k(0z)xx(v2)xx(w)1(

.t.s

zmin

*j

*j

kl

)l,k(

n

1jkjlj

*j

n

1j

2kj

2lj

*j

kln

1jkjlj

*j

n

1j

2kj

2lj

*j

)l,k(kl

=≥

Ω∈∀≥

=−⎥⎥⎦

⎢⎢⎣

⎡−−−

Ω∈∀≥+−−−

∑ ∑∑

∑∑

Ω∈ ==

==

Ω∈

Page 36: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3636

71

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Il metodo LINMAP interpreta la soluzione del problema come segue:1. se wj

*>0 si calcola xj*=vj

*/wj*

2. se wj*=0 e vj

*=0 si definisce xj*=0

3. se wj*=0 e vj

*>0 si definisce xj*=+∞

4. se wj*=0 e vj

*<0 si definisce xj*=-∞

Le alternative vengono ordinate in base alla distanza (al quadrato) calcolata come

dove I'=j: wj*>0 ed I"=j: wj

*=0 e vj*≠0

∑∑∈∈

=−−="Ij

ij*j

'Ij

2*jij

*ji m,...,1ixv2)xx(ws

72

Metodi Metodi MulticriterioMulticriterio -- Metodi MADMMetodi MADM

Metodi MADM – preferenze tra coppie di alternative• Metodo LINMAP

Note:LINMAP si basa su una funzione di costo quadraticai pesi degli attributi sono un output del metodoidentifica la funzione di costo nell'ipotesi di indipendenza degli attributi nel senso delle preferenze

Page 37: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3737

73

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi Decisionali Multiobiettivo (MODM)• Problema di ottimizzazione vettoriale (Vector Optimization

Problem, VOP)

x = vettore delle variabili decisionalifj(.) = j-mo obiettivo

• Risolvere il VOP consiste nel determinare X* l'insieme delle soluzioni efficienti

• Per determinare X* si definiscono e risolvono problemi di ottimizzazione scalare

[ ]n

Tk1

Xx.t.s

)x(f),...,x(f)x(Fmax

R⊆∈

=

ni RSx,m,...,1i,0)x(g:xX ⊆∈=≤=

74

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi Decisionali Multiobiettivo (MODM)• Un approccio tra i più noti per la soluzione del VOP è

la Scalarizzazione con pesi

Dato

si risolve il problemadefinito per un w∈W

Teorema:x* è soluzione efficiente di VOP se esiste w∈W tale che x*

risolve P(w) e se wj>0 per ogni j=1,...,k, oppure x* èsoluzione unica

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

=≥∈= ∑=

1w,0w,Rw:wWk

1jjj

k

∑=∈

k

1jjj

Xx)x(fwmax:)w(P

Page 38: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3838

75

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi Decisionali Multiobiettivo (MODM)• Una possibile classificazione dei metodi di MODM sulla

base del tipo di informazione di preferenza fornita dal DM:

1. Metodi senza informazione dal DM2. Metodi che usano informazioni fornite a priori dal DM3. Metodi iterativi (che usano informazione fornita

progressivamente dal DM)4. Metodi che usano informazione fornita a posteriori dal

DM

76

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – senza informazione dal DM• Metodo del criterio globale

La soluzione x° è determinata minimizzando un criterio globale definito in base agli obiettivi originali

La soluzione ideale rispetto l'obiettivo j-mo è x*(j)

determinata risolvendo

max fj(x)s.t. gi(x)≤0 i=1,...,m

Il valore ideale dell'obiettivo j-mo è fj(x*(j))

Page 39: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

3939

77

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – senza informazione dal DM• Metodo del criterio globale

Il criterio globale è definito come:

p è un parametro che può essere ad esempio fissato come p=1 oppure p=2 (in questo secondo caso il criterio globale può essere calcolato come (Fp)1/2)La soluzione x° è calcolata risolvendo

min Fp

s.t. gi(x)≤0 i=1,...,m

pk

1j *)j(j

j*

)j(jp

)x(f

)x(f)x(fF ∑

= ⎥⎥⎦

⎢⎢⎣

⎡ −=

78

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – informazione a priori• Questo tipo d'informazione può essere suddivisa in tre

classi:Informazione di tipo ordinale [Lessicografico]Informazione di tipo cardinale [Goal Programming]Livelli di accettabilità

Page 40: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4040

79

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – informazione ordinale a priori• Metodo Lessicografico

Il DM indica un'ordine di importanza (priorità) per gli obiettiviLa soluzione si determina ottimizzando un obiettivo alla volta, iniziando da quello più importanteSupponendo l'indice dell'obiettivo indicativo della sua importanza:

(P1) max f1(x)s.t. gi(x)≤0 i=1,...,m

Se la soluzione di (P1), x*(1), è unica x°=x*

(1), altrimenti si risolve

(P2) max f2(x)s.t. gi(x)≤0 i=1,...,m

f1(x)=f1(x*(1))

80

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – informazione ordinale a priori• Metodo Lessicografico

Il procedimento itera, risolvendo al j-mo passo

(Pj) max fj(x)s.t. gi(x)≤0 i=1,...,m

fw(x)=fw(x*(w)) w=1,...,j-1

sino a j=k o quando x*(w) risulta soluzione unica

Variante: ad ogni passo si considera una soglia di tolleranza, δj j=1,...,k, sugli obiettivi

(Pj) max fj(x)s.t. gi(x)≤0 i=1,...,m

fw(x)≥fw(x*(w))- δw w=1,...,j-1

Page 41: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4141

81

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – inf. a priori: livelli d’accettabilità• Goal Programming

Metodologia generale: può usare i tre tipi di informazione a priori

Principio: il DM indica quali valori per i diversi obiettivi rappresentano i suoi goal ed il metodo cerca una soluzione di compromesso più vicina possibile ad essi

I goal: yj* j=1,...,k

Posto yj=fj(x) si definiscono due deviational variables

Over-achievement

Under-achievement

⎪⎩

⎪⎨⎧ >−=+

altrimenti0yyseyyd

*jj

*jj

j

⎪⎩

⎪⎨⎧ <−=−

altrimenti0yyseyyd

*jjj

*jj

82

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – inf. a priori: livelli d’accettabilità• Goal Programming

Dalle definizioni si ha che

La soluzione di compromesso di può determinare risolvendo

+− −=− jjj*j ddyy

+− +=− jjj*j ddyy

0dd jj =⋅ +−

0d0d jj ≥≥ +−

i0)x(g.t.s

)x(fywmin

i

p

jj

*jj

x

∀≤

−∑

Page 42: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4242

83

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – inf. a priori: livelli d’accettabilità• Goal Programming

Esplicitando le nuove variabili

j0d,0d

j0dd

jdd)x(fy

i0)x(g.t.s

)dd(wmin

jj

jj

jjj*j

i

p

jjjj

x

∀≥≥

∀=⋅

∀−=−

∀≤

+

+−

+−

+−

+−∑

84

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – inf. a priori: livelli d’accettabilità• Goal Programming

Se gli obiettivi ed i vincoli sono lineari è un problema di Linear Goal Programming, che viene risolta con un simplesso modificato che tiene conto implicitamente del vincolo non lineare (che impone che una delle variabili deviazionali sia sempre nulla)

Le deviazioni possono essere pesate anche diversamente

Nel caso in cui uno di tali pesi sia nullo si parla di One-sideGoal Programming

Page 43: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4343

85

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – inf. a priori: livelli d’accettabilità• Goal Programming

Un problema di Goal Programming di tipo generale

j0d0d0dd

i0d0d0dd

jdd)x(fy

idd)x(gb.t.s

)]d,d(hP),...,d,d(hP),d,d(hP[min

jjjj

iiii

jjj*j

iii*i

qq2211x

∀≥≥=⋅

∀≥≥=⋅

∀−=−

∀−=−

⋅⋅⋅

+−+−

+−+−

+−

+−

+−+−+−

goal rispetto i vincoli

(vincoli fuzzy)

relazioni particolari sulle deviazioni rispetto certi goal

pesi "ordinaliordine di prioritàdelle funzioni hqPe>> Pe+1

86

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – informazione progressiva• Metodi iterativi:

Il DM fornisce informazione circa le proprie preferenze mentre "esplora" le soluzioniLe informazioni corrispondono a trade-off locali rispetto alla soluzione corrente e vengono usate per determinare una nuova soluzione

Vantaggi dei metodi interattivi:1. nessuna informazione a priori2. apprendimento del DM (parte attiva nel processo

decisionale)3. preferenze locali4. migliore accettabilità della soluzione finale5. ipotesi in genere meno restrittive

Page 44: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4444

87

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – informazione progressiva• Due classi di metodi:

Metodi che usano informazione esplicita sui trade-off

Metodi che usano informazione implicita sui trade-off

88

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius

Si può usare per funzioni obiettivo lineari o concave e con vincoli lineariViene ipotizzata la presenza di una value function V(.) non nota a priori, ma con struttura lineare o concava

PrincipioDeterminare iterativamente i pesi di un problema P(w) in modo che esso fornisca la miglior soluzione di compromesso estraendola dall'insieme delle soluzioni efficienti.

Page 45: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4545

89

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Sommario (obiettivi lineari)

1. Si aggregano le fj() con pesi arbitrari wj. Si determina l'ottimo

2. Si selezionano tra le variabili xi fuori base quelle "efficienti" (se portate in base producono un miglioramento in qualche obiettivo ed un peggioramenti in qualche altro)

3. Per ogni xi efficiente si calcolano i trade-off rispetto gli obiettivi

4. Si verifica se il DM è disposto ad accettare qualcuna di tali variazioni rispetto ai valori degli obiettivi associati alla soluzione corrente

5. In caso positivo si determinano i nuovi pesi degli obiettivi e si itera il procedimento

6. L'algoritmo termina se non esistono variabili fuori base efficienti o se il DM non accetta alcun trade-off

90

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

1. Inizializzazione: q=1, w1 pesi arbitari tali che

2. Soluzione del problema scalarizzato (ipotesi: fj(x) e gh(x) lineari)Si risolve

dove X=gh(x)≤0 ∀h, x≥0

.0w1w 1j

k

1j

1j >ε≥=∑

=

∑=∈

k

1jj

qjXx

)x(fwmax

Page 46: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4646

91

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

3. Determinazione delle variabili fuori base efficientiPer ogni variabile fuori base xi si calcola

ossia la variazione del j-mo obiettivo causata da un aumento unitario della xi, rispetto alla soluzione x*

calcolata al passo 2.Il vettore x(i) è la soluzione ammissibile corrispondente alla variazione unitaria di xiNel caso lineare le λij corrispondano ai costi ridotti delle variabili fuori base rispetto alle varie funzioni obiettivo.

i

)i(j*

jij x

)x(f)x(f −=λ

92

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

3. Determinazione delle variabili fuori base efficientiSe λij≥0 per ogni fj(x) la variabile fuori base xi non èefficiente (perché?)Se qualche λij<0 allora si verifica se xi è efficiente risolvendo:

Se Z < 0 ⇒ xi efficientej0w1w

basefuori.varx,ie0w

wminZ

jk

1jj

ek

1jjej

k

1jjij

w

∀≥=

≠∀≥λ

λ=

=

=

=

Page 47: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4747

93

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

4. Fase decisionaleSe non esistono variabili fuori base efficienti l'algoritmo termina, determinando i pesi wq miglioriLa soluzione corrente è la migliore soluzione di compromesso

Altrimenti, per ogni xi variabile fuori base efficiente si verifica se il DM è disposto ad accettare complessivamente una variazione di λi1 per l'obiettivo f1(x), di λi2 per l'obiettivo f2(x), e così via.

94

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

4. Fase decisionaleIl DM può accettare o non accettare la variazione o considerarla indifferente

Se il DM non accetta alcuna variazione per ogni xiefficiente, la procedura termina, i pesi wq sono quelli definitivi e la soluzione corrente è la migliore soluzione di compromesso

Altrimenti, se ci sono variazioni accettate, si costruisce un insieme di vincoli nelle variabili w per determinare un nuovo insieme di pesi per gli obiettivi

Page 48: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4848

95

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

4. Fase decisionale• per ogni xi efficiente per cui il DM ha risposto

positivamente

(a)

• per ogni xi efficiente per cui il DM ha risposto negativamente

(b)

• per ogni xi efficiente per cui il DM è rimasto indifferente

(c)

∑=

ε−≤λk

1jjijw

∑=

ε≥λk

1jjijw

0wk

1jjij =λ∑

=

96

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – trade-off espliciti• Metodo di Ziont e Wallenius – Passi

4. Fase decisionaleε>0 è una costante che rappresenta la soglia minima oltre la quale è interessante una variazione del criterio globale

5. Calcolo dei nuovi pesiSi risolve il problema di ammissibilità per i vincoli (a), (b), (c) e per

Si pone q=q+1 e si assegna la soluzione del problema di ammissibilità a wq

Si itera al passo 2

1wk

1jj =∑

=

Page 49: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

4949

97

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

E' un metodo per la Multiobjective Linear Programming(MOLP)

Richiede al DM di specificare i livelli di accettabilità locali rispetto ad una soluzione (più semplice che valutare un trade-off).

Problema MOLP:

0xbxA

]xc,...,xc[max Tk

T1

≥≤

98

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

Si calcolano i valori ideali per gli obiettivi:

fj*= fj(xj) =max fj(x)s.t. gi(x)≤0 i=1,...,m

Si assume che il DM abbia un comportamento pessimista: l'insoddisfazione del DM per la soluzione è rappresentata dalla più grande deviazione rispetto ai valori ideali

min d∞(F(x),F*) =x∈X

]))x(ff(w[maxmin j*jj

j−⋅

Page 50: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5050

99

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

Posto J0=1,...,k l'insieme degli indici degli obiettivi e X0

l'insieme di ammissibilità originale del problema, ad ogni passo q si risolve un problema lineare

Per q=0 il problema corrisponde a

(P0) min λ

s.t. λ≥wj[fj* - fj(x)] j∈J0

x∈X0 λ≥0

nelle variabili x e λ

100

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

I pesi wj sono calcolati ad ogni passo in base alla matrice dei payoff

dove fj*= fj(xj) e fji= fj(xi).

*k

jk

1kk

kj

*j

1jj

k1

j1

*11

kj1

ffff

ffff

ffff

fff

LL

MMMM

LL

MMMM

LL

LL

Page 51: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5151

101

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

I pesi wj esprimono l'importanza relativa degli scostamenti rispetto ai vari obiettivi, ovvero misurano quanto è difficile avvicinarsi al valore massimo dell'obiettivo (wj=0 obiettivo i non critico)

∑=

= k

1hh

jj

u

uw

2/1n

1i

2ij

j

minj

*j

j

c

1f

ffu

⎟⎟⎠

⎞⎜⎜⎝

⎛⋅

−=

∑=

)x(fminf rj

kr1minj ≤≤

=⎪⎩

⎪⎨⎧

<

>=

0fsef

0fseff *

jminj

*j

*j

j∑=

=n

1jjiji xc)x(f

dove

102

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

Risolto il problema ad una iterazione q e trovata una soluzione x(q), si interroga il DM chiedendo di confrontare i valori degli obiettivi, f1(x(q)),..., fk(x(q)), rispetto ai valori ideali, f1*,..., fk*

Se il DM identifica degli obiettivi il cui valore non èsoddisfacente, viene chiesto al DM di indicare quali tra gli obiettivi che risultano soddisfacenti potrebbero essere peggiorati nella speranza di poter migliorare i primi

In questo modo il DM specifica implicitamente un trade-off

Page 52: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5252

103

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

Se il DM accetta una diminuzione di ∆fh rispetto all'obiettivo fh, allora si procede ad una nuova iterazione (q+1) definendo

hj)x(f)x(f,f)x(f)x(f,Xx:xX )q(jjh)q(hhq ≠∀≥∆−≥∈=

qq1q XXX ∩=+∑≠

=

hjj

jj u

uw, wh=0, , Jq+1 = Jq - h

104

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method)

Si risolve il problema della iterazione (q+1)

(Pq+1) min λ

s.t. λ≥wj[fj* - fj(x)] j∈Jq+1

x∈Xq+1 λ≥0

Il processo termina quando il DM è soddisfatto della soluzione corrente, oppure se nessun obiettivo soddisfa il DM oppure se q=k

Page 53: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5353

105

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – trade-off impliciti• Metodo STEM (STEp Method) - passi

1. Determinare fj*, j=1,...,k. Inizializzare q=0; Xq=X; Jq=1,...,k2. Risolvere il problema (Pq) e calcolare fj(x(q)), j=1,...,k3. Far valutare al DM i valori fj(x(q)) con fJ*, j=1,...,k.

Se il DM è soddisfatto l'algoritmo termina e x(q) è la miglior soluzione di compromesso, altrimenti se nessun obiettivo soddisfa il DM l'algoritmo termina non essendo in grado di determinare una soluzione di compromesso.Se il DM è soddisfatto solo da alcuni obiettivi, si chiede al DM di scegliere un obiettivo h rispetto al quale sia disposto ad accettare un peggioramento per cercare di migliorare gli obiettivi non soddisfacenti. Sia ∆fh il peggioramento accettato.

4. Se q=k l'algorimo termina senza che sia stata determinata una soluzione di compromesso, altrimenti q=q+1, si aggiorna Xq, Jq ed i pesi w e si itera al passo 2).

106

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – informazione a posteriori• Sono metodi che risolvono il VOP determinando

l'insieme delle soluzioni non dominate, o un suo sottinsieme. Queste alternative vengono proposte successivamente al DM che seleziona quella preferita

• Non vengono fatte ipotesi sulla struttura della V(.)

• Di solito sono metodi non pratici poichè il numero delle soluzioni generato può essere molto elevato

• Spesso sono incorporati in altri metodi

Page 54: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5454

107

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – informazione a posteriori• Il metodo parametrico

Utilizza la scalarizzazione per generare le soluzioni non dominate, ovvero risolve una sequenza di problemi P(w), fissando di volta in volta i valori dei parametri w

Se la preferenza varia in maniera monotona rispetto i valori di ciascuna funzione obiettivo e la regione di ammissibilità delle soluzioni è convessa, facendo variare sistematicamente i valori dei pesi w è possibile generare l'insieme delle soluzioni non dominate

Geometricamente ciò corrisponde a determinare, nello spazio degli obiettivi, quali tra gli iperpianiL=F(x): wTF(x)=c sono tangenti allo spazio di ammissibilità con c massimo

108

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODM

Metodi MODM – informazione a posteriori• Un metodo generale per determinare le soluzioni non

dominate (poco pratico):1. Per ogni wj scegliere un insieme di valori discreti tra 0 ed 1,

Wj=wj1,...,wj

e1, dove wj1=0 e wj

e1=1

2. Generare l'insieme di k-ple W1xW2x...xWk

3. Per ciascuna delle e1xe2x...xek combinazioni risolvere P(w)

4. Verificare se le soluzioni ottenute sono non dominate, ovvero se vale almeno una delle seguenti condizioni:

a. wj>0 per j=1,...,k

b. la soluzione è unica

c. la soluzione supera il seguente "test di non inferiorità" (noninferiority test)

Page 55: Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi sulla struttura di preferenza del decisore) Formulazione del problema (obiettivi

5555

109

Metodi Metodi MulticriterioMulticriterio -- Metodi MODMMetodi MODMMetodi MODM – informazione a posteriori• Noninferiority test:

con αj>0, j=1,...,k

Il test è superato se δ=0;se δ>0 la x* è dominata, ma la nuova soluzione trovata è non dominata;se δ=∞, nell'ipotesi che X sia convesso e le fj(x) siano concave (massimizzazione), non esistono soluzioni non dominate per il VOP.

Se il problema è MOLP esiste un algoritmo basato sul simplesso per la soluzione del LVOP.

j0

j)x(f)x(f

Xx.t.s

max

j

*jjj

k

1jjj

∀≥ε

∀=ε−

εα=δ ∑=