Insegnamento mutuato da: B000072 - FONDAMENTI DI RICERCA OPERATIVA Laurea Triennale (DM 270/04) in INGEGNERIA INFORMATICA
Lingua Insegnamento
italiano
Contenuto del corso
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,
https://www.amazon.it/Fondamenti-Ricerca-Operativa-Fabio-Schoen/dp/1542342023/ref=sr_1_5?s=books&ie=UTF8&qid=1506496891&sr=1-5&keywords=fabio+schoen
Obiettivi Formativi
1) Capacità di formulare semplici modelli di programmazione lineare (PL), di programmazione lineare intera (PLI), e di modelli per problemi su grafi.
2) Conoscenza di fondamenti teorici di PL, di PLI e di modelli di grafi.
3) Conoscenza di algoritmi per la soluzione di problemi di PL, di PLI, di problemi su grafi.
Prerequisiti
Algebra lineare: matrici, vettori, determinanti, sistemi lineari
Metodi Didattici
Didattica frontale
Modalità di verifica apprendimento
L'esame consta di una prova scritta (o alternativamente di una prova orale) nella quale si verifica:
- mediante domande teoriche la conoscenza di semplici modelli di programmazione matematica e di fondamenti teorici alla base degli algoritmi di PL, di PLI e degli algoritmi su grafi;
- mediante esercizi numerici la conoscenza degli algoritmi di PL, PLI e degli algoritmi su grafi.
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