Elementi introduttivi. Generalita’ sui problemi di ottimizzazione. Richiami sugli insiemi convessi e sull’Algebra Lineare Numerica: fattorizzazione LU di una matrice, pivoting, fattorizzazione LDL^T per matrici simmetriche e definite positive. 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 con limite superiore. Forma matriciale del metodo del simplesso. Il metodo del simplesso rivisto, forma prodotta e reinversione. Metodo del simplesso e fattorizzazione LU. Il metodo di decomposizione di Dantzig-Wolfe. Problema duale di un problema PL e teorema della dualita’. Moltiplicatori del simplesso ed utilizzo della teoria della dualita’ in teoria dei giochi. Stabilita’ della soluzione di un problema PL. Proprieta’ di scarto complementare. Il metodo del simplesso duale. Il metodo primale-duale del simplesso.

Problemi di ottimizzazione su grafo. 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. Problemi di flusso su rete: il problema del flusso del minimo costo. Il metodo del simplesso rivisto per problemi di flusso di minimo costo. Procedura ad albero. Problema del massimo flusso. Il metodo primale-duale per il problema del trasporto: algoritmo e forma matriciale. Il metodo ungherese per il problema delle assegnazioni.

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