34878 - RICERCA OPERATIVA M

Conoscenze e abilità da conseguire

Introduzione alla simulazione di sistemi discreti e al linguaggio SIMSCRIPT. Conoscenze approfondite di programmazione lineare intera, teoria dei grafi, teoria della complessità, algoritmi branch-and-bound.

Contenuti

1. SIMULAZIONE DI SISTEMI DISCRETI:
1.1 richiami di statistica: variabili aleatorie;
1.2 generazione di valori pseudo-casuali, metodo della trasformazione inversa;
1.3 descrizione statica e dinamica di un sistema;
1.4 metodo della programmazione degli eventi;
1.5 diagrammi di flusso per problemi di simulazione;
1.6 linguaggio SIMSCRIPT II.5 .
2. PROGRAMMAZIONE LINEARE:
2.1 proprieta' fondamentali della programmazione convessa;
2.2 richiami sulla programmazione lineare e l'algoritmo del simplesso;
2.3 teoria della dualità: problema duale, condizioni di ortogonalità;
2.4 algoritmo del simplesso duale;
2.5 algoritmo primale-duale.
3. PROGRAMMAZIONE LINEARE INTERA:
3.1 Unimodularità;
3.2 metodo dei piani di taglio di Gomory;
3.3 metodo branch-and-bound;
3.4 programmazione lineare mista e binaria;
3.5 problema knapsack 0-1;
3.6 algoritmi branch-and-cut (cenni); 3.7 software.
4 PROBLEMI SU GRAFI:
4.1 richiami di teoria dei grafi;
4.2 relazioni tra cammini minimi, flussi e programmazione lineare;
4.3 unimodularita' delle matrici di incidenza;
4.4 circuiti hamiltoniani: algoritmo enumerativo; 4.5 problemi di vehicle routing.
5 TEORIA DELLA COMPLESSITA':
5.1 classi P ed NP; problemi NP-completi;
5.2 complessità dei principali problemi di ottimizzazione combinatoria;
5.3 programmazione dinamica;
5.4 problemi fortemente NP-completi.
6. ALGORITMI BRANCH-AND-BOUND:
6.1 schemi di branching;
6.2 rilassamenti: continuo, lagrangiano, surrogato;
6.3 applicazione al problema knapsack multiplo;
6.4 procedure di riduzione;
6.5 algoritmi approssimati: analisi sperimentale, probabilistica, worst-case;
6.6 algoritmi metaeuristici (cenni)
7. PROBLEMI E TECNICHE DELL'OTTIMIZZAZIONE COMBINATORIA:
7.1 Problemi di matching;
7.2 Problema dell' assegnamento lineare min-sum;
7.3 Altri problemi di assegnamento lineare;
7.4 Problemi di assegnamento quadratico;
7.5 Tecniche metaeuristiche;
7.6 Problemi di impaccamento;
7.7 Problemi di trasporto.

 

Testi/Bibliografia

S. Martello, 'Ricerca Operativa LS', Esculapio (progetto Leonardo), Bologna, Edizione 2009.
Contiene:
1. riproduzione dei trasparenti utilizzati per le lezioni;

2. esercizi svolti.
Il testo non e' indispensabile per gli studenti che frequentano regolarmente lezioni ed esercitazioni.

Dispense aggiuntive verranno rese disponibili dal docente.

Per eventuali approfondimenti:

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

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

C. Papadimitriou, K. Steiglitz, 'Combinatorial Optimization', Prentice Hall, 1982.

S. Martello, P. Toth, 'Knapsack Problems: Algorithms and Computer Implementations',
Wiley, 1990 (download http://www.or.deis.unibo.it/knapsack.html )

R. Burkard, M. Dell'Amico, S. Martello, 'Assignment Problems', SIAM, Philadelphia, 2009 (see www.assignmentproblems.com) .

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.
Durante le esercitazioni in laboratorio (libere e facoltative) vengono messi a disposizione 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 due ore 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

Lavagna luminosa.

Proiettore

 

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