Ricerca Operativa (AA092)
Corso di Laurea in Informatica Applicata
a.a. 2008/2009
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
Appunti del corso
I seguenti paragrafi degli appunti non fanno parte del programma del
corso per l'anno corrente:
- 2.4.3 Albero di copertura bottleneck
- 2.5.3 Algoritmo basato su preflussi
- 2.6.4 Basi di cicli
- 2.7.3 Accoppiamento di massima cardinalità a bottleneck
- 4.2.3 Diseguaglianze valide
- 5.1.1.2 Il problema dell'assegnamento di costo minimo
- 5.1.1.4 Ordinamento di lavori su macchine con minimizzazione del tempo
di completamento
- 5.1.1.5 Ordinamento di lavori su macchine con minimizzazione del
numero delle macchine
- 5.1.1.6 Il problema di copertura
- 5.1.1.7 Il problema (CMST)
- 5.1.2.2 Gli algoritmi SPT e LPT per (MMMS)
- 5.1.3 Matroidi
- 5.2 Algoritmi di ricerca locale
- 6.1.2.2 Uso dell'informazione duale
- 6.3 Rilassamento Lagrangiano
- 6.4 Rilassamento surrogato
- 7.1.2.3 Regole di dominanza
- 7.1.2.5 Preprocessing
- 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)