UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione 1

a.a. 2002-03

docente: Franca Rinaldi

Finalità: "La Ricerca Operativa ... ha lo scopo di fornire basi razionali al processo decisionale cercando di comprendere e strutturare situazioni complesse ed utilizzare questa comprensione per prevedere il comportamento dei sistemi e migliorare le loro prestazioni. Gran parte di questo lavoro utilizza tecniche analitiche e numeriche per sviluppare e manipolare modelli matematici e informatici per sistemi organizzativi composti da persone, macchine e procedure..."(INFORMS, What is OR/MS?)

L'ottimizzazione è una delle più importanti discipline teoriche che forniscono gli strumenti analitici alla Ricerca Operativa. Nel corso vengono svolti gli argomenti principali dell'ottimizzazione con particolare enfasi sugli aspetti matematici ed algoritmici.

INTRODUZIONE AI PROBLEMI DI OTTIMIZZAZIONE (4 ore)

CENNI DI COMPLESSITÀ COMPUTAZIONALE (12)

Complessità di un algoritmo. Complessità di un problema. Classe P. Classe NP. Trasformazioni. Problemi NP-completi.

CENNI DI ANALISI CONVESSA (6)

Definizioni fondamentali. Teorema di separazione. Piani di supporto. Funzioni convesse.

DUALITÀ (8)

Problema duale. Condizioni di ottimalità. Esempi. Dualità e convessità. Proprietà differenziali della dualità. Dualità e sensibilità.

PROGRAMMAZIONE LINEARE (18)

Proprietà geometriche. Proprietà algebriche. Complementarità. Metodo del simplesso. Varianti del metodo del simplesso. Metodi ai punti interni.

PROGRAMMAZIONE LINEARE INTERA (20)

Algoritmi poliedrali. Metodi branch-and-bound. Metodi branch-and-cut

Modalità d'esame

È prevista una prova orale.

Libro di testo: Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000.

Per ulteriori informazioni sulla ricerca operativa e sull'ottimizzazione si consulti il sito dell'INFORMS (Institute for Operations Research and Management Science) oppure quello del CIRO (Centro Interuniversitario in Ricerca Operativa)