logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-03102004-180356


Tipo di tesi
Tesi di laurea vecchio ordinamento
Autore
Triglia, Luca
URN
etd-03102004-180356
Titolo
Alcuni metodi risolutivi per la Programmazione Multiobiettivo
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
MATEMATICA
Relatori
relatore Bigi, Giancarlo
relatore Pallottino, Stefano
Parole chiave
  • approssimazione
  • ottimizzazione multicriterio
  • pareto ottima
Data inizio appello
30/03/2004
Consultabilità
Completa
Riassunto
Nel Capitolo 1 della presente tesi, dopo aver introdotto i concetti di cono e di ordinamento su R^{n}, abbiamo richiamato la definizione di punto di massimo (e di minimo) di un sottoinsieme di R^{n} e di soluzione Pareto ottima di un problema multicriterio, fornendo alcune condizioni affinché l'insieme di tali soluzioni sia non vuoto. Il Capitolo si conclude con la descrizione di due importanti tecniche di risoluzione il cui obiettivo è quello di ridurre problemi di Ottimizzazione multicriterio ad un problema, oppure ad una famiglia di problemi, con singolo criterio.

Nel Capitolo 2 la nostra attenzione si sposta sui problemi di Programmazione Lineare Multiobiettivo definiti su un qualsiasi politopo convesso. Per tali problemi mostriamo alcune proprietà delle soluzioni Pareto ottime e, dopo aver descritto un noto metodo di risoluzione per problemi di Programmazione Lineare con singolo obiettivo, detto Metodo del Simplesso, lo adattiamo al caso multicriterio fornendo un metodo per determinare l'insieme delle soluzioni Pareto ottime. Purtroppo, il metodo descritto non puòo essere applicato a problemi di Programmazione Lineare Intera Multiobiettivo e quindi forniamo una tecnica sequenziale per affrontare tali problemi.

Nel Capitolo 3 descriviamo qualche metodo per determinare alcune soluzioni Pareto ottime di un qualsiasi problema di Ottimizzazione multicriterio. L'idea di base consiste nel determinare la soluzione ammissibile che renda minima la distanza tra lo spazio immagine e un punto di riferimento fissato. Inizialmente, si dimostra che se utilizziamo una distanza indotta da una metrica L_{p}, con 1 < p < infty, la soluzione ottenuta è Pareto ottima, mentre, utilizzando la distanza indotta dalla metrica L_{infty}, la soluzione ottenuta può essere Pareto ottima debole.
In seguito, consideriamo le distanze indotte dalle metriche pesate ottenendo alcune condizioni sulla metrica usata affinché la soluzione sia Pareto ottima.

Nel Capitolo 4 esaminiamo uno dei primi metodi creati per affrontare l'Ottimizzazione multicriterio, la Goal Programming. Dato un problema multiobiettivo, l'idea di base è di stabilire, per ogni criterio, un livello da raggiungere; se non può essere raggiunto, cercheremo una soluzione che si discosti il meno possibile da tale livello. Descriviamo, quindi, due metodi di risoluzione per i problemi di Goal Programming e mostriamo le condizioni affinché le soluzioni di tali problemi siano Pareto ottime.

Concludiamo la tesi mostrando, nel Capitolo 5, due metodi che ci permettono di fornire approssimazioni lineari di sottoinsiemi dell'insieme delle soluzioni Pareto ottime per problemi multiobiettivo convessi e non convessi. Descriviamo, per primo, il metodo di approssimazione per problemi multicriterio convessi e successivamente estendiamo i risultati al caso non convesso; per entrambi si definisce, inizialmente, un'approssimazione di partenza e due criteri di arresto che stabiliscono la qualità dell'approssimazione richiesta e il massimo numero di punti Pareto ottimi da generare. Ad ogni iterazione viene calcolata una misura poliedrale utilizzata sia per ottenere una nuova soluzione Pareto ottima, che per calcolare la qualità dell'approssimazione, arrestando il processo solo quando sono rispettati i criteri di arresto.
Infine, mostriamo un'estensione del metodo di approssimazione per problemi non convessi a problemi multiobiettivo discreti, con cui riusciamo a localizzare regioni dello spazio immagine in cui si trovano le soluzioni Pareto ottime del problema discreto.
File