13477 - OTTIMIZZAZIONE COMBINATORIA

Anno Accademico 2022/2023

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

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.

Strumenti a supporto della didattica

Verranno messi a disposizione degli studenti le slides utilizzate dal docente, assieme ad un eserciziario.

Orario di ricevimento

Consulta il sito web di Ugo Dal Lago