PROGRAMMAZIONE MATEMATICA (m)
1o MODULO
A. A. 1997-98
Prof. Alan A.Bertossi
Programma
Programmazione Lineare
- Introduzione: la dieta di Polly.
- Formulazioni Equivalenti.
- Come lavora il Metodo del Simplesso.
- Problemi nel Metodo del Simplesso: come evitarli.
- La Dualita`: motivazioni e teoria.
- Interpretazione Geometrica.
- Analisi di sensitivita` ed interpretazione economica.
- Applicazioni.
- Efficienza: quanto e` veloce il Metodo del Simplesso?
- Accenni storici.
Programmazione Combinatoria
Problemi Polinomiali
- Cammini Minimi e Potenziali.
- Problemi di Taglio e di Flusso.
- Accoppiamenti e Coperture.
- Relazioni tra la Progammazione Combinatoria a la Programmazione Lineare.
- Nozione di unimodularita` e suo ruolo.
Problemi NP-ardui
- Richiami alla Teoria della Complessita`.
- Algoritmi Euristici.
- La Programmazione Intera.
- Tagli di Gomory.
- Algoritmi di Enumerazione Implicita:
schemi di "branch and bound" e di "branch and cut".
Testo adottato
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, New Jersey (1982),
Capitoli: 1-6, 9-10, 13-14.
Testi di Consultazione
V. Chva'tal, Linear Programming, Freeman, New York (1983).
F. Maffioli, Elementi di Programmazione Matematica, Masson, Milano (1990).
Modalita` e svolgimento dell'Esame
L'esame consta di una prova scritta e di una prova orale.