Ricerca Operativa

Antonio Frangioni      Tel. 0502212789

Algoritmica e laboratorio, Matematica Discreta

Conoscenza delle principali classi di problemi di ottimizzazione, e comprensione delle basi matematiche dei corrispondenti algoritmi risolutivi. Sviluppo della capacità di formulare autonomamente modelli matematici corrispondenti a problematiche reali(stiche).

Conoscenze. Modelli di rilevanti classi problemi di ottimizzazione: problemi di flusso e cammino, Programmazione Lineare, Programmazione Lineare Intera, problemi combinatori utili per le applicazioni. Algoritmi esatti ed approssimati per problemi di ottimizzazione "difficili".

Capacità. Formulare autonomamente modelli matematici corrispondenti a problematiche reali(stiche). Ideare ed implementare algoritmi risolutivi per problemi di ottimizzazione.

Comportamenti. Capacità di leadership nell'introduzione di strumenti modellistici ed algoritmici sofisticati all'interno di un progetto od organizzazione.

Il corso illustra l'importanza della costruzione di modelli analitici di sistemi reali presentando esempi relativi a diversi problemi, in modo da fornire allo studente la capacità di modellare autonomamente i problemi. Vengono inoltre illustrate alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione, in ordine crescente di complessità: problemi di flusso su reti, problemi di programmazione lineare e problemi di ottimizzazione combinatoria, in modo da chiarificare alcune delle principali difficoltà inerenti alla soluzione di modelli analitici di problemi reali insieme ad alcune delle possibili soluzioni.

The course has two main aims. The first is to illustrate the importance of analytic models of real-world systems by presenting examples pertaining to different applications, in order to provide the students with autonomous modeling capabilities. The second is the necessary complement of the first, i.e., to illustrate some of the main algorithmic techniques for the solution of three large classes of optimization problems of growing computational complexity: network flow problems, Linear Programs and Integer Linear Programs. This is done in order to clarify where some of the main difficulties in the solution of analytic models come from, together with some of the possible solutions.

Il corso presenta le principali classi di problemi di ottimizzazione in ordine crescente di complessità. Per ciascuna classe di problemi vengono presentati uno o più algoritmi risolutivi, con particolare enfasi sulle proprietà matematiche che ne suggeriscono lo sviluppo e permettono di dimostrarne proprietà di correttezza ed efficienza. L'obiettivo finale è quello di fornire allo studente i principali concetti algoritmici utili alla soluzione di problemi di ottimizzazione. Il corso alterna costantemente parti teoriche, con dimostrazione rigorosa di enunciati matematici, ad esemplificazioni atte ad illustrare le proprietà ed il funzionamento degli algoritmi proposti. La verifica dell'apprendimento dei concetti del corso viene effettuata attraverso le esercitazioni/esemplificazioni e le verifiche intermedie.

1. Problemi e Modelli (4 ore)

    

   • Il processo decisionale
   • Esempi di problemi ottimizzazione

    

2. Grafi e Reti di flusso (16 ore)

    

   • Flussi su reti
   • Visita di un grafo
   • Cammini di costo minimo
   • Albero di copertura di costo minimo
   • Flusso massimo
   • Flusso di costo minimo
   • Problemi di accoppiamento

    

3. Programmazione Lineare (18 ore)

    

   • Geometria della Programmazione Lineare
   • Teoria matematica della dualità
   • Algoritmo del simplesso primale
   • Teorema forte della dualità e scarti complementari
   • Algoritmo del simplesso duale
   • Riottimizzazione ed analisi parametrica

    

4. Ottimizzazione Combinatoria (16 ore)

    

   • Ottimizzazione Combinatoria e Programmazione Lineare Intera
   • Tecniche di modellazione
   • Dimostrazioni di ottimalità
   • Algoritmi euristici
   • Tecniche di rilassamento
   • Algoritmi enumerativi

    

Prova scritta seguita da una prova orale. Sono esonerati dalla prova scritta coloro che hanno superato le due verifiche intermedie.