Alla fine del corso, lo studente conoscerà: -concetti fondamentali legati al mondo della Ricerca Operativa, dell'ottimizzazione e della complessità computazionale [*] -principali tecniche di modellazione di problemi di Programmazione Lineare e Programmazione Lineare Intera [*] -principali algoritmi di risoluzione per problemi di Programmazione Lineare e Programmazione Lineare Intera -concetti fondamentali della teoria dei grafi e dei problemi su grafo o rete -l'utilizzo basico di prodotti software dedicati alla risoluzione di modelli di ottimizzazione [*]
A seguito del superamento dell'esame, lo studente sarà in grado di: -sviluppare, risolvere al calcolatore, e analizzare modelli di PL o PLI per problemi di ottimizzazione descritti in linguaggio naturale [*] -risolvere problemi PL e PLI di piccole dimensioni implementando esplicitamente gli algoritmi visti a lezione -risolvere problemi di ottimizzazione su grafi di piccole dimensioni implementando esplicitamente gli algoritmi visti a lezione
___________________________________________________________________________________________________________ [*] valido anche per l'insegnamento mutuato "Laboratorio di tecniche di ottimizzazione"
Prerequisiti
Conoscenze base di: -algebra lineare, spazi vettoriali, sistemi di equazioni lineari -geometria lineare convessa -analisi matematica.
Si ricorda che l'insegnamento di "Algebra e geometria" costituisce una propedeuticità formale. [*]
___________________________________________________________________________________________________________ [*] non valido per l'insegnamento mutuato "Laboratorio di tecniche di ottimizzazione"
Metodi didattici
Lezioni frontali di teoria, affiancate da esempi e esercitazioni dedicate.
Una parte delle esercitazioni è riservata all'utilizzo di software dedicato alla risoluzione di modelli PL/PLI.
Verifica Apprendimento
[RICERCA OPERATIVA - GESLT, MECMLT] Prova finale scritta (obbligatoria) e in una prova orale (facoltativa): -la prova scritta (obbligatoria) comprende esercizi di formulazione di modelli PL/PLI, esercizi di applicazione e analisi di algoritmi studiati nel corso, e domande aperte relative all'intero programma del corso -la prova orale, facoltativa e dedicata solamente a chi eccelle nella prova scritta, verterà su tutti gli argomenti del corso
[LABORATORIO DI TECNICHE DI OTTIMIZZAZIONE - MECMLM] Prova finale scritta e al pc: -la prova scritta consiste in un esercizio di formulazione di modelli PL/PLI -la prova al pc consiste nell'implementazione in Matlab del modello formulato
Testi
Testi in italiano: -Silvano Martello: Ricerca Operativa. Esculapio, Bologna 2021 (III ed.). -Frederick S. Hillier, Gerald J. Lieberman: Ricerca Operativa - Fondamenti (9/ed a cura di D. Ambrosino, R. De Leone, A. Sciomachen). McGraw-Hill 2010. -Roberto Tadei, Federico Della Croce: Elementi di Ricerca Operativa. Esculapio, Bologna 2010.
Testi in inglese: -Frederick S. Hillier, Gerald J. Lieberman: Introduction to Operations Research. McGraw-Hill.
Contenuti
-Introduzione alla Ricerca Operativa e fondamenti di ottimizzazione [*] -Problemi di Programmazione Lineare (PL) e tecniche di modellazione [*] -Problemi di Programmazione Lineare Intera (PLI) e tecniche di modellazione [*] -Fondamenti di complessità computazionale -Teoria della PL: geometria della PL, teoremi fondamentali, algoritmo del simplesso, dualità, analisi di sensitività -Teoria della PLI: geometria della PLI, rilassamento continuo, algoritmi risolutivi per PLI (branch and bound, cutting planes) -Problemi, modelli e algoritmi di ottimizzazione su grafo (albero a costo minimo, cammino minimo, project scheduling, massimo flusso/minimo taglio) -Analisi di problemi PL/PLI all'interno di applicazioni in ambito ingegneristico ed economico
___________________________________________________________________________________________________________ [*] compreso nel programma mutuato per l'insegnamento "Laboratorio di tecniche di ottimizzazione"
Lingua Insegnamento
Italiano
Altre informazioni
Gli studenti avranno a disposizione slide relative sia alle lezioni di teoria sia alle esercitazioni svolte in aula. Inoltre saranno disponibili temi d’esame degli anni accademici precedenti (con le relative soluzioni) e esercizi di preparazione all'esame finale.
Tutto il materiale didattico per lo studio individuale sarà disponibile sul Moodle (comunità didattica) del corso.
