13477 - OTTIMIZZAZIONE COMBINATORIA

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 in termini di vincoli lineari (o lineari interi) e funzione obiettivo lineare, ovvero riconoscere che il problema non può essere cosi' formulato. E' inoltre in grado di modellare problemi combinatori su grafi (ad esempio flussi massimi e accoppiamenti), e può risolverli per mezzo dei principali algoritmi noti nella letteratura.

Contenuti

Il corso tratterà i seguenti argomenti: problemi di ottimizzazione, esempi di modelli di problemi di ottimizzazione, programmazione lineare, grafi e modelli su grafi, programmazione lineare intera.

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 o lineare intera.
• Conoscere i principali algoritmi per problemi di flusso massimo e flusso di costo minimo su grafi.
• Conoscere e saper applicare l'algoritmo del simplesso e il metodo branch-and-bound, assieme alle relative basi teoriche.
  

Il voto finale del Corso di Ottimizzazione Combinatoria 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. Studenti/sse con DSA o disabilità temporanee o permanenti: si raccomanda di contattare per tempo l’ufficio di Ateneo responsabile (https://site.unibo.it/studenti-con-disabilita-e-dsa/it): sarà sua cura proporre agli/lle studenti/sse interessati/e eventuali adattamenti, che dovranno comunque essere sottoposti, con un anticipo di 15 giorni, all’approvazione del/della docente, che ne valuterà l'opportunità anche in relazione agli obiettivi formativi dell'insegnamento. Con riferimento all'uso dell'intelligenza artificiale nelle prove d'esame, si precisa che il corso adotta lo Scenario 1: Esame in ambiente controllato con divieto di utilizzo dell'IA.

Strumenti a supporto della didattica

Verranno messi a disposizione degli studenti le slides utilizzate dal docente e dispense sui principali contenuti, assieme ad esempi di esercizi svolti.

Orario di ricevimento

Consulta il sito web di Daniele Vigo