Docente
|
BRUNI RENATO
(programma)
1) Introduzione all’Ottimizzazione Combinatoria
Problemi di Decisione, Struttura generale dei problemi di Ottimizzazione Combinatoria (OC).
Parallelismo tra OC con funzione obiettivo lineare e PL01.
Primo esempio di OC: Pianificazione degli Investimenti.
2) Introduzione alla Teoria dei Grafi
Definizioni e terminologia:
Grafi orientati, non orientati, tagli, cammini, cicli, componenti connesse, alberi, etc.
3) Cenni di Complessità Computazionale
La valutazione della complessità computazionale.
Modelli di calcolo e Classi di Complessità computazionale.
Le classi P ed NP.
4) Formulazioni e Bound
Valutazione di soluzioni ammissibili tramite Bound.
Bound da rilassamento lineare. Formulazioni e Formulazioni Ottime.
Algoritmo di Branch & Bound.
Totale Unimodularità.
5) Problemi di flusso a costo minimo
Flusso su una rete, Flusso ammissibile.
Totale unimodularità della matrice e interezza delle soluzioni
Cammino minimo e massimo flusso come casi particolari
6) Problemi di Cammino Minimo
Concetto di Cammino minimo.
Formulazione e suo duale.
Algoritmo di Bellman-Ford; algoritmo di Floyd-Warshall.
7) Problemi di Massimo Flusso
Concetto di Massimo flusso.
Formulazione e suo duale.
Teorema massimo flusso/minimo taglio.
8) Problemi di Localizzazione Impianti
Formulazione Forte e Debole.
Simplesso Dinamico.
Uso di strumenti software per la risoluzione.
Implementazione tramite AMPL del simplesso dinamico.
9) Problema del minimo Ciclo Hamiltoniano
Concetto di euristica, utilità delle euristiche. Greedy e Ricerca Locale.
Ricerca Locale con intorni esponenziali e matching.
Problema del minimo Albero Ricoprente.
Algoritmo di Christofides.
10) Problemi di Vehicle Routing
Clustering e Routing.
Modello Completo e sue varianti: capacità veicoli, numero veicoli variabile e aspetti temporali.
Approcci risolutivi: euristiche costruttive, euristiche due fasi, euristiche migliorative.
11) Problemi di Scheduling di Personale
Definizione del problema e Modello di PL01.
Tecniche per ottenere soluzione bilanciata e tenere conto delle preferenze dei lavoratori.
Materiale didattico
Slides delle lezioni (contenenti anche esempi svolti) scaricabili dalla pagina web del docente. Tale materiale
è sufficiente per la preparazione dell’esame. Le lezioni seguiranno molto fedelmente le slides.
Testi per eventuale approfondimento
A. Sassano: Modelli e Algoritmi della Ricerca Operativa, 2a edizione, Franco Angeli editore, 2004.
D. Bertsimas J.N. Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
|