34878 - RICERCA OPERATIVA M

Conoscenze e abilità da conseguire

Il corso fornisce metodologie teoriche e algoritmiche avanzate per la soluzione di problemi decisionali che si presentano, in ambiti industriali ed organizzativi, quando si debbono gestire in modo ottimo risorse limitate. Gli studenti acquisiranno la capacità di 1. rappresentare, mediante modelli di programmazione lineare, grafi e modelli di simulazione, casi reali nei quali sono presenti problemi di ottimizzazione; 2. determinarne la soluzione applicando l'algoritmo di ottimizzazione appropriato o definendo un programma di simulazione

Contenuti

1. Il metodo scientifico: sistemi, modelli, metodologie

2. Programmazione Matematica
2.1 Problemi di ottimizzazione
2.2 Insiemi e funzioni convesse
2.3 Programmazione convessa

3. Programmazione Lineare
3.1 Forma generale, canonica e standard
3.2 Basi e soluzioni base
3.3 Politopi convessi

4. Algoritmo del Simplesso
4.1 Spostamento tra soluzioni base
4.2 Il tableau e il pivoting
4.3 Criterio di ottimalità
4.4 Algoritmo del simplesso
4.5 Metodo delle due fasi
4.6 Aspetti geometrici dell'ottimizzazione

5. Dualità
5.1 Duale di un problema di programmazione lineare
5.2 Proprietà della dualità
5.3 Lemma di Farkas
5.4 Scarti complementari
5.5 Algoritmo del simplesso duale
5.6 Algoritmo primale-duale

6. Programmazione Lineare Intera
6.1 Unimodularità
6.2 Algoritmi cutting-plane e tagli di Gomory
6.3 Algoritmi branch-and-bound
6.4 Strategie di esplorazione
6.5 Problema knapsack 0-1
6.6 Algoritmi branch-and-cut

7. Problemi su Grafi
7.1 Shortest spanning tree
7.2 Cammini minimi
7.3 Problema del flusso massimo
7.4 Modelli matematici e condizioni di unimodularità
7.5 Metodo CPM
7.6 Circuiti hamiltoniani e traveling salesman problem
7.7 Problemi di vehicle routing

8. Complessità
8.1 Versione riconoscimento di un problema
8.2 Classi P ed NP
8.3 Problemi NP-completi
8.4 Programmazione dinamica
8.5 Problemi fortemente NP-completi

9. Rilassamenti
9.1 Rilassamento per eliminazione; rilassamento continuo
9.2 Rilassamento surrogato
9.3 Rilassamento lagrangiano
9.4 Rilassamento per decomposizione
9.5 Ottimizzazione subgradiente
9.6 Relazioni di dominanza tra rilassamenti
9.7 Tecniche di riduzione

10. Algoritmi Approssimati ed Euristici
10.1 Algoritmi approssimati e schemi di approssimazione
10.2 Algoritmi euristici
10.3 Algoritmi metaeuristici

11 Simulazione Discreta
11.1 Generazione di valori pseudo-casuali
11.2 Componenti della simulazione
11.3 Linguaggi di simulazione
11.4 Entità temporanee e permanenti
11.5 Eventi ed event notice
11.6 Esecuzione degli esperimenti

Testi/Bibliografia

Libro di testo: S. Martello, Ricerca Operativa per la Laurea Magistrale, Esculapio (progetto Leonardo), Bologna, 2011.

Slide (in Inglese)

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

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

S. Martello, D. Vigo, Esercizi di Simulazione Numerica, Esculapio (progetto Leonardo), Bologna, 2001.

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, esercitazioni in aula ed esercitazioni in laboratorio.
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 matematici o di simulazione numerica.
Per i modelli matematici la soluzione viene determinata mediante gli algoritmi illustrati nelle lezioni.
In laboratorio sono disponibili ambienti in cui si possono utilizzare pacchetti software di programmazione lineare e programmazione lineare intera, nonche' il linguaggio di simulazione numerica SIMSCRIPT II.5 .

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 simulazione numerica e nella soluzione, mediante gli opportuni algoritmi, di semplici problemi di ottimizzazione. La prova dura circa 2h30' e la valutazione avviene in trentesimi.
I candidati che riportano voto positivo nella prova scritta debbono sostenere una prova orale sulla conoscenza teorica della materia (proprieta', dimostrazioni, ecc.), anch'essa valutata in trentesimi. Detto k l'appello in cui si e' superata la prova scritta, l'orale va sostenuto entro l'appello k + 2.
Il voto finale e' 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 validita').

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