00884 - RICERCA OPERATIVA

Conoscenze e abilità da conseguire

Al termine del corso lo studente è in grado di definire modelli logico-matematici di problemi di ottimizzazione e decisione impiegando la programmazione matematica e la teoria dei grafi. Sa analizzare la complessità dei problemi computazionali e caratterizzarne la difficoltà. Sa determinare, anche mediante il calcolatore, ed interpretare, con autonomia di giudizio, la soluzione di alcune classi di problemi. Lo studente è capace di redigere in modo sistematico relazioni tecniche e di esporne in modo appropriato i contenuti.

Contenuti

1. Introduzione: Problemi decisionali e di ottimizzazione. Modelli dei problemi decisionali e di ottimizzazione e loro classificazione. Metodologia della Ricerca Operativa. Algoritmi esatti ed euristici e cenni alla complessità computazionale di problemi ed algoritmi.
2. Modelli ed algoritmi di Teoria dei Grafi: Generalità e definizioni. Problemi di determinazione di alberi a costo minimo: algoritmi di Prim e Kruskal. Problemi di determinazione di cammini a costo minimo: Algoritmo di Dijkstra. Cenni a problemi più complessi (flusso su rete, Commesso viaggiatore, instradamento di veicoli ...).
3. Ottimizzazione lineare: Cenni ai problemi di ottimizzazione convessa. Forma canonica e standard di un problema di ottimizzazione lineare. Soluzioni ammissibili e soluzione base. Algoritmo del simplesso: interpretazione geometrica, criterio di ottimalità, pivoting, degenerazione, metodo delle due fasi per la determinazione di una soluzione base iniziale. Forma tableau. Analisi di sensitività. Cenni all'uso di un package di risoluzione.
4. Ottimizzazione lineare intera: Formulazioni di un problema di ottimizzazione lineare intera. Soluzione grafica. Introduzione al metodo branch and bound. Introduzione agli algoritmi euristici tradizionali e metaeuristici. Illustrazione di modelli ed algoritmi per problemi applicativi specifici (instradamento di veicoli, taglio ed impiccamento, layout e gestione di reti di telecomunicazione... ).
5. Teoria della dualità ed algoritmo del simplesso duale
6. Metodi di analisi delle decisioni
   

Testi/Bibliografia

slides disponibili online

(per consultazione ed approfondimento)

S. MARTELLO, D. VIGO,,
ESERCIZI DI RICERCA OPERATIVA, PROGETTO LEONARDO, BOLOGNA, 1999.

S. MARTELLO,
LEZIONI DI RICERCA OPERATIVA, PROGETTO LEONARDO, BOLOGNA, 2002

M. FISCHETTI,
LEZIONI DI RICERCA OPERATIVA, EDIZIONI LIBRERIA PROGETTO, PADOVA, 1995

M. Dell'Amico,
120 esercizi di ricerca operativa, Bologna, Pitagora, 1996

S. Pallottino, A. Sciomachen (a cura di)
Scienza delle Decisioni per i Trasporti, Franco Angeli, 1999.

Modalità di verifica e valutazione dell'apprendimento

prova scritta obbligtoria e prova orale obbligatoria

Link ad altre eventuali informazioni

http://or.ingce.unibo.it

Orario di ricevimento

Consulta il sito web di Daniele Vigo