Department of Applied Mathematics, University of Venice

QUADERNI DI DIDATTICA

Francesco Mason

Appunti di Programmazione a più Criteri

Quaderno di Didattica n. 29/2008 Ottobre 2008

1

Appunti di Programmazione a più Criteri

Francesco Mason

<fmason@unive.it>

Dipartimento di Matematica Applicata

Università Ca’ Foscari di Venezia

(Ottobre 2008)

I Quaderni di Didattica sono pubblicati a cura del Dipartimento di Matematica Applicata dell’Università di Venezia. I lavori riflettono esclusivamente le opinioni degli autori e non impegnano la responsabilità del Dipartimento. I Quaderni di Didattica vogliono promuovere la circolazione di appunti e note a scopo didattico. Si richiede di tener conto della loro natura provvisoria per eventuali citazioni o ogni altro uso.

2

1. Introduzione

Il modello generale di programmazione matematica, max (min) f(x), con vincoli gi(x)≤0 non tiene conto del fatto che spesso, nella vita reale, il decisore ha contemporaneamente più elementi di valutazione per adottare una certa decisione. E’ anzi da ritenere rara la circostanza nella quale tutto si possa ridurre alla minimizzazione di un costo (penalità) o alla massimizzazione di un guadagno (utilità, rendimento). Il paradigma più semplice è quello dell’acquisto di un’automobile. Non a caso la stampa specializzata compila tabelle che raffrontano i vari modelli di automobile (decisioni!) sulla base di numerosi elementi, lasciando poi al decisore di mediare tra tutte le proprie inclinazioni (e possibilità economiche!). Maggiori prestazioni ed un maggiore comfort, in genere, si accompagnano ad un prezzo più elevato. Gli obiettivi che si vorrebbero raggiungere si presentano quindi – assai spesso - in maniera tra loro conflittuale. A dire il vero, la programmazione matematica ‘classica’ può dare dei suggerimenti, anche in queste circostanze: lo può fare individuando, tra tutti, un obiettivo ‘principale’, che assume il ruolo di vera e propria funzione obiettivo, e travestendo gli altri (‘secondari’, se vogliamo) come vincoli. Si cercherà allora, ad esempio, di minimizzare un costo, vincolando altri parametri di prestazione a superare determinate soglie di accettabilità. Viceversa, la programmazione a più criteri (detta anche programmazione vettoriale) si propone di dare regole razionali, utili al decisore, più esplicitamente, tenendo in considerazione tutti i vari obbiettivi. Come si vedrà, non sempre questo, concretamente, arriva a configurare una unica soluzione ottima, ma piuttosto può servire a scremare l’insieme delle alternative tra cui scegliere, lasciando comunque al decisore la responsabilità finale della individuazione di una politica da adottare. Nell’ambito della programmazione a più criteri si distinguono:

- la programmazione multi attributo (PMA), quando le alternative tra cui scegliere si presentano in numero finito;

- la programmazione multi obiettivo (PMO), quando viceversa le alternative sono infinite.

Il confine non è netto: tuttavia la distinzione torna utile. I modelli di decisione che verranno presentati si riferiscono prevalentemente alla situazione ‘multi attributo’. Nel caso della programmazione multi obiettivo, ci si soffermerà prevalentemente sulla Goal Programming.

3

2. Definizioni fondamentali. Prima di formalizzare i problemi di programmazione a più criteri, è opportuno soffermarsi sulla terminologia utilizzata in tale materia. Si utilizzano spesso termini che, da un punto di vista linguistico, possono apparire sinonimi, mentre in realtà hanno significati con sfumature anche abbastanza lontane. Innanzitutto, il termine attributo indica una caratteristica, qualità o paramero di prestazione delle alternative. Sono attributi, nella scelta di acquisto di un’automobile, l’accelerazione, la velocità, il comfort, le condizioni di acquisto, il prezzo e così via. Il termine criterio è strettamente legato a quello di attributo: un attributo diventa criterio quando si precisa in quale direzione il valore dell’attributo rende l’alternativa più attraente. I criteri si dividono a loro volta in obiettivi e goal. Obiettivo è uno scopo da perseguire quanto più possibile ed indica la direzione secondo la quale ci si vuole muovere. Tipicamente gli obiettivi sono quantità che si cerca di rendere massime oppure minime. Goal (o anche target) è uno stato che si vuole raggiungere. Il termine in lingua italiana che rende con maggior precisione questa idea è bersaglio. Il goal può consistere in un valore (al quale ci si vuole quanto più possibile avvicinare) o in un intervallo di valori (una ‘finestra’). Esempi ben noti di goal di questo ultimo tipo sono gli standard fisiologici dei liquidi organici (ad es., la quantità di globuli bianchi presenti nel sangue di una persona). Le alternative sono le decisioni che il decisore ha a propria disposizione: in generale, una decisione consiste in un vettore x di variabili decisionali. Nei casi più semplici, le alternative possono essere semplicemente elencate; in situazioni più complesse possono essere descritte implicitamente come soluzioni di un sistema di equazioni / disequazioni. I vincoli, come di consueto in programmazione matematica, sono delle condizioni che i vettori di decisione devono rispettare. Un generico problema di programmazione a più criteri può sempre essere espresso nella forma:

max f1(x), max f2(x), … , max fk(x) con vincoli gi(x) ≤ 0, i = 1, 2, …, m. La forma di massimo non è restrittiva perché ad essa ci si può sempre ricondurre con opportuni cambiamenti di segno. Analogamente il verso dei vincoli può sempre essere posto nella forma sopra scritta: si possono far rientrare nella formulazione anche eventuali vincoli di non negatività.

4

In maniera più concisa, si può indicare in forma vettoriale l’insieme delle funzioni obiettivo e si può indicare con X l’insieme delle soluzioni (alternative ammissibili). In tal modo il problema si può presentare nella forma:

max f(x) s.t. x ∈ X.

X prende anche il nome di spazio delle alternative. Ad ogni vettore m-dimensionale x ∈ X corrisponde un vettore f di dimensione k che esprime il valore dei k attributi in corrispondenza di quell’alternativa. L’insieme di questi vettori (di valori di attributi) viene indicato con Γ e denominato spazio degli attributi: è chiaro che concettualmente si possono far coincidere alternative che danno luogo allo stesso vettore di attributi e che lo stesso problema di scelta si può trasportare dallo spazio delle alternative a quello degli attributi (spazi che, per altro,vanno tenuti distinti). Nella PMA lo spazio delle alternative (e quindi anche quello degli attributi) sono di tipo discreto; nella PMO, invece, lo spazio delle alternative è di tipo continuo. Passando al concetto di soluzione, e osservato che generalmente non esiste una vera e propria soluzione ad un problema di programmazione a più criteri (a differenza della programmazione classica), distinguiamo varie tipologie di soluzioni. Def. 1 Un vettore x* ∈ X, se esiste, che rende massime contemporaneamente tutte le funzioni obiettivo viene detto soluzione ottima oppure soluzione utopistica o più semplicemente utopia. Nei problemi reali di programmazione a più criteri l’esistenza di una soluzione utopistica è l’eccezione, più che la regola. In mancanza della soluzione ottimale, particolare attenzione va dedicata alla individuazione di soluzioni ‘ragionevoli’, o, se si vuole, alla esclusione di soluzioni insensate, quali quelle che danno luogo a vettori di attributi ‘dominati’ da altri vettori. Def. 2 Si dice che una soluzione (alternativa) x domina una alternativa y se per ogni criterio i (i=1, 2, …, k) si ha fi(x) ≥ fi(y) e per almeno un indice i la disuguaglianza vale in senso stretto. Se x domina y, si dice anche, leggendo la relazione nel verso opposto, che y è dominata da x. E’ abbastanza evidente che in un problema di decisione non si dovrebbero mai adottare alternative dominate da altre, perché risultano migliorabili sotto qualunque aspetto (criterio).

5

Def. 3 Si dice Pareto-ottima o Pareto-ottimale ogni soluzione (alternativa) non dominata da altre. Passando alle decisioni che effettivamente il decisore adotta, si danno altre definizioni. Def. 4 Diciamo che x* è soluzione soddisfacente se x* appartiene al sottoinsieme dell’insieme ammissibile contenente tutte le alternative in corrispondenza delle quali risultano superati dei livelli prefissati relativi ai vari obiettivi. Una soluzione soddisfacente, che richiede evidentemente che siano prefissate delle soglie per i valori dei vari attributi, può risultare dominata (non essere Pareto – ottima). Def. 5 Diciamo che x* è la soluzione preferita (o migliore) se x* è non dominata ed è stata scelta dal decisore. In presenza di due soli criteri, Z1 e Z2, la dominanza tra decisioni può essere visualizzata mediante una rappresentazione nello spazio degli attributi come segue. Su un sistema cartesiano ortogonale riportiamo in ascissa i valori del primo attributo e in ordinata quelli del secondo. Ogni decisione può essere rappresentata da un punto: la figura che segue si riferisce ad un esempio di problema con 6 alternative.

In figura si è evidenziata la decisione D1 per la quale i valori dei due attributi sono, rispettivamente, a1 e b1. Le decisioni D1, D4 e D6 risultano Pareto ottime (non dominate) in quanto per ognuna di esse non esiste alcuna altra decisione che presenti valori migliori per entrambi gli attributi. Viceversa le altre tre decisioni sono dominate (D2 è dominata da tutte e tre le decisioni Pareto ottime; D3 è dominata da D4; D5 è dominata sia da D4 che da D6). In generale, sempre nelle situazioni con soli due criteri, data una qualsiasi decisione D, il piano cartesiano può essere diviso in quattro zone, come nella figura che segue:

D1 (a1, b1)

D2

D3

D4

D6

D5

a1

b1

6

La decisione D domina ogni altra (eventuale) decisione che si collochi nella zona P; risulta dominata da tutte le decisioni della zona N; invece è non confrontabile rispetto alle decisioni in M ed N. Se si collegano con dei segmenti i punti rappresentativi di decisioni non dominate adiacenti (procedendo, ad es., per valori crescenti del primo attributo), si ottiene una spezzata avente appunto quali vertici le soluzioni Pareto ottimali che viene anche detta frontiera di Nord Est per il problema allo studio.

3. Esempi applicativi.

La programmazione a più criteri ha un’area di applicazione molto vasta. Alcune problematiche potenzialmente interessate sono le seguenti.

a) Capital budgeting e problemi affini. L’analisi multicriterio può essere applicata a problemi di pianificazione finanziaria e di bilancio preventivo. La pianificazione finanziaria consiste nel fissare l a politica di investimenti e/o finanziamenti a medio termine di un’azienda. Una decisine a medio termine è ovviamente collegata con lo studio e la scelta di un insieme di opportunità che, oltre ad assicurare il più alto utile, consentano di mantenere una copertura adeguata per far fronte a problemi di liquidità a breve e lungo termine. Questi due obiettivi sono, evidentemente, in conflitto. La gestione finanziaria di un’operazione di questo tipo si basa sull’analisi di più indicatori di performance quali: misure di redditività immediata e futura in termini di caèpitale; tasso di crescita delle vendite, dividendi e guadagni per azione; richieste di interessi (fissi) sul capitale al tasso corrente; copertura dei dividendi e degli interessi da pagare nel tempo. I valori di questi indicatori vincolano le possibili strategie di investimento e finanziamento dell’azienda. Nel capital budgeting ci si trova di fronte a problemi di decisine con più obiettivi e goal. Lo schema di riferimento stavolta è il seguente. Dato il valore attuale di un insieme di alternative indipendenti di investimento e date le spese richieste per il progetto in ogni periodo di tempo dell’orizzonte temporale considerato, determinare il sottoinsieme di progetti che massimizza il valore

M N D P Q

7

attuale globale e che, contemporaneamente, soddisfa il vincolo sulle spese relative ad ogni periodo.

