73030 - OTTIMIZZAZIONE SU RETI M

Conoscenze e abilità da conseguire

Introduzione alla teoria dei grafi. Alberi, cammini, flussi nelle reti di trasporto, metodi PERT-CPM, circuiti hamiltoniani, problemi di routing. Rilassamento lagrangiano e surrogato. Algoritmi approssimati, euristici e metaeuristici.

Contenuti

Prerequisiti:
È necessario che l'allievo abbia seguito il corso Ricerca Operativa M.

Programma:
1. Richiami da Ricerca Operativa M

2. Teoria dei grafi e delle reti
2.1 Introduzione
2.2 Terminologia

3. Problemi fondamentali su grafi
3.1 Alberi di costo minimo
3.2 Problemi di cammini minimi
3.3 Metodo CPM per la gestione di progetti

4. Reti di flusso
4.1 Problemi di flusso massimo
4.2 Problemi di flusso a costo minimo
4.3 Modelli matematici per problemi su grafi e reti
4.4 Condizioni di unimodularità

5. Circuiti ottimi
5.1 Circuiti hamiltoniani
5.2 Problema del commesso viaggiatore
5.3 Problemi di instradamento

6. Rilassamenti
6.1 Rilassamento surrogato
6.2 Rilassamento lagrangiano e per decomposizione
6.3 Ottimizzazione subgradiente
6.4 Tecniche di riduzione

7. Algoritmi approssimati ed euristici
7.1 Algoritmi greedy
7.2 Comportamento nel caso peggiore
7.3 Ricerca locale
7.4 Algoritmi metaeuristici

Testi/Bibliografia

Libro di testo: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2014.

Slide (in Inglese)

Il libro di testo contiene numerosi esercizi svolti. Per ulteriori esercizi:

S. Martello, D. Vigo, Esercizi di Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2003.

Per eventuali approfondimenti:

C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990 (download gratuito) 

R. Burkard, M. Dell'Amico, S. Martello, Assignment Problems - Revised reprint, SIAM, Philadelphia, 2012.

Metodi didattici

Il corso e' strutturato in lezioni ed esercitazioni in aula.
Durante le lezioni vengono discusse le problematiche teoriche e gli aspetti algoritmici degli argomenti trattati.
Durante le esercitazioni vengono proposti casi industriali in cui si presentano problemi di ottimizzazione e vengono derivati i corrispondenti modelli su grafi o reti.
La soluzione viene determinata mediante gli algoritmi illustrati nelle lezioni.

Modalità di verifica e valutazione dell'apprendimento

L'apprendimento viene verificato mediante una prova scritta ed una prova orale.

La prova scritta consiste nella modellizzazione di un sistema mediante modelli su grafi e reti e nella soluzione, mediante gli opportuni algoritmi, di  semplici problemi di ottimizzazione. La prova dura circa un'ora e la valutazione avviene in trentesimi.

I candidati che riportano voto positivo nella prova scritta devono sostenere una prova orale sulla conoscenza teorica della materia (proprietà, dimostrazioni, ecc.), anch'essa valutata in trentesimi. Detto k l'appello in cui si è superata la prova scritta, l'orale va sostenuto entro l'appello k + 2.

Il voto finale è dato dalla media pesata:
       2/3 (voto prova scritta) + 1/3 (voto prova orale)
arrotondata per eccesso.

I candidati respinti alla prova orale conservano il voto dello scritto (nell'ambito della sua validità).

Strumenti a supporto della didattica

Proiettore

Lavagna

Applet e freeware

Link ad altre eventuali informazioni

http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html

Orario di ricevimento

Consulta il sito web di Silvano Martello