Ricerca Operativa (AA092)
Corso di Laurea in Informatica Applicata
a.a. 2005/2006
A. Frangioni
Il corso si propone di fornire allo/a studente/essa le conoscenze di base
relative alla modellazione e soluzione di problemi di ottimizzazione.
Verrà discussa l'importanza della costruzione di modelli analitici
di sistemi reali e verranno presentati esempi relativi a diversi problemi,
in modo da fornire allo studente la capacità di modellare
autonomamente i problemi. Verranno 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.
PROGRAMMA DEL CORSO
- Problemi e Modelli (4 ore)
- Il processo decisionale
- Esempi di problemi ottimizzazione
- 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
- 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
- Ottimizzazione Combinatoria (16 ore)
- Ottimizzazione Combinatoria e Programmazione Lineare Intera
- Tecniche di modellazione
- Dimostrazioni di ottimalità
- Algoritmi euristici
- Tecniche di rilassamento
- Algoritmi enumerativi
(Le ore indicate non includono le esercitazioni)
Testi di riferimento
- Appunti del corso
- F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa",
Franco Angeli, Milano (1999)
- A. Sassano, "Modelli e algoritmi della ricerca operativa", Franco
Angeli, Milano (1999)
- C. Vercellis, "Modelli e decisioni", Progetto Leonardo, Bologna (1997)