UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione

a.a. 2001-02

docenti: Paolo Serafini e 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.

MODULO I

(P. Serafini)

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.

MODULO II - prima parte

(F. Rinaldi)

RETI DI FLUSSO (14)

Definizioni fondamentali. Simplesso su reti di flusso. Algoritmi polinomiali per Cammino minimo (algoritmo di Dijkstra) e Massimo flusso.

PROGRAMMAZIONE DINAMICA DETERMINISTICA (14)

Principio di ottimalità. Equazione di Bellman. Algoritmo di Bellman-Ford per reti generali. Algoritmo per reti acicliche e a livelli. Algoritmo di Floyd-Warshall. Problemi di `knapsack'. Problemi di ottimizzazione combinatoria.

OTTIMIZZAZIONE COMBINATORIA (20)

Problemi di matching. Matroidi e alberi di supporto. Combinatorica poliedrale.

MODULO II - seconda parte

(P. Serafini)

PROGRAMMAZIONE LINEARE INTERA (20)

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

METODI EURISTICI (12)

Ricerca locale. Metodi greedy. Disaggregazione.

Modalità d'esame

È prevista una prova orale per ognuno dei periodi didattici. Il voto del secondo modulo è dato dalla media dei voti della prima e della seconda parte.

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)