Section outline
-
Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali di gestione ed allocazione delle risorse, con applicaizioni in moltissimi campi della scienza e dell'ingegneria ed attività economiche (logistica, trasporti, telecomunicazioni, finanza, energia, salute, ...). Verrà innanzi tutto introdotto il concetto di modellazione matematica per due classi particolarmente rilevanti di problemi di ottimizzazione, la Programmazione Lineare e la Programmazione Lineare Intera, mostrando come sia possibile attraverso di esse costruire modelli di moltissime situazioni reali (o realistiche, o anche completamente immaginarie). Verranno poi illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.
PROGRAMMA DEL CORSO
-
-
Introduzione (4 ore)
- Il processo decisionale
-
Problemi decisionali e problemi di ottimizzazione
-
Modelli e loro formulazione (6 ore)
- Tecniche di formulazione in Programmazione Lineare Intera
- Cenni all'utilizzo pratico (linguaggi di modellazione)
-
Grafi e Reti di flusso (14 ore)
- Modello generale dei problemi di flusso
- Il problema dei cammini minimi
- l problema dell'albero di copertura di costo minimo
- Il problema del flusso massimo
- Il problema del flusso di costo minimo
- Problemi di accoppiamento (cenni)
-
Programmazione Lineare (16 ore)
- Geometria della programmazione lineare
- Algoritmo del simplesso primale
- Dualità e scarti complementari
- Algoritmo del simplesso duale
-
Programmazione Lineare Intera (8 ore)
- Ottimizzazione combinatoria e sua complessità
- Metodi enumerativi: l'algoritmo "Branch & Bound"
- Implementazioni ad-hoc per zaino, commesso viaggiatore, cammino minimo vincolato
- Tecniche poliedrali (tagli di Chvátal e Gomory) ed il "Branch & Cut"
-
(Le ore indicate includono le esercitazioni)
-