72935 - RICERCA OPERATIVA M

Conoscenze e abilità da conseguire

Modelli matematici, programmazione lineare, algoritmo del simplesso, dualità. Programmazione lineare intera, piani di taglio, branch-and-bound. Complessità. Programmazione dinamica. Simulazione discreta.

Contenuti

Prerequisiti:
È necessario che l'allievo comprenda la lingua inglese scritta per poter seguire le slide di lezione.

Programma:
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. Complessità
7.1 Versione riconoscimento di un problema
7.2 Classi P ed NP
7.3 Problemi NP-completi
7.4 Programmazione dinamica
7.5 Problemi fortemente NP-completi

8 Simulazione Discreta
8.1 Generazione di valori pseudo-casuali
8.2 Componenti della simulazione
8.3 Linguaggi di simulazione
8.4 Entità temporanee e permanenti
8.5 Eventi ed event notice
8.6 Esecuzione degli esperimenti

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.
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 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 matematici o di simulazione numerica.
Per i modelli matematici 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 matematici e di simulazione numerica, e nella soluzione, mediante gli opportuni algoritmi, di semplici problemi di ottimizzazione. La prova dura circa due ore 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

Applet e freeware

Orario di ricevimento

Consulta il sito web di Valentina Cacchiani

Consulta il sito web di Silvano Martello