2019/2020

2019/2020

DM270

MAT/09 (RICERCA OPERATIVA)

DIPARTIMENTO DI MATEMATICA 'FELICE CASORATI'

MATEMATICA

PERCORSO COMUNE

1°

Secondo Semestre (02/03/2020 - 09/06/2020)

6

56 ore di attività frontale

INGLESE

ORALE

GUALANDI STEFANO (titolare) - 6 CFU

Il corso fa parte della formazione in matematica applicata per gli studenti di matematica e ingegneria. Per seguire meglio il corso lo studente deve aver frequentato i corsi e acquisito le conoscenze nelle materie di base in programmazione, analisi e algebra lineare.

Il corso offre un’introduzione alla teoria, ai modelli e agli algoritmi di ottimizzazione matematica. Gli obiettivi del corso sono:

1. Presentare agli studenti lo stato dell’arte della teoria e nella pratica per la soluzione di problemi di ottimizzazione vincolata.

2. Far maturare agli studenti l’esperienza e la capacità di formulare e risolvere problemi di ottimizzazione di grandi dimensioni usando dei software di ottimizzazione.

- Prima Parte: Modelli di Ottimizzazione

Il saper formulare dei modelli di ottimizzazione richiede la capacità di ridurre un problema di calcolo o ingegneristico complesso in un modello matematico che può essere risolto con un software di ottimizzazione. Imparando a riconoscere degli schemi ricorrenti nei modelli di ottimizzazione risolti in problemi reali, lo studente svilupperà le competenze per riuscire a capire quali problemi possono formulati e risolti utilizzando i software di ottimizzazione esistenti (come ad esempio, CPLEX e GUROBI).

- Seconda Parte: Problemi di Flusso

I problemi di flusso sono un caso particolare di problemi di programmazione lineare, che appaiono in moltissimi casi come sottoproblemi di applicazioni complesse. In questa parte del corso vedremo come formulare e risolvere i problemi di flusso fondamentali: il problema del cammino minimo, di flusso massimo, e di flusso di costo minimo.

- Terza Parte: Ottimizzazione Lineare

L’ottimizzazione lineare include i problemi in cui sia la funzione obiettivo che i vincoli sono lineari, e le variabili sono reali. Gli argomenti fondamentali trattati sono: l’algoritmo del simplesso, la teoria della dualità, l’analisi di sensitività, i metodi di punto interno, e alcuni aspetti implementativi.

- Quarta Parte: Ottimizzazione Lineare Intera

L’ottimizzazione lineare intera include i problemi in cui sia la funzione obiettivo che i vincoli sono lineari, ma alcune variabili sono vincolate ad assumere valori interi. Gli argomenti trattati sono: algoritmi di branch-and-bound, algoritmi di generazione di tagli e algoritmi euristici.

Il corso prevede lezioni frontali e esercitazioni in laboratorio informatico.

Dispense distribuite dal docente e reperibili dal sito web del corso.


Capitoli selezionati dei seguenti libri:
• H.P. Williams. Model building in mathematical programming. John Wiley & Sons, 2013.
• R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows, 1988.
• D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific, 1997.
• D. Bertsimas and R. Weismantel. Optimization over Integers. Belmont, MA: Dynamic Ideas, 2005.

L'esame è orale e ha l'obiettivo di verificare il livello di apprendimento degli studenti sul programma del corso. Parte dell'esame orale sarà dedicato alla presentazione di un progetto elaborato durante lo svolgimento del corso.

Il corso è articolato in quattro parti. Durante ciascuna parte, verrano usati come esempi problemi di Biologia Computazionale (ad esempio, i problemi di Alignment of Genomic Sequencing, Metabolic Networks, Haplotype Analysis), di Pianificazione e Scheduling (ad esempio, problemi di gestione di servizi medici a domicilio, turnistica di personale ospedaliero), e di Machine Learning (ad esempio, problemi di regressione, clustering, e classificazione).