Ricerca
Operativa (Informatica, Matematica)
(Prof. Claudio Arbib)
Materiale
Didattico Integrativo
Temi
di Esame ed Esercizi Proposti
Orario
Lunedì
14.15
16.15
Aula 1.7
Martedì
14.15
16.15
Aula 1.6
Lezioni
Martedì 6 marzo, 14:15-16:15
Introduzione al corso. Problemi e
modelli di ottimizzazione: logistica militare (flusso massimo, taglio minimo),
problema della dieta, problema del percorso più breve.
Giovedì 8 marzo, 14:15-16:15
Problemi e modelli di ottimizzazione:
illustrazione di un caso reale (logistica industriale). Formulazione di
problemi di programmazione lineare intera: cutting stock, formulazione di Kantorovich.
Martedì 13 marzo, 14:15-16:15
Un modello di ottimizzazione dei
livelli di produzione di un’industria. Variabili di
decisione, funzione obiettivo, vincoli; regione ammissibile. Problemi di
Programmazione Matematica e di Programmazione Lineare (PL). Soluzione per via
grafica, esempi.
Giovedì 15 marzo, 14:15-16:15
Prerequisiti di algebra lineare:
vettori e matrici; somma di vettori, prodotto per uno
scalare, combinazione lineare, affine, conica, convessa; prodotto
scalare; forma compatta di un sistema di (dis)equazioni.
Insiemi convessi. Le soluzioni di un sistema di disequazioni lineari formano un
insieme convesso. Esempi.
Martedì 20 marzo, 14:15-16:15
Iperpiani e semispazi chiusi,
esempi. Poliedri convessi e sistemi di disequazioni lineari. Disequazioni
implicate, combinazione conica di disequazioni lineari. Proiezione in IRn–1. Teorema di Fourier
(enunciato).
Giovedì 22 marzo, 14:15-16:15
Dimostrazione del teorema di
Fourier. Metodo di eliminazione di Fourier-Motzkin. Esempi ed esercizi.
Applicazione alla soluzione di un problema di PL.
Soluzione del problema tramite excel.
Martedì 27 marzo, 14:15-16:15
Esercitazione sul metodo di
Fourier-Motzkin. Scelta della colonna da eliminare in base alla complessità del
calcolo. Calcolo di un punto soluzione. Esempio di applicazione alla soluzione di
un problema di PL. Cenni sulla complessità del
metodo. Esercizio: formulazione di un problema di determinazione ottima dei
livelli di produzione in sistemi interconnessi.
Giovedì 29 marzo, 14:15-16:15
Indipendenza lineare e affine.
Esempi. Involucro conico, affine, convesso. Esempi.
Martedì 3 aprile, 14:15-16:15
Una terza applicazione del metodo
di Fourier-Motzkin: calcolo del sistema di disequazioni che definisce
l’involucro conico (convesso, affine) di un insieme finito di punti di IRn. Basi per un
insieme. Rappresentazione in una data base, unicità della rappresentazione,
teorema di sostituzione (Steinitz). Generalità sul
metodo del Simplesso: forma standard (definizione), basi, soluzioni
(ammissibili) di base.
Giovedì 12 aprile, 14:15-16:15
Equivalenza tra problemi in forma
generale e standard. Forma canonica di Gauss-Jordan e
forma canonica di Dantzig. Fase II del Simplesso:
criterio di ottimalità. Esempi.
Martedì 17 aprile, 14:15-16:15
Riepilogo delle lezioni
precedenti. Operazione di pivot e cambio di base: criteri per garantire
ammissibilità della nuova base e miglioramento della vecchia. Esempi.
Giovedì 19 aprile, 14:15-16:15
Criterio di illimitatezza.
Riepilogo, esercizi e applicazioni.
Martedì 8 maggio, 14:15-16:15
Prova d’esonero.
Giovedì 10 maggio, 14:15-16:15
Soluzione degli esercizi della
prova d’esonero.
Martedì 15 maggio, 14:15-16:15
Teoria della dualità per poliedri
di IRn: dal Teorema
di Fourier al Teorema di Gale, Lemma di Fàrkas; esempi. Dualità nella
programmazione lineare: teorema forte della dualità, enunciato ed
esemplificazione.
Martedì 22 maggio, 14:15-16:15
Dualità nella programmazione
lineare: teorema forte della dualità, dimostrazione. Reciprocità, dominanza,
complementarietà. Primale/duale illimitato. Esempi e riassunto.
Giovedì 24 maggio, 14:15-16:15
Applicazioni della teoria della
dualità. Prezzo implicito delle risorse. Selezione di un portafoglio di titoli:
strategia max-min, formulazione come programmazione
lineare. Esempio numerico: soluzione con il metodo del simplesso, basi
degeneri.
Martedì 29 maggio, 14:15-16:15
Esempio di coppia primale-duale
priva di soluzioni. Giochi a somma zero: strategie max-min e min-max, relazioni primale-duale. Esercitazione.
Problemi di ottimo su reti: percorso minimo, formulazione come ottimizzazione
combinatoria, codifica delle soluzioni, condizioni soddisfatte dalle soluzioni ammissibili, funzione obiettivo.
Giovedì 31 maggio, 14:15-16:15
Formulazione del problema del
percorso minimo come programmazione lineare intera. Cicli di peso negativo e
loro influenza sulla validità del modello. Problema di flusso massimo e sua
formulazione come PL. Problema del flusso a costo
minimo: formulazione come PL, casi particolari (flusso massimo e percorso
minimo). Determinazione di una soluzione ammissibile iniziale (se esiste).
Martedì 5 giugno, 14:15-16:15
Matrici unimodulari e totalmente
unimodulari. Formulazione del problema del cammino minimo come programmazione
lineare. Metodo del simplesso per problemi di flusso ottimo. Basi e alberi
ricoprenti.
Giovedì 7 giugno, 14:15-16:15
Metodo del simplesso per problemi
di flusso ottimo. Basi e soluzioni ammissibili di base. Problema duale e
criterio di ottimalità. Operazione di pivot (somma di circolazione). Esempi.
Martedì 12 giugno, 14:15-16:15
Esercitazione numerica sul metodo
del simplesso su reti: riduzione a valori di soglia nulli, come riconoscere una
soluzione ammissibile di base, criterio di ottimalità, aggiornamento della base
corrente.
Orario di
Ricevimento
|
Martedì |
11.30 |
13.00 |
studio del docente |
Appelli
Studenti della Facoltà
di Scienze: I appello: prova scritta, venerdì 25 giugno 2012, ore 14:30, aula da definire.
II appello: prova scritta,
giovedì 19 luglio 2012, ore 15:00, aula da definire.
Studenti della Facoltà
di Ingegneria: I appello: prova scritta, venerdì 25 giugno 2012, ore 14:30, aula da definire.
II
appello: prova scritta,
lunedì 2 luglio 2012, ore
14:30, aula da definire.
III
appello: prova scritta,
giovedì 19 luglio 2012, ore
15:00, aula da definire.
Per tutti gli appelli:
Prove
orali nei giorni a seguire.
Programma
Prerequisiti: teoria dei grafi
Definizioni di base: grafi
simmetrici, asimmetrici, antisimmetrici, grafo complemento, grafo completo e
grafo vuoto, isomorfismo. Sottografi (indotti). Cammini e percorsi, connettività debole e forte, componenti connesse. Grado,
numero di vertici di grado dispari in un grafo simmetrico.
(Argomenti complementari: Grafi d-regolari: matching, cicli e grafi cubici. Clique
e insieme stabile, numero di clique e di stabilità.
Colorazione di grafi: indice e numero cromatico. Grafi bipartiti e loro
caratterizzazione. Grafi privi di cicli: alberi e foreste.
grafi cordali;
grafi intersezione: proprietà fondamentali dei grafi intervallo, colorare e
trovare una clique massima in un grafo intervallo,
grafo di adiacenza di un grafo simmetrico, numero di clique
e di stabilità di un grafo di adiacenza.)
Prerequisiti: algebra lineare
Scalari, vettori e operazioni
elementari in IRn: prodotto scalare;
combinazione lineare, affine, conica e convessa. Involucro convesso di un
insieme di vettori. Semispazi chiusi, poliedri e loro rappresentazione
algebrica. Sistemi di disequazioni lineari. Dipendenza e indipendenza lineare,
rango, determinante. Base per un insieme di vettori. Teorema di
rappresentazione. Teorema di Steinitz.
Modelli di programmazione lineare
e lineare intera
Problemi di programmazione
lineare, soluzione ammissibile e soluzione ottima, forma canonica, generale e
standard. Esempi: il problema della dieta, ottimizzazione di un processo di
produzione, problemi max-min (giochi a somma zero), gestione ottima di un portafoglio titoli etc.
Formulazione di problemi di ottimizzazione combinatorica
come programmazione lineare 0-1. Esempi: clique,
insieme stabile, node-cover, colorazione, (s, t)-cammino
minimo, problema del commesso viaggiatore. Programmazione intera: knapsack
intero, ottimizzazione di un palinsesto televisivo etc.
Teoria della dualità
Teorema e metodo di
Fourier-Motzkin. Teoremi dell’alternativa: Teorema di Gale, Lemma di Farkas, esempi. Teorema di Dualità Forte. Il duale di un
programma lineare in forma standard. Proprietà del problema duale: reciprocità
e dominanza. Condizioni di ottimalità primale-duale: ortogonalità. Regole per
la costruzione del problema duale. Interpretazione economica del duale: prezzo
implicito delle risorse. Aspetti geometrici della programmazione lineare:
vertici e direzioni di un poliedro, politopi, cono di
recessione. Teorema di Weyl (enunciato). Esempi.
Teorema fondamentale della programmazione lineare: divergenza, o convergenza a
un vertice, in un programma lineare ammissibile.
Il metodo del simplesso
Basi e soluzioni (ammissibili) di base.
Equivalenza tra programmi lineari. Tabella canonica. Fase II
del simplesso: criteri di ottimalità e illimitatezza; miglioramento della base
corrente tramite pivot; regola di Bland. Fase
I del simplesso: calcolo di una soluzione ammissibile (se esiste) con il
problema ausiliario. Applicazioni alla programmazione lineare intera:
rilassamento lineare, limiti superiori/inferiori, cenni sui metodi di branch-and-bound ed esempi.
Programmazione lineare intera
Matrici (totalmente) unimodulari.
Criterio di totale unimodularità, esempi e applicazione alla programmazione
lineare intera.
Problemi di ottimo su reti
Problema di flusso a costo minimo.
Casi particolari: (s, t)-cammino minimo, (s, t)-flusso massimo, matching bipartito, cammino critico. Metodo del simplesso
su reti. Applicazioni ed esempi.
Testi di
Riferimento
A. Sassano, Modelli e Algoritmi della
Ricerca Operativa, Franco Angeli (1999)
A. Agnetis, C. Arbib, M. Lucertini, S. Nicoloso,
Il Processo Decisionale, Nuova Italia Scientifica (1992)
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and
Applications, Prentice Hall (1993)
C.H.
Papadimitriou, K.E. Steiglitz,
Combinatorial optimization: algorithms and
complexity, Dover Publications (1999), cap. 12 "Spanning Trees and Matroids"
D.
Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization,
Materiale
Didattico Integrativo
2.
Esercitazioni
a.
Esempi di problemi combinatorici
b.
Alcuni esercizi svolti (aggiornato al
9/2/06)
c.
Esercitazione sulle formulazioni di PL 0-1 (aggiornato all’8/2/07)
d.
Soluzione degli esercizi non svolti
3.
Modelli di ottimizzazione
a.
Layout ottimo di circuiti VLSI
b.
Gestione ottima di una centrale termoelettrica
(aggiornato al 26/1/06)
4.
Programmazione lineare
a.
Basi di IRn
b.
Poliedri in IRn: il metodo di Fourier-Motzkin (aggiornato al 20/3/12)
c.
Teoria della dualità (aggiornato al 1/3/06)
d.
Geometria della programmazione lineare (aggiornato
al 14/3/06)
e.
Il metodo del simplesso (aggiornato al 16/3/06)
5.
Programmazione lineare intera
a.
Matrici totalmente unimodulari (aggiornato al
15/5/10)
6.
Reti
a.
Problemi di flusso ottimo (aggiornato al 15/5/10)
b.
Metodo del simplesso per distribuzione single commodity
(aggiornato al 17/2/11)
c.
Cammini critici (aggiornato
al 15/6/10)
7.
Approfondimenti
a.
Geometria del simplesso (aggiornato al 16/3/06)
b.
Esercitazione sugli iperpiani di regressione
(aggiornato al 17/3/06)
c.
Esercitazione sui giochi a somma zero
(aggiornato al 17/3/06)
d.
Ottimizzazione combinatoria (aggiornato al 31/1/06)
e.
Cammino
minimo: metodo primale-duale (aggiornato
al 14/6/10)
f.
Cammino
minimo: metodo di Dijkstra
(aggiornato al 14/6/10)
Temi di
Esame ed Esercizi Proposti
Soluzioni prova scritta dell'11 settembre 2012
Soluzioni prova scritta del 25 giugno 2012
Soluzioni prova scritta dell’8 maggio 2012
Soluzioni prova scritta del 31 gennaio 2011
Soluzioni prova scritta del 24 novembre 2010
Soluzioni prova scritta del 27 settembre 2010
Soluzioni prova scritta del 13 settembre 2010
Soluzioni prova scritta del 21 luglio 2010
Soluzioni prova scritta del 5 luglio 2010
Soluzioni prova scritta del 5 maggio 2010
Bacheca
Avviso 13
La prova orale dell’esame di ricerca operativa si terrà lunedì 18 febbraio alle 11:00 in aula da definire. Gli ammessi all'orale sono:
| Cocco | Piermarco | 203737 |
| Pierabella | Luca | 205587 |
| Vaccarelli | Andrea | 168618 |
| Battistelli | Simone | 160162 |
| D'Andrea | Gabriella | 202281 |
Avviso 14
Sono ammessi all'orale che si terrà mercoledì 6 febbraio:
Di Carlo Matteo 184245
Di Giovanni Vanessa 172811
Pierabella Luca 205587
Scipioni Luca 175089
Avviso 13
La prova orale dell’esame di ricerca operativa (scritto del 28 gennaio) si terrà mercoledì 6 febbraio alle 11:00 nell'aula A1.3 (Coppito 0). La lista degli ammessi all'orale sarà pubblicata a breve. Si consiglia comunque la partecipazione e la visione del compito scritto.
Avviso 12
La prova orale dell’esame di ricerca operativa (scritto del 26 novembre) si terrà mercoledì 5 dicembre alle 15:00 presso lo studio del docente.
Avviso
11
Risultati della prova scritta del 26 novembre 2012
| Matricola | Voto |
| 168618 | insuff. |
| 160162 | insuff. |
| 190031 | 24 |
| 189426 | 23 |
| 184245 | insuff. |
| 153694 | insuff. |
| 175089 | insuff. |
Avviso 10
La prova orale dell’esame di ricerca operativa (scritto del 25 settembre) si terrà mercoledì 3 ottobre alle 10:30 presso lo studio del docente.
Avviso 9
| Ricerca Operativa | ||
| risultati prova scritta del 25 settembre 2012 | ||
| matricola | voto | |
| 1 | 153694 | insufficiente |
| 2 | 179071 | insufficiente |
| 3 | 187062 | insufficiente |
| 4 | 203301 | 21 |
| 5 | 203574 | 18 |
| 6 | 203737 | insufficiente |
Avviso 8
La prova orale dell’esame di ricerca operativa (scritto dell'11 settembre) si terrà mercoledì 19 settembre alle 10:30 presso lo studio del docente.
Avviso 7
| Ricerca Operativa | ||
| risultati prova scritta dell'11 settembre 2012 | ||
| matricola | voto | |
| 1 | 153694 | insufficiente |
| 2 | 177072 | 20 |
| 3 | 179071 | 20 |
| 4 | 187721 | 26 |
| 5 | 189202 | 23 |
| 6 | 193537 | 20 |
| 7 | 196076 | 18 |
| 8 | 202206 | insufficiente |
| 9 | 202281 | insufficiente |
| 10 | 202684 | 26 |
| 11 | 203301 | insufficiente |
| 12 | 203737 | 21 |
Avviso 6
La prova orale dell’esame di
ricerca operativa (scritto del 19 luglio) si terrà lunedì 23 luglio alle 10:30 presso lo studio del
docente.
I risultati della prova scritta verranno comunicati lunedì prima della prova orale.
Avviso 5
|
Ricerca Operativa |
||
|
risultati prova scritta del 25 giugno 2012 |
||
|
|
matricola |
voto |
|
1 |
170427 |
22 |
|
2 |
173665 |
insufficiente |
|
3 |
180289 |
insufficiente |
|
4 |
184549 |
20 |
|
5 |
186831 |
insufficiente |
|
6 |
186862 |
25 |
|
7 |
186865 |
18 |
|
8 |
187062 |
21 |
|
9 |
189426 |
insufficiente |
|
10 |
189998 |
19 |
|
11 |
192527 |
24 |
|
12 |
193435 |
24 |
|
13 |
194788 |
insufficiente |
|
14 |
194791 |
insufficiente |
|
15 |
197015 |
18 |
|
16 |
201991 |
23 |
|
17 |
203018 |
24 |
|
18 |
203301 |
17 |
|
19 |
203797 |
24 |
|
20 |
204809 |
21 |
|
21 |
213461 |
insufficiente |
|
Ricerca Operativa |
||
|
risultati prova scritta d'esonero del 25 giugno 2012 |
||
|
|
matricola |
voto |
|
1 |
184004 |
22 |
|
2 |
196088 |
19 |
|
3 |
202684 |
18 |
Avviso 4
La prova orale dell’esame di
ricerca operativa (scritti del 25 giugno e del 2 luglio) si terrà mercoledì 4 luglio alle 10:30 presso lo studio del
docente.
Avviso 3
Si rende noto che l’orario
di ricevimento è stato modificato. Gli studenti impossibilitati possono
contattare il docente via email.
Avviso 2
|
Ricerca Operativa |
||
|
risultati prova scritta del'8 maggio 2012 |
||
|
|
matricola |
voto |
|
1 |
184004 |
21 |
|
2 |
187725 |
21 |
|
3 |
189202 |
insufficiente |
|
4 |
192527 |
18 |
|
5 |
196088 |
28 |
|
6 |
197015 |
insufficiente |
|
7 |
202684 |
26 |
|
8 |
203574 |
23 |
Avviso 1
La prova di esonero si terrà martedì 8 maggio 2012 alle ore 14:30 in aula da
definire.