/ 1
- Dettagli
- Categoria: Area Scientifica
- Scritto da Daniele Depetrini
- Visite: 1338
PubbliTesi - La Tesi
Algoritmi per la risoluzione di problemi di Linear Multiplicative Programming
Scheda Sintetica
Autore: Daniele Depetrini
Relatore: Marco Locatelli
Università: Università degli Studi di Torino
Facoltà: Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso: Laurea Spec. in Metodologie e Sistemi Informatici
Data di Discussione: 17/07/2007
Voto: 110 cum laude
Disciplina: Ricerca Operativa
Tipo di Tesi: di Ricerca
Lingua: Italiano
Grande Area: Area Scientifica
Dignità di Stampa: Si
Settori Interessati: progettazione impianti industriali complessi, ottimizzazione portafoglio titoli, ottimizzazione globale
Descrizione:
In questa tesi sono analizzati degli algoritmi per la soluzione di problemi di tipo LMP (Linear Multiplicative Programming), in cui la regione ammissibile è un poliedro e la funzione obiettivo è data dal prodotto di funzioni affini. Più precisamente l’analisi si concentrerà sui problemi nella classe 2LMP in cui si ha il prodotto di due sole funzioni affini. E’ stato dimostrato in [1] che tali problemi sono NP-Hard. Essi rientrano nella categoria dei problemi di ottimizzazione globale, ovvero caratterizzati dal fatto che la funzione obiettivo può avere diversi minimi locali non globali.
Grado di Innovazione:
A mio parere ci sono principalmente due punti di forza:
-è stata dimostrata la complessita’ dell’algoritmo approssimato
-è stato verificato computazionalmente che i tempi di risoluzione anche esatta dei problemi 2LMP sono paragonabili ai tempi di risoluzione dei problemi lineari