PRESENTAZIONE

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.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

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.

OBIETTIVI FORMATIVI (DETTAGLIO)

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:

• 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, statici/dinamici, 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.

MODALITA' DIDATTICHE

Lezioni frontali.

PROGRAMMA/CONTENUTO

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)

• Esercizi sugli argomenti del Corso.
• Strumenti software per la Ricerca Operativa (Lingo, Matlab Optimization Toolbox, ecc.).

TESTI/BIBLIOGRAFIA

Materiale didattico fornito a lezione.

Matteo Fischetti, “Lezioni di Ricerca Operativa”, 1999.

DOCENTI E COMMISSIONI

Commissione d'esame

DAVIDE GIGLIO (Presidente)

MARCELLO SANGUINETI (Presidente)

FEDERICA BRIATA

MAURO GAGGERO

DANILO MACCIO'

LEZIONI

INIZIO LEZIONI

19 settembre 2016

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Scritto e orale

MODALITA' DI ACCERTAMENTO

Sia domande di teoria sia svolgimento di esercizi

Calendario appelli