Docente

• Prof. Franca Rinaldi

Indirizzo e-mail
franca.rinaldi@uniud.it

Indirizzo Pagina Web Personale
http://www.dimi.uniud.it/~rinaldi/scheda.html

Crediti

6 CFU

Finalità

Il corso continua la presentazione di alcuni argomenti fondamentali dell’ottimizzazione matematica, sviluppando la teoria della dualità, la teoria delle reti di flusso, la programmazione dinamica e lo studio di particolari problemi di ottimizzazione su grafi.

Programma

Dualità. Rilassamento lagrangiano e metodo del subgradiente. Metodo del simplesso con generazione di colonne.

Reti di flusso Reti, flussi e potenziali. Il problema di flusso a costo minimo e sue applicazioni. Metodo del simplesso per reti di flusso. I problemi del massimo flusso e del taglio di capacità minima. L'algoritmo di Dinic-Karzanov. Il problema del cammino minimo e l'algoritmo di Dijkstra.

Programmazione dinamica Principio di ottimalità ed equazione di Bellman. Procedure di PD per problemi di cammino minimo. Procedure di PD per problemi di knapsack. Procedure di PD per altri problemi di ottimizzazione combinatoria.

Ottimizzazione combinatoria Matroidi e algoritmo greedy. Algoritmi per l'albero di supporto di costo minimo. Problemi di accoppiamento. Algoritmi per l'accoppiamento di cardinalità massima su grafi bipartiti e generici. Modelli di programmazione lineare intera per il problema dell'accoppiamento di costo minimo.

Bibliografia

Dispense del docente
Paolo Serafini, Ottimizzazione, Zanichelli, Bologna 2000.

Modalità d'esame

L’esame consiste in una prova scritta e in una prova orale.