Obiettivi formativi
Il corso si propone di introdurre lo studente ai principali algoritmi e
tecniche di programmazione intera e combinatoria, con particolare
riguardo alle loro applicazioni in ambito industriale e gestionale. In questo
corso lo studente imparerà a formulare e risolvere problemi di
programmazione intera e combinatoria. Il corso fornisce inoltre alcuni
strumenti per interpretare e analizzare le soluzioni.
Prerequisiti
Programmazione Lineare
Contenuti dell'insegnamento
L'obiettivo del corso è di introdurre i problemi di ottimizzazione che
ricadono nell'ambito della programmazione intera e della ottimizzazione
combinatoria, e di presentare alcuni metodi classici per la loro analisi e
soluzione. Gli argomenti trattati includono: Ottimizzazione su grafi e reti,
tecniche di esplorazione. Programmazione intera (PI): tecniche di
formulazione e qualità delle formulazioni. Criteri di interezza per le
soluzioni di programmi lineari: totale unimodularità. Qualità delle
soluzioni: rilassamenti e dualità; rilassamenti lagrangiani e dualità
lagrangiana. Metodi esatti di soluzione: metodi di enumerazione
implicata; piani di taglio; branch and bound; ricerca locale, etc., tempo
permettendo. Le applicazioni e i problemi discussi nel corso includono:
Problemi e modelli di localizzazione: localizzazione degli impianti e dei
nodi logistici. Logistica distributiva: problemi di trasporto; problemi di
distribuzione; il problema del commesso viaggiatore; instradamento di
veicoli in reti di trasporto; schedulazione di attività. Modelli di Input-
Output. Modelli di Produzione.
Programma esteso
1. Elementi di programmazione intera e ottimizzazione combinatoria.
Richiami di programmazione lineare. Introduzione alla teoria dei giochi.
Richiami di ottimizzazione su grafi e reti. Tecniche di esplorazione di un
grafo. Criteri di interezza per le soluzioni di programmi lineari: totale
unimodularità. Programmazione lineare intera: tecniche di formulazione
per problemi a numeri interi e di ottimizzazione combinatoria. Metodi
esatti di soluzione per problemi di programmazione intera e combinatoria:
metodi di enumerazione implicita; piani di taglio; metodo del branch and bound;
programmazione dinamica. Qualità delle soluzioni: rilassamenti e dualità;
rilassamenti lagrangiani e dualità lagrangiana. Cenni di programmazione non
lineare. Metodi euristici: tecniche "greedy", euristiche di ricerca locale, migliorative,
costruttive, in due fasi. 2. Applicazioni. Problemi e modelli di localizzazione:
localizzazione degli impianti e dei nodi logistici. Logistica distributiva: problemi
di trasporto; problemi di distribuzione; il problema del commesso viaggiatore;
instradamento di veicoli in reti di trasporto; schedulazione di attività. Modelli
di Input-Output. Modelli di Produzione.
Bibliografia
- L. A. Wolsey, Integer Programming, Wiley-Interscience, New York, 1998.
- F. Maffioli, Elementi di programmazione matematica, seconda edizione, Casa Editrice Ambrosiana, Milano, 2000.
- Ghiani G., Musmanno R., Modelli e metodi per l’organizzazione dei sistemi logistici, Pitagora Editrice, Bologna, 2000.
- F. S. Hillier, G. J. Lieberman, Introduzione alla ricerca operativa, Ottava edizione, McGraw-Hill, Milano, 2006.
Metodi didattici
Gli argomenti teorici del corso sono presentati tramite lezioni frontali e
corredati da esempi significativi, applicazioni, e numerosi esercizi.
Durante il corso vengono assegnati esercizi che vengono poi discussi e
commentati durante le ore di lezione.
Modalità verifica apprendimento
L'esame consta di una prova scritta, che prevede la soluzione di alcuni
esercizi, e di una prova orale sugli argomenti teorici e le applicazioni
discussi durante il corso.
Altre informazioni
- - -
Obiettivi agenda 2030 per lo sviluppo sostenibile
- - -
