Ricerca operativa è un insegnamento di matematica applicata che fa da ponte tra gli insegnamenti di base dei primi tre semestri della laurea e quelli applicativi della laurea magistrale in Ingegneria Matematica. Come tale, esso è un insegnamento di sintesi di contenuti diversi, che spaziano dall’analisi matematica all’algebra lineare, dall’analisi numerica alla teoria delle probabilità, e si articola sia su concetti teorici che su applicazioni a problemi concreti. La ricerca operativa, come suggerisce il nome stesso, mira a ricercare il modo ottimale di operare, ovvero trovare una soluzione che ottimizzi un criterio di valutazione, nel rispetto dei vincoli del problema. A titolo di esempio possiamo cercare il piano di trasporto che minimizza il consumo di carburante, o ricavare i prezzi di un prodotto che massimizzano il profitto dalle vendite. In contesti più complessi, occorre trovare una soluzione di compromesso tenendo conto di molteplici criteri in conflitto tra di loro. Tutto ciò richiede di costruire un modello matematico del problema reale, per poi applicare un algoritmo numerico di soluzione. Parte integrante del processo decisionale sono la raccolta dei dati, l’implementazione in software, l’analisi dei risultati e la validazione del modello. Inoltre, l’insegnamento fornisce concetti di ottimizzazione essenziali negli insegnamenti di statistica e machine learning della laurea magistrale.

• Capacità di razionalizzazione di un problema decisionale: formulazione di criteri di valutazione e vincoli. • Costruzione di modelli matematici di ottimizzazione. • Scelta di un algoritmo esatto o approssimato di soluzione. • Capacità di implementare algoritmi di decisione in MATLAB.

Sono prerequisiti essenziali gli insegnamenti di matematica del primo e secondo anno, con particolare riferimento ai contenuti seguenti: • Algebra lineare e geometria: spazi vettoriali, matrici, indipendenza lineare, forme quadratiche; programmazione in MATLAB, approssimazione di funzioni, algebra lineare numerica. • Analisi II: gradiente, matrice Hessiana, polinomio di Taylor, massimi e minimi liberi. Verranno anche usati alcuni concetti elementari di teoria delle probabilità introdotti nell’insegnamento parallelo di Metodi matematici per l’ingegneria.

Costruzione di modelli di ottimizzazione: • Classificazione dei modelli di ottimizzazione. • Esempi in logistica, finanza, statistica e machine learning, ingegneria, marketing. • Modelli con obiettivi multipli: concetto di soluzione efficiente, goal programming. Concetti geometrici in ottimizzazione: • Convessità di insiemi e funzioni. • Gradienti e subgradienti. • Coni e poliedri. Programmazione non-lineare: • Condizioni di ottimalità per problemi di ottimizzazione vincolata e loro interpretazione economica. • Teoria della dualità. • Metodi locali di soluzione: funzioni di penalità; metodi basati sul gradiente e sue varianti (trust region; quasi-Newton); metodi per punti interni; metodi derivative-free. Programmazione lineare: • Algoritmo del simplesso. • Dualità nella programmazione lineare. • Metodi per punti interni. • Analisi di sensitività e suoi limiti. Elementi di complessità computazionale: classi P e NP; problemi NP-completi e NP-hard. Ottimizzazione non convessa: • Programmazione mista intera; algoritmi branch and cut; formulazioni forti e deboli. • Cenni di ottimizzazione globale: metodi deterministici e stocastici; metaeuristiche. • Applicazioni al problema di routing di veicoli (VRP). Esercitazioni su MATLAB: Optimization toolbox e Global optimization toolbox.

L’organizzazione dell'insegnamento dipenderà in parte dalla possibilità o meno di erogare didattica in presenza. Sono previste lezioni frontali ed esercitazioni numeriche, anche supportate da MATLAB. L’implementazione di procedure di soluzione in MATLAB è oggetto di elaborati di gruppo ed è parte integrante dell’esame.

Verranno fornite slide e porzioni di dispense didattiche preparati dal docente. Il materiale si basa in gran parte sui riferimenti seguenti: • M.Z. Bazaraa, H.D. Sherali, G.M. Shetty. Nonlinear Programming: Theory and Algorithms, (3rd ed.). Wiley, 2006. • P. Brandimarte. Quantitative methods: An introduction for business management. Wiley, 2011. • D.-S. Chen, R.G. Batson, Y. Dang. Applied Integer Programming: Modeling and Solution. Wiley, 2011 • P. Toth D. Vigo. Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM, 2016 • P. Williams. Model Building in Mathematical Programming (5th ed.). Wiley, 2013.

Modalità di esame: Prova orale obbligatoria; Elaborato progettuale in gruppo;

CRITERI DI VALUTAZIONE Per l'orale: capacità di formulare modelli di ottimizzazione; comprensione profonda della teoria e degli algoritmi di soluzione; capacità di dimostrare semplici teoremi e di strutturare e analizzare algoritmi di soluzione; valutazione critica delle assunzioni semplificative necessarie. Per gli elaborati di gruppo (valutati dal docente sulla base dei report e del software): documentazione del software prodotto; completezza degli esperimenti computazionali; analisi del tradeoff tempo/prestazioni. PUNTEGGI Per la valutazione, 18 punti sono assegnati sulla base dell'orale, 12 sulla base degli elaborati di gruppo.

Modalità di esame: Prova scritta (in aula); Prova orale facoltativa; Elaborato progettuale in gruppo;

CRITERI DI VALUTAZIONE Per l'esame scritto: capacità di formulare modelli di ottimizzazione; capacità di strutturare e analizzare algoritmi di soluzione; valutazione critica delle assunzioni semplificative necessarie. Per l'esame orale (facoltativo): comprensione profonda della teoria e degli algoritmi di soluzione; capacità di dimostrare semplici teoremi. Per gli elaborati di gruppo (valutati dal docente sulla base dei report e del software): documentazione del software prodotto; completezza degli esperimenti computazionali; analisi del tradeoff tempo/prestazioni. PUNTEGGI 16 punti sono assegnati sulla base dello scritto (90 minuti, closed book), 10 sulla base degli elaborati di gruppo. L'orale è opzionale e ha un range di valutazione da -2 a +4 (NB: non necessariamente positivo). L'orale è riservato a chi ha acquisito un punteggio di almeno 22 tra scritto e elaborati. Lo scritto in aula è sostituito da una prima parte di orale obbligatorio per gli eventuali esami a distanza.