Thesis etd-03102004-180356 |
Link copiato negli appunti
Thesis type
Tesi di laurea vecchio ordinamento
Author
Triglia, Luca
URN
etd-03102004-180356
Thesis title
Alcuni metodi risolutivi per la Programmazione Multiobiettivo
Department
SCIENZE MATEMATICHE, FISICHE E NATURALI
Course of study
MATEMATICA
Supervisors
relatore Bigi, Giancarlo
relatore Pallottino, Stefano
relatore Pallottino, Stefano
Keywords
- approssimazione
- ottimizzazione multicriterio
- pareto ottima
Graduation session start date
30/03/2004
Availability
Full
Summary
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.
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
Nome file | Dimensione |
---|---|
tesi.pdf | 593.25 Kb |
Contatta l’autore |