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.
Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate. Agli studenti verrà insegnato a: interpretare e modellare un processo decisionale (di progettazione, di gestione, ecc.) nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali da ottimizzare e la funzione di costo (o la cifra di merito) da minimizzare (o da massimizzare); inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, ecc.); realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione.
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: Su appuntamento
DAVIDE GIGLIO (Presidente)
MARCELLO SANGUINETI (Presidente)
FEDERICA BRIATA
MAURO GAGGERO
DANILO MACCIO'
19 settembre 2016
Scritto e orale
Sia domande di teoria sia svolgimento di esercizi
