54681 - FONDAMENTI DI RICERCA OPERATIVA LS

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

Il corso illustra i principali strumenti metodologici messi a disposizione dalla Ricerca Operativa per la soluzione dei problemi decisionali e di ottimizzazione che si presentano in campo industriale e gestionale.

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. Teoria della Dualità: Definizione della coppia Primale-Duale. Teoremi della dualità debole e forte e degli scarti complementari. Prezzi ombra. Algoritmo del simplesso duale. Analisi di sensitività.
   
5. 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...).

Testi/Bibliografia

(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.

P. Toth, D. Vigo (a cura di)

The Vehicle Routing Problem, SIAM Philadelphia, 2001.

 

Metodi didattici

Il corso prevede lezioni in aula, esercitazioni in aula ed esercitazioni libere in laboratorio.

 

Modalità di verifica e valutazione dell'apprendimento

Prova scritta e prova orale obbligatoria

Strumenti a supporto della didattica

dispense disponibili in rete

Link ad altre eventuali informazioni

http://or.ingce.unibo.it

Orario di ricevimento

Consulta il sito web di Daniele Vigo