b) Organizzazione della produzione e problemi combinatrici. In campo operativo, le applicazioni tendono ad essere del tipo PMA, vale a dire, multi-attributo, essendo assai frequente il caso in cui le alternative sono in numero finito (a volte, alcune unità solamente). In campo economico – aziendale, le scelte di prodotti da immettere nel mercato e di mezzi per campagne pubblicitarie sono solitamente prese tenendo conto di più criteri. A volte un elemento preliminare da risolvere consistre nella stesa scelta degli attributi di cui tener conto (né troppo numerosi, ma nemmeno tali da trascurare elementi importanti nella determinazione del risultato finale). Nei problemi di localizzazione esiste generalmente una preselezione di località tra le quali dovrà cadere la scelta definitiva. Ma i criteri da tenere in considerazione sono molteplici. Si pensi al problema di localizzazione di un aeroporto, con le contrapposte esigenze di comunicazione con i nuclei urbani (che porterebbero a scelte in prossimità dei centri stessi) e ridotto impatto ambientale, rumorosità ecc. (che inducono a scelte opposte, lontano dalle grandi aree metropolitane). Analoga problematica si presenta con le discariche di rifiuti (ogni ulteriore commento appare addirittura superfluo). Problematiche multi - criterio si presentano anche nell’ambito della selezione del personale (costruzione di team con componenti di caratteristiche complementari ecc.). Nell’ottimizzazione su reti (grafi) si studiano classici problemi quali la determinazione del percorso ottimo tra coppie di nodi, con più obiettivi simultanei (lunghezza del cammino, tempo di percorrenza, indici di sicurezza del cammino stesso). Un cenno a parte merita il caso della programmazione lineare a più obiettivi, al quale verrà dedicato il paragrafo seguente. 4. Programmazione lineare con più obiettivi.

L’estensione della Programmazione Lineare al caso ‘multicriteri’, dal punto di vista puramente formale, è ovvia: si tratta di introdurre non più una sola funzione obiettivo, ma un numero finito di funzioni obiettivo differenti. Altro è estendere la metodologia di calcolo (il metodo del simplesso non può evidentemente essere utilizzato così com’è!). Ferme restando le caratteristiche della regione ammissibile (insieme convesso, eventualmente aperto), e la proprietà ben nota che, per ogni obiettivo, se esistono soluzioni ottime, queste possono essere ricercate tra i vertici della regione Ammissibile, si verifica ovviamente che ogni obiettivo verrà raggiunto in uno o più vertici differenti da quelli degli altri obiettivi.

8

Con due variabili e due obiettivi si può dare una raffigurazione geometrica sia delle soluzioni ammissibili che dei valori conseguibili con le funzioni oggetto. Si parla rispettivamente di rappresentazione nello spazio delle soluzioni e nello spazio degli obiettivi . Consideriamo il problema a due obiettivi (che potremmo definire in forma ‘canonica’):

max {f1(x) = c1x1 + c2x2}, max {f2(x) = c’1x1 + c’2x2}, s.t. a1x1 + a2x2 ≤ b, x1, x2 ≥ 0, dove x è un vettore a due componenti mentre a1 ed a2 sono vettori (colonna) n-dimensionali (la matrice dei coefficienti dei vincoli è allora A = (a1, a2)). La rappresentazione grafica, come si è detto, consiste in due raffigurazioni. Si può innanzi tutto rappresentare su un primo piano cartesiano la Regione Ammissibile (nello spazio delle soluzioni): questo insieme, salvo casi particolari, è un poligono dotato di punti interni. Successivamente ad ogni soluzione ammissibile x si può fare corrispondere in un secondo piano cartesiano la coppia di valori delle funzioni oggetto, (f1(x), f2(x)). Le coppie così ottenute formeranno (nello spazio degli obiettivi) una figura geometrica che, se le due funzioni oggetto hanno gradienti con direzioni differenti, cioè se il determinante della matrice

c1 c2 c’1 c’2 è diverso da zero, è dotata di punti interni, così come la Regione Ammissibile di partenza ed è quindi un altro poligono P. Per di più, ai vertici della Regione Ammissibile corrispondono (biunivocamente) vertici di P. Su questa seconda rappresentazione si possono facilmente individuare le soluzioni Pareto ottime. Operativamente, è necessario poi risalire da quest’ultima rappresentazione a quella nello spazio delle soluzioni. Si tenga presente che il assaggio dallo spazio delle soluzioni a quello degli attributi si effettua con una trasformazione lineare: come ben noto, queste trasformazioni mantengono la proprietà di allineamento tra punti per cui una retta viene sempre trasformata in un’altra retta. Si consideri il seguente esempio. E’ dato il problema di PL bi-obiettivo

9

max (2x – y); max (x + y)

con i vincoli 2y – x ≤ 6 3y + x ≤ 19 y + 2x ≤ 18 x, y ≥ 0 Nello spazio delle soluzioni la regione ammissibile assume l’aspetto della figura che segue

Le coordinate dei punti sono, rispettivamente, H(0, 3); K(4, 5); L(7, 4); M(9, 0). Nello spazio degli attributi, al vertice H corrisponde H’(-3, 3); K viene trasformato in K’(3, 9); L in L’(10, 11) ed infine M diventa M’(18, 9). All’origine O(0, 0) corrisponde ancora O’(0, 0) – ma nello spazio degli attributi! L’insieme delle coppie di attributi ottenibili dalle decisioni ammissibili va a formare il poligono rappresentato nella figura che segue:

Si vede facilmente come vi siano infinite soluzioni Pareto ottime, e cioè tutte quelle che corrispondono al segmento L’M’: nello spazio delle soluzioni, esse corrispondono alle decisioni del segmento LM (si osservi come NON siano Pareto ottime le decisioni interne al segmento KL!). Tra i punti in LM si potrà scegliere ulteriormente solo introducendo altri elementi, quale ad esempio, qualche indicatore dell’importanza relativa dei due criteri, cosa che comunque spetta al decisore (non all’analista!). Si vedrà poi come, una volta introdotti dei pesi per i due criteri, la decisione ottima riacquisterà la proprietà tipica della PL data dal fatto che la soluzione ottima, salvo situazioni di ‘pari merito’ va a cadere su un vertice.

z2

z1

L’ K’ M’ H’ O’

L K H O M

y

x

10

5. Scalarizzazione e Pareto ottimalità.

Per scalarizzazione si intende il procedimento di sostituzione di più obiettivi con uno solo che li riassume e consente al tempo stesso di giungere ad una scelta tra le alternative: se il decisore, di fronte a più criteri di valutazione è in grado di esprimerne l’importanza relativa e di calcolare l’utilità di ogni alternativa, il problema a più criteri viene ricondotto ad uno di tipo scalare. Dal punto di vista formale ciò può essere espresso dicendo che il decisore esprime una funzione di utilità

u(x) = u(f1(x), f2(x), …, fk(x))

ed il problema diventa max u(x)

x∈X cioè diventa un problema di programmazione non lineare. Se il decisore non è in grado di indicare u(x), allora ci si deve limitare alla individuazione delle soluzioni Pareto ottime.

Ciò non esclude che vi siano situazioni intermedie, di informazione parziale, per le quali la letteratura ha proposto delle metodologie, proprio con l’ottica di usare quanto più possibile le informazioni disponibili.

Su questi temi i contributi scientifici sono numerosi. In particolare, è stato studiato sotto vari aspetti il problema delle condizioni per poter costruire una funzione di utilità o le condizioni che giustificano l’uso di metodi di scalarizzazione molto popolari (quali ad esempio, i metodi a punteggio). Altro problema che la letteratura ha affrontato e cercato di risolvere è il seguente: di fronte a più decisori, ognuno dei quali ha titolo ad esprimere un proprio ordine di preferenze, vi è la possibilità di trovare un compromesso tra le varie opinioni al fine di giungere ad una graduatoria comune? Nei prossimi paragrafi questi due temi verranno approfonditi con l’analisi del contributo di studiosi che hanno dato il loro nome a risultati oramai classici nell’ambito della programmazione a più criteri.

11

6. I teoremi di Debreu ed Arrow ed il problema della scalarizzazione.

Introduciamo alcune notazioni. Date due alternative x e y,

se la prima è preferita alla seconda useremo la scrittura x f y oppure y p x .

Scriveremo invece x ~ y

per indicare che x e y sono egualmente preferiti (indifferenti). Se si può introdurre una funzione di utilità, u (⋅), la prima scrittura implica u(x) > u(y), mentre la seconda equivale a u(x) = u(y). Tuttavia non è detto che l’esistenza in un insieme di scelte di una relazione f implichi necessariamente l’esistenza di una funzione di utilità (anche se la relazione f soddisfa le consuete proprietà richieste, in particolare la transitività e la completezza). Ad esempio, se ogni decisione x è caratterizzata da una coppia di valori (a, b) con α1 ≤ a ≤ α2 e β1 ≤ b ≤ β2, e si ha che

x (p, q) f y (r, s) se e solo p > r oppure, nel caso in cui p = r,

x (p, q) f y (r, s) se e solo se q > s, allora si può vedere come non esista alcuna funzione a valori reali definita sul rettangolo

T = [α1 ≤ a ≤ α2, β1 ≤ b ≤ β2] in grado di tradurre l’ordinamento di preferenze sopra indicato (che, detto per inciso, è un ordinamento di tipo lessicografico). Basti pensare che la funzione u (a, b) dovrebbe essere strettamente crescente su ogni segmento verticale S che intersechi il rettangolo (lungo tale segmento rimane costante il valore a) mentre dovrebbe essere anche

u (a + δ, β1) > u (a, β2) per ogni δ > 0, comunque piccolo. (In altri termini, su ogni segmento situato alla destra di S tutti i valori di u dovrebbero essere superiori ai valori su S: questo è impossibile se i segmenti del tipo di S sono una infinità continua).

Viceversa, Debreu ha dimostrato il seguente Teorema:

Se Σ è uno spazio connesso, p è un ordinamento su Σ e gli insiemi

{x ∈ Σ: x p y} e {x ∈ Σ: y p x} sono chiusi, allora esiste una funzione di utilità continua u: Σ → R tale che:

u(x) < u(y) ⇔ x p y.

Nell’esempio sopra riportato (in cui u non può esistere) si nota che, fissato un punto (=decisione) y del rettangolo T, i punti x non preferiti a y costituiscono un insieme non chiuso in quanto vanno a formare un insieme T* ⊂ T, a sua volta un

12

rettangolo, che però non contiene tutta a propria frontiera (contiene solo una parte del lato verticale di destra). Per poter ricorrere alla scalarizzazione in un problema multi-criteri è di primaria importanza stabilire se tra gli attributi vale la proprietà di indipendenza preferenziale. Questa a volte viene data (implicitamente) per scontata, ma viceversa occorre essere consapevoli che ciò non rappresenta la realtà in molti casi concreti. Il concetto di indipendenza delle preferenze può essere descritto sinteticamente con l’espressione ‘ceteris paribus …’: formalmente esprime il fatto che se cambiano allo stesso modo, in due circostanze diverse, alcuni dati al contorno, la scelta tra due alternative non dovrebbe essere modificata. Facendo ricorso alla rappresentazione in forma matriciale di un problema (decisioni × attributi) partizioniamo gli attributi stessi in due sottoinsiemi, γ1 e γ2. Parallelamente, ogni vettore x(i) di valori degli attributi per una data decisione di viene partizionato in due blocchi, che diremo y1

(i) e y2(i).

γ1 γ2

A1 A2 …. Ap Ap+1 Ap+2 … An

d1 x11 x12 …. x1p x1,p+1 x1,p+2 … x1n … … … . … … … . … di xi1 xi2 …. xip xi,p+1 xi,p+2 … xin … … … . … … … . … dm xm1 xm2 …. xmp xm,p+1 xm,p+2 … xmn Possibili valori ↑ ↑ degli attributi: insieme Y1 insieme Y2

Nel caso della figura avremo

y1(i) = (xi1 xi2 …. xip); y2

(i) = (xi,p+1 xi,p+2 … xin). Sia Y1 l’insieme di tutti i possibili vettori dei valori degli attributi in γ1 e Y2 l’insieme dei valori per gli attributi in γ2.

Diremo che l’insieme degli attributi γγγγ1 e preferenzialmente indipendente dal suo complementare γγγγ2 se per ogni coppia (di insiemi di valori di attributi) y1

’, y1” ∈ Y1 per

cui vale (y1

’, y2) f ( y1” , y2)

ne consegue (modificando in eguale misura i valori degli attributi in Y2) che

(y1

’, y2’) f ( y1

” , y2’).

13

Quindi, di fronte a due alternative d1 e d2, che si differenziano per il valore di un certo insieme γ1 di attributi, mentre per un secondo gruppo di attributi γ2 presentano valori eguali, la preferenza del decisore non cambia se vengono modificati allo stesso modo i valori degli attributi del gruppo γ2. Un esempio può aiutare a chiarire ulteriormente il concetto. Supponiamo il decisore manifesti la seguente preferenza:

