B027531 - FUNDAMENTALS OF OPERATIONAL RESEARCH

Italiano

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.

Fabio 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#customerReviews

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.

Algebra lineare: matrici, vettori, determinanti, sistemi lineari.

Didattica frontale.

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.

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.