Home » Archivo » Archvio 2013 » RICERCA OPERATIVA - 2013/2014

Laurea in Informatica

Salta il menu di secondo livello

RICERCA OPERATIVA - 6 CFU - A.A. 2013/2014

Insegnante

Dott. Luigi De Giovanni

Periodo

III Anno - 1 Trimestre | 01/10/2013 - 07/12/2013

Ore: 48 (12 esercitazione, 8 laboratorio, 28 lezione)

Torna su ▲

Prerequisiti

Conoscenze di base di analisi matematica e algebra.

Conoscenze e abilità da acquisire

Costruzione di modelli matematici per il supporto alle decisioni e relativi algoritmi, con particolare riferimento alla programmazione
lineare nel continuo e nel discreto e all'ottimizzazione su grafi. Uso di pacchetti software per la soluzione di problemi di ottimizzazione.

Modalità di esame

Scritto, con eventuali orale e/o discussione di un mini-progetto.

Criteri di valutazione

L'esame scritto richiede lo svolgimento di esercizi per la valutazione del livello di apprendimento degli argomenti svolti (ad esempio, modellazione di un problema di ottimizzazione in programmazione lineare intera, applicazione dell'algoritmo del simplesso, applicazione di algoritmi di ottimizzazioni su rete, applicazione della teoria della dualità, applicazione dell'algoritmo del Branch-and-Bound, domande sui diversi argomenti svolti etc.)

contenuti

1. Problemi di ottimizzazione e modelli: modellazione e utilizzo di risolutori software in laboratorio.

2. Programmazione lineare: teoria e metodo del simplesso, teoria della dualità e applicazioni.

3. Ottimizzazione su grafi: modelli e algoritmi per il problema dell'albero di copertura di costo minimo, il problema del cammino minimo (algortimi di Dijkstra e Bellman-Ford), il problema del flusso massimo (algoritmo di Ford-Fulkerson) e del flusso di costo minimo.

4. Elementi di Programmazione Lineare Intera e Ottimizzazione Combinatoria: metodi esatti (Branch-and-Bound), cenni su metodi euristici e metaeuristici (ricerca locale e varianti).

Attività di apprendimento previste e metodologie di insegnamento

L'insegnamento prevede lezioni frontali ed esercitazioni in laboratorio. Le esercitazioni in laboratorio consistono nell'implementazione in un linguaggio di modellazione algebrica di semplici modelli di programmazione lineare (mista intera).

Eventuali indicazioni sui materiali di studio

Vengono rese disponibili delle dispense degli argomenti trattati a lezione e dei lucidi degli argomenti trattati in laboratorio, che contengono tutte le nozioni richieste all'esame.
Gli studenti interessati possono approfondire gli argomenti sui seguenti testi:
- M. Fischetti, Lezioni di Ricerca Operativa, 1999, Libreria Progetto Padova.
- D. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, 1996, Athena Scientific.
- R. K.Ahuja, T. L. Magnanti, J. B. Orlin "Network flows. Theory, algorithms, and applications", 1993, Prentice Hall.
- L. A. Wolsey: "Integer programming", 1998, Wiley.

Testi di riferimento

Torna su ▲