Teoria e metodi di ottimizzazione lineare

Prefazione1Programmazione lineare: esempi1.1.Il problema della dieta1.2.Il problema di miscelazione ottimale1.3.Il problema dei trasporti1.4.Problemi di flusso su reti 1.4.1. Flussi su reti – 1.4.2. Il problema del cammino di costo minimo – 1.4.3. Problemi di flusso di costo minimo2Fondamenti di programmazione lineare2.1.Forma di un problema di programmazione lineare 2.1.1. Vincoli di diseguaglianza – 2.1.2. Variabili libere 2.2.Soluzioni, basi, soluzioni ammissibili2.3.Interpretazione del concetto di base 2.3.1. Basi e soluzioni di base in problemi di flusso2.4.Il teorema fondamentale della programmazione lineareEsercizi2.5.Una geometria per la programmazione lineareEsercizi 3Il metodo del simplesso3.1.Formulazione matriciale 3.1.1. Ottimalità di una soluzione ammissibile – 3.1.2. Scelta di una nuova soluzione ammissibile di base – 3.1.3. Ulteriori considerazioni sulla condizione di ottimalità – 3.1.4. Inizializzazione del metodo del simplesso Esercizi3.2.Un tableau per il simplesso3.3.Un tableau per il metodo due fasiEsercizi4Teoria della dualità4.1.Introduzione4.2.Definizione di problema duale4.3.Teoremi di dualità4.4.Interpretazione del problema duale 4.4.1. Duale del problema della dieta – 4.4.2. Duale del problema del cammino di costo minimo4.5.Complemenatry slackness 4.5.1. Interpretazione delle condizioni di complementary slackness 4.6.Informazione duale nel tableau4.7.Dualità per problemi non lineari4.8.Il metodo del simplesso dualeEsercizi5Analisi di sensitività5.1.Introduzione5.2.Sensitività sul termine noto5.3.Sensitività sul vettore dei costi 5.3.1. Variazione del costo di una variabile non di base – 5.3.2. Variazione del costo di una variabile di base5.4.Aggiunta di una nuova variabile5.5.Sensitività sulla matrice dei coefficienti 5.5.1. Modifica di una colonna non di base – 5.5.2. Modifica di una colonna di base5.6.Aggiunta di un nuovo vincoloEsercizi6Aspetti computazionali del metodo del simplesso6.1.Il metodo del simplesso modificato 6.1.1. Forma prodotto dell'inversa – 6.1.2. Decomposizione LU Esercizi 7Il metodo primale-duale7.1.Descrizione del metodo 7.1.1. Inizializzazione del metodo primale-duale Esercizi8Il problema del cammino di costo minimo8.1.Il metodo primale-duale8.2.L'algoritmo di DijkstraEsercizi9Il problema del massimo flusso9.1.Il metodo primale-duale9.2.L'algoritmo di Ford-Fulkerson 9.2.1. Il teorema Max-flow min-cut. Esercizi.Appendice A. Cenni di teoria dei grafi.Appendice B. Il problema della dieta.Appendice C. Un problema di miscelazione.Appendice D. Un problema di trasporto.Riferimenti bibliografici.Soluzione degli esercizi.