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.
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'
Programma del corso
1. Programmazione Lineare
Schoen, Fondamenti di Ricerca Operativa, ISBN
978-1-105-49496-3, 2012, disponibile su www.lulu.com (http:
//www.lulu.com/spotlight/fabioschoen)
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