Ricerca Operativa II
A.A. 2003/2004
Ricerca Operativa II
A.A. 2003/2004
(Prof. Claudio Arbib)
Materiale Didattico Integrativo
Orario
Lezioni
IX settimana
Martedì 25 novembre 2003
Problema di Cutting-Stock: formulazioni di Kantorovich e Gilmore-Gomory.Mercoledì 26 novembre 2003
Il metodo di generazione colonne per il problema di Cutting-Stock.
Giovedì 27 novembre 2003
Esercitazione sul metodo di generazione colonne.
VIII settimana
Scarica qui il materiale integrativo di questa settimana
Martedì 18 novembre 2003
Strumenti di simulazione e valutazione per il project management. Reti di attività, fasi critiche e cammini critici. Metodo del cammino critico (CPM): formulazione come programmazione lineare.
Mercoledì 19 novembre 2003
Un metodo duale per il CPM: formulazione e problema di flusso separabile associato. Linearizzazione dei costi e algoritmo di soluzione.
Giovedì 20 novembre 2003
Esercitazione: applicazione del metodo duale per il CPM, soluzioni Pareto-ottime e forma della curva di efficienza.
VII settimana
Martedì 11 novembre 2003
Metodo del simplesso su reti: teorema di corrispondenza basi-alberi; calcolo della prima base.Mercoledì 12 Novembre 2003
Simplesso su retiGiovedì 13 novembre 2003
Esercitazione sul metodo del simplesso su reti. Basi degeneri. Utilità marginale in un problema di trasporto.
VI settimana
Martedi' 4 novembre 2003
Problema di trasporto. Metodo del simplesso su reti, fase I: calcolo di una soluzione iniziale. Problema ausiliario e applicazione del metodo di Ford-Fulkerson.
V settimana
Scarica qui il materiale integrativo di questa settimana
Martedì 28 ottobre 2003
Considerazioni sulla complessità e correttezza del metodo di Ford-Fulkerson. Due esempi patologici. Metodi di programmazione dinamica per problemi di cammino ottimo.Mercoledì 29 Ottobre 2003
La Tecnica del Rilassamento Lagrangiano per la risoluzione di problemi di
Ottimizzazione Combinatoria.Giovedì 30 Ottobre 2003
Un'applicazione della tecnica di Rilassamento Lagrangiano ad un problema
di Scheduling Competitivo in sistemi di telecomunicazione cellulare UMTS.
IV settimana
Martedì 21 ottobre 2003
Il problema dell'(s,t)-cammino di peso minimo: grafi privi di circuiti negativi e applicazione del metodo primale-duale. Esempio.Mercoledì 22 ottobre 2003
Il metodo duale per il problema dell'(s,t)-cammino di peso minimo: esercitazione. Metodo di Dijkstra. Dimostrazione di correttezza.Giovedì 23 ottobre 2003
Il metodo primale-duale per problemi di (s,t)-flusso massimo. Cammini aumentanti e metodo di Ford-Fulkerson.
III settimana
Martedì 14 ottobre 2003
Esercitazione sul metodo primale-duale. Matrici unimodulari e totalmente unimodulari. Esempi. Applicazione alla programmazione lineare intera.Mercoledì 15 ottobre 2003
Un criterio di unimodularità totale. Esempi.Giovedì 16 ottobre 2003
Il problema dell'(s,t)-cammino di peso minimo. Una formulazione del problema come programmazione lineare. Limiti della formulazione: grafi con ciricuiti negativi e complessità.
II settimana
Scarica qui il materiale integrativo di questa settimana
Martedì 7 ottobre 2003
Flusso single- e multi-commodity: esempi. Problemi di flusso ottimo.
Funzioni costo: problemi separabili. Problemi lineari. Problema del
trasporto e sue specializzazioni: flusso massimo, cammino minimo, matching
bipartito.Mercoledì 8 ottobre 2003
Problemi di trasporto e relazioni con taglio minimo, node-cover bipartito, CPM. Metodo primale-duale: condizione di ottimalità.Giovedì 9 ottobre 2003
Metodo Primale-duale.
I settimana
Martedì 30 settembre 2003
Introduzione al corso, contenuti generali, orari, testi di riferimento.Giovedì 2 ottobre 2003
Distribuzione di flusso, potenziale, divergenza; relazioni fondamentali;
matrice di incidenza nodi-archi.
Orario di Ricevimento
Mercoledì dalle ore 15.00 alle ore 16.30
Appelli
17 dicembre 2003 ore 10:30 aula 2.4
Programma
Testi di Riferimento
C.H. Papadimitriou, K.E. Steiglitz, Combinatorial Optimization, Algorithms and Complexity, Prentice Hall (1982)
Ahuja, Magnanti, Orlin, Network Flows
E. Lawler, Combinatorial Optimization: Networks and Matroids
Materiale Didattico Integrativo
C. Arbib, Metodo primale-duale, presentazione
C. Arbib, Ford, Fulkerson, presentazione
C. Arbib, Metodo del cammino critico (CPM), presentazione
* i file sono in formato .pps (presentazione Microsoft PowerPoint) e compressi con WinZip
Temi di Esame
26 giugno 2001
21 febbraio 2001
05 febbraio 2001
16 gennaio 2001
22 giugno 2000
24 febbraio 2000
22 gennaio 2000
20 gennaio 2000
29 settembre 1999
15 settembre 1999
12 luglio 1999
04 giugno 1999
18 febbraio 1999
27 gennaio 1999
16 settembre 1998
21 luglio 1998
30 giugno 1998
02 giugno 1998
Bacheca
Avviso 5
L'esame orale di Ricerca Operativa 2 si terrà domani 10 dicembre alle ore 10.30 in aula da definire. Presentarsi presso lo studio del prof. Arbib.Avviso 4
Risultati della prova scritta del 6 dicembre 2004
Avviso 3
L'appello della sessione di recupero si terrà il 17 dicembre 2003 ore 10:30 aula 2.4
Avviso 2
La lezione di recupero di Ricerca Operativa 2 si terrà martedì 04-11-2003 alle ore 09:30 in aula da definire.Avviso 1
Mercoledì 01-10-2003 la lezione di Ricerca Operativa 2 non avrà luogo. Tale lezione verrà recuperata in data da destinarsi