- Docente: Aristide Mingozzi
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea Magistrale in Matematica (cod. 8208)
Conoscenze e abilità da conseguire
Al termine del corso lo studente conosce i principali metodi teorici ed algoritmici della programmazione matematica; è in grado di sviluppare per un problema reale modelli matematici alternativi; sa come realizzare un algoritmo di programmazione matematica per risolvere un problema reale.
Contenuti
- Modelli e formulazioni. Vengono presentati diversi problemi reali e le loro formulazioni matematiche sia con variabili continue che con variabili intere Viene introdotta la distinzione fra "buone" e "cattive" formulazioni.
- Programmazione Lineare e teoria della Dualità. I metodi per risolvere un problema di programmazione lineare. Il metodo del simplesso primale, la teoria della dualità, il metodo del simplesso duale. Le relazioni degli scarti complementari
- Problemi interi "facili". Problemi di programmazione intera che possono essere risolti mediante i metodi di programmazione lineare. Cammini minimi in un grafo. Flusso massimo in un grafo. Flusso massimo a costo minimo e i casi speciali del problema dell'assegnamento e del problema dei trasporti.
- Complessità degli algoritmi. Introduzione informale alla differenza in difficoltà fra i problemi "facili" e difficili.
- Problemi interi "difficili". Metodi di soluzione di tipo "cutting plane" e "branch and bound". Discussione dei vari metodi di rilassamento (continuo, lagrangiano etc) per il calcolo del lower bound. Applicazioni.
- Programmazione dinamica. Elementi base di programmazione dinamica. Applicazioni al problema del Knapsack, il taglio bi-dimensionale e il TSP.
- Metodi di decomposizione. Decomposizione Lagrangiana e decomposizione di Dantzig Wolfe.
- Metodi column-generation. Esempi applicativi.
- Algoritmi euristici. Metodi per ottenere "buone" soluzioni ammissibili di un problema intero. Applicazioni a problemi reali
Testi/Bibliografia
- Bazaraa M.S., John J. Jarvis and Hanif D. Sherali. Linear programming and network flows. Wiley, 2010.
- Laurence A. Wolsey, Integer Programming , Wiley, 1998.
- Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity , 1998.
Modalità di verifica e valutazione dell'apprendimento
Propedeuticità. Fondamenti di Informatica e programmazione e algebra lineare.
Prova scritta.
Strumenti a supporto della didattica
Dispense a cura del docente: Collezione AMS Campus http://campus.cib.unibo.it/.
Orario di ricevimento
Consulta il sito web di Aristide Mingozzi