(3 4 9 2 15) f (3 2 10 2 15) * * * * * * dove quelli indicati sono due vettori di valori di attributi per altrettante decisioni, con la particolarità che le decisioni stesse non differiscono per i valori del primo, quarto e quinto attributo. In base alla definizione, gli attributi secondo e terzo sono preferenzialmente indipendenti dai restanti se, cambiando allo stesso modo i valori degli attributi 1, 4 e 5, e lasciando invariati i valori degli attributi 2 e 3,l’ordine di preferenza non cambia. Quindi, in regime di indipendenza preferenziale, ad esempio, si avrà:

(8 4 9 1 7) f (8 2 10 1 7) * * * * * * Gli obiettivi si dicono mutuamente preferenzialmente indipendenti se ogni sotto-insieme di attributi è preferenzialmente indipendente dal suo complementare. Debreu ha dimostrato il seguente altro teorema: Dati k obiettivi, esiste una funzione di utilità di tipo additivo u(f) =

∑ =ni ii fu1 )( se e solo se gli obiettivi sono mutuamente

preferenzialmente indipendenti. Questo teorema giustifica in via teorica la pratica corrente di aggregare gli obiettivi mediante una combinazione lineare (a coefficienti positivi) dei valori degli attributi o delle loro utilità:

u(x) = ∑ =

n

i ii fa1

(x), ai ≥ 0.

Al contrario, si comprende come non abbia una base razionale la costruzione di punteggi di tipo additivo quando vi sia una qualche forma di dipendenza tra le caratteristiche o i valori degli obiettivi legati ad una certa decisione. Pertanto tutti i modelli a punteggio (scoring) dovrebbero essere preceduti da una analisi approfondita sulla indipendenza degli attributi. Si può dimostrare che una alternativa x che sia punto di massimo in senso stretto per u(x) è anche Pareto ottima (non vale necessariamente il viceversa). Sotto opportune condizioni di convessità nello spazio degli obiettivi (cosa che la PL garantisce!) ogni soluzione x Pareto - ottima massimizza una funzione obiettivo che sia una combinazione

14

lineare degli obiettivi ∑ ⋅=ni ii f1α , per una opportuna scelta dei pesi

αi. Tornando all’esempio sopra riportato della PL con due obiettivi, tutti i punti del semento L’M’ sono ottimi a seconda dei pesi che si danno ai due obiettivi:

α1(2x-y) + α2(x+y).

Innanzitutto si vede come tutto dipenda non tanto dal valore effettivo dei due coefficienti α1 ed α2, quanto dal loro rapporto (purché ovviamente i coefficienti siano entrambi non negativi). Si potrà quindi fare riferimento al caso in cui α1 + α2 = 1, cioè con pesi normalizzati. La funzione obiettivo (unica) che si ottiene si può scrivere

z = (α1 + 1)x + (1 - 2α1)y (coincide con la prima funzione obiettivo z1 quando α1 = 1; con la seconda z2 quando α1 = 0). Con calcoli opportuni si vede come il punto L sia soluzione ottima per 0 ≤ α1 ≤ 0.2 mentre è soluzione ottima M quando si verifica 0.2 ≤ α1 ≤ 1. Sulla possibilità di comporre gli ordinamenti di un certo numero di decisori in un ordinamento globale univocamente individuato esiste un risultato, ben noto agli studiosi di Economia Politica, dovuto ad Arrow. Il teorema in questione viene detto anche di impossibilità in quanto stabilisce che è impossibile in generale la costruzione dell’ordinamento globale rispettando appunto alcuni principi di razionalità. La funzione che dovrebbe portare dagli ordinamenti singoli a quello collettivo viene anche detta funzione di scelta sociale. Per illustrare il teorema, supponiamo innanzitutto di avere m decisori ognuno dei quali esprime un ordinamento di preferenze su un certo insieme di n alternative. Indicheremo gli m ordinamenti che si ricavano con i simboli

1f , 2f , … mf .

Useremo il simbolo f G per indicare l’ordinamento globale. I requisiti di razionalità proposti da Arrow sono sostanzialmente i seguenti: - deve essere possibile costruire f

G a partire da qualsiasi insieme di ordinamenti parziali (vale a dire, la funzione di scelta sociale deve essere applicabile a partire da qualsiasi situazione = requisito di universalità); - fissato ad arbitrio un ordinamento globale f

G*, deve esistere un opportuno insieme di ordinamenti individuali per i quali la funzione di scelta sociale sia data proprio da f

G* (requisito detto di sovranità del cittadino);

15

- la funzione di scelta sociale deve essere non dittatoriale, cioè non deve esistere alcun decisore il cui ordinamento individuale diventa automaticamente quello globale; - se in ogni ordinamento if una alternativa A è preferita alla

alternativa B, allora anche nell’ordinamento globale A deve risultare preferita a B (requisito di unanimità); - se esistono due gruppi di decisori, con i rispettivi ordinamenti { 1f , 2f , … mf } ed { 1f ’, 2f ’, … mf ’} e questi due

gruppi sono tali che, per un determinato sottoinsieme Q di alternative, per ogni i, Qif coincide con Qif ’, allora negli

ordinamenti globali f G e f G ‘ le alternative in Q devono avere lo stesso ordinamento (indipendenza dalle alternative irrilevanti). Il requisito di unanimità è a volte sostituito da un altro detto di monotonicità (monotonia): se un decisore cambia il proprio ordinamento migliorando la valutazione di una certa alternativa (che quindi sale di posto nella graduatoria) allora l’ordinamento globale non può peggiorare la situazione dell’alternativa stessa (o la considera migliore, a sua volta, o la lascia invariata). Il risultato di Arrow ha carattere negativo: se le alternative sono almeno tre e i decisori almeno due allora non esiste una regola generale di costruzione di f G che soddisfi tute le proprietà elencate. Ovviamente, di fronte ad un tale risultato sono fioriti studi volti a coglierne gli aspetti pratici e a superare l’impasse che propone.

7. Programmazione a molti attributi.

Un problema di decisione con più attributi – come implicitamente è stato anticipato nel paragrafo precedente - può essere espresso in maniera concisa in forma matriciale mediante una tabella (m × n) il cui generico elemento xij indica la valutazione o il valore dell’attributo j-esimo nell’alternativa i-esima.

attributi A1 A2 … Aj … An

d1 x11 x12 … x1j … x1n

d2 x21 x22 … x2j … x2n

decisioni … … … … … o di xi1 xi2 … xij … xin

alternative … … … … … dm xm1 xm2 … xmj … xmn

16

L’elemento generico xij può avere natura diversa: può trattarsi di un valore numerico legato all’attributo (valore a carattere oggettivo, quale ad es. la velocità massima raggiungibile da un mezzo), di un punteggio in una prefissata scala, ma anche di una indicazione qualitativa (un comfort giudicato basso, medio, elevato ecc.). E’ evidente che i metodi di Programmazione Multi Attributo richiedono una trasformazione di eventuali indicazioni qualitative in indicazioni numeriche: ma occorre dire che, per alcuni modelli di decisione, è sufficiente che, nei riguardi di ogni attributo, le decisioni siano soltanto poste in graduatoria, da quella che presenta l’attributo in misura più elevata a quella che invece, sempre nei riguardi di tale attributo, si trova ad essere la decisione peggiore (con eventuali posizioni a pari merito). Nell’utilizzo della tabella (decisioni × attributi), in effetti, si pongono due tipi di problemi: l’uno legato alla presenza di attributi qualitativi, l’altro dovuto alla convenzione che richiede che ogni obiettivo sia da massimizzare e che quindi i valori preferibili degli attributi corrispondano ai valori numerici più elevati. Inoltre, nei modelli che si basano esclusivamente sui dati contenuti nella tabella stessa, occorre generalmente rettificare i valori numerici con qualche metodo di normalizzazione, per evitare che siano le unità di misura a influire sulla scelta del decisore. La trasformazione

indicazioni qualitative →→→→ valori numerici può essere effettuata in vari modi (con graduatorie, punteggi ecc.), ma deve comunque garantire che le indicazioni non privilegino a priori alcune decisioni rispetto ad altre. Non esiste una soluzione universale, ma sta alla sensibilità dell’analista e del decisore far sì che questa trasformazione di indicazioni non snaturi il problema originario. La trasformazione (se necessaria) dei valori di un attributo in modo che si abbia di fronte comunque un obiettivo da massimizzare può essere effettuata in vari modi, tra I quali occorre scegliere con attenzione perché anche in questo caso differenti metodi possono portare poi a indicazioni operative diverse. Fondamentalmente si può ricorrere ad un cambiamento di segno, utilizzando successivamente – se si vuole - costanti additive per avere a che fare con valori tutti positivi. In alternativa, se il valore 0 non fa parte del range dei valori ammissibili per l’attributo in questione, si può ricorrere al passaggio al reciproco (sostituendo al generico valore xij il valore 1/ xij). Quest’ultima operazione è quella che si effettua quando il consumo di carburante in litri/km (che il decisore in genere desidera minimizzare) viene trasformato nel dato reciproco km/litro, che invece deve evidentemente essere massimizzato.

17

Per quanto riguarda la normalizzazione, una volta ottenuta una tabella di dati numerici nella quale gli obiettivi siano tutti di massimo, si può procedere in vari modi:

- trasformare tutti i valori di un attributo in scala 0-1, in modo che il valore più basso riscontrato sia zero e il più grande sia 1;

- dividere tutti i valori di ogni colonna per il valore massimo sulla colonna stessa;

- rapportare tutti i valori ad una scala in cui il massimo, posto eguale a 1, sia il massimo valore ottenibile in assoluto per quell’attributo, a prescindere dai valori raggiunti con le decisioni disponibili e analogamente con il minimo della scala posto a 0.

Queste trasformazioni, è il caso di ribadire, vanno adottate in modo che non venga snaturato il problema decisionale o reso inutile il metodo di soluzione. La tabella (decisioni × attributi) può essere arricchita quando siano disponibili ulteriori informazioni. In particolare, si può aggiungere una riga di ‘pesi’ (wj) che indicano l’importanza per il decisore dei singoli attributi: A1 A2 … An

w1 w2 … wn

d1 x11 x12 … x1n

d2 x21 x22 … x2n

… … … … dm xm1 xm2 … xmn I pesi, ovviamente, sono numeri non negativi, di somma 1:

wj ≥ 0, ∀j; Σ wj = 1.

Se la tabella non è normalizzata, i pesi hanno anche lo scopo di correggere l’influenza delle unità di misura. I metodi di decisione di tipo Multi – Attributo (MADM, Multi Attribute Decision Making ) costituiscono delle proposte di procedure che, a partire dalle informazioni disponibili, portano a suggerire una scelta tra le varie decisioni. Come si vedrà, l’indicazione può consistere nella caratterizzazione di una decisione ‘ottimale’ oppure addirittura nella formulazione di una graduatoria tra tutte le alternative, ma, al contrario, può consistere nella individuazione di un sottoinsieme di alternative (più di una!), tra cui è ragionevole scegliere, escludendo le rimanenti, senza ulteriori indicazioni.

18

I modelli proposti in letteratura possono essere suddivisi in due categorie: non compensatori e compensatori. Sono del primo tipo i modelli che non utilizzano confronti tra gli attributi (in particolare, non richiedono che vengano espressi dei pesi: criterio della dominanza, minimax, maxmax, metodi congiuntivo e disgiuntivo). Sono compensatori invece i modelli:

a) a punteggio (scoring), quali il metodo dei pesi semplicemente additivo, l’AHP, ecc; in questi si sceglie l’alternativa che alla fine ha la valutazione (utilità) maggiore;

b) modelli di compromesso, quali il TOPSIS, il LINMAP, ecc; si sceglie l’alternativa che appare più prossima alla soluzione ideale;

c) modelli di concordanza, quali il metodo delle permutazioni, dell’assegnazione lineare, i vari metodi ELECTRE, nei quali si costruiscono o paragonano delle classifiche di preferenza.

I modelli di tipo compensatorio sono di più facile applicazione quando i valori degli attributi sono di tipo quantitativo oppure – nel caso di attributi ‘qualitativi’ – i valori stessi sono comunque espressi in forma numerica, ricorrendo ad opportune scale di misura.

Come ogni classificazione, quella espressa non coglie tutte le sfumature: ad esempio, il metodo lessicografico non usa dei pesi veri e propri, ma si basa comunque su confronti tra attributi.

7.1 Decisioni in assenza di informazioni sulle preferenze del decisore.

