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, su alcuni problemi di scheduling 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. Il problema del postino cinese diretto.
7. Elementi di teoria dello scheduling.
Introduzione ai problemi di scheduling. Classificazione dei problemi di scheduling. Problemi di
scheduling su singola macchina. Problemi di scheduling su macchine parallele e identiche.
Macchine eterogenee: cenni sui problemi di “flow shop” e “job shop”.
8. 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.
M. Pinedo – Scheduling: theory, algorithms and systems – Second Edition - Prentice Hall,
Englewood Cliffs, New Jersay, 2002.
G. Ghiani, G. Laporte, R. Musmanno. Introduction to Logistics Systems Planning and
Control. Wiley, 2004.
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 all'ultimo appello precedente il primo appello relativo al corso erogato nel successivo
anno accademico.
La prova di esercizi, se ripetuta, annulla automaticamente
l'esito della precedente solo in caso di consegna. La ripetizione della
prova di teoria, invece, invalida automaticamente l'esito della precedente in quanto la consegna è
obbligatoria.
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.