Programma

• Programmazione Lineare

  Introduzione: la dieta di Polly. Formulazioni Equivalenti. Come lavora il Metodo del Simplesso. Problemi nel Metodo del Simplesso: come evitarli. La Dualità: motivazioni e teoria. Interpretazione Geometrica. Analisi di sensitività ed interpretazione economica. Applicazioni. Efficienza: quanto è 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 unimodularità e suo ruolo.
  • Problemi $NP$-ardui Richiami alla Teoria della Complessità. Algoritmi Euristici. La Programmazione Intera. Tagli di Gomory. Algoritmi di Enumerazione Implicita: schemi di ``branch and bound'' e di ``branch and cut''.