METODI DI OTTIMIZZAZIONE – mod. ottimizzazione combinatoria

Il corso di Metodi di Ottimizzazione si compone di due moduli: Ottimizzazione Combinatoria e Modelli per la Pianificazione delle Attività.

Il modulo di Ottimizzazione Combinatoria ha lo scopo di fornire strumenti matematici per la formulazione e la soluzione di problemi di ottimizzazione su grafi e combinatori.

Docente Alessandro Agnetis
Vai alla homepage del docente.

Programma a.a. 2019/20
- Richiami sulla programmazione lineare e sulla dualità

- Totale unimodularità

- Problemi e algoritmi di cammino minimo (Dijkstra, Floyd-Warshall)

- Problema del massimo flusso, algoritmo di Ford-Fulkerson
- Problemi di matching, problema dell’assegnamento, algoritmo ungherese
- Formulazione di problemi in termini di ottimizzazione su grafi
Programmazione Lineare Intera:

- Formulazioni ideali, piani di taglio, Metodo dei piani di Gomory
- Branch and bound
- Generazione di colonne
- Problemi di knapsack
- Formulazione di problemi come Programmazione Lineare Intera (PLI).

Modalità d'esame del modulo Ottimizzazione Combinatoria
Sono previste due prove in itinere: una a metà del corso (data prevista: 6/11/2019, con inizio alle ore 10) e una al termine del corso (data prevista: 4/12/2019, ore 10). Gli studenti che riportano un voto sufficiente nelle due prove sono ammessi alla prova orale, purché questa si svolga entro la prima sessione (febbraio 2020). La prova orale è obbligatoria.

Durante la sola prima sessione (febbraio 2020) sarà possibile recuperare una delle due prove in itinere. L’orale andrà comunque sostenuto entro la fine della sessione di febbraio.

Per chi non svolge o non supera le prove in itinere, l’esame segue le modalità standard, consistenti in una prova scritta e una prova orale.

Il voto conseguito in questo modulo fa media con quello del modulo di Modelli per la Pianificazione delle Attività per dare luogo al voto finale di Metodi di Ottimizzazione (12 CFU).


Lezioni
Le lezioni si svolgono in aula F il mercoledi (9.15-13) e il giovedi (14.15-16).

NON vi sarà lezione nei seguenti giorni:

14/11/2019

e dopo la seconda prova in itinere

Orario di ricevimento
Martedi 16-17.30, stanza R101 (Torre Rossa), salvo modifiche dovute a impegni imprevisti che saranno comunicate.

Materiale didattico

- Fischetti, M., Lezioni di Ricerca Operativa, Libreria progetto, Padova, (edizione

2013): capp. 5.7, 6.1, 6.2, 6.3, 6.4, 7.1, 7.2, 7.3, 7.6, 7.7

Dispense integrative:

Problemi di matching

Duale del massimo flusso

Generazione di colonne 

Ottimizzazione di grafi: esercizi di formulazione 

Raccolta di esercizi di PLI svolti

Scansione fogli lezioni