Nel caso in cui l’unica informazione disponibile è quella contenuta nella tabella di decisione, un problema Multi Attributo può essere risolto con l’individuazione delle alternative non dominate (lasciando al decisore la scelta di una di esse) o con altri criteri quali il maxmin ed ilmaxmax. La scelta per dominanza, oltre che come metodo a se stante, può servire per ridurre l’insieme delle alternative a disposizione prima di procedere ad applicare un qualche altro criterio. Il criterio maxmin prevede di valutare ogni decisione sulla base dell’attributo con la valutazione più piccola; infine tra tutte le decisioni si sceglie quella per cui tale valutazione ‘prudenziale’ sia la più grande. Si tratta evidentemente di un atteggiamento piuttosto pessimistico. Ogni alternativa viene giudicata sulla base della peggiore delle prestazioni che offre. Poi, ovviamente, si cerca quella che si comporta alla ‘meno peggio’.

19

In pratica, nella tabella (decisioni × attributi), per ogni decisione si individua il minimo tra i valori dei vari attributi: vi = min j xij. Tra i valori vi si individua il massimo, max i vi e questo individua la decisione preferita. Poiché si tratta di confrontare direttamente i valori di attributi di natura diversa il criterio richiede evidentemente che gli attributi siano normalizzati. Per esemplificare il procedimento, si consideri il problema di acquisto di un’autovettura avendo a disposizione 4 modelli dei quali vengono presi in considerazione gli attributi di velocità (A1), costo (A2), affidabilità (A3), manovrabilità (A4) e consumo (A5). Supponiamo la tabella sia la seguente:

A1 A2 A3 A4 A5 d1 120 13 media alta 15 d2 160 16 bassa media 13 d3 110 12.5 alta alta 16 d4 150 14.5 media media 13.5 Per poter applicare il criterio di scelta maxmin, i dati vanno rielaborati:

- costo e consumo devono essere espressi in modo che i corrispondenti obiettivi siano di massimizzazione: mentre per il consumo – come si è visto sopra - la cosa è pressoché immediata (facendo ricorso al chilometraggio per litro), per il costo occorre ricorrere ad un espediente, che introduce un evidente motivo di arbitrarietà;

- occorre trasformare i dati qualitativi in quantitativi; - infine, tutti i dati devono essere normalizzati.

Supponiamo di adottare i seguenti criteri: normalizzazione dei valori delle velocità (tutti i dati vengono divisi per 160) e del consumo (dati divisi per 16); passaggio ai reciproci per i costi e normalizzazione in modo che il costo più basso corrisponda al valore 1; per gli attributi qualitativi, utilizzo di una scala quantitativa a 7 valori (scala di Likert a 7 punti): molto scadente = 1, scadente = 2, basso = 3, medio-basso = 4, medio = 5, medio-alto = 6, alto = 7, valori normalizzati poi dividendoli per 7.. La tabella diventa allora:

A1 A2 A3 A4 A5 d1 0.75 0.96 0.71 1.00 0.94 v1 = 0.71* d2 1.00 0.77 0.43 0.71 0.81 v2 = 0.43 d3 0.69 1.00 1.00 1.00 1.00 v3 = 0.69 d4 0.94 0.86 0.71 0.71 0.84 v4 = 0.71*

e vi sono due decisioni migliori, a pari merito, cioè d 1 e d4. Il metodo maxmax è analogo al precedente salvo il fatto che adesso l’atteggiamento non è più cauto, ma ottimista: si valuta ogni decisione sulla base dell’attributo che ha la prestazione più elevata e quindi si individua la decisione (o le decisioni) che presenta (presentano) tale massimo. E’ evidente che se la normalizzazione viene effettuata attribuendo valutazione 1 a tutti i valori migliori per i vari attributi, il rischio di individuare più decisioni ottime è maggiore.

20

In effetti, con riferimento all’esempio precedente, si vede facilmente come ben tre decisioni si presentano con il valore massimo eguale ad 1, sicché alla fine il criterio ha il solo effetto di escludere la quarta alternativa. La eventuale propensione ‘di buon senso’ per d3 , che presenta ben quattro valori al livello massimo, non è contemplata da questo metodo, ma può essere un buon criterio suppletivo.

7.2 I pesi degli attributi e la loro determinazione.

Prima di esporre alcune tecniche multiattributo, che utilizzano valutazioni sulla importanza dei vari attributi, vale a dire, che usano dei pesi, discutiamo appunto in questo paragrafo le metodologie che possono aiutare il decisore (eventualmente, assistito nella procedura dall’analista) nel formulare i pesi stessi.

E’ ovvio che, di fronte ad un decisore che indica chiaramente per i vari attributi degli indici di importanza coerenti (cioè, dei numeri non negativi e di somma 1), il problema nemmeno si pone. Ma è altrettanto chiaro che, generalmente parlando, è improbabile che un decisore, di fronte, poniamo, a quattro attributi, arrivi a formulare un vettore di pesi così dettagliato come, per esemplificare, (.135, .568, .203, .094), posto che vi sia qualche ragione ‘oggettiva’ per presumere che questo vettore dovrebbe essere il più idoneo! Le approssimazioni sono in questo campo la regola. E altrettanto facilmente si può cadere in errori formali (‘pesi’ positivi, ma di somma diversa da 1).

Il decisore può essere aiutato con una procedura graduale, come quella che segue. Al decisore stesso vengono posti dei quesiti del tipo: ‘ Quante volte l’attributo Ai è ritenuto più importante dell’attributo

Aj ?’. Questo giudizio numerico verrà indicato in seguito con il simbolo aij. E’ plausibile – anche se irrilevante per il procedimento - che il decisore si esprima mediante un numero intero (ad es., se Ai è 3 volte più importante di Aj, allora aij = 3), oppure con il reciproco di un numero intero (ad es., se è Aj ad essere più importante di Ai - poniamo, due volte - il decisore esprimerà questa sua opinione con l’indicazione aij = 1/2). Di confronti del tipo indicato se ne possono proporre n(n-1) (è evidente che ogni attributo è della stessa importanza di se stesso, per cui aii = 1, per ogni i), e quindi i risultati dei confronti possono essere raccolti in una matrice di confronti a coppie tra attributi. Va notato, tuttavia, che se ci si limita ad n-1 quesiti, prendendo come riferimento un particolare attributo (ad es. A1), e ponendo solo le domande relative al confronto di tale attributo A1 con i rimanenti (ottenendo quindi a12, a13, …, a1n), allora questi valori sono sufficienti ad individuare correttamente i pesi.

21

Infatti, da un punto di vista teorico, deve risultare aij = wi / wj. Di conseguenza, conoscendo il valore dei rapporti

a11 = 1

1

w

w, a12 =

2

1

w

w , a13 =

3

1

w

w, … , a1n =

nw

w1

e passando ai reciproci

(1/a11) = 1

1

w

w, (1/a12) =

1

2

w

w , (1/a13) =

1

3

w

w, … , (1/a1n) =

1w

wn ,

si ottiene

(1/a11) + (1/a12) + (1/a13) + … + (1/a1n) = 1

1

w

w+

1

2

w

w+

1

3

w

w+…+

1w

wn =

= (1/ w1) Σ wj = 1/ w1.

Di conseguenza, si può ricavare innanzitutto il peso di A1:

w1 = 1 / [(1/a11) + (1/a12) + (1/a13) + … + (1/a1n)],

e quindi i pesi rimanenti

wj = w1 / a1j. Tuttavia l’esperienza induce a chiedere al decisore di esprimersi su tutte le possibili coppie di attributi, per evidenziare eventuali incoerenze e poterle poi correggere. Il decisore (e quindi la matrice dei confronti a coppie) è coerente se le sue valutazioni soddisfano i seguenti requisiti:

1) aij = 1 / aji; 2) aik akj = aij. La prima condizione è ovvia (e si può pensare generalmente verificata): se l’attributo Ai è un certo numero q di volte più importante di Aj, allora Aj ha 1/q – esimo di importanza rispetto ad A i. La seconda condizione, pur se altrettanto ovvia, può non essere rispettata a causa della stessa povertà della scala di misurazione dei rapporti di importanza. In teoria, un decisore che ritiene Ai 3 volte più importante di Ak e poi ritiene Ak 2 volte più importante di Aj, dovrebbe anche valutare Ai 6 volte più importante di Aj: ma può capitare che, di fronte ad un numero non banale di attributi, senza rendersi conto dell’incoerenza in cui cade, indichi Ai come (solo) 5 volte più importante di Aj. Come si è detto, se le 1) e 2) sono soddisfatte, si dice che la matrice dei confronti a coppie è coerente. Compito dell’analista è innanzitutto quello di verificare la coerenza delle indicazioni del decisore. Se poi queste non lo sono del tutto (nel senso che per qualche insieme di indici non valgono le relazioni appena indicate), si tratterà di individuare comunque dei

22

pesi che rispecchino (senza stravolgerle) le indicazioni del decisore, rendendole coerenti. A tale scopo sono state proposte diverse tecniche: in questa sede ne illustriamo due. Il metodo dei minimi quadrati e il metodo degli autovalori. Il metodo dei minimi quadrati affronta il problema della costruzione di pesi, che rispettino sostanzialmente lo spirito delle indicazioni del decisore, partendo dalla constatazione che, in condizioni di perfetta coerenza, vale la eguaglianza

.j

iij w

wa =

Di conseguenza, sempre se il decisore è coerente, i coefficienti aij ed i pesi wk soddisfano la relazione

aij ⋅ wj - wi = 0. (*) Se il decisore non è coerente

.j

iij w

wa ≠

e la relazione (*), in generale, non è più vera. Si propone allora di risolvere il seguente problema di programmazione matematica (nelle incognite w1, w2, … wn)

Min Σij (aij ⋅ wj - wi)2

con i vincoli Σi wj = 1; wj ≥ 0. Il problema è sostanzialmente equivalente al seguente: essendo aij ≠ wi / wj, se indichiamo con εij la differenza (aij - wi / wj), si tratta di minimizzare, con una opportuna scelta dei pesi, la somma degli scarti al quadrato tra i valori espressi dal decisore, aij, e i apporti tra i pesi:

Min Σij (aij ⋅ wj - wi)2 = Min Σij (εij ⋅ wj )

2

Tuttavia è facile constatare come questa seconda formulazione sia non immediatamente utilizzabile perché sia gli scarti εij sia i pesi sono incogniti. Il metodo degli autovalori è ben noto perché collegato ad un modello di decisione che verrà illustrato in seguito, l’AHP. Premettiamo alcuni concetti relativi alle trasformazioni lineari. Dati una matrice A di dimensione m×n, l’insieme dei vettori x n-dimensionali e l’insieme dei vettori m-dimensionali y, la eguaglianza y = Ax può essere interpretata come una trasformazione che, a partire dal vettore x, per mezzo

23

appunto della matrice A, dà origine al vettore y. In generale cambiando x muta il vettore y che si ottiene (ma non è detto che la trasformazione sia biunivoca!). I vettori x (di partenza) e y (trasformato di x), appartengono in generale a spazi diversi (a ciò si può anche aggiungere che, in base alle definizioni usuali dell’algebra vettoriale e matriciale, nell’impostazione data, x è un vettore colonna mentre y è un vettore riga!). Tuttavia, se la matrice A è quadrata, ci si può chiedere se è possibile individuare particolari vettori x* per i quali valga Ax* = (x* )T , cioè vettori che, a parte il passaggio da colonna a riga, rimangono invariati nelle loro componenti dopo la trasformazione. Ragioni teoriche inducono tuttavia a rendere più morbido il requisito: ci si chiede se esistono vettori x* tali che risulti, per qualche valore λ, Ax* = λ (x* )T. In questo modo il problema iniziale (ricerca di vettori che vengano trasformati in se stessi) viene modificata nel seguente: ricerca di vettori che, dopo la trasformazione, mantengono la stessa direzione (risultano allungati o accorciati rispetto alla situazione di partenza, ma continuano a essere posizionati lungo la stessa retta). Il fatto di essere ‘trasformati in se stessi‘ – a meno di una dilatazione – viene enfatizzato definendoli come autovettori; la costante λ viene invece denominata autovalore: pertanto si parla di autovettore ed autovalore ad esso associato. Per individuare autovettori ed autovalori, si deve considerare che il sistema

Ax = λx equivale a

