Tu sei qui:

13477 - OTTIMIZZAZIONE COMBINATORIA

Anno Accademico 2023/2024

                
                        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)

                            Risorse didattiche su Virtuale
                        
                                    Orario delle lezioni
                                
dal 18/09/2023 al 28/11/2023

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, 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.
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 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