00884 - RICERCA OPERATIVA

Conoscenze e abilità da conseguire

Al termine del corso lo studente conoscerà i principali strumenti teorici e pratici per la formulazione e la risoluzione di modelli matematici per tre classi di problemi di ottimizzazione: problemi di Programmazione Lineare continua (LP), problemi di flusso su rete, e alcuni problemi combinatorici su grafi.

Contenuti

Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi di gestione ed allocazione delle risorse, con applicazioni in moltissimi campi (logistica, trasporti, telecomunicazioni, finanza, energia, sanità, etc).

Verrà prima sviluppato il concetto di formulazione LP per un problema di ottimizzazione, le sue proprietà e le tecniche per risolverlo. Poi saranno presentati problemi di flusso su rete e alcuni problemi combinatorici su grafi (con relative proprietà e algoritmi), mediante i quali è possibile astrarre e modellare problemi di ottimizzazione per l’allocazione delle risorse e la gestione dei processi.

• Introduzione ai problemi di ottimizzazione matematica e loro formulazione mediante LP
• Programmazione lineare
  • Elementi di ottimizzazione convessa
  • Geometria e algebra della programmazione lineare (LP): proprietà dei poliedri, basi e soluzioni base, metodo delle curve di livello
  • Teorema fondamentale della LP e teoria della dualità
  • Algoritmo del simplesso (primale e duale)
  • Analisi di sensitività
• Grafi e reti di flusso
  
  • Modelli matematici per problemi su grafi e reti
  • Condizioni di unimodularità
  • Alberi, cammini e tagli, visite di grafi e alberi
  • Problema dei cammini minimi
  • Problema del flusso massimo
  • Problema del flusso di costo minimo
  • Problema dell'albero di copertura di costo minimo
  • Problemi di matching e di assegnamento
• Cenni di Programmazione Lineare Intera

Testi/Bibliografia

• Jon Lee "A First Course in Linear Optimization"
• Fabio Schoen "Optimization Models"
• R.K. Ahuja, T.L. Magnanti, J. Orlin "Network flows. Theory, algorithms and applications"
• F.S. Hillier, G.J. Lieberman "Introduction to Operations Research"
• Matteo Fischetti "Lezioni di Ricerca Operativa"

Metodi didattici

Il corso consiste in lezioni frontali ed esercitazioni in aula.

Modalità di verifica e valutazione dell'apprendimento

Lo studente sarà valutato rispetto alla sua abilità nel modellare e formulare problemi di ottimizzazione in termini di LP, oppure mediante l’astrazione di problemi su grafi e reti di flusso. Sarà inoltre verificata la conoscenza delle proprietà teoriche e degli algoritmi per tali classi di problemi.

L'esame consiste in una prova scritta seguita da prova orale che devono essere sostenute entro la stessa sessione. Nel caso di valutazione "insufficiente" nello scritto, lo studente dovrà ripetere la prova scritta in un’altra sessione. Nel caso di valutazione almeno "sufficiente" lo studente procederà all'orale. La prova orale è volta alla verifica della conoscenza degli argomenti trattati a lezione. Il voto finale tiene conto dei risultati conseguiti in entrambe le prove.

Per sostenere l'esame (sia per la parte scritta che per quella orale) è obbligatorio iscriversi alla lista su AlmaEsami e, nel caso si sia impossibilitati a sostenere l'esame, è obbligatorio togliersi dalla suddetta.

Strumenti a supporto della didattica

Il materiale didattico (slides, note ed esercizi) sarà reso disponibile sulla piattaforma di e-learning dell'Università di Bologna (https://virtuale.unibo.it ).

Orario di ricevimento

Consulta il sito web di Laura Galli