Fondamenti di Ricerca Operativa

B000072 - FONDAMENTI DI RICERCA OPERATIVA
Sito web dedicato al corso: http://e-l.unifi.it/course/view.php?id=1457
settore MAT/09. Anno II semestre I
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.

Docente: 
Anno Accademico: 
2012-2013
CFU: 
6
Programma: 

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

 

Libri di testo consigliati: 

Fabio Schoen, Fondamenti di Ricerca Operativa, 444pp, 2012, ISBN 978-1-105-49496-3, disponibile su  www.lulu.com
 
Il volume è anche disponibile in formato e-book
 

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 dell'apprendimento: 

Esame orale, comprendente due esercizi numerici. L'esame orale puo' essere sostenuto anche mediante prove scritte

Altre Informazioni (es: appelli):