corso

Ricerca Operativa

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

Settore disciplinare:		MAT/09 - Ricerca Operativa

Docente

Antonio Frangioni

Tel. 0502212789

Prerequisiti

Algebra

Obiettivi di apprendimento

Conoscenza delle principali classi di problemi di ottimizzazione, e comprensione delle basi matematiche dei corrispondenti algoritmi risolutivi. Sviluppo della capacità di formulare autonomamente modelli matematici corrispondenti a problematiche reali(stiche).

Conoscenze. Modellazione di problemi di ottimizzazione. Problemi di flusso e cammino. Programmazione Lineare. Programmazione Lineare Intera. Algoritmi esatti ed approssimati per problemi di ottimizzazione "difficili".

Capacità. Formulare autonomamente modelli matematici corrispondenti a problematiche reali(stiche). Sviluppare algoritmi risolutivi per 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.

Indicazioni metodologiche

Il corso presenta le principali classi di problemi di ottimizzazione in ordine crescente di complessità. Per ciascuna classe di problemi vengono presentati uno o più algoritmi risolutivi, con particolare enfasi sulle proprietà matematiche che ne suggeriscono lo sviluppo e permettono di dimostrarne proprietà di correttezza ed efficienza; obiettivo finale è quello di fornire allo studente i principali concetti algoritmici utili alla soluzione di problemi di ottimizzazione. Il corso alterna costantemente parti teoriche, con dimostrazione rigorosa di enunciati matematici, ad esemplificazioni atte ad illustrare le proprietà ed il funzionamento degli algoritmi proposti. La verifica dell'apprendimento dei concetti del corso viene effettuata attraverso le esercitazioni/esemplificazioni e le verifiche intermedie.

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)

Ore lezione:

Ore esercitazione:

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.