14511 - OTTIMIZZAZIONE

Anno Accademico 2018/2019

  • Docente: Ugo Dal Lago
  • Crediti formativi: 6
  • SSD: INF/01
  • Lingua di insegnamento: Italiano
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea in Informatica (cod. 8009)

    Valido anche per Laurea Magistrale in Physics (cod. 9245)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente apprende i fondamenti della programmazione lineare (PL), della programmazione lineare intera (PLI), e dell'ottimizzazione combinatoria; conosce l'algoritmo del simplesso per la PL e sa in quali casi un problema di PL ammette soluzioni intere. E' quindi in grado di modellare un problema incognito in termini di vincoli lineari (o lineari interi) e funzione obiettivo lineare, ovvero riconoscere che il problema non può essere così formulato. E' inoltre in grado di modellare problemi combinatori su grafi come problemi di cammini minimi, flussi massimi e abbinamenti, e può risolverli per mezzo dei principali algoritmi noti nella letteratura. Infine, sa distinguere quali problemi di ottimizzazione combinatoria sono inerentemente intrattabili.

Contenuti

Il corso tratterà i seguenti argomenti: problemi di ottimizzazione, esempi di modelli, ottimalità con molti obiettivi, programmazione lineare, grafi e modelli su grafi, programmazione lineare intera, modelli di percorsi, modelli particolari di programmazione lineare.

Testi/Bibliografia

Paolo Serafini. Ricerca Operativa. Springer, 2009.

Metodi didattici

Lezioni frontali.

Modalità di verifica e valutazione dell'apprendimento

L'esame di fine corso mira a valutare il raggiungimento degli obiettivi didattici seguenti:

  • Conoscere il concetto di problema di ottimizzazione, con particolare riferimento alla programmazione lineare.
  • Essere in grado di modellare problemi concreti come problemi di programmazione lineare.
  • Conoscere i principali algoritmi per problemi di flusso massimo e flusso di costo minimo su grafi.
  • Conoscere e saper applicare l'algoritmo del simplesso, assieme alle relative basi teoriche.
Il voto finale del Corso di Ottimizzazione viene definito, mediante una prova scritta, cui può seguire una prova orale a discrezione del docente.

Link ad altre eventuali informazioni

http://www.cs.unibo.it/~dallago/OTT1718

Orario di ricevimento

Consulta il sito web di Ugo Dal Lago