72935 - RICERCA OPERATIVA M

Scheda insegnamento

  • Docente Silvano Martello

  • Moduli Silvano Martello (Modulo 1)
    Valentina Cacchiani (Modulo 2)

  • Crediti formativi 8

  • SSD MAT/09

  • Modalità didattica Convenzionale - Lezioni in presenza (Modulo 1)
    Convenzionale - Lezioni in presenza (Modulo 2)

  • Lingua di insegnamento Italiano

Anno Accademico 2019/2020

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.

Programma/Contenuti

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

MODULO 1: Silvano Martello

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

6.7 Software e freeware

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

MODULO 2: Valentina Cacchiani

Simulazione Discreta: introduzione alla simulazione discreta, descrizione statica e dinamica di un sistema, entità temporanee e permanenti, eventi ed event notice. Esercitazioni per la modellazione di sistemi realistici.


Testi/Bibliografia

MODULO 1

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.

 

MODULO 2

Slide disponibili su Insegnamenti OnLine.

Per ulteriori esercizi di simulazione:

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

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 dell'apprendimento

L'apprendimento viene verificato mediante una prova scritta (comprensiva dei due moduli, con unica votazione) ed una prova orale.

La prova scritta ha durata di circa due ore ed e` composta da un esercizio relativo al MODULO 1 (modellizzazione di un sistema mediante modelli matematici e soluzione, mediante gli opportuni algoritmi, di semplici problemi di ottimizzazione) , cui sono attribuiti 15 punti, e da un esercizio relativo al MODULO 2 (modellizzazione di un sistema mediante simulazione discreta), cui sono attribuiti 15 punti. I due esercizi devono essere svolti nella stessa prova scritta. La prima volta che vengono consegnati i due elaborati, viene aggiunto al punteggio un bonus di 3 punti. Il voto della prova scritta e` quindi dato da:

voto prova scritta modulo 1 + voto prova scritta modulo 2 + bonus (se e` la prima consegna).

I candidati che riportano voto positivo nella prova scritta devono sostenere una prova orale sulla conoscenza teorica relativa al solo MODULO 1 (proprietà, dimostrazioni, ecc.), valutata in trentesimi. Detto k l'appello in cui si è superata la prova scritta, la prova orale va sostenuta 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 della prova scritta (nell'ambito della sua validità).

I candidati che rifiutano il voto finale ottenuto devono ripetere la prova scritta e la prova orale.

Strumenti a supporto della didattica

Applet e freeware

Orario di ricevimento

Consulta il sito web di Silvano Martello

Consulta il sito web di Valentina Cacchiani