(A-λI) x = 0, e si tratta pertanto di un sistema omogeneo per il quale si hanno soluzioni non nulle se e solo se il determinante della matrice dei coefficienti è diverso da zero. Questa condizione è quella che permette di individuare innanzitutto λ (in generale, si hanno più valori di λ: si considera in genere quello di modulo massimo) e quindi a sua volta si può individuare x. Alla base del metodo sta la constatazione che, se la matrice dei confronti a coppie è coerente, allora si verifica che aij = wi / wj e anche A w = n w. Infatti, se A è coerente, la stessa matrice può essere scritta come

a11 a12 … a1n w1 / w1 w1 / w2 … w1 / wn a21 a22 … a2n w2 / w1 w2 / w2 … w2 / wn … … … … = … … … … an1 an2 … ann wn / w1 wn / w2 … wn / wn Si vede facilmente come il prodotto della matrice A per il vettore (colonna) w = (w1 w2 … wn) dia in effetti nw. Pertanto si può affermare che se A è coerente, il vettore w dei pesi è un autovetture di A e l’autovalore corrispondente coincide con la dimensione di A. Se A non è coerente, l’autovalore (massimo) non è n, ma se l’inconsistenza di A non è molto forte, l’autovalore massimo risulta prossimo a n. La differenza (λmax – n) viene assunta quale indicatore della consistenza (inconsistenza) della matrice A. Il metodo prevede, pertanto, di risolvere l’equazione, nell’incognita λ,

24

det (A - λ I) = 0, e quindi di utilizzare l’autovalore (di modulo) massimo, λmax nella risoluzione del sistema (ove le incognite sono i pesi w1, w2, …, wn):

=∑

⋅=⋅

=1

1

max

n

iiw

wwA λ

Un esempio potrà chiarire ulteriormente la procedura. Supponiamo che il decisore, di fronte a 3 attributi, abbia espresso dei giudizi riassunti nella matrice dei confronti a coppie seguente: 1 1/3 1/2 A = 3 1 3 2 1/3 1 Si può constatare che la matrice non è coerente (il secondo attributo è 3 volte più importante dei restanti due, i quali dovrebbero avere quindi lo stesso peso: ma ciò viene messo in discussione dal fatto che il primo attributo è giudicato meno importante del terzo, addirittura la metà!). Calcoliamo quindi gli autovalori di A, cioè risolviamo l’equazione 1-λ 1/3 1/2 det (A-λI) = 3 1-λ 3 = 0. 2 1/3 1-λ Sviluppando il determinante, si ottiene l’equazione (di terzo grado in λ):

-λ3 + 3 λ2 + 1/2 = 0,

La cubica y = -λ3 + 3 λ2 + 1/2 presenta un punto di minimo in λ = 0 (il valore del minimo è 1/2) e quindi ha una sola intersezione con l’asse delle ascisse. L’equazione che si vuole risolvere ha quindi una sola radice reale (ne ha altre due, complesse coniugate) che può essere individuata per via numerica e risulta approssimabile, a meno di un decimillesimo, con λ = 3.0536. Si tratta adesso di risolvere il sistema

=∑

⋅=⋅

=1

0536.33

1iiw

wwA

dal quale si ricava il vettore w = (.1571 .5936 .2493). Può essere interessante riscrivere la matrice dei confronti a coppie coerente con i pesi appena ottenuti. Essa risulta 1 .265 .630 A = 3.770 1 2.381 1.587 .420 1 E’ anche il caso di osservare che la difficoltà numerica sta nel fatto che gli autovalori si individuano mediante la risoluzione di una equazione avente grado pari al numero degli attributi: già con tre attributi, quindi, si tratta di dover ricorrere ad espedienti tipici del calcolo numerico!

25

Esistono in letteratura altre proposte per il calcolo dei pesi degli attributi. Segnaliamo due tecniche. Il metodo dell’entropia non richiede confronti da parte del decisore, ma si basa esclusivamente sui dati dei singoli attributi: ha quindi un certo carattere di ‘oggettività’ anche se con tutti i limiti che si vedranno. Il principio che sta a fondamento del metodo è il seguente: se un attributo ha valori simili per tutte le alternative, allora ha una importanza scarsa: al limite, non è utile per discriminare tra le varie alternative, se il valore, per ognuna di queste, è lo stesso. Viceversa, quanto più il range dei valori assunti è alto, tanto più l’attributo deve essere ritenuto importante. Il metodo si basa su concetti tipici della teoria dell’informazione, in particolare sull’entropia, usata quale indicatore del grado di dispersione degli elementi in gioco, opportunamente adattata al contesto. Si procede nel modo seguente. Si trasformano i valori degli attributi in modo tale che la somma dei valori di uno stesso attributo per le varie alternative sia eguale a 1. Indichiamo tali nuovi valori con i simboli pij: il simbolo, non a caso, richiama il concetto di ‘probabilità’, contesto nel quale l’entropia stessa fu inizialmente definita. Si calcola quindi per ogni attributo la quantità

Ej = -( ij

n

i ij pp ln1∑ =

)/ln n

che viene detta entropia (dell’attributo j-esimo). Si pone quindi dj = 1 – Ej e infine

wj = dj / ∑ =

m

i jd1

.

E’ relativamente facile constatare che, se un attributo ha lo stesso valore per tutte le alternative, allora la sua entropia assume il suo valore massimo, vale a dire 1 e quindi risulta dj = wj = 0. Con una dimostrazione un po’ più laboriosa, si può fare vedere, invece, che l’entropia è tanto più piccola (→ 0+) quanto più i valori di un attributo si avvicinano ad una situazione nella quale una alternativa ha il valore dell’attributo stesso al livello più grande (prossimo quindi a 1) mentre presenta valori prossimi a 0 in tutte le alternative rimanenti. In ogni caso, l’entropia è una quantità non negativa. Un risultato (che può apparire paradossale o, quanto meno, che fornisce pesi che non aiutano molto nella decisione) è il seguente: se ogni attributo presenta un valore di eccellenza in una alternativa e valori relativamente scarsi in tutte le altre, allora gli attributi tendono ad avere tutti lo stesso peso. E’ razionale, invece il fatto che, se un attributo ha valori eguali in tutte le alternative, allora potrebbe addirittura essere eliminato dalla tabella di decisione. Comunque la critica più forte viene dalla considerazione, anche questa del tutto legittima, che i pesi, intesi come indicatori di importanza, non dovrebbero dipendere dai livelli stessi degli attributi, elemento invece che è proprio la caratteristica fondamentale del metodo dell’entropia. Il metodo LINMAP è un vero e proprio criterio di decisione che, oltre che individuare dei pesi, dà anche indicazioni sulla decisione da scegliere: per questo motivo verrà accennato più avanti.

26

7.3 Decisioni con informazioni sugli attributi.

Le informazioni disponibili per i vari attributi possono assumere varie forme. Si possono specificare:

- livelli standard per ogni attributo; - importanza relativa di ogni attributo, espressa mediante una

preferenza di tipo ordinale (un puro e semplice ordinamento degli attributi, dal più importante al meno);

- importanza relativa espressa con preferenze cardinali o pesi;

- tassi marginali di sostituzione tra attributi.

7.3.1 Metodi congiuntivo e disgiuntivo Se si dispone dei livelli standard , che indicheremo con xj

*, e da pensare come dei livelli minimali desiderati per le varie caratteristiche, si possono applicare al problema di decisione i metodi congiuntivo e disgiuntivo. Il metodo congiuntivo prevede che una alternativa è accettabile se e solo se per ogni attributo il valore è non inferiore al corrispondente livello standard. Il metodo disgiuntivo prevede invece che una alternativa è accettabile se e solo se almeno un livello standard è soddisfatto. Un esempio può chiarire i due procedimenti. Consideriamo innanzitutto il metodo congiuntivo. Sia data la tabella di decisione

A1 A2 A3 A4 A5 d1 8.3 3 110 0.67 41 d2 7.7 8 120 0.72 38 d3 2.0 9 145 0.33 29 d4 5.1 7 125 0.49 50

e supponiamo che i livelli standard siano: 5.0 per A1, 6 per A2, 115 per A3, 0.45 per A4, 40 per A5. In base al primo dei livelli standard viene eliminata d3, per il secondo attributo viene eliminata d1. Rimangono d2 e d4 che entrambe superano le soglie per i criteri A3 e A4, mentre passando a considerare A5 si vede che l’unica decisione tra le due rimaste che rispetta lo standard è d4. Si può facilmente osservare che se si applicasse il metodo disgiuntivo con le stesse soglie, tutte le decisioni risulterebbero accettabili: è evidente che nel metodo disgiuntivo si possono porre soglie più stringenti. Adottando le soglie 9 (A1); 10 (A2); 140 (A3); 0.70 (A4); 60 (A5), le decisioni accettabili sono d3 (per il suo valore di eccellenza nell’attributo A3) e d2 (per il suo elevato valore nell’attributo A4).

27

7.3.2 L’eliminazione per aspetti e il metodo lessicografico.

Con preferenze ordinali tra attributi si può ricorrere al metodo dell’eliminazione per aspetti ed al metodo lessicografico.

Nella tecnica detta di eliminazione per aspetti, gli aspetti stessi sono sostanzialmente gli attributi con i loro valori. Per ogni ‘aspetto’ si fissa un livello, da considerare come una soglia che si desidera sia superata per l’alternativa scelta. Oltre a ciò, vi è un ordinamento degli attributi, dal più al meno importante. Si procede ponendosi una successione di domande del tipo: per l’attributo in questione, quali alternative – tra quelle ancora in gioco - soddisfano la soglia fissata? Le alternative che non superano tale livello vengono eliminate e si passa all’attributo (aspetto) successivo. La procedura può avere due esiti diversi:

- rimangono una o più decisioni che superano tutte le soglie: in tal caso è a queste che dovrà rivolgersi il decisore per la sua scelta;

-giunti ad un certo punto, nessuna alternativa soddisfa un determinato requisito, ed allora si possono considerare valide le alternative rimaste dopo la domanda precedente. Nel metodo lessicografico si individuano le alternative ottimali sulla base del criterio ritenuto più importante. Se ve ne è una sola, la procedura ha termine. Se ne esiste più di una, si confrontano le alternative che sono risultate a pari merito sulla base del primo attributo analizzandone i valori che presentano per il secondo – sempre in ordine di importanza - degli attributi. Di nuovo, se una sola tra le alternative rimaste presenta il valore massimo per il secondo attributo, allora è l’alternativa preferita; se ve ne sono due o più a pari merito, queste vengono confrontate sulla base del terzo attributo e così via. Il metodo prende il nome dall’ordinamento che è tipico delle parole in un dizionario linguistico (ad es., in un vocabolario di italiano). Date due parole diverse, l’ordine con cui si trovano viene stabilito confrontando la prima lettera delle parole stesse (calore viene prima di dado); se però la prima lettera è uguale, allora il confronto si esegue sulla seconda (calore viene prima di colore); se anche le seconde lettere sono eguali, si passa alla terza (per cui calore viene dopo cabina). Per evitare che un differenza molto lieve possa portare verso una alternativa trascurandone altre che potrebbero essere molto più valide di questa per altri attributi, si può modificare la procedura introducendo dei margini di tolleranza e considerare vincenti per ogni attributo le alternative che presentano il valore massimo oppure si discostano d questo per non più di un certo valore (o di una percentuale) h. Con questo accorgimento, il metodo lessicografico si avvicina nella filosofia al precedente (è come se per livello soglia di ogni aspetto si fissasse il valore massimo riscontrato nell’attributo diminuito di una quantità (che può essere fissa o variare da un attributo ad un altro). Esemplifichiamo le due procedure – e la variante – con un esempio. Consideriamo quindi la seguente tabella di decisione, nella quale supponiamo che l’ordinamento di importanza tra gli attributi sia

28

A2 f A4 f A5 f A3 f A1.

A1 A2 A3 A4 A5 d1 8.3 9 110 0.57 41 d2 7.7 8 120 0.72 38 d3 2.0 9 145 0.57 29 d4 5.1 7 125 0.49 50 a) eliminazione per aspetti: se le soglie sono: 5 (per A2); 0.55 (per A4); 35 (per A5); 120 (per A3); 5.0 (per A1), allora la prima soglia non discrimina tra le alternative; la seconda porta alla eliminazione di d4; la terza fa eliminare d3; la quarta soglia fa eliminare d1, mentre la quinta soglia non cambia nulla. b) metodo lessicografico (versione originaria): sulla base di A2 la scelta si restringe a d1 e d3; considerando A4 la situazione rimane invariata; passando all’attributo A5 si individua la soluzione preferita d1 (gli altri attributi sono, a questo punto, ininfluenti). c) metodo lessicografico con tolleranza: se il margine è del 15%, sulla base dell’attributo A2 viene eliminata solo d4; poi, sulla base dei valori per A4 viene scelta d2 (che con il metodo lessicografico originario veniva eliminata al primo passo). La disponibilità di pesi sui vari attributi dà la possibilità di utilizzare vari metodi di scelta, sia con l’obiettivo di individuare la decisione migliore, sia con lo scopo di stabilire una graduatoria tra tutte le decisioni. Si osservi che una graduatoria può essere utile per consentire un margine di libertà al decisore stesso e soprattutto per avere indicazioni in ogni caso in cui, per un motivo qualsiasi, la decisione ‘ottima’ diventasse impraticabile.

