44015 - PROGRAMMAZIONE MATEMATICA

Scheda insegnamento

  • Docente Aristide Mingozzi

  • Crediti formativi 6

  • SSD MAT/09

  • Modalità di erogazione In presenza (Convenzionale)

  • Lingua di insegnamento Italiano

  • Orario delle lezioni dal 26/09/2017 al 22/12/2017

Anno Accademico 2017/2018

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.

Programma/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 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