Anno accademico 2023-2024

OTTIMIZZAZIONE

Docenti

Franca Rinaldi
Anno di corso
3
Totale crediti
6
Periodo didattico
Primo Periodo
Tipologia
Caratterizzante
Prerequisiti. Conoscenza dei concetti e dei risultati fondamentali dell’algebra lineare e della geometria affine.
Metodi didattici. Lezioni teoriche ed esercitazioni.
Modalità di verifica. L’esame prevede una prova scritta ed una prova orale. La prova scritta consiste in alcuni esercizi atti a verificare la capacità dello studente di applicare le conoscenze teoriche e metodologiche acquisite alla risoluzione di istanze numeriche, alla formulazione di modelli e alla dimostrazione di facili enunciati. La prova orale consiste in alcune domande di carattere generale sugli argomenti in programma ed ha lo scopo di verificare la conoscenza e la capacità di presentazione dei contenuti del corso.

Il voto verrà stabilito in base ai criteri approvati dal Consiglio di Corso di Studio consultabili al link

https://www.uniud.it/it/didattica/corsi/area-scientifica/scienze-matematiche-informatiche-multimediali-fisiche/laurea/matematica/studiare/criteri-guida-di-assegnazione-del-voto-degli-esami-di-profitto/view

Altre informazioni. A completamento dei contenuti del corso viene anche svolto (ad anni alterni) un Laboratorio di programmazione lineare e programmazione lineare intera in cui lo studente impara ad utilizzare il linguaggio di modellizzazione AMPL ed alcuni risolutori di PL/PLI per la risoluzione di problemi sia applicativi che teorici.
Obiettivi formativi
Al termine del corso lo studente dovrà:

Conoscenza e comprensione: conoscere le proprietà fondamentali degli insiemi convessi; conoscere la teoria, i principali metodi risolutivi, gli aspetti computazionali ed alcune applicazioni della programmazione lineare; conoscere la teoria ed i principali metodi risolutivi della programmazione lineare intera e i modelli di PLI per alcuni classici problemi di ottimizzazione combinatoria; conoscere i principali concetti, risultati e problemi della teoria dei grafi e la loro complessità.

Capacità di applicare conoscenza e comprensione: essere in grado di formulare modelli di programmazione lineare e lineare intera per semplici problemi combinatori o applicativi; saper applicare gli algoritmi studiati alla risoluzione di semplici istanze di PL e/o PLI; saper applicare argomentazioni di dualità per la risoluzione di coppie di problemi primale/duale; sapere applicare l’analisi di sensitività.

Autonomia di giudizio: sapere individuare un modello appropriato (di PL o PLI o teoria dei grafi) per semplici problemi combinatori e applicativi.

Abilità comunicative: sapere presentare gli argomenti svolti nel corso con rigore formale e completezza.

Capacità di apprendimento: essere in grado di approfondire autonomamente gli argomenti del corso in relazione ad aspetti formali non svolti in classe.

Contenuti
Il corso presenta tre argomenti fondamentali dell’ottimizzazione matematica: la programmazione lineare (PL), la programmazione lineare intera (PLI) e la teoria dei grafi. Per ciascun argomento vengono sviluppati i fondamenti teorici e le metodologie risolutive e ne vengono discussi gli aspetti computazionali. Viene inoltre illustrato il processo di modellizzazione di un problema come problema di PL e PLI introducendo numerosi esempi sia teorici che applicativi. Nelle prime lezioni vengono anche introdotti elementi di analisi convessa e di complessità computazionale.
Testi di riferimento
– Paolo Serafini, “Ottimizzazione”, Zanichelli, Bologna 2000

– Dispense fornite dal docente