Algoritmi e Modelli di Ottimizzazione
I semestre
Il corso è offerto sia in versione da
6 CFU sia in versione da
9 CFU, a seconda del piano di studi. La pagina ufficiale del corso con tutto il materiale didattico (dispense, esercizi, compiti d'esame, ecc.) è disponibile su
moodle.
Orario delle lezioni
| Giorno | Orario | Aula |
|---|
| Lunedì | 10:00 – 12:00 | N13 |
| Giovedì | 12:00 – 14:00 | N13 |
| Venerdì | 8:00 – 10:00 | N13 |
Modalità di esame
Sono previste prove intermedie durante il corso.
L'esame consiste in una prova scritta al termine del corso, secondo il calendario indicato. Gli studenti che riportano un voto quasi sufficiente, o che desiderano discutere lo scritto, integrano l'esame con una prova orale da sostenersi nello stesso appello.
L'esame per gli appelli successivi al primo (appelli di recupero) consiste in una prova scritta e orale.
Programma del corso
- Introduzione alla Programmazione Lineare a numeri interi (PLI): relazione fra PL e PLI, formulazioni equivalenti, rilassamenti, matrici totalmente unimodulari, tecniche standard per la formulazione di problemi di PLI.
- Formulazione di tipici problemi di ottimizzazione: localizzazione di impianti, scelta di investimenti, sequenziamento di attività, ottimizzazione su reti, trasporti, set covering, set partitioning, set packing, turni del personale, cloud computing.
- Soluzione esatta di problemi di Programmazione Lineare a numeri interi: programmazione dinamica, branch and bound, piani di taglio, cenni al branch and cut.
- Problemi su grafi: max matching, min vertex cover. Grafi euleriani e grafi bipartiti.
- Utilizzo di un software commerciale per la soluzione di problemi di programmazione matematica.
Testi di riferimento
- [1] M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995. (Cap. 2, 5, parte del 6 e del 7).
- [2] R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993. (pg. 189-191, 473-475, 494-496).
- [3] Dispense fornite dal docente e/o disponibili sul web.
Ricevimento
Per appuntamento da prendere via email.
← Torna alla homepage