| | | corso | | | | |
Ricerca Operativa
Codice: | AA092 | Crediti: | 12 | Semestre: | 2 | Sigla: | RO | |
|
Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Antonio Frangioni
Tel. 0502212789Prerequisiti
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: | 50 | Ore esercitazione: | 30 | | | |
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.