Ricerca Operativa

Numero di crediti ECTS: 10 (96 ore frontali)

SSD di riferimento: MAT/09

Docente: A. Fuduli

Prerequisiti

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

• 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 – McGraw 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.