UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione 1

a.a. 2003-04

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 (o programmazione matematica) è una disciplina che gioca un ruolo di primo piano nel processo di modellizzazione e risoluzione dei complessi problemi di decisione che emergono in ambito applicativo.

Il corso si propone di presentare una panoramica delle principali classi di problemi di ottimizzazione, quali la programmazione lineare, la programmazione lineare intera e l'ottimizzazione combinatoria, e delle rispettive metodologie risolutive. Nel modulo I verranno anche richiamate alcune nozioni di base di tre argomenti fondamentali per lo sviluppo del programma di ottimizzazione: la teoria della complessità computazionale, l'analisi convessa e la teoria dei grafi.

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)

INTRODUZIONE AI PROBLEMI DI OTTIMIZZAZIONE (4 ore)

Problemi reali, modelli e algoritmi risolutivi. Esempi di problemi di ottimizzazione continua e discreta: problemi di programmazione lineare, non lineare e lineare intera. Esempi di problemi di ottimizzazione combinatoria: Bin Packing, Knapsack, Assegnamento tridimensionale, Set Covering, Set Packing, Set Partitioning, Soddisfattibilità.

CENNI DI TEORIA DEI GRAFI (4)

Definizioni fondamentali. Matrici di incidenza. Tagli e cammini. Connessione e forte connessione. Alberi, cricche e insiemi stabili. Problemi di ottimizzazione su grafi.

CENNI DI COMPLESSITA` COMPUTAZIONALE (6)

Algoritmi e loro complessità. Problemi di decisione. Classi P e NP. Trasformazioni polinomiali ed NP-completezza. Esempi di problemi NP-completi.

CENNI DI ANALISI CONVESSA (10)

Definizioni fondamentali. Teorema di Caratheodory. Operazioni algebriche su insiemi. Proprietà topologiche. Teoremi di separazione. Poliedri. Funzioni convesse. Proprietà differenziali. Minimizzazione di funzioni convesse.

PROGRAMMAZIONE LINEARE (12)

Definizioni fondamentali ed esempi. Geometria della PL. Dualità. Condizioni di complementarità. Cenni sulla complessità della PL. Metodo del simplesso. Analisi di sensistività.

PROGRAMMAZIONE LINEARE INTERA (12)

Introduzione ed esempi. Matrici totalmente unimodulari. Metodo del branch and bound. Metodo del branch and cut. Diseguaglianze di Chvátal e tagli di Gomory.

Modalità d'esame

Sono previste una prova scritta ed una prova orale.

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