#acl SUAGroup:read,write,admin,delete,revert All:read

== Ricerca Operativa ==

'''Numero di crediti ECTS''': 10 (96 ore frontali)

'''SSD di riferimento''': MAT/09

'''Docente''': A. Fuduli


'''Prerequisiti''' 
<<BR>>

[[MatematicaDiscretaSUA|Matematica discreta]].

'''Obiettivi'''

Il corso si pone l’obiettivo di introdurre la Ricerca Operativa come disciplina di supporto alle decisioni. In particolare ci si soffermerà sulla modellistica dei problemi di ottimizzazione e sulle tecniche di risoluzione basate sulla Programmazione Lineare e sulla Programmazione Lineare Intera. Lo studente acquisirà anche competenze sui principali problemi di ottimizzazione su rete e sull’uso di software per l’ottimizzazione. 


'''Programma'''

 * Modelli e decisioni.
  * Introduzione alla Ricerca Operativa. Scopi e metodologie della Ricerca Operativa. I problemi decisionali. Classificazione dei problemi decisionali. Un esempio di problema decisionale con più decisori: il dilemma dei prigionieri. I problemi di ottimizzazione. Formulazione matematica dei problemi di ottimizzazione: funzione obiettivo e vincoli. Introduzione alla Programmazione Lineare (PL). Esempi di modelli di Programmazione Lineare.

 * Geometria della programmazione lineare.
  * Cenni di geometria convessa. Rappresentazione dei vincoli e della funzione obiettivo. Soluzione grafica dei problemi di PL.

 * Il metodo del simplesso.
  * Forma standard di un problema di PL. Riduzione alla forma standard. Definizione di soluzione di base. Interpretazione geometrica delle soluzioni di base. Forma canonica e riduzione alla forma canonica. Il teorema fondamentale della programmazione lineare. L’algoritmo del simplesso. Degenerazione e regole anticiclaggio. Il simplesso a due fasi.

 * Teoria della dualità. 
  *Duale di un problema di PL. Legami fra primale e duale. Dualità debole. Dualità forte. Condizioni di scarto complementare. 

 * Programmazione lineare intera.
  * Definizione di un problema di Programmazione Lineare Intera (PLI). Interpretazione geometrica. Matrici unimodulari e totalmente unimodulari. Algortitmo di Branch & Bound. Cenni sulla Programmazione Lineare Mista. Il problema dello zaino.

 * Problemi di ottimizzazione su rete.
  * Richiami di teoria dei grafi. Matrici di adiacenza e di incidenza. Formulazione del problema di flusso a costo minimo. Alberi ricoprenti e soluzioni di base. Il simplesso su rete. Formulazione del problema del massimo flusso. Il teorema del massimo flusso e minimo taglio. L’algoritmo di Ford & Fulkerson per il problema del massimo flusso. Il problema del cammino di costo minimo: formulazione e algoritmo di Dijkstra. Formulazione del problema dei trasporti e del problema dell’assegnamento. Risoluzione del problema dei trasporti e  del  problema dell’assegnamento. 

 * Laboratorio.
  * Uso dell’EXCEL per la risoluzione dei problemi di ottimizzazione. Uso dei principali software per la Ricerca Operativa: LINGO (Linear, INteractive and General Optimizer) e CPLEX-OPL (Optimization Programming Language). Cenni di AMPL (A Mathematical Programming Language). Uso di Matlab nella Programmazione Lineare.



'''Bibliografia'''
<<BR>>

 * F. Shoen - Teoria e metodi di ottimizzazione lineare: il metodo del simplesso - La Nuova Italia  Scientifica, 1991.
 * M. Fischetti - Lezioni di Ricerca Operativa – Edizioni Libreria Progetto Padova, 1995.
 * B. Taylor - Introduction to Management Science  - Prentice Hall, 1995.
 * F.S. Hillier, G.J. Lieberman - Introduction to Operations Research – Mc``Graw Hill, 2005.
 * M.S. Bazaraa, J.J. Jarvis, H.D. Sherali – Linear Programming and Network Flows – John Wiley, 2005.
 * D.P. Bertsekas - Network Optimization -  Athena Scientific, 1998.
 * Appunti forniti dal docente.


   
'''Tipologia di attività didattiche'''

 * Lezioni teoriche frontali.
 * Esercitazioni in aula.
 * Esercitazioni in laboratorio.


'''Metodi di valutazione'''

 * Prova scritta con esercizi numerici.
 * Test teorico a risposta multipla.