- Docente: Silvano Martello
- Crediti formativi: 8
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- 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.
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.
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 modelli matematici e di teoria dei grafi, 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
Proiettore
Lavagna
Applet e freewareLink 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