73030 - OTTIMIZZAZIONE SU RETI M

Scheda insegnamento

Anno Accademico 2020/2021

Conoscenze e abilità da conseguire

Il corso introduce lo studente ai problemi su grafi e reti ed alle principali tecniche algoritmiche relative. Al termine del corso lo studente consegue competenze nella modellizzazione di problemi industriali rappresentabili mediante grafi o reti di flusso e nelle principali metodologie per la loro soluzione.

Contenuti

Prerequisiti:
Si richiede che lo studente abbia seguito il corso Ricerca Operativa M o un corso equivalente sulla Ricerca Operativa.

Programma:

1. Richiami di Ricerca Operativa M

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

3. Problemi fondamentali su grafi
3.1 Albero ricoprente 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 vehicle routing

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

7. Algoritmi approssimati ed euristici
7.1 Algoritmi greedy
7.2 Rapporto di 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.

Slides (in English)

Il libro di testo contiene numerosi esercizi svolti. Ulteriori esercizi svolti sono in:

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

Per 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 (free download).

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 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à).

ESAMI ONLINE
Nel caso in cui gli esami vengano svolti in modalità online, verificare le istruzioni nella sezione "Avvisi".

Strumenti a supporto della didattica

Proiettore

Lavagna

Application e freeware

Orario di ricevimento

Consulta il sito web di Silvano Martello