Insegnamento mutuato da: B000072 - FONDAMENTI DI RICERCA OPERATIVA Laurea Triennale (DM 270/04) in INGEGNERIA INFORMATICA
Lingua Insegnamento
Italiano
Contenuto del corso
Introduzione ai modelli di ottimizzazione e alla Programmazione Lineare (sia continua che a variabili intere). Teoria e principali algoritmi di risoluzione
per problemi di ottimizzazione lineare anche in presenza di variabili intere. Teoria e principali algoritmi per problemi di flusso ottimo su reti.
Essere in grado di formulare dei modelli di ottimizzazione per affrontare problemi pratici.
Essere in grado di risolvere algebricamente problemi di ottimizzazione lineare (anche intera o su rete) di piccole dimensioni.
Conoscere i principali risultati teorici ed i principali algoritmi per l’ottimizzazione lineare anche con variabili intere o su rete.
Prerequisiti
Algebra lineare: matrici, vettori, determinanti, sistemi lineari.
Metodi Didattici
Didattica frontale.
Modalità di verifica apprendimento
Esame scritto o orale. L'esame può essere sostituito da due prove intermedie scritte. Nella prova di esame si intende verificare:
- la conoscenza di semplici modelli di programmazione matematica e dei fondamenti teorici alla base degli algoritmi di PL, di PLI e degli algoritmi su grafi;
- la conoscenza degli algoritmi di PL, PLI e degli algoritmi su grafi, anche mediante esercizi numerici.
Programma del corso
1. Introduzione alla Programmazione Lineare (PL).
Introduzione all’approccio modellistico e formulazione di semplici modelli di Programmazione Lineare.
Forma standard di un problema di PL; soluzioni; basi; soluzioni di base ammissibili; interpretazione del concetto di base; teorema fondamentale della PL; geometria della PL.
Il metodo del simplesso: formulazione matriciale e interpretazione geometrica.
Teoria della dualità: introduzione; definizione del problema duale; teoremi di dualità; interpretazione di problemi duali; teorema di "complementary
slackness"; 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.
Rilassamento continuo e 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.