Facoltà: Ingegneria Gestionale per la Produzione Industriale - classe 34/S
Collocazione: 5735
Autore: Mazzucchelli Mauro
Data: 20/04/2007
Titolo: CONFRONTO DELLE PRESTAZIONI DELLE FUNZIONI DI OTTIMIZZAZIONE DI MATLAB APPLICATE A PROBLEMI DI FLUSSO DELLE RETI
Relatore: Strozzi Fernanda
Correlatore: Rossignoli Chiara
Autorizzazione per la consultazione: NO
Le tesi si possono consultare unicamente in sede
Il progetto di Tesi si è concentrato sull’analisi delle prestazioni di alcune funzioni di ottimizzazione dei toolbox di Matlab. Le funzioni sono state applicate a problemi di flusso nelle reti che rappresentano una comune tipologia di problemi decisionali. I problemi scelti sono lineari e non-lineari, rispettivamente il problema di flusso minimo, il problema del trasporto, il problema di assegnamento, il problema del cammino minimo, come problemi lineari ed il problema della dissipazione minima in due tipi di reti elettriche come problemi non-lineari. I metodi di ottimizzazione implementati dalle funzioni Matlab scelte si differenziano come specifici per problemi lineari: il metodo del simplesso di Dantzig e il Linear-programming Interior Point Solver (LIPSOL) ed in metodi applicabili anche per i problemi non-lineari: il Sequential Quadratic Programming Method (SQP) l’Algortimo Genetico (GA) ed un metodo Pattern Search (PS). L’analisi dei metodi è avvenuta in due modi. Dapprima è stato fatto il confronto tra le soluzioni ottenute e la velocità di convergenza considerando il tempo di calcolo ed il numero di iterazioni. In seguito è stata fatta una valutazione della complessità computazionale dei GA e dell’algoritmo di Dantzig applicati ai problemi lineari studiando la relazione tra le dimensioni del problema ed il tempo di calcolo. La metodologia applicata è stata la seguente: per ogni tipologia di problema sono stati generati dieci problemi di dimensione crescente e, per ognuno di essi, sono stati fatti variare i parametri in modo da ottenere 100 problemi diversi. Per ogni problema di una data dimensione è stato calcolato il tempo di esecuzione peggiore tra i 100 generati. La prima analisi ha confermato la superiorità dell’algoritmo di Dantzig e LIPSOL per degli algoritmi specifici per i problemi lineari, e di SQP per quelli non-lineari rispetto ai GA. Nonostante i GA siano applicabili a tutti i tipi di problemi si sono rivelati più lenti dei soprattutto nel caso dei problemi lineari. La seconda analisi ha permesso di dimostrare e quantificare l’aumento esponenziale del tempo di calcolo dei GA e del metodo di Dantzig all’aumentare della dimensione dei problemi e di confrontare così la loro efficienza per problemi di grandi dimensioni ovvero identificare la dimensione dei problemi di reti che i diversi algoritmi sono in grado di risolvere.
