UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione

a.a. 1998-99

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)

CENNI DI TEORIA DEI GRAFI (6)

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

CENNI DI COMPLESSITÀ COMPUTAZIONALE (8)

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. Subgradienti.

DUALITÀ (14)

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

Metodi branch-and-bound. Limitazioni inferiori. Esempi.

MODULO II

(F. Rinaldi)

OTTIMIZZAZIONE COMBINATORIA (20)

Tecniche di "cutting planes". Algoritmi branch-and-cut. Matroidi e alberi di supporto. Problemi di matching. Combinatorica poliedrale.

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.

ALGORITMI APPROSSIMATI (6)

Definizioni. Schemi di approssimazione polinomiali e completamente polinomiali. Algoritmi per Delta-TSP, Knapsack' e `Bin-packing'.

Modalità d'esame

L'esame può consistere a scelta o in una prova orale sul contenuto del modulo oppure (versione raccomandata) nello svolgimento (a casa) di un certo numero di esercizi (in questo caso la prova orale non è richiesta).

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)