corso

Ricerca Operativa

Codice:	AA092	Crediti:	12	Semestre:	2	Sigla:	RO

Settore disciplinare:		MAT/09 - Ricerca Operativa

Docente

Antonio Frangioni

Tel. 0502212789

Obiettivi di apprendimento

Il corso si propone di fornire allo/a studente/essa le conoscenze di base relative alla modellazione e soluzione di problemi di ottimizzazione.

Descrizione

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.

English Description

The course highlights the importance of constructing mathematical models of real-world systems, presenting some examples relative to different problems in order to give the students the ability to autonomuosly modeling problems. Furthermore, the corse presents some of the main methodologies for solving three large classes of optimization problems, in increasing order of difficulty: network flow problems, linear programming problems and combinatorial optimization problems.

Programma

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à
- Teorema forte della dualità e scarti complementari
- Algoritmo del simplesso primale
- 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)

Bibliografia

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)

Modalità di esame

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