Il corso si pone l›obiettivo di approfondire ed ampliare alcune tecniche di ottimizzazione, già studiate nel corso di Ricerca Operativa, con particolare riferimento ai problemi di Scheduling, di Programmazione Lineare a più obiettivi e di Ottimizzazione su Reti. Verranno inoltre presentati e risolti alcuni problemi applicativi, classici della Ricerca Operativa.
1. 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”.
2. Programmazione lineare multiobiettivo.
Introduzione alla programmazione lineare multiobiettivo. Soluzioni efficienti e debolmente
efficienti. Il teorema fondamentale della programmazione multiobiettivo. Spazio dei risultati:
convessità e trasformati dei punti estremi. Risoluzione grafica di un problema di programmazione
lineare multiobiettivo. Il metodo Goal Programming. Il metodo STEM.
3. Cenni sul rilassamento lagrangiano.
Introduzione al concetto di rilassamento di un problema di ottimizzazione. I concetti di lower bound
e upper bound. Il rilassamento lagrangiano nella programmazione lineare intera. Il duale
lagrangiano. Il duale lagrangiano nella programmazione lineare. Relazioni fra il rilassamento
lagrangiano e il rilassamento continuo. La proprietà di interezza.
4. Problemi di set covering e set partitioning.
Formulazione del problema di set covering. Formulazione del problema di set partitioning.
Applicazioni dei problemi di set covering e set partitioning. Tecniche euristiche di risoluzione per il
problema di set covering: l’algoritmo di Chvatal e l’algoritmo di aggiustamento dei moltiplicatori.
Dominanza di righe e di colonne. Trasformazione di un problema di set partitioning in un problema
di set covering.
5. Problemi di vehicle routing.
Introduzione ai problemi di vehicle routing. Problemi di "node routing" e "arc routing". Il problema del
commesso viaggiatore asimmetrico. L’algoritmo di patching. Il problema del commesso viaggiatore
simmetrico. L’algorirtmo Nearest Neighbour. L’algoritmo dell’albero. L’algoritmo di Christofides.
Il problema del postino cinese diretto.
A. Fuduli – Appunti di Ricerca Operativa – Youcanprint Editore, 2015.
A. Fuduli – Esercizi di Ricerca Operativa – Youcanprint Editore, 2015.
M. Pinedo – Scheduling: theory, algorithms and systems – Second Edition - Prentice Hall,
Englewood Cliffs, New Jersay, 2002.
C. H. Papadimitriou, K. Steiglitz. Combinatorial optimization: algorithms and complexity.
Dover, 1998.
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. La prova orale è facoltativa.
La consegna dello svolgimento di una nuova prova scritta annulla automaticamente
l'esito della precedente. Durante la prova non è possibile consultare alcun tipo di materiale didattico.
Per poter sostenere la prova è obbligatorio prenotarsi su
ESSE3
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.