UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione

a.a. 2000-01

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 (8)

CENNI DI TEORIA DEI GRAFI (8)

Definizioni fondamentali. Circuiti. Tagli. Matrici d'incidenza.

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 (12)

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

DUALITÀ (8)

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

MODULO II - prima parte

(F. Rinaldi)

PROGRAMMAZIONE LINEARE (18)

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

RETI DI FLUSSO (18)

Definizioni fondamentali. Condizioni di ottimalità: curva Gamma. Rete residua. Algoritmi polinomiali per Cammino minimo (algoritmo di Dijkstra) e Massimo flusso. Metodo `out of kilter'. Algoritmi di riscalamento. Applicazione al problema dell'assegnamento pesato. Simplesso su reti di flusso.

PROGRAMMAZIONE DINAMICA DETERMINISTICA (12)

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.

MODULO II - seconda parte

(P. Serafini)

OTTIMIZZAZIONE COMBINATORIA (20)

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

PROGRAMMAZIONE LINEARE INTERA (12)

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

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)