Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: http://www.dii.unisi.it/%7Elamed/images/barra2.jpg

Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: HomeDescrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Links

 

 

 

·         Home

·         People

·         Research

·         Seminars/Courses

·         Teaching

·         Link

 

:: Teaching

 



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. 2017/18
- 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, TSP, scheduling
- 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 (20/11/2017, con inizio alle ore 10) e una al termine del corso (data da stabilire). Gli studenti che riportano un voto sufficiente nelle due prove sono ammessi alla prova orale, purché questa si svolga entro la prima sessione (febbraio 2018). La prova orale è obbligatoria.

Durante la sola prima sessione (febbraio 2018) 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 svolgeranno in aula 101 il lunedi (9-13) e in aula 13 il giovedi (11-13). NON vi sarà lezione nei seguenti giorni:

9/10/2017

12/10/2017

23/10/2017

26/10/2017

30/11/2017

18/12/2017

 

 

 

Orario di ricevimento
Martedi 14.30-16. 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 nuova). In particolare, per gli argomenti oggetto di questo modulo:

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

edizione vecchia: capp. 4.7, 5.1, 5.2, 5.3, 5.4, 6.1, 6.2, 6.3, 6.6, 6.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  

 

Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: Descrizione: http://www.dii.unisi.it/%7Elamed/images/basso.gif