7.3.3 Metodo dei pesi additivi E’ noto anche con la sigla SAW (Simple Additive Weigthing). E’ il criterio più semplice, in presenza di indicazioni sui pesi, e consiste nell’attribuzione ad ogni alternativa di un punteggio sulla base della media pesata dei valori degli attributi. I valori stessi devono essere normalizzati (a meno che non si inglobi nel peso di ogni attributo anche un elemento di correzione per tenere conto di differenti unità di misura nei valori degli attributi stessi). Formalmente, l’alternativa i-esima viene valutata con

∑ == n

j ijji xwv1

E’ anche il caso di ricordare che questa valutazione ha significato se e solo se gli attributi sono preferenzialmente indipendenti, come visto in un paragrafo precedente).

29

7.3.4 Metodi di valutazione e costruzione di ranking Mirano alla valutazione / costruzione di graduatorie il metodo delle permutazioni ed il metodo dell’assegnazione lineare. Il metodo delle permutazioni (che può anche essere definito delle concordanze e discordanze) si pone l’obiettivo di valutare graduatorie tra le alternative (e quindi di confrontare tra di loro due o più ordinamenti tra le decisioni disponibili). Supponiamo quindi che il decisore abbia espresso una sua propria graduatoria tra le alternative, graduatoria che corrisponde ad una permutazione degli indici 1, 2, …, m delle decisioni. Con riferimento a questa graduatoria si calcolano due insiemi di valutazioni. Siano dh e dk due alternative che il decisore ha collocato nella graduatoria in modo tale che

…f dh f… f dk f… cioè, egli ritiene che, in una valutazione complessiva degli attributi, dh sia da preferire a dk. D’altra parte, il decisore ha espresso anche dei pesi sugli attributi. In generale, in una situazione in cui non vi siano alternative dominate (eventualmente, quando queste sono state cancellate dall’elenco delle decisioni ammissibili!) dh risulterà migliore di dk per certi attributi ma peggiore per certi altri. La concordanza Chk (tra la graduatoria in cui dh precede dk e i pesi) indica quanto l’ordinamento scelto rispetta i pesi degli attributi ed è data dalla somma dei pesi degli attributi per cui dh è migliore (non peggiore) di dk, cioè quando xhj ≥ xkj. Formalmente:

Chk = ∑ ≥ kjhj xxj jw

In modo del tutto analogo si può definire la discordanza Dhk, somma dei pesi degli attributi nei quali l’alternativa dh è non migliore di dk. Concordanze e discordanze possono essere raccolte in una tabella (matrice di concordanza/discordanza), dove il valore degli elementi sulla diagonale è irrilevante: sulla parte al di sopra della diagonale principale vengono riportate le concordanze; le discordanze sono indicate invece nella zona al di sotto della diagonale. Si calcola la somma delle concordanze e si sottrae quella delle discordanze. Il valore ottenuto è un indice della ‘bontà’ della graduatoria. Consideriamo il seguente esempio. Sia data la tabella di decisione in forma normale nella quale sono indicati anche i pesi dei vari attributi:

30

A1 A2 A3 A4 A5 d1 8.3 9 110 0.57 41 d2 7.7 8 120 0.72 38 d3 2.0 9 145 0.57 29 d4 5.1 7 125 0.49 50 pesi 0.15 0.10 0.25 0.30 0.20 e consideriamo l’ordinamento d2 f d4 f d3 f d1 . Può essere utile scrivere un’altra matrice di decisione nella quale per ogni attributo si indica il ranking tra le varie alternative, che è a ben vedere l’unico elemento che interessa nei calcoli successivi:

A1 A2 A3 A4 A5

pesi 0.15 0.10 0.25 0.35 0.15 d1 1 1 4 2 2 d2 2 3 3 1 3 d3 4 1 1 2 4 d4 3 4 2 4 1 La matrice di concordanza / discordanza è del tipo 4 × 4 e risulta la seguente:

d2 d4 d3 d1 d2 - 0.60 0.65 0.60 d4 0.40 - 0.30 0.40 d3 0.35 0.70 - 0.70 d1 0.40 0.60 0.75 - (nella quale, per esemplificare, il valore 0,65, sulla prima riga, è la somma dei pesi di A1, A4 e A5, attributi per i quali d2 ha una performance migliore di d3). L’indice sintetico risulta

3.25 – 3.20 = 0.05. Il valore numerico dell’indice, in quanto tale, non ha particolare significato. Il criterio, in effetti, acquista senso se si hanno a disposizione più graduatorie da confrontare: sarà ovviamente da preferire il ranking con il più elevato indice. La denominazione del metodo proviene dal fatto che le possibili graduatorie sono tante quante le permutazioni su un numero di elementi eguale al numero delle alternative: questo suggerirebbe la ricerca della graduatoria migliore mediante valutazione esaustiva di tutti i possibili ordinamenti. In pratica, questo è ragionevole solo quando le alternative sono al più una decina. In caso fossero più numerose, il tempo macchina richiesto da un elaboratore elettronico diventerebbe proibitivo. Il metodo dell’assegnazione lineare, a differenza del precedente, si pone l’obiettivo di costruire il ranking migliore tra gli n! possibili. Come nel metodo delle permutazioni, necessita dei pesi associati ai vari attributi e della graduatoria di valore di ogni attributo nei riguardi delle varie alternative: non richiede espressamente i valori numerici degli attributi stessi. Si adatta quindi bene anche a situazioni in cui alcuni attributi sono di tipo

31

qualitativo e i corrispondenti valori sono ‘aggettivi’ piuttosto che numeri. Il metodo prevede di indicare per ogni decisione quale è il posto ‘migliore’ che questa deve occupare in un ranking di tutte le alternative disponibili. Si tratta quindi di stabilire un ‘ordine di arrivo’ ideale per le varie alternative, viste come elementi di una gara in cui ci si disputano i vari piazzamenti. Il termine assegnazione indica, in Ricerca Operativa, l’associazione (biunivoca) tra gli elementi di due insiemi, di natura diversa, ma contenenti lo stesso numero n di elementi. Una assegnazione tra i 2n elementi consiste in un insieme di n coppie. Nel caso in questione, ogni coppia è costituita da una alternativa e da una posizione in graduatoria. Con riferimento ad un problema con m alternative e k attributi, si costruisca una matrice quadrata Π, di dimensione m×m, il cui elemento generico πij esprime una valutazione del fatto che la decisione (alternativa) di venga collocata nel j-esimo posto della graduatoria. Indicando le posizioni con i simboli P1, P2, …, Pm, si può scrivere P1 P2 … Pj … Pm

d1 π11 π12 … π1j … π1m

d2 π21 π22 … π2j … π2m

Π = … … … … … di πi1 πi2 … πij … πim

… … … … … dm πm1 πm2 … πmj … πmm Il generico πij è calcolato come la somma dei pesi degli attributi per i quali la decisione i-esima si colloca al posto j-mo. Ricorrendo all’esempio proposto riguardo del metodo precedente, data la tabella di ranking tra gli attributi

A1 A2 A3 A4 A5

