14511 - OTTIMIZZAZIONE

Anno Accademico 2020/2021

  • 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 ha appreso 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 puo' essere cosi' formulato. E' inoltre in grado di modellare problemi combinatori su grafi come problemi di cammini minimi, flussi massimi e abbinamenti, e puo' 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 ed esercitazioni.

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 della durata di due ore, cui può seguire una prova orale a discrezione del docente. Durante la prova scritta non è consentita la consultazione di materiale.

Orario di ricevimento

Consulta il sito web di Ugo Dal Lago

SDGs

Consumo e produzione responsabili

L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.