Ricerca Operativa - Programmazione a molti obiettivi

Torna alla pagina di Ricerca Operativa

---

:: Ricerca Operativa - Programmazione a molti obiettivi ::

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:

1. analisi della corrispondenza tra cause ed effetti, dalla quale bisognerà estrarre un algoritmo che ci aiuti a comprenderla
2. 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:

1. determinazione dell'insieme delle soluzioni cosiddette efficienti o pareto-ottime, ovvero quelle tra cui è possibile fare una scelta razionale
2. scelta di una soluzione finale tra quelle efficienti, utilizzando opportuni criteri che vedremo poi

Dominanza e regione paretiana

Vediamo cos'è una soluzione pareto-ottima introducendo il concetto di dominanza.
Se stiamo massimizzando, diciamo che una soluzione xⁱ è dominata da una soluzione x^j se per ogni funzione obiettivo (di seguito indicata con h) il valore della soluzione xⁱ 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ⁱ 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:

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.

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").

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) = λ₁f₁(x) + λ₂f₂(x) + ... λ_kf_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:

-> φ(x) ->

Dato che abbiamo solo due funzioni obiettivo possiamo usare un unico λ distinguendo in: λ e (1-λ)

Ora che abbiamo parametrizzato il problema MO considero φ(x) nei casi estremi:

• λ = 0 (curve di livello orizzontali), φ(0) = x₂
• λ = 1 (curve di livello parallele a quelle di f₁), φ(1) = 2x₁ + x₂

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λ

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)

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.

->

Quell'x appartenente ad X mi dice che sto mantenendo tutti i vincoli di partenza, a cui ne aggiungo uno nuovo: x₂ >= ε. 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).

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

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):

Criterio della massima curvatura

Il criterio della massima curvatura consiste nel trovare quel punto in cui ad un piccolo miglioramento di f₁ corrisponde un grosso peggioramento di f₂ (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.

Criterio dell'utopia

L' utopia è il punto le cui coordinate f₁^*, f₂^*, .. , 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

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 ε₁, ε₂, .. , ε_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.

In formula:

max z

La seconda e terza riga si leggono come "il miglioramento di f₁ e f₂ rispetto ad ε₁ ed ε₂ deve essere maggiore o uguale ad un certo z da massimizzare".

---

Torna alla pagina di Ricerca Operativa