73030 - OTTIMIZZAZIONE SU RETI M

Scheda insegnamento

  • Docente Silvano Martello

  • Crediti formativi 4

  • SSD MAT/09

  • Modalità didattica Convenzionale - Lezioni in presenza

  • Lingua di insegnamento Italiano

  • Orario delle lezioni dal 23/09/2019 al 16/12/2019

Anno Accademico 2019/2020

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.

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

Strumenti a supporto della didattica

Proiettore

Lavagna

Application e freeware

Orario di ricevimento

Consulta il sito web di Silvano Martello