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 Python ed 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 e Python, 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) e su Python.

La consegna degli elaborati Python è facoltativa ma va effettuata entro le date stabilite, e quindi prima della fine dell'insegnamento. Non sarà possibile sostituire i casi proposti con altri e consegnare elaborati alternativi in ritardo rispetto alle date di consegna stabilite. Il lavoro può essere svolto individualmente o da un gruppo di massimo tre studenti.

Sono previste lezioni frontali ed esercitazioni numeriche, anche supportate da MATLAB e/o Python. L’implementazione di procedure di soluzione in MATLAB e/o Python è oggetto di elaborati di gruppo (facoltativi) ed è parte integrante dell’esame.

Sarà disponibile il libro di testo del corso: • P. Brandimarte. Ottimizzazione per la ricerca operativa. CLUT, 2022 (in corso di pubblicazione). Ulteriori riferimenti utili sono: • 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.

Slides; Libro di testo;

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

Exam: Written test; Group project;

... CRITERI DI VALUTAZIONE Per la prova scritta (90 minuti, closed book): 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, 26 punti sono assegnati sulla base dello scritto, 4 sulla base degli elaborati di gruppo (facoltativi, svolti individualmente o in gruppi di massimo tre studenti).

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.