Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi...
Transcript of Metodi Decisionali Multi Criterio - discovery.dist.unige.it · Metodo MCDM (decision rule, ipotesi...
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
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")
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
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⊆∈
=
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)
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.
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]
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)
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)
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
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)
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
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
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
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
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
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
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.
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
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
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
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 ∀=∑
=
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)
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 ⋅=
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
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 ≠λ
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 =
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(
∆∆=
−
−=λ
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
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
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
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
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛−= ∑
=
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( −=⎩⎨⎧
<≥−
=− +
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
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
=≥
Ω∈∀≥
=−⎥⎥⎦
⎤
⎢⎢⎣
⎡−−−
Ω∈∀≥+−−−
∑ ∑∑
∑∑
∑
Ω∈ ==
==
Ω∈
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
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
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))
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à
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
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
∀≤
−∑
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
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
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.
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
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
∀≥=
≠∀≥λ
λ=
∑
∑
∑
=
=
=
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
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 =∑
=
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−⋅
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
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
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
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
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)
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
∀≥ε
∀=ε−
∈
εα=δ ∑=