Introduzione alla programmazione matematica, in particolare all'ottimizzazione lineare (sia continua che a variabili intere). Teoria ed principali algoritmi di risoluzione per problemi di ottimizzazione lineare, per problemi di flusso ottimo su reti, per problemi lineari con variabili discrete.
Fabio Schoen, Fondamenti di Ricerca Operativa, ISBN 978-1-105-49496-3, 2012, disponibile su www.lulu.com (http://www.lulu.com/spotlight/fabioschoen)
Obiettivi Formativi
Conoscere la teoria ed i metodi di ottimizzazione lineare, di ottimizzazione lineare intera, di ottimizzazione lineare su grafi; saper risolvere piccoli problemi di programazione lineare, sapere utilizzare la dualità, saper risolvere problemi di cammino di costo minimo e di flusso massimo su reti.
Prerequisiti
Algebra lineare: matrici, vettori, determinanti, sistemi lineari
Metodi Didattici
Didattica frontale
Modalità di verifica apprendimento
Esame orale, comprendente due esercizi numerici. L'esame orale puo' essere sostenuto anche mediante prove scritte
Programma del corso
1. Programmazione Lineare
esempi: il problema della dieta, problema di miscelazione ottimale, problema del trasporto, introduzione alla teoria dei grafi, problemi di flusso su reti.
Introduzione alla Programmazione Lineare (PL). Forma di un problema di PL; soluzioni, basi, soluzioni ammissibili; interpretazione del concetto di base; teorema fondamentale della PL; geometria della PL.
Il metodo del simplesso; formulazione matriciale
Teoria della dualità Introduzione; definizione del problema duale; teoremi di dualità; interpretazione di problemi duali; teorema di "complementary slackness"; dualità e teoria dei giochi (cenni introduttivi); il metodo del simplesso duale.
Analisi di sensitività. Introduzione; sensitività sul termine noto; sensitività sul vettore dei costi; aggiunta di una nuova variabile; aggiunta di un nuovo vincolo
2. Programmazione Lineare Intera
Esempi di problemi e modelli di programmazione intera.
Connessioni tra PL e programmazione lineare intera.
Algoritmi generali per la programmazione intera: il metodo di Gomory, il metodo Branch & Bound.
3. Reti di flusso
Basi e soluzioni di base nei problemi di flusso;
Il problema del cammino di costo minimo: algoritmo di Dijkstra
Il problema del flusso massimo: algoritmo di Ford & FUlkerson. Teorema massimo flusso/sezione di capacita' minima
Il metodo del simplesso su reti