Docente

Prof. Franca Rinaldi franca.rinaldi@uniud.it http://www.dimi.uniud.it/~rinaldi/scheda.html

Crediti

6 CFU

Finalità

Scopo principale del corso è quello di presentare due argomenti centrali dell'ottimizzazione matematica, la programmazione lineare e la programmazione lineare intera, e le rispettive metodologie risolutive. Lo studente viene anche introdotto alla definizione e all'utilizzo di modelli di PL e PLI per problemi teorici e applicativi. Vengono inoltre richiamate alcune nozioni di base di analisi convessa e di teoria dei grafi. 

Programma

Introduzione al corso: Ricerca operativa e ottimizzazione matematica. Descrizione del processo di modellazione e risoluzione di un problema reale.
Cenni di analisi convessa: Insiemi convessi, coni e insiemi affini. Teorema di Caratheodory. Teoremi di separazione. Descrizione interna ed esterna di insiemi convessi. Poliedri e loro proprietà.
Programmazione lineare: Definizioni fondamentali ed esempi. Forme canonica e standard. Geometria della PL. Teorema fondamentale della PL. Metodo del simplesso. Dualità. Analisi di sensitività. Metodo del simplesso duale.
Programmazione lineare intera: Definizioni fondamentali ed esempi. Geometria della PLI. Matrici totalmente unimodulari. Metodi di cutting plane. Diseguaglianze di Chvátal e tagli di Gomory. Metodi di branch and bound.
Cenni di teoria dei grafi: Definizioni fondamentali. Tagli e cammini. Connessione e forte connessione. Alberi, cricche, insiemi stabili, accoppiamenti e ricoprimenti. Matrici di adiacenza e incidenza. Problemi di ottimizzazione su grafi e loro modelli di PLI. 

Bibliografia

Dispense del docente
Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000. 

Modalità d'esame

L’esame consiste in una prova scritta e in una prova orale.