PROGRAMMA DI  RICERCA OPERATIVA

Docente : Giandomenico Mastroeni  

Anno Accademico  2007/08
Laurea in Matematica ,  Anno di Corso: Secondo , Semestre: Secondo 
Numero crediti: 7 

CONTENUTI DEL CORSO

 1. INTRODUZIONE AI PROBLEMI DI RICERCA OPERATIVA. Formulazioni matematiche di alcune situazioni reali. Un problema di programmazione dei trasporti. Problemi di produzione. Problemi di miscelazione ottimale. Problemi di flusso su reti. Il problema del cammino minimo. Problemi di flusso di costo minimo. 

 2. PROGRAMMAZIONE LINEARE. Elementi di analisi convessa: insiemi convessi, involucro convesso, combinazioni convesse, coni, funzioni convesse, richiami sui teoremi di separazione e teorema di Weierstrass. Geometria della programmazione lineare (PL). Proprieta' dei poliedri. Risoluzione geometrica della PL. Metodo delle curve di livello. L'insieme dei punti di minimo di un programma di PL. 
Soluzioni di base degeneri, non degeneri e complementari.  Teorema fondamentale della PL. Algoritmo del simplesso. Metodo di Gauss-Jordan.  Il problema ausiliario. Introduzione alla teoria della dualita'.  
Dualita' lineare.  Dualita' debole, dualita' forte. Teorema degli scarti complementari. Teoremi di alternativa. Lemma di Farkas e suoi corollari. L'insieme delle soluzioni ottime del problema duale. Esistenza del minimo di un problema di PL. Un' interpretazione economica del problema duale. L'algoritmo duale del simplesso.

 3. PROGRAMMAZIONE LINEARE SU GRAFI. Alcuni elementi di teoria dei grafi: grado, cammini, cicli, alberi di copertura, matrici associate ad un grafo.
 Il problema del cammino minimo. Algoritmo per la ricerca dell'albero dei cammini minimi di radice data. Il duale del problema del cammino minimo. Il problema  del flusso massimo su una rete ed il suo duale. Teorema max flow-min cut. Algoritmo di Ford-Fulkerson. Il problema del flusso di costo minimo: algoritmo del simplesso su reti. 

TESTI DI RIFERIMENTO:  F. Giannessi. Metodi Matematici della Programmazione. Problemi lineari e non lineari. Pitagora Editrice.
 M. Minoux: Mathematical Programming. Theory and Algorithms, Wiley. 
M. Pappalardo e M. Passacantando: Lezioni di Ricerca Operativa, ETS Editrice, Pisa.
Appunti integrativi delle lezioni a cura del docente.

OBBIETTIVI  FORMATIVI: Approfondimento della teoria della programmazione lineare con particolare riferimento alle applicazioni ai problemi di flusso su reti.
PREREQUISITI: Nozioni fondamentali di algebra lineare. Teoria degli estremi liberi per funzioni di piu’ variabili. 
METODI DIDATTICI: Lezioni frontali e svolgimento di esercizi in aula.
MODALITA’ DI VERIFICA DELL’APPRENDIMENTO: Verranno effettuati due compitini  durante il corso   e una prova orale al termine del corso.

.