UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione

a.a. 1999-2000

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

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

CENNI DI COMPLESSITÀ COMPUTAZIONALE (11)

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

CENNI DI ANALISI CONVESSA (14)

Definizioni fondamentali. Teorema di separazione. Piani di supporto. Facce. Poliedri. Funzioni convesse. Subgradienti. Minimizzazione di funzioni convesse

DUALITÀ (8)

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

PROGRAMMAZIONE LINEARE (14)

Proprietà geometriche. Proprietà algebriche. Complementarità. Complessità. Metodo del simplesso. Varianti del metodo del simplesso. Generazione di colonne.

MODULO II

(F. Rinaldi)

PROGRAMMAZIONE LINEARE INTERA (16)

Tecniche di enumerazione implicita.

OTTIMIZZAZIONE COMBINATORIA (18)

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

RETI DI FLUSSO (20)

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.

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)