|
Docente
|
VENTURA PAOLO
(programma)
1. Definizioni fondamentali di teoria dei grafi. Connessione, acicilicità , alberi, circuiti euleriani. Grafi bipartiti e problemi di colorazione.
2. L'uso delle condizioni di ottimalità per il problema dell'albero ricoprente e del cammino minimo. Il problema del massimo flusso e il problema del minimo taglio. Matching nei grafi bipartiti.
3. Richiami di calcolo combinatorio ed elementi di conteggio. Dimostrazioni per induzione e pigeon-hole principle.
4. Programmazione lineare. Metodo del simplesso. Dualità e condizioni di ottimalità. Analisi di sensitività.
5. Programmazione lineare intera. Branch and bound.
6. Esempi di formulazioni di problemi PL e PLI: problema della dieta, facility location, problemi di scheduling, set covering, set packing, vertex coloring.
7. Tutorial per AMPL (A Mathematical Programming Language).
 1. Linear Programming V. Chvatal, Freeman and Company.
2. Graphs, Network and Algorithms. D. Jungnickel; Springer.â•š3. Discrete Mathematics and its Applications. K.H. Rosen; Mc Graw-Hill.â•š4. Lecture Notes
|
