Il Corso introduce a modelli e metodi di ottimizzazione matematica utilizzabili per la soluzione di problemi decisionali. Si articola nei temi della modellazione di problemi, della loro trattabilità, dei metodi di soluzione tramite la programmazione lineare e non-lineare, l'ottimizzazione combinatoria, l'ottimizzazione su reti e grafi e la programmazione dinamica, fino ad arrivare ad algoritmi implementabili su un calcolatore. La materia viene presentata nei suoi aspetti metodologici, teorici ed applicativi.
Il corso fornisce le competenze per affrontare problemi applicativi sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate
Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi sviluppando modelli e metodi anche originali, che operino in modo efficiente in presenza di risorse limitate. Gli studenti impareranno a:
Lezioni frontali.
INTRODUZIONE ALLA RICERCA OPERATIVA
Le origini della Ricerca Operativa.
Problemi reali e modelli matematici. Limiti dei modelli.
Obiettivi, variabili decisionali, vincoli.
Classificazioni dei problemi di ottimizzazione.
Dimensione dei problemi e inefficienza degli algoritmi “brute force”.
Un esempio numerico introduttivo.
PROGRAMMAZIONE LINEARE (PL)
Modelli di PL di importanza applicativa.
Esempio grafico introduttivo.
Algebra e geometria della PL.
Algoritmo del simplesso. Interpretazioni algebrica e geometrica. Simplesso sul tableau.
Analisi di post-ottimalità.
DUALITÀ
Problemi duali: modelli di PL di importanza applicativa.
Dualità debole e dualità forte.
Interpretazione economica della dualità (prezzi ombra).
Slackness complementare.
PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI)
Modelli di PLI di importanza applicativa (Matching, Sequencing, Fixed-Charge, Knapsack, Steiner Tree, Plant Location, Scheduling).
Algebra e geometria della PLI. Matrici totalmente unimodulari.
Algoritmo di tipo branch-and-bound.
Algoritmo basati su piani di taglio. Tagli di Gomory.
Algoritmi di tipo branch-and-cut.
GRAFI E RETI
Definizioni e generalità sui grafi.
Rappresentazione dei grafi.
Il problema di Shortest Path (SP) e il suo modello di PLI. Algoritmo di Dijkstra. Algoritmo di Bellman-Ford.
Il problema di Shortest Spanning Tree (SST) e il suo modello di PLI. Algoritmo di Kruskal. Algoritmo di Primm-Dijkstra.
Algoritmi greedy.
Cenni al Travelling Salesman Problem (TSP) e al suo modello di PLI.
Problemi di flusso (Max-Flow, Min-Cost-Flow). Algoritmo di Ford-Fulkerson per il Max-Flow)
CENNI ALLA TEORIA DELLA COMPLESSITÀ
Concetto di istanza e dimensione di un'istanza.
Complessità computazionale di un algoritmo.
Problemi trattabili ed intrattabili. Problemi in forma decisionale.
Classi P, NP e co-NP. Concetto di algoritmo non-deterministico.
Il teorema di Cook. La classe dei problemi NP-completi.
Esempi di problemi NP-completi e rispettivi modelli di PLI: knapsack, Steiner tree, …
Problemi NP-hard.
PROGRAMMAZIONE DINAMICA (PD)
Esempio introduttivo.
Problemi di ottimizzazione a stadi. Contesto deterministico.
Fase backward e fase forward.
Principio di ottimalità.
Le equazioni di Bellman.
Estensione al contesto stocastico.
La “maledizione della dimensionalità”.
CENNI ALLA PROGRAMMAZIONE NON LINEARE (PNL)
ESERCITAZIONI (facoltative; distribuite durante il Corso)
Materiale didattico fornito a lezione.
Matteo Fischetti, “Lezioni di Ricerca Operativa”, 1999.
Ricevimento: Students may also take appointment via email sent to mauro.gaggero@cnr.it
MAURO GAGGERO (Presidente)
SILVIA SIRI (Presidente)
SIMONA SACONE
19 settembre 2016
Scritto e orale
Sia domande di teoria sia svolgimento di esercizi