pesi 0.15 0.10 0.25 0.35 0.15 d1 1 1 4 2 2 d2 2 3 3 1 3 d3 4 1 1 2 4 d4 3 4 2 4 1 la matrice Π è di tipo 4 × 4 e, per esemplificare, l’elemento π11 vale 0.25 (somma dei pesi del primo e secondo attributo); π12 vale 0.50 (perché la prima decisione si colloca al secondo posto relativamente agli attributi A4 e A5; π13 invece vale 0 perché la prima decisione non è mai al terzo posto, e così via. La matrice Π risulta alla fine la seguente:

P1 P2 P3 P4

d1 .25 .50 .00 .25 d2 .35 .15 .50 .00 d3 .35 .35 .00 .30 d4 .15 .25 .15 .45

32

Si tratta adesso di attribuire ogni decisione ad un posto e, viceversa, far sì che ogni posto sia occupato da una sola decisione. A tale scopo si introducono, come variabili di decisione, m2 variabili xij, che possono assumere solo uno dei due valori, 0 oppure 1, con il seguente significato: xij = 1, se e solo se la decisione i-ma occupa il posto j-esimo: si crea

la coppia (di, Pj); xij = 0, in caso contrario.

Le variabili di decisione devono rispettare due categorie di vincoli: per ogni indice i, una sola variabile xij può assumere valore 1; analogamente, per ogni indice j. Pertanto, una soluzione ammissibile del problema può essere rappresentata con una matrice X, ancora di tipo m×m, nella quale vi è un solo elemento eguale a 1 per ogni riga e un solo elemento eguale a 1 per ogni colonna: tutti gli elementi restanti sono eguali a 0. Nel caso dell’esempio che stiamo sviluppando, una soluzione ammissibile può essere la seguente:

P1 P2 P3 P4

d1 0 0 0 1 d2 1 0 0 0 d3 0 0 1 0 d4 0 1 0 0 che esprime il ranking d2 f d4 f d3 f d1. Come criterio (funzione obiettivo) da massimizzare, si utilizza la somma degli elementi πij corrispondenti agli xij che assumono valore 1. Si ottiene quindi il problema di programmazione matematica seguente

Max Σij πij xij

con i vincoli Σj xij = 1, (per i = 1, 2, …, m); Σi xij = 1, (per j = 1, 2, …, m); xij ∈{0, 1} (per i, j = 1, 2, …, m). L’ultimo insieme di vincoli (vincoli di interezza) esprimono appunto il fatto che ogni variabile di decisione può assumere solo uno dei due valori, 0 oppure 1. Il problema di programmazione cui si è giunti è una variante del cosiddetto problema di assegnazione (AP, assignment problem) ben noto in letteratura: la differenza sostanziale è che nella versione classica la funzione obiettivo è da minimizzare. A sua volta, il problema di assegnazione può essere visto come una variante del problema (modello) di trasporto, nel quale

- vi siano tante origini quante destinazioni;

33

- la merce disponibile in ogni luogo di produzione è in quantitativo unitario; - altrettanto unitaria si presenta la domanda in ogni luogo di consumo. In più, rispetto al modello di trasporto, vi è il vincolo che la merce uscente da un luogo di produzione non può essere suddivisa tra destinazioni diverse: ma si dimostra che, nella soluzione ottima, una suddivisione del carico non è mai conveniente. Pertanto, per la risoluzione di questi problemi si può ricorrere tranquillamente alle solite tecniche di Programmazione Lineare (e al software comunemente disponibile negli elaboratori di recenti generazioni), con la garanzia che la soluzione finale è costituita esclusivamente da valori 0 oppure 1. Tornando all’esempio di cui sopra, si determina l’ordinamento migliore come quello corrispondente alla matrice X che segue:

P1 P2 P3 P4

d1 0 1 0 0 d2 0 0 1 0 d3 1 0 0 0 d4 0 0 0 1 che corrisponde all’ordinamento d3 f d1 f d2 f d4 con un valore della funzione obiettivo z = 1.80.

7.3.5 Il metodo AHP Il metodo AHP, Analytic Hierarchy Process, è un procedimento che permette di attribuire alle varie alternative un peso che ne rappresenta l’efficacia relativa nel raggiungimento dell’obiettivo finale. Questo non è specificato ulteriormente, ma è sottinteso nel processo stesso che si tratta della massima soddisfazione da parte del decisore. La tecnica fu proposta dal matematico americano, di origine irachena, Thomas Saaty negli anni ’70. Fu oggetto di studi e critiche molto approfonditi: lo stesso Saaty estese il modello di decisione proponendo il più elaborato Analytic Network Process, che qui non verrà preso in considerazione. Nell’AHP si suppone che nel procedimento di decisione il decisore si trova di fronte a elementi di giudizio organizzati in vari livelli (almeno tre): tali elementi sono rappresentati mediante nodi di un grafo disposti su tante righe quanti sono i livelli. Al livello superiore compare un unico nodo, che rappresenta l’obiettivo: questo non viene ulteriormente specificato, ma può essere espresso semplicemente come la soddisfazione del decisore (che deve essere massimizzata). Al livello più basso figurano le alternative. Nei livelli intermedi compaiono le caratteristiche da tenere in considerazione nel processo decisionale: nel caso più semplice, vi è un solo livello intermedio e in esso compaiono gli attributi. Ogni elemento di un livello esercita un ‘influsso’ su tutti o parte degli elementi del livello immediatamente superiore. L’esistenza di questo influsso viene espressa mediante un arco (segmento).

34

L’entità dell’influsso è in sostanza un peso, associato all’arco, che viene di volta in volta determinato facendo sistematicamente ricorso ad una delle tecniche di determinazione dei pesi (in particolare, al metodo degli autovalori). Sempre con riferimento al caso più semplice, supponendo di avere a disposizione due alternative e di valutarle su tre attributi, la rappresentazione è la seguente: Si noti che con tali premesse, i valori degli attributi, anche se questi risultano di tipo quantitativo, e quindi facilmente esprimibili numericamente, non sono rilevanti: quello che conta è il raffronto sull’efficacia di ogni elemento dello stesso livello nei riguardi di ciascun elemento del livello superiore. In sostanza, per formulare il problema e ottenere una indicazione operativa, nel caso in figura di due decisioni e tre attributi, il decisore deve rispondere ad una serie di domande come segue:

- (tenendo a mente l’obiettivo complessivo) quanto ogni attributo è più o meno importante, rispetto agli altri, ai fini del raggiungimento dell’obiettivo? (vanno quindi confrontati a due a due i tre attributi, ottenendo la matrice dei confronti a coppie di tipo 3x3, da rendere coerente);

- (per ciascuno dei tre attributi) quanto (= quante volte) la

prima decisione è da ritenere più soddisfacente dell’altra nei riguardi dello specifico attributo? (trattandosi qui di due sole decisioni, il problema della coerenza non si pone; si hanno comunque tre matrici 2x2 di confronti a coppie.

In strutture con più di tre livelli possono esserci in uno

stesso livello caratteristiche che specificano in maniera più dettagliata gli elementi del livello immediatamente superiore: ma l’impostazione rimane la stessa e, per ogni elemento di un dato livello, occorre sempre chiedersi quale è la importanza su di esso di tutti gli elementi del livello immediatamente inferiore

obiettivo

Attributo 1 Attributo 2 Attributo 3 Decisione 1 Decisione 2

35

(l’importanza può essere nulla se manca un arco o il suo peso è zero).

Riassumendo, con ogni arco (segmento) che congiunge due caselle (di livelli adiacenti) si esprime il fatto che esiste una relazione (influsso) tra questi elementi, influsso che va dal basso verso l’alto.

Può succedere che una alternativa non abbia nessi logici con tutti gli attributi o, viceversa, che un attributo abbia significato solo per certe alternative (non per tutte). Se tutti gli elementi di ogni livello sono collegati con tutti gli elementi del livello superiore, si dice che la gerarchia è completa (in caso contrario, si dirà incompleta). Tuttavia, da una gerarchia incompleta se ne può generare una completa aggiungendo archi di peso nullo. Ai segmenti che collegano differenti elementi di un livello (inferiore) ad uno stesso elemento di un livello immediatamente superiore, come si è detto, vengono attribuiti dei valori numerici che prendono il nome di priorità . Queste esprimono l’importanza normalizzata degli elementi di uno stesso livello nei riguardi del livello superiore al quale sono collegati. Ad esempio, con la figura livello superiore livello inferiore si esprime il fatto che il primo elemento del livello inferiore è due volte più efficace rispetto al terzo elemento (e 6 volte rispetto al secondo) nel raggiungimento delle caratteristiche proprie dell’elemento indicato nel livello superiore. Per arrivare alla soluzione ottima, si deve scegliere al livello più basso l’alternativa migliore per il conseguimento dell’obiettivo che sta all’apice della gerarchia. Per chiarire come va valutata un’alternativa, consideriamo l’esempio che segue:

0.6 0.1 0.3

36

In questo caso (di gerarchia incompleta!) l’alternativa evidenziata ha una priorità elevata per quanto riguarda il primo attributo: infatti ha peso 0.9 (si noti che le altre due alternative hanno peso 0.05 entrambe: la somma dei pesi è 1 per l’elemento ‘attributo’!); ha peso 0.5 per il secondo attributo (le altre due alternative hanno peso, rispettivamente, 0.2 e 0.3); ha peso 0.8 per il quinto attributo; ha peso nullo per gli attributi 3° e 4° (nell’esempio gli altri pesi non sono indicati in quanto non rilevanti per l’esempio). Occorre a questo punto tenere conto anche del fatto che i vari attributi hanno diversa importanza per il conseguimento dell’obiettivo finale (che, come si è detto, è la massima utilità o massimo gradimento). Perciò, anche se l’alternativa è molto valida per quanto riguarda il primo attributo, è l’attributo stesso ad avere poco peso (0.1) nei riguardi del gradimento finale; viceversa, il secondo attributo è più importante (0.4): la nostra alternativa è efficace, nei suoi riguardi, con peso 0.5. In definitiva, quello che viene suggerito nell’AHP è di calcolare, per ogni alternativa un indice dato dalla somma dei prodotti delle priorità lungo tutti i percorsi che collegano l’alternativa all’obiettivo. Nel nostro caso il ‘valore’ della prima alternativa è:

0.9 × 0.1 + 0.5 × 0.4 + 0.8 × 0.3 = 0.53.

Analogamente si procede con le altre alternative: in ogni caso, la somma dei valori delle varie alternative è 1. Esempio Si debba acquistare una macchina fotografica. Si prendono in considerazione le seguenti caratteristiche (attributi): qualità del corpo macchina (CC); prestazioni tecniche (PR); affidabilità (AF);

0.1 0.4 0.1 0.3 0.1 0.8 0.05 0.05 0.3 0.2 0.1 0.1 0.9 0.5

37

qualità degli obiettivi disponibili (QO); valore dell’usato (VU); design (DS). Si hanno a disposizione tre modelli di apparecchiatura fotografica, A, B, e C. Supponiamo anche che la gerarchia sia completa. E’ data la seguente tabella dei confronti a coppie degli attributi, riguardo al conseguimento dell’obiettivo finale:

CC PR AF QO VU DS CC 1 1/9 1/9 1/7 1/6 1/ PR 9 1 1 3 5 5 AF 9 1 1 3 5 5 QO 7 1/3 1/3 1 3 3 VU 6 1/5 1/5 1/3 1 1 DS 6 1/5 1/5 1/3 1 1 Con alcuni controlli (utilizzando anche il metodo degli autovalori), si vede che la matrice non è coerente (λmax = 6.295 > 6). Con lo stesso metodo (autovalori) si individuano i pesi, come segue:

CC → 0.021; PR → 0.336; AF → 0.336; QO → 0.157; VU → 0.075; DS → 0.075.

Indicheremo in seguito il vettore di questi pesi con w = (.021 .336 .336 .157 .075 .075). Con queste informazioni si ottiene uno schema come quello che segue :

.021 .336 .336 .157 .075 .075 CC PR AF QO VU DS

A B C

38

Esso va completato inserendo le valutazioni delle alternative rispetto ai singoli attributi. Per il prezzo, trattandosi di un dato oggettivo, si può evitare il ricorso alla matrice dei confronti a coppie. Tuttavia, trattandosi di un elemento da minimizzare, occorre qualche trasformazione: nel nostro caso, passiamo ai reciproci e normalizziamo. Pertanto, supponendo che i prezzi in Euro siano:

per A: 175; per B: 200; per C: 250,

si ottiene lo schema (parziale, da inserire nella figura precedente): Analogamente, occorre confrontare tra di loro le tre alternative rispetto agli altri attributi. Il procedimento è sempre quello di costruire la matrice dei confronti a coppie e poi renderle coerenti e ricavare i pesi. Anziché fare riferimento alla figura precedente (in essa andrebbero indicati, accanto a tutti gli archi i pesi individuati, elenchiamo i pesi stessi nella seguente tabella:

CC PR AF QO VU DS A .388 .169 .25 .109 .235 .582 B .340 .388 .50 .582 .294 .109 C .272 .443 .25 .309 .471 .309 (si osservi che la somma degli elementi di ogni colonna vale 1).

Chiameremo questa matrice B. Per calcolare la priorità (valore) di ogni tipo di macchina rispetto all’obiettivo generale, si tratta di sommare i prodotti dei pesi lungo tutti i percorsi che portano dalle alternative all’obiettivo generale. Così, rispettivamente, per A, B e C si ottiene: zA = .388 × .021 + .169 × .337 + .25 × .336 + .109 × .157 + .235 × .075 + .581 × .075 = .2274 zB = .340 × .021 + .388 × .337 + .50 × .336 + .582 × .157 + .294 × .075 + .109 × .075 = .4273 zC = .272 × .021 + .443 × .337 + .25 × .336 + .309 × .157 + .471 × .075 + .309 × .075 = .3463

CC

0.338 0.272 0.340 A B C

39

Si può constatare che, se diciamo z il vettore dei pesi delle alternative, cioè se poniamo

z = (.2274 .4273 .3463),

si ha che z stesso può essere ottenuto con l’operazione z = B w. Nel caso di più di tre livelli il procedimento è simile: si tratta sempre di calcolare la somma dei valori di tutti i percorsi che portano da ogni alternativa all’obiettivo generale e ogni percorso va valutato calcolando il prodotto dei pesi degli archi che lo compongono. Da un punto di vista algebrico, si possono raccogliere i pesi tra un livello e l’altro in più matrici (analoghe a B) B1, B2, …, Bk e si ha sempre z = B1 B2 …Bk w.

7.3.6 Il metodo TOPSIS Il termine TOPSIS sta a indicare una Tecnica per la costruzione di Preferenze di tipo Ordinale mediante Somiglianza con una Soluzione Ideale (l’acronimo si giustifica con l’inversione grammaticale inglese: Ideal Solution). In altri termini, Topsis è una tecnica di ordinamento delle preferenze per vicinanza ad una soluzione fittizia utopistica, che viene detta soluzione ideale: al tempo stesso si cerca di essere lontani dal ‘worst case’ cioè da un’altra soluzione fittizia, detta ‘ideale negativa’. La soluzione (fittizia) ideale, detta anche più esplicitamente ideale positiva viene costruita prendendo da una tabella decisioni attributi, per ogni attributo, il valore più elevato. Al contrario, la soluzione ideale negativa è costruita prendendo i valori peggiori di tutti gli attributi. Se gli attributi sono due, si può esemplificare la situazione come segue: Sol. ideale positiva Soluzione ideale negativa

40

Si indichi ora con si+ lo scarto o distanza della alternativa i-esima

dalla soluzione ideale positiva e con si- la distanza dalla soluzione

ideale negativa (vedremo tra poco come calcolare queste distanze). Sol. ideale positiva si

+ alternativa i-ma si

- Soluzione ideale negativa Si calcola il valore della decisione i-esima vi = v(di) come:

v(di) = si- / (si

+ + si-).

Pertanto il valore di una decisione è tanto più grande quanto questa è lontana dalla soluzione ideale negativa e quanto più piccola è invece la distanza dalla soluzione ideale positiva. In pratica occorre tenere conto di due elementi: il diverso peso degli attributi e la necessità che le scale di misura degli stessi non influiscano sul risultato distorcendolo (quest’ultimo inconveniente, ovviamente, è evitato se i valori degli attributi sono normalizzati in qualche modo). In ogni caso, le distanze andranno opportunamente pesate. Per esemplificare il procedimento, consideriamo la seguente tabella di valori normalizzati:

A1 A2 (w1 = 0.6) (w2 = 0.4)

d1 0.90 0.18 d2 1.00 0.25 d3 0.75 1.00 d4 0.17 0.85 ideale positiva 1 1 ideale negativa 0.17 0.18 Da questa tabella si passa alla matrice di decisione pesata, ottenuta moltiplicando gli elementi di ogni colonna per i relativi pesi

41

(moltiplichiamo i valori della prima colonna per 0.6 e quelli della seconda per 0.4). Si ottiene:

A1 A2

d1 0.54 0.072 d2 0.60 0.10 d3 0.45 0.40 d4 0.102 0.34 ideale positiva 0.6 0.4 ideale negativa 0.102 0.072 A questo punto si calcolano le distanze euclidee. Nel caso della prima decisione si ha:

s1+ = =−+− 22 )4.0072.0()6.054.0( 0.3334;

s1- = =−+− 22 )072.0072.0()102.054.0( 0.438.

Il valore v(d1) risulta allora:

v(d1) = 3334.0438.0

438.0

+ = 0.5678.

Analogamente, si calcolano i rimanenti valori che risultano, rispettivamente:

v(d2) = 0.6244, v(d3) = 0.7612, v(d4) = 0.3482

e quindi la decisione migliore risulta d3.

7.3.7 Il metodo ELECTRE.

Il metodo Electre è strettamente legato a Bernard Roy, che lo ha sviluppato e proposto in varie successive versioni, vale a dire, l’Electre I, II, III, IV, IS e TRI. ELECTRE sta per ELimination Et Choix Traduisant la Realité: (metodo di) eliminazione e scelta che traduce la realtà. Il primo di questi modelli vide la luce nel 1968. Hanno tutti una caratteristica fondamentale in comune: puntano a costruire un ordinamento delle alternative che non pretende però di essere completo, ed è quindi in genere solo un ordine parziale (in altre parole, si possono avere situazioni di alternative non confrontabili tra di loro).

Anche Electre, nelle sue varie versioni, è un metodo che utilizza dei pesi attribuiti ai vari attributi, ma questi hanno un valore limitato, in quanto, pur rappresentando l’importanza degli attributi

42

stessi, non possono essere adoperati per compensare indiscriminatamente valori negativi e valori positivi, come avviene invece ad esempio nel metodo dei pesi semplicemente additivi (il SAW, già visto in precedenza): in quel caso, una cattiva performance in un attributo può essere compensata da una migliore in altri attributi.

In Electre, oltre certi livelli – e qui sta la filosofia del metodo - il decisore non accetta questo genere di tradeoff: di fronte a due alternative, di e dk, la prima molto buona per certi attributi, ma non per altri, dove è invece molto migliore la seconda, non accetta di individuare chi delle due prevale semplicemente pesando i valori su tutti gli attributi e preferisce ritenere le alternative di e dk non confrontabili.

L’Electre utilizza i concetti di concordanza e discordanza e dei parametri detti soglie (thresholds). Nella versione più semplice, i parametri richiesti sono due:

- un parametro p, che potremmo definire soglia di concordanza;

- un parametro q, che invece potremo definire soglia di discordanza.

Per illustrare la procedura, facciamo innanzitutto riferimento ad una tabella in forma normale A1 A2 … An

w1 w2 … wn

d1 x11 x12 … x1n

d2 x21 x22 … x2n

… … … … dm xm1 xm2 … xmn Consideriamo in questa due alternative, di e dk: ci si chiede se si può considerare la prima migliore della seconda (e quindi stabilire che vale la relazione di f dk). Si ripartisce l’insieme degli attributi in due sottoinsiemi, Jik

+ e Jik-,

quello per cui la prima decisione di è migliore (o non peggiore) della seconda, dk, e il suo complementare (dove invece è dk a prevalere su di). Per quanto riguarda l’insieme Jik

+ si vuole che la somma dei pesi degli attributi che lo compongono, che indicheremo con Cik, detto indice di concordanza, superi la prefissata soglia p. In formule:

∑+∈

>=ikJh

hik pwC .

Si costruisce poi anche un indice di discordanza Dik il cui calcolo è relativamente più elaborato. Per individuare Dik:

43

- si calcolano tutti gli scarti pesati tra i valori degli attributi per le due alternative, cioè si calcola, per ogni attributo Aj, la quantità

wj |xij - xkj|;

- si individua il più grande di questi scarti, vale a dire

max j wj |xij - xkj|;

- si individua il più grande degli scarti relativi agli attributi in

Jik-,

max j∈J- wj (xkj – xij);

- si calcola il rapporto tra queste due ultime quantità, ponendo

Dik = )(max

max

ijkjjJj

kjijjj

xxw

xxw

−

−

−∈

Il test sull’indice Dik viene effettuato sulla base del parametro q, cioè si vuole che Dik < q. Questo significa che si vuole che, rispetto agli scarti che si hanno nei vari attributi tra le due decisioni, gli scarti che vedono di perdente non siano relativamente piccoli rispetto a quelli dove invece di è migliore rispetto a dk. Se nel raffronto tra di e dk entrambi i test vengono superati, si dice che di è preferibile a dk e quest’ultima decisione può essere eliminata. In genere si fissano, rispettivamente, i valori p = 0.7 e q = 0.3: è evidente come il test divenga più difficile da superare allorché si aumenta p e si diminuisce q, rischiando di non individuare alcuna decisione da eliminare. Altre varianti del metodo Electre prendono in considerazione altri aspetti psicologici nella valutazione delle alternative, in particolare il fatto che se, confrontando due decisioni, il valore di un attributo non differisce per un ammontare superiore ad una certa soglia, allora le due decisioni vengono percepite come indifferenti: anche questo fatto riduce la possibilità di istituire un ranking tra le alternative disponibili (aumenta tendenzialmente il numero delle decisioni ‘non dominate’).

7.4 Decisioni con informazioni sulle alternative. I metodi che utilizzano informazioni sulle alternative richiedono che il decisore esprima a priori delle preferenze tra coppie di alternative: il problema sta nel fatto che, in genere, tali preferenze

44

non sono del tutto coerenti (se lo fossero, individuare l’alternativa migliore diventerebbe banale). Uno di tali metodi – probabilmente il più conosciuto - è il LINMAP.

7.4.1 Il metodo LINMAP

Il termine LINMAP sottintende l’espressione LInear Programming techniques for Multidimensional Analysis of Preferences. Sono date m alternative d1, d2, …, dm, n attributi e la matrice dei valori degli stessi, xij. Il decisore indica inoltre un insieme P di coppie del tipo (di, dk), sottoinsieme di tutte le coppie ordinate possibili. La coppia (di, dk) sta ad indicare che per il decisore di f dk. Queste indicazioni di preferenza possono anche non essere transitive (e contengono, in generale, delle incoerenze). Si fa l’ipotesi che esista una decisione ideale, incognita, che verrà identificata insieme ai pesi da attribuire agli attributi. Il metodo indica infine un ordinamento (parziale) delle alternative, che aita quindi la scelta del decisore. Se fosse nota la decisione ideale d*, con valori degli attributi x1*, x2*, …, xn*, la generica decisione dj potrebbe essere definita tanto migliore quanto più piccola è la sua distanza euclidea da d* o, per comodità, il suo quadrato:

si = 2

1

** )(∑ =−n

j jijj xxw .

Se tra le preferenze indicate figura una coppia del tipo (di, dk), si ha congruenza se si verifica che si ≤ sk (incongruenza in caso contrario). Definiamo incongruenza della soluzione, individuata in termini di d* e dei pesi, rispetto alla coppia (di, dk) la quantità:

0, se sk ≥ si

(sk- si)- =

si – sk, se sk < si

e livello (totale) di incongruenza la quantità B = Σ (sk- si)- . Si

tratta di rendere minima la quantità B. Tuttavia questo problema, così posto, porterebbe alla soluzione wj* = 0, e quindi occorre aggiungere qualche ulteriore vincolo. Si definiscono allora anche la ‘congruenza’ della soluzione rispetto alla singola coppia e il livello di congruenza G dati rispettivamente da

45

sk – si, se sk ≥ si (sk- si)

+ = 0, se sk < si;

G = Σ (sk- si)+.

Si impone quindi il vincolo che il livello di congruenza sia superiore a quello di incongruenza. Il problema diventa allora:

min B = min Σ (sk- si)-

s.t. G > B. Il modello così posto non dà luogo ad un problema lineare: tuttavia, con l’introduzione di nuove variabili si può ricondurre il problema precedente ad un problema di Programmazione lineare, cosa che giustifica la denominazione del metodo.

8 Cenni sulla programmazione a più obiettivi.

8.1 Una classificazione dei metodi multiobiettivo.

Ricordiamo innanzitutto che nei problemi definiti ‘multobiettivo’ il numero delle possibili soluzioni (decisioni, alternative) è infinito. Pertanto queste vengono espresse in modo implicito o sono generate nel processo stesso risolutivo (non ha senso, ovviamente, pensare ad una tabella in forma normale). Conseguentemente, si possono distinguere le tecniche risolutive in campo Multi - Obiettivo in generative e non generative. Naturalmente si possono anche adottare altri criteri di classificazione, in particolare quelli, analoghi a quanto già visto in campo Multi – Attributo, basati sulle informazioni fornite dal decisore all’analista. Le tecniche generative puntano a individuare un sottoinsieme finito di alternative, tra le quali il decisore potrà poi effettuare la sua scelta. Le tecniche non generative, viceversa, puntano a costruire la decisione finale. In questa seconda categoria rientra il metodo che verrà presentato in questa sede, e cioè il metodo della Goal Programming.

8.2 La Goal Programming. Il metodo della Goal Programming è particolarmente interessante perché si presta a introdurre vari concetti di portata generale utili nell’ambito della teoria delle decisioni. E’ applicabile in vari

46

campi, ma particolarmente suggestive appaiono le interpretazioni che fanno riferimento al campo medico, in particolare alle analisi del sangue. In un referto di analisi, si trovano in genere indicati sia il livello riscontrato che i valori ‘normali’, espressi questi ultimi a volte come un valore numerico preciso, altre volte (assai più spesso!) come un intervallo entro il quale il valore dovrebbe ricadere. E’ poi da notare che sono in genere indesiderati, in qualsiasi test clinico, sia valori inferiori che superiori a quelli ‘normali’ di riferimento. In questo senso, quindi, i valori di riferimento sono dei target, cioè livelli che si desidera raggiungere, sia partendo da valori superiori che inferiori a quelli di norma. Ad ogni scostamento dai valori normali si può associare un dato numerico da interpretare come penalità. Una esempio di funzione di penalità è quello che segue: penalità a b valore riscontrato I due numeri a e b sono gli estremi dell’intervallo che si desidera raggiungere. La funzione di penalità è decrescente a sinistra di a e crescente a sinistra di b. Aumenta, in generale, all’aumentare della distanza dai valori normali. La forma della funzione di penalità dipende ovviamente dal problema specifico. I due tratti esterni all’intervallo [a, b] possono essere lineari (con pendenza non necessariamente eguale) oppure convessi, e ciò indica che scostamenti più grandi procurano una penalità che aumenta più che proporzionalmente rispetto allo scostamento (ma si potrebbero avere anche penalità di tipo concavo). Infine, se il valore di riferimento è un dato numerico preciso, l’intervallo [a, b] si riduce ad un punto. Nella Goal Programming, di fronte ai vari obiettivi, si ipotizza che il decisore indichi quali valori rappresentano i suoi goals: indicheremo tali valori con yj* (j=1, 2, …, k). Si cerca la migliore soluzione di compromesso. L’insieme delle soluzioni è descritto, come nei problemi di programmazione matematica, attraverso dei vincoli, del tipo

47

g i(x) ≤ 0 (i = 1, 2, …, n) quindi in forma implicita. Tali vincoli individuano i vettori ammissibili x. Per ogni soluzione ammissibile si può calcolare il valore nei riguardi di ciascun obiettivo, yj = fj(x). Si definiscono, per ciascun obiettivo, due variabili di scostamento (deviational variables):

yj – yj*, se yj > yj*;

dj+ =

0, se yj < yj*;

yj* – yj, se yj < yj*;

dj- =

0, se yj > yj*.

La variabile dj+ viene detta anche over-achievement; viceversa dj

- è l’ under-achievement: entrambe sono non negative, dipendono dal vettore soluzione x e, in base alle definizioni, il loro prodotto è nullo:

dj+ ≥ 0; dj

- ≥ 0; dj+ dj

- = 0. Infine, si constata facilmente che vale la relazione:

−+ +=−=− jjjjjj ddxfyyy )(**

A questo punto la Goal Programming propone di risolvere il seguente problema di programmazione matematica:

min x Σj wj yj*-f j(x)p

s.t. gi(x) ≤ 0; (i = 1, 2, …, n)

fj(x) + dj- - dj

+ = yj*

dj+ dj

- = 0 dj

+ ≥ 0; dj- ≥ 0

In esso, al variare del parametro p, si possono ottenere differenti funzioni di penalità (per p = 1, ovviamente, la penalità è lineare).