- Docente: Silvano Martello
- Crediti formativi: 8
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Moduli: Silvano Martello (Modulo 1) Valentina Cacchiani (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Bologna
- Corso: Laurea Magistrale in Ingegneria informatica (cod. 0937)
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.
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 Analisi di sensitività
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 e valutazione 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).
La visione degli elaborati corretti e` possibile unicamente nella data prefissata (normalmente coincidente con quella della successiva prova orale).
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