|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.RO-ProgrammazioneMO History
Show minor edits - Show changes to output
Changed lines 110-114 from:
Caratteristica del '''criterio della massima curvatura''' è che si riesce spesso ad applicare anche ad occhio, e consiste nel trovare quel punto in cui ad un piccolo miglioramento di f'_1_' corrisponde un grosso peggioramento di f'_2_' (e viceversa).
to:
Il '''criterio della massima curvatura''' consiste nel trovare quel punto in cui ad un piccolo miglioramento di f'_1_' corrisponde un grosso peggioramento di f'_2_' (e viceversa).
Ovviamente nell'esempio accanto e nella descrizione operativa del metodo abbiamo considerato solo due funzioni obiettivo per semplicità di espressione, ma può essere generalizzato a ''k'' funzioni.
Il criterio della massima curvatura è una di quelle poche tecniche che si riesce ad applicare anche ad occhio guardando solo il grafico. Changed lines 119-122 from:
L' '''utopia''' è il punto le cui coordinate f'_1_''^*^', f'_2_''^*^', .. , f'_k_''^*^' (siamo quindi nello spazio degli obiettivi) sono ottenute ottimizzando separatamente ciascuna funzione obiettivo. Di solito l'utopia non è una soluzione ammissibile, perché se lo fosse vorrebbe dire che le funzioni obiettivo non sono in conflitto tra loro, e quindi non sarebbe necessaria la MO. La soluzione paretiana è quella più vicina all'utopia. to:
L' '''utopia''' è il punto le cui coordinate f'_1_''^*^', f'_2_''^*^', .. , f'_k_''^*^' (siamo quindi nello spazio degli obiettivi) sono ottenute ottimizzando separatamente ciascuna funzione obiettivo.
Di solito l'utopia non è una soluzione ammissibile, perché se lo fosse vorrebbe dire che le funzioni obiettivo non sono in conflitto tra loro, e quindi non sarebbe necessaria la MO.\\
La soluzione paretiana è quella più vicina all'utopia.
Added line 108:
!!!Criterio della massima curvatura Deleted line 109:
!!!Criterio della massima curvatura
Added line 113:
Deleted line 114:
Added line 118:
!!!Criterio degli standard Deleted line 119:
!!!Criterio degli standard
Changed line 130 from:
La seconda e terza riga si legge come "il miglioramento di f'_1_' e f'_2_' rispetto ad ε'_1_' ed ε'_2_' deve essere maggiore o uguale ad un certo z da massimizzare". to:
La seconda e terza riga si leggono come "il miglioramento di f'_1_' e f'_2_' rispetto ad ε'_1_' ed ε'_2_' deve essere maggiore o uguale ad un certo z da massimizzare".
Changed line 96 from:
%rframe%Attach:ROcurveIndiff.jpg to:
%lframe%Attach:ROcurveIndiff.jpg Added line 108:
%rframe%Attach:ROmaxCurvatura.jpg Deleted line 109:
%lframe%Attach:ROmaxCurvatura.jpg
Added line 113:
%lframe%Attach:ROcritUtopia.jpg Deleted line 114:
%lframe%Attach:ROcritUtopia.jpg
Added line 118:
%rframe%Attach:ROcritStandard.jpg Deleted line 119:
%lframe%Attach:ROcritStandard.jpg
Changed lines 73-74 from:
La seconda tecnica per calcolare la regione paretiana è il '''metodo dei vincoli''', che consiste nello scegliere una sola funzione obiettivo trasformando le altre in vincoli. Ha senso trasformarle? Beh sì, ad esempio posso vedere la massimizzazione di una funzione come un vincolo che le impone di essere maggiore o uguale a qualcosa, o viceversa se sto minimizzando. Questi "qualcosa", ovvero i termini noti dei nuovi vincoli, si chiamano '''standard''' e sono indicati con ε'_i_'. In formula:\\
'''max f'_i_'(x)'''\\ to:
La seconda tecnica per calcolare la regione paretiana è il '''metodo dei vincoli''', che consiste nello scegliere una sola funzione obiettivo trasformando le altre in vincoli. Ha senso trasformarle? Beh sì, ad esempio posso vedere la massimizzazione di una funzione come un vincolo che le impone di essere maggiore o uguale a qualcosa, o viceversa se sto minimizzando. Questi "qualcosa", ovvero i termini noti dei nuovi vincoli, si chiamano '''standard''' e sono indicati con ε'_i_'. In formula:
'''max f'_i_'(x)''' Deleted line 88:
Changed lines 98-99 from:
Il primo criterio è quello delle '''curve di indifferenza''', ovvero insiemi di soluzioni che sono ritenute egualmente buone. La soluzione finale sarà il punto in cui una di queste curve risulterà tangente alla regione pareto-ottima, situazione in cui ci aspettiamo il miglior risultato possibile dato che abbiamo un unico punto di contatto. to:
Il primo criterio è quello delle '''curve di indifferenza''', ovvero insiemi di soluzioni che sono ritenute egualmente buone.
La soluzione finale sarà il punto in cui una di queste curve risulterà tangente alla regione pareto-ottima, situazione in cui ci aspettiamo il miglior risultato possibile dato che abbiamo un unico punto di contatto. Added line 105:
Changed lines 122-130 from:
to:
In formula:
'''max z'''
->'''f'_1_'(x) - ε'_1_' >= z'''
->'''f'_2_'(x) - ε'_2_' >= z'''
-> x appartiene a X
-> '''z >= 0'''
La seconda e terza riga si legge come "il miglioramento di f'_1_' e f'_2_' rispetto ad ε'_1_' ed ε'_2_' deve essere maggiore o uguale ad un certo z da massimizzare".
Changed lines 84-86 from:
(:cell align=center valign=middle:)[+[@->@]+]\\
'''φ(x)'''\\
[+[@->@]+] to:
(:cell align=center valign=middle:)[+[@->@]+] Added line 96:
%rframe%Attach:ROcurveIndiff.jpg Changed lines 98-99 from:
%rframe%Attach:ROcurveIndiff.jpg
Il primo criterio è quello delle '''curve di indifferenza''', ovvero insiemi di soluzioni che sono ritenute egualmente buone. La soluzione finale sarà il punto in cui una di queste curve risulterà tangente alla regione pareto-ottima, situazione in cui ci aspettiamo il miglior risultato possibile dato che abbiamo un unico punto di contatto. Evidentemente questo criterio può essere usato solo nel continuo dato che il concetto di tangente non esiste nel discreto.
to:
Il primo criterio è quello delle '''curve di indifferenza''', ovvero insiemi di soluzioni che sono ritenute egualmente buone. La soluzione finale sarà il punto in cui una di queste curve risulterà tangente alla regione pareto-ottima, situazione in cui ci aspettiamo il miglior risultato possibile dato che abbiamo un unico punto di contatto.
Evidentemente questo criterio può essere usato solo nel continuo dato che il concetto di tangente non esiste nel discreto.
Changed line 83 from:
Attach:ROmetodoVincoli1.jpg to:
Added lines 71-117:
!!!Metodo dei vincoli
La seconda tecnica per calcolare la regione paretiana è il '''metodo dei vincoli''', che consiste nello scegliere una sola funzione obiettivo trasformando le altre in vincoli. Ha senso trasformarle? Beh sì, ad esempio posso vedere la massimizzazione di una funzione come un vincolo che le impone di essere maggiore o uguale a qualcosa, o viceversa se sto minimizzando. Questi "qualcosa", ovvero i termini noti dei nuovi vincoli, si chiamano '''standard''' e sono indicati con ε'_i_'. In formula:\\
'''max f'_i_'(x)'''\\
->x appartiene a X
->'''f'_i_'(x) >= ε'_i_'''' , per ogni i = 2, ... , k
Come per il metodo dei pesi, anche con quello dei vincoli parto da un problema di programmazione MO ad uno di PM parametrica, dove i parametri stavolta sono proprio gli ''standard''. Un altro modo di interpretarli è considerarli (se sto massimizzando) il minimo richiesto perché il valore della funzione sia considerato decente. Va da sé che cambiando gli ε cambia anche la soluzione ottima, quindi dovrò risolvere il problema per ognuno dei loro valori.
Riprendiamo il problema dell'esempio di prima e utilizziamo questa volta il metodo dei vincoli.
(:table cellpadding=10 cellspacing=10 width=80%:)
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROmetodoVincoli1.jpg
(:cell align=center valign=middle:)[+[@->@]+]\\
'''φ(x)'''\\
[+[@->@]+]
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROmetodoVincoli2.jpg
(:tableend:)
Quell'x appartenente ad X mi dice che sto mantenendo tutti i vincoli di partenza, a cui ne aggiungo uno nuovo: x'_2_' >= ε. Quest'ultimo mi costringe di fatto a stare al di sopra di una certa retta orizzontale condizionata da ε, e graficamente (vedi grafico sotto) potremo facilmente intuire che man mano che alzo la retta faccio scorrere l'ottimo lungo alcuni segmenti del perimetro del poliedro (indicati in blu).
%center%Attach:ROmetodoVincoliGraf.jpg
!!Scelta di una soluzione finale
Passiamo ora alla seconda delle due fasi che abbiamo descritto all'inizio, ovvero quella in cui dovremo scegliere una soluzione finale tra tutte quelle paretiane calcolate. Si osservi che questa operazione è di tipo politico, cioè non dipende dal problema ma da una nostra scelta. Ovviamente non siamo lasciati in balia dell'incertezza, ma esistono vari criteri rigorosi e matematicamente giustificabili che ci guidano nella scelta.
!!!Curve di indifferenza
%rframe%Attach:ROcurveIndiff.jpg
Il primo criterio è quello delle '''curve di indifferenza''', ovvero insiemi di soluzioni che sono ritenute egualmente buone. La soluzione finale sarà il punto in cui una di queste curve risulterà tangente alla regione pareto-ottima, situazione in cui ci aspettiamo il miglior risultato possibile dato che abbiamo un unico punto di contatto. Evidentemente questo criterio può essere usato solo nel continuo dato che il concetto di tangente non esiste nel discreto.
Alcune curve di indifferenza facili da usare sono quelle originate da questa formula (a cui seguono degli esempi):
%center%Attach:ROcurveIndiffEs.jpg
!!!Criterio della massima curvatura
%lframe%Attach:ROmaxCurvatura.jpg
Caratteristica del '''criterio della massima curvatura''' è che si riesce spesso ad applicare anche ad occhio, e consiste nel trovare quel punto in cui ad un piccolo miglioramento di f'_1_' corrisponde un grosso peggioramento di f'_2_' (e viceversa).
[[<<]]
!!!Criterio dell'utopia
%lframe%Attach:ROcritUtopia.jpg
L' '''utopia''' è il punto le cui coordinate f'_1_''^*^', f'_2_''^*^', .. , f'_k_''^*^' (siamo quindi nello spazio degli obiettivi) sono ottenute ottimizzando separatamente ciascuna funzione obiettivo. Di solito l'utopia non è una soluzione ammissibile, perché se lo fosse vorrebbe dire che le funzioni obiettivo non sono in conflitto tra loro, e quindi non sarebbe necessaria la MO. La soluzione paretiana è quella più vicina all'utopia.
[[<<]]
!!!Criterio degli standard
%lframe%Attach:ROcritStandard.jpg
Con il '''criterio degli standard''' bisogna prima accordarsi sui valori minimi di decenza (gli standard) per ciascuna delle funzioni obiettivo, poi verificare se il punto che ha coordinate ε'_1_', ε'_2_', .. , ε'_k_' sia ammissibile. Generalmente questo punto si trova lontano dall'ottimo, quindi non è paretiano; tuttavia può essere migliorato rispetto a tutte le funzioni obiettivo, ovvero un procedimento che le migliori tutte di una stessa percentuale.
Changed line 50 from:
(:cell align=center:)[+[@->@]+]\\ to:
(:cell align=center valign=middle:)[+[@->@]+]\\ Changed lines 54-55 from:
Attach:ROmetodoPesi2.jpg\\ to:
Changed lines 68-70 from:
* 0 <= λ <= 1/6 , ha coordinate [@x* = (0,6)@] e ha [@φ* = 6@]
* 1/6 <= λ <= 1/2 , ha coordinate [@x* = (3,5)@] e ha [@φ* = 5 + 6λ@]
* 1/2 <= λ <= 1 , ha coordinate [@x* = (5,3)@] e ha [@φ* = 3 + 10λ@] to:
* 0 <= λ <= 1/6 , ha coordinate [@x* = (0,6)@] e ha φ* = 6
* 1/6 <= λ <= 1/2 , ha coordinate [@x* = (3,5)@] e ha φ* = 5 + 6λ
* 1/2 <= λ <= 1 , ha coordinate [@x* = (5,3)@] e ha φ* = 3 + 10λ
Changed line 58 from:
%rframe%ROmetodoPesiGraf.jpg to:
%rframe%Attach:ROmetodoPesiGraf.jpg
Changed lines 32-33 from:
Consideriamo il grafico a destra, in cui i puntini blu rappresentano le soluzioni e le freccette in rosso indicano le dominanze. Graficamente possiamo dire che tutte le volte che posso collegare un punto a un altro che si trova "in alto" o "a destra", significa che la soluzione corrispondente è dominata. I punti cerchiati in verde sono intuitivamente quelli che formano la regione pareto-ottima.\\ to:
Consideriamo il grafico a destra, in cui i puntini blu rappresentano le soluzioni e le freccette in rosso indicano le dominanze. Graficamente possiamo dire che tutte le volte che posso collegare un punto a un altro che si trova "in alto" o "a destra", significa che la soluzione corrispondente è dominata. I punti cerchiati in verde sono intuitivamente quelli che formano la regione pareto-ottima. Added lines 35-69:
Vediamo ora alcuni metodi operativi per trovare la regione paretiana.
!!!Metodo dei pesi
Il '''metodo dei pesi''' consiste nel dare un peso a ciascuna delle funzioni obiettivo, così da ridurre il problema MO in uno di programmazione matematica parametrica. Consideriamo ad esempio una funzione '''φ(x)''' data dalla somma pesata di tutte le funzioni obiettivo: \\
'''φ(x) = λ'_1_'f'_1_'(x) + λ'_2_'f'_2_'(x) + ... λ'_k_'f'_k_'(x)'''\\
Perché questa funzione possa essere considerata valida deve soddisfare due condizioni: x appartiene a X (quindi i vincoli del problema non cambiano), e la sommatoria di tutte le λ'_i_' deve essere pari a 1 (i dati devono essere normalizzati).\\
Che valore dare ai vari λ'_i_' lo decidiamo noi, ma attenzione: cambiando valore otteniamo una soluzione diversa! Che fare allora? Dovremo risolvere il problema per tutti i valori possibili di λ.
Commentiamo l'esempio sulle slide:
Riportiamo l'esempio presente sulle slide:
(:table cellpadding=10 cellspacing=10 width=80%:)
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROmetodoPesi1.jpg
(:cell align=center:)[+[@->@]+]\\
'''φ(x)'''\\
[+[@->@]+]
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROmetodoPesi2.jpg\\
Dato che abbiamo solo due funzioni obiettivo possiamo usare un unico λ distinguendo in: λ e (1-λ)
(:tableend:)
%rframe%ROmetodoPesiGraf.jpg
Ora che abbiamo parametrizzato il problema MO considero φ(x) nei casi estremi:
* ''λ = 0'' (curve di livello orizzontali), φ(0) = x'_2_'
* ''λ = 1'' (curve di livello parallele a quelle di f'_1_'), φ(1) = 2x'_1_' + x'_2_'
Gli altri valori che può assumere λ sono tutti tutti quelli che si trovano su quella parte del perimetro del poliedro compresa tra gli estremi appena definiti.
Guardando il grafico accanto possiamo dire che la regione pareto-ottima, composta da tutte le soluzioni che per un certo valore di λ possono essere ottime, è quella segnata in verde. Tutte le altre soluzioni ammissibili nel poliedro sono infatti dominate da quelle segnate in verde.\\
Per quanto riguarda i valori ottimi possiamo distinguere tre casi:
* 0 <= λ <= 1/6 , ha coordinate [@x* = (0,6)@] e ha [@φ* = 6@]
* 1/6 <= λ <= 1/2 , ha coordinate [@x* = (3,5)@] e ha [@φ* = 5 + 6λ@]
* 1/2 <= λ <= 1 , ha coordinate [@x* = (5,3)@] e ha [@φ* = 3 + 10λ@]
Added line 29:
%rframe%Attach:ROregioneParetiana.jpg Changed line 31 from:
%rframe%Attach:ROregioneParetiana.jpg
to:
Added lines 22-33:
!!Dominanza e regione paretiana
Vediamo cos'è una soluzione pareto-ottima introducendo il concetto di '''dominanza'''.\\
Se stiamo massimizzando, diciamo che una soluzione '''x'^i^'''' è ''dominata'' da una soluzione '''x'^j^'''' se per ogni funzione obiettivo (di seguito indicata con ''h'') il valore della soluzione '''x'^i^'''' non è migliore di '''x'^j^'''' per nessuno dei suoi obiettivi, ed esiste almeno un obiettivo per cui ne è strettamente peggiore. Quindi non è razionale scegliere x'^i^' dal momento che scegliendo x'^j^' non peggiorerei rispetto a nessun obiettivo e anzi migliorerei in almeno un caso. In conclusione, tutte le soluzioni dominate dovranno essere scartate senza nemmeno essere considerate.\\
Mettendo tutto in formula otteniamo:
%center%Attach:ROdominanza.jpg
Notare che se stessimo minimizzando, le disequazioni del sistema dovrebbero essere invertite.
Cosa resta dopo aver scartato tutte le soluzioni dominate? La '''regione pareto-ottima''' o '''regione paretiana''', cioè quell'insieme di soluzioni ammissibili non dominate.
%rframe%Attach:ROregioneParetiana.jpg
Consideriamo il grafico a destra, in cui i puntini blu rappresentano le soluzioni e le freccette in rosso indicano le dominanze. Graficamente possiamo dire che tutte le volte che posso collegare un punto a un altro che si trova "in alto" o "a destra", significa che la soluzione corrispondente è dominata. I punti cerchiati in verde sono intuitivamente quelli che formano la regione pareto-ottima.\\
Se stiamo minimizzando vale il discorso inverso ("in basso" o "a sinistra"). Deleted line 34:
Added lines 1-26:
(:title Ricerca Operativa - Programmazione a molti obiettivi:)
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
----
%titolo%''':: Ricerca Operativa - Programmazione a molti obiettivi ::'''
>>frame<<
Tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
>><<
!!Introduzione
La '''programmazione a molti obiettivi''' ('''MO''') è molto importante per la Ricerca Operativa, dato che la maggior parte dei problemi che si trova a dover risolvere nella pratica hanno spesso più obiettivi da realizzare simultaneamente. Ma cosa cambia rispetto a prima? Avremo sempre un decisore, un ambiente deterministico, ma molte funzioni obiettivo, rappresentabili come un vettore di funzioni.
Per affrontare questo tipo di problemi bisogna fare una distinzione importante tra due fasi distinte della risoluzione:
# analisi della corrispondenza tra cause ed effetti, dalla quale bisognerà estrarre un algoritmo che ci aiuti a comprenderla
# decisione, presa da un decisore umano che si assume la responsabilità della scelta
Nella programmazione MO si riesce a cogliere molto bene questa distinzione, poiché abbiamo anche qui due momenti ben distinti nella risoluzione:
# determinazione dell'insieme delle soluzioni cosiddette ''efficienti'' o '''pareto-ottime''', ovvero quelle tra cui è possibile fare una scelta razionale
# scelta di una soluzione finale tra quelle efficienti, utilizzando opportuni criteri che vedremo poi
TO BE CONTINUED
----
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
|
|
