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.
1. Modelli e decisioni.
Introduzione alla Ricerca Operativa. Scopi e metodologie della Ricerca
Operativa. I problemi decisionali. Classificazione dei problemi decisionali.
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.
2. Geometria della programmazione lineare.
Cenni di geometria convessa. Rappresentazione dei vincoli e della
funzione obiettivo. Soluzione grafica dei problemi di PL.
3. 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 anticiclo. Il simplesso a due fasi.
4. Teoria della dualità.
Duale di un problema di PL. Legami fra primale e duale. Dualità debole.
Dualità forte. Condizioni di scarto complementare.
5. Programmazione lineare intera.
Definizione di un problema di Programmazione Lineare Intera (PLI).
Interpretazione geometrica. Matrici unimodulari e totalmente unimodulari.
Algoritmo di Branch & Bound. Cenni sulla Programmazione Lineare
Mista. Il problema dello zaino.
6. 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.
7. Laboratorio.
Uso dell’EXCEL per la risoluzione dei problemi di ottimizzazione. Uso
dei seguenti software per la Ricerca Operativa: LINGO (Linear,
INteractive and General Optimizer) e CPLEX-OPL (Optimization
Programming Language).
A. Fuduli – Appunti di Ricerca Operativa – Youcanprint Editore, 2015.
A. Fuduli – Esercizi di Ricerca Operativa – Youcanprint Editore, 2015.
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.
F.S. Hillier, G.J. Lieberman - Introduction to Operations Research –
McGraw Hill, 2005.
L'esame prevede lo svolgimento di una prova scritta
caratterizzata da esercizi numerici, e di un test a risposta multipla di
carattere puramente teorico. Entrambe le prove, indipendenti l'una dall'altra,
rimangono valide fino al 31 dicembre dell'anno in cui sono state svolte.
La consegna dello svolgimento di una nuova prova annulla automaticamente
l'esito della precedente. Durante le prove non è possibile consultare alcun tipo di materiale didattico.
È possibile sostenere il test di teoria in qualsiasi appello,
indipendentemente dall'appello in cui è stata svolta la prova numerica.
Per poter sostenere le prove è obbligatorio prenotarsi su
ESSE3 per entrambe,
separatamente, almeno due giorni prima della prova stessa e presentarsi muniti di tesserino universitario.
A. Fuduli – Appunti di Ricerca Operativa – Youcanprint Editore, 2015.
A. Fuduli – Esercizi di Ricerca Operativa – Youcanprint Editore, 2015.
Storia della Ricerca Operativa.
Dodici tipiche "schiocchezze"
sulla Ricerca Operativa...da sfatare.
Moduli risolutore Excel: foglio dati,
foglio formule,
foglio risolutore.
LINGO.
OPL-CPLEX.