Ricerca operativa A - (5 cfu)
| Prof. Alberto Caprara | - |
Finalità
Il modulo si propone di analizzare i principali strumenti messi a disposizione dalla Ricerca Operativa per la soluzione dei problemi decisionali che si presentano nell'industria e nei servizi. In questa ottica verranno analizzate le tecniche di simulazione numerica e quelle relative alla soluzione dei problemi di programmazione lineare e programmazione lineare intera.
Programma
Il corso si divide in 5 parti principali.
La prima parte prevede una introduzione ai problemi decisionali e di ottimizzazione e la definizione delle possibili approcci proposti dalla Ricerca Operativa e dei possibili modelli associati.
La seconda parte del corso analizza i problemi di ottimizzazione di base definiti su grafi; in particolare vengono analizzati i problemi di determinazione di alberi a costo minimo, di determinazione di cammini minimi, di determinazione del flusso massimo, di pianificazione di progetti. Infine vengono forniti cenni a problemi più complessi, quali il problema del commesso viaggiatore o il problema del vehicle routing.
La terza parte del corso è relativa alla teoria della programmazione lineare. Vengono fornite le nozioni di base relative alla programmazione lineare, evidenziando le potenzialità ed i limiti dei modelli lineari e introducendo il metodo di risoluzione grafica per l’ottimizzazione lineare.
La quarta parte del corso è relativa alla programmazione lineare intera. In particolare, vengono descritti modelli di base di programmazione lineare intera, le possibili modalità con cui vincoli logici possono essere introdotti nei modelli matematici, e viene analizzata in dettaglio la tecnica branch-and-bound per la soluzione di problemi di programmazione lineare intera; vengono infine dati cenni relativi ad altri possibili approcci risolutivi per questo tipo di problemi.
L’ultima parte del corso è relativa alla simulazione numerica. In particolare, vengono descritti i possibili metodi di programmazione utilizzabili (metodo della programmazione degli eventi e metodo della interazione dei processi) e le modalità di implementazione e sperimentazione dei modelli di simulazione.
Attività d'esercitazione
Il corso prevede lo svolgimento in aula di esercitazioni relativamente a tutti gli argomenti trattati.
Modalità d'esame
2 prove scritte (simulazione ed ottimizzazione) ed una prova orale.
E’ possibile svolgere un progetto consistente nella modellazione di un problema reale e nella implementazione del corrispondente modello matematico mediante un opportuno package di soluzione;lo svolgimento corretto di tale progetto sostituisce la prova orale.
Propedeuticità
Nessuna
Testi consigliati
Dispense a cura del docente (distribuite durante le lezioni e/o disponibili in rete).
S. Martello, Lezioni di Ricerca Operativa, III Edizione, Progetto Leonardo, Bologna, 1998.
S. Martello, D. Vigo, Esercizi di Ricerca Operativa , IV Edizione, Progetto Leonardo, Bologna, 1999
Testi d'approfondimento
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto, Padova, 1995.
M. Dell’Amico, 120 Esercizi di Ricerca Operativa, Pitagora, Bologna, 1996.
C.Papadimitriou, K.Steiglitz, Combinatorial Optimization, Prentice Hall, 1982.
Ultimo aggiornamento: 07-11-2002