PROGRAMMA DEL CORSO DI RICERCA OPERATIVA I

Prof. Luigi Brugnano

Corso di Laurea in Matematica, a.a. 2002-03.

 

Elementi introduttivi. Generalita’ sui problemi di ottimizzazione. Richiami sugli insiemi convessi. Cenni sul linguaggio MATLAB.

Problemi di Programmazione Lineare. Forma standard di un problema di programmazione lineare. Il teorema fondamentale della programmazione lineare. Il metodo del simplesso standard. Trattamento di soluzioni basiche degeneri. Il metodo del simplesso a due fasi. Variabili limitate superiormente. Forma matriciale del metodo del simplesso. Il metodo del simplesso rivisto, forma prodotta e reinversione. Problema duale di un problema PL e teorema della dualita’. Moltiplicatori del simplesso e scarto complementare. Stabilita’ della soluzione di un problema PL. Il metodo del simplesso duale. Il metodo primale-duale del simplesso. Cenni sui metodi a punti interni.

Probleni di ottimizzazione su grafi. Il problema del trasporto bilanciato: l’algoritmo del Nord-Ovest per il calcolo di una soluzione basica accettabile, triangolarita’ delle basi, interezza delle soluzioni. L’algoritmo del trasporto: degenerazione e problema delle assegnazioni. Il problema del flusso di costo minimo. Procedura ad albero. Il problema del massimo flusso. Tagli di una rete.

 

Testo consigliato: D.G.Luenberger, Linear and nonlinear programming, Addison Wesley, 1984.