Anno accademico 2021-2022

MODELLI E ALGORITMI PER LE DECISIONI

Docenti

Franca Rinaldi
Giuseppe Lancia
Totale crediti
6
Periodo didattico
Secondo Periodo
Tipologia
Affine/Integrativa
Prerequisiti. Conoscenza della teoria e delle principali tecniche risolutive della programmazione lineare e della programmazione lineare intera.

Concetti e definizioni di base della teoria dei grafi e delle reti di flusso.

Metodi didattici. Lezioni teoriche ed esercitazioni.
Modalità di verifica. L’esame prevede una prova orale atta a verificare la conoscenza degli argomenti trattati nel corso e la capacità di presentarli in modo adeguato, evidenziandone gli aspetti salienti con un linguaggio preciso e formalmente corretto.
Altre informazioni. ~
Obiettivi formativi
Al termine del corso lo studente dovrà:

Conoscenza e comprensione:

– conoscere i principali metodi risolutivi esatti ed euristici che possono essere adottati per problemi di ottimizzazione che emergono nella gestione dei sistemi reali;

– avere dimestichezza nella lettura/scrittura di modelli matematici formali e rigorosi;

– essere in grado di esprimere in forma algoritmica un processo risolutivo astratto, usando un linguaggio di programmazione o uno pseudocodice;

Capacità di applicare conoscenza e comprensione:

– saper riconoscere gli aspetti fondamentali nella formulazione di un modello per un problema di ottimizzazione reale (variabili, vincoli, obiettivo);

– saper valutare la complessità computazionale di un problema e l’efficacia di un algoritmo risolutivo;

– saper proporre procedure euristiche per problemi complessi;

Autonomia di giudizio:

– essere in grado di applicare l’approccio algoritmico più adatto alla risoluzione di un particolare problema;

– essere in grado di aiutare a formulare in modo matematicamente corretto un problema di ottimizzazione del mondo produttivo/industriale;

Abilità comunicative:

– conoscere il linguaggio della teoria dei grafi e dell’ottimizzazione matematica;

– saper presentare il contenuto di un articolo scientifico della disciplina;

Capacità di apprendimento:

– studiare in maniera autonoma, a partire dalla bibliografia consigliata;

– saper formulare modelli opportuni per i problemi illustrati a lezione e per altri definiti in modo autonomo.

Contenuti
Nella prima parte del corso vengono presentate le principali tecniche per la risoluzione euristica di problemi di ottimizzazione (algoritmi approssimati, euristiche greedy, metauristiche di ricerca locale) e la loro applicazione a classici problemi di ottimizzazione combinatoria NP-hard. Nella seconda parte vengono trattate in dettaglio classi di problemi di grande interesse applicativo, in particolare problemi di routing e di scheduling delle macchine, e le relative metodologie di risoluzione.
Testi di riferimento
Dispense e altro materiale bibliografico segnalato e/o messo a disposizione dal docente.