Ricerca Operativa (Informatica, Matematica)
Ricerca Operativa (Informatica, Matematica)
(Prof. Claudio Arbib)
Materiale Didattico Integrativo
Orario
Canale A
Martedí dalle ore 9:30 alle ore 11:30, Aula Magna
Mercoledí dalle ore 15:00 alle ore 17:00, Aula Magna
Giovedí dalle ore 11:30 alle ore 13:30, Aula Magna
Canale B
Martedí dalle ore 15:00 alle ore 17:00, Aula Magna
Mercoledí dalle ore 9:30 alle ore 11:30, Aula Magna
Giovedí dalle ore 17:00 alle ore 19:00, Aula Magna
Lezioni
IX settimana
Martedì 12 Marzo 2002
Metodi generali per la soluzione di problemi di ottimizzazione combinatoria. Enumerazione implicita (branching). Uso del simplesso per ottenere limitazioni inferiori/superiori(bound). Metodo di branch-and-bound. Esempi.Mercoledì 13 Marzo 2002
Simulazione di scambi commerciali. Prezzi impliciti delle risorse. Interpretazione economica del problema duale. Esempi.Giovedì 14 Marzo 2002
Simulazione di gestione di un portafoglio titoli. Giochi a somma zero. Problema primale (maxmin) e problema duale (minmax). Esempi.
VIII settimana
Martedì 05 Marzo 2002
Relazione tra basi, vertici e soluzioni ottime. Problema ridotto e forma canonica. Criterio di ottimalità nel metodo del simplesso. Criterio di illimitatezza (enunciato). Operazione di pivot.
Mercoledì 06 Marzo 2002
Trasformazioni canoniche: esempi. Miglioramento della soluzione corrente. Metodo del simplesso. Esempi.
VII settimana
Martedì 26 febbraio 2002
Teoremi dell'alternativa: il Teorema di Gale.
Mercoledì 27 febbraio 2002
Teoria della dualità: teorema di dualità forte e problema duale.
Giovedì 28 febbraio 2002
Teoria della dualità: teoremi di reciprocità e di dualità debole. Regole per la costruzione del duale di un problema di PL. Esempi. Basi e soluzioni (ammissibili) di base per problemi in forma standard.
VI settimana
Martedì 19 febbraio 2002
Esercitazione: discussione dei problemi posti nella prova di esonero.
Mercoledì 20 febbraio 2002
Formulazione di problemi di ottimizzazione combinatoria: problemi di scheduling (lavori in competizione per l'uso di un insieme di risorse); problemi di partizione (gestione della memoria).Giovedì 21 febbraio 2002
Problemi multicriterio. Ottimizzazione secondo Pareto: soluzioni dominate e non dominate. Curve di regressione: calcolo della retta di regressione tramite programmazione lineare. Esercitazione: uso di un foglio di calcolo per la formulazione e risoluzione di un problema di programmazione lineare.
V settimana
Martedì 5 febbraio 2002
Esercitazione sul metodo di Fourier-Motzkin. Forma algebrica dell'involucro conico, affine e convesso di un insieme finito di vettori.Mercoledì 6 febbraio 2002
EsercitazioneGiovedì 7 febbraio 2002
Esercitazione
IV settimana
Martedì 29 gennaio 2002
Spazi vettoriali a dimensione finita, combinazione lineare, dipendenza e indipendenza lineare. Matroide vettoriale.Mercoledì 30 gennaio 2002
Corrispondenza tra matroide vettoriale e grafico. Sistemi di disequazioni lineari e loro rappresentazione geometrica. Combinazione conica, affine e convessa. EsempiGiovedì 31 gennaio 2002
Poliedri. Diseguaglianze implicate, proiezione di un poliedro e Teorema di Fourier (enunciato). Metodo di Fourier-Motzkin. Esempi.
III settimana
Martedì 22 gennaio 2002
Problemi subclusivi con la proprietà di scambio. Teorema di Rado (condizione sufficiente).Giovedì 24 gennaio 2002
Teorema di Rado (condizione necessaria). Sistemi di indipendenza e matroidi. Esempi: matroide uniforme, grafico, partizione.
II settimana
Martedì 15 gennaio 2002
Problemi discreti: formulazione come programmazione pseudo-booleana, ottimizzazione combinatoria, programmazione lineare intera. Esempi. Algoritmo universale e algoritmo greedy.Mercoledì 16 gennaio 2002
Problemi di ottimizzazione combinatoria. Problemi subclusivi e superclusivi. Esempi: copertura di un ambiente con telecamere a circuito chiuso e formulazione come edge-cover, clique e insieme stabile, matching, albero ricoprente, knapsack 0-1. Comportamento dell'algortimo greedy.
I settimana
Mercoledì 9 gennaio 2002
Introduzione al corso. Origini della ricerca operativa. Alcuni modelli elementari: il problema della dieta, il problema dell'abbinamento. Problemi di ottimizzazione.Giovedì 10 gennaio 2002
Modellazione di un sistema. Descrittori qualitativi e quantitativi, indicatori, vincoli, obiettivi. Esempi.
Orario di Ricevimento
Mercoledì dalle ore 12.00 alle ore 13.00
Giovedì dalle ore 15.00 alle ore 16.30
Appelli
Prima Prova Parziale
12 febbraio 2002 ore 15.00 Aule 1.6, 1.7, 2.5 e aula Magna
Programma
Testi di Riferimento
A. Sassano, Modelli e Algoritmi della Ricerca Operativa, Franco Angeli Ed.(1999)
A. Agnetis, C. Arbib, M. Lucertini, S. Nicoloso, Il Processo Decisionale, Nuova Italia Scientifica (1992)
Materiale Didattico Integrativo
Esercitazioni*, presentazione
Branch-and-Bound*, presentazione
Metodo di Fourier Motzkin *, presentazione
Problemi combinatorici ed Esempi*, presentazione
Il problema della dieta*, formato .xls
Il metodo di Fourier Motzkin*, presentazione
Esempio sul metodo di Fourier Motzkin*, presentazione
L'auto ideale*, presentazione
Il metodo del Simplesso*, presentazione
Poliedri*, presentazione
Branch&Bound, Stabile, Zaino *, slide delle lezioni del 6 e 12 marzo 2002
Appunti delle lezioni, dispense in distribuzione.
* i file sono in formato .pps (presentazione Microsoft PowerPoint) e compressi con WinZip
Temi di Esame
04 febbraio 2002
18 settembre 2001
26 giugno 2001
21 febbraio 2001
05 febbraio 2001
16 gennaio 2001
22 giugno 2000
01 giugno 2000
24 febbraio 2000
20 gennaio 2000
15 settembre 1999
12 luglio 1999
04 giugno 1999
18 febbraio 1999
27 gennaio 1999
16 settembre 1998
21 luglio 1998
30 giugno 19998
02 giugno 1998
25 febbraio 1998
Risposte prova scritta intermedia del 12 febbraio 2002 GRUPPO A
Risposte prova scritta intermedia del 12 febbraio 2002 GRUPPO B
Risposte prova scritta intermedia del 12 febbraio 2002 GRUPPO C
Risposte prova scritta intermedia del 12 febbraio 2002 GRUPPO D
Risutati prova scritta del 12 febbraio 2002 GRUPPO A
Risutati prova scritta del 12 febbraio 2002 GRUPPO B
Risutati prova scritta del 12 febbraio 2002 GRUPPO C
Risutati prova scritta del 12 febbraio 2002 GRUPPO D
Soluzioni della II° prova scritta del 21 marzo 2002
Bacheca
Avviso 06 Febbraio 2002
La convocazione per la prima prova parziale è martedì 12 Febbraio ore 15.00.
La ripartizione dei canali nelle aule sarà affissa appena possibile (lunedì pomeriggio) nell'aula Magna.Avviso 27 Marzo 2002
La verbalizzazione del gruppo D sarà effettuata martedì 9 Aprile alle ore 17 negli Studi dei docenti.Avviso 9 Aprile 2002
La verbalizzazione del gruppo D è stata rinviata a mercoledì 17 Aprile alle ore 17 negli Studi dei docenti.