Ricerca
Operativa (Informatica, Matematica)
(Prof. Claudio Arbib)
Materiale
Didattico Integrativo
Temi
di Esame ed Esercizi Proposti
Orario
Lunedì
11.30
13.30
Aula 1.7
Martedì
11.30
13.30
Aula 1.7
Lezioni
Lunedì 8 marzo, 11:30-13:30
Introduzione al corso. Problemi e
modelli di ottimizzazione: formazione di equipaggi, investimenti formativi,
problema del matching; colorazione di carte
geografiche, assegnazione di aule, problema di graph coloring.
Martedì 9 marzo, 11:30-13:30
Problemi e modelli di
ottimizzazione: navigazione satellitare, problema del percorso più breve.
Formulazione come programmazione lineare intera, rilassamento lineare.
Lunedì 15 marzo, 11:30-13:30
Instradamento in reti a commutazione di
pacchetto, problema del percorso più sicuro, formulazione come programmazione
non lineare, linearizzazione; gestione di centrali di trasformazione termoelettrica,
formulazione del problema di economic dispatching come percorso minimo.
Martedì 16 marzo, 11:30-13:30
Esempi di programmazione lineare:
problema della fabbrica. Soluzioni ammissibili e soluzioni ottime. Iperpiani, poliedri e sistemi di disequazioni lineari.
Intuizione geometrica: direzione di miglioramento, vertice.
Lunedì 22 marzo, 11:30-13:30
Ripasso su iperpiani,
poliedri e sistemi di disequazioni lineari. Combinazione lineare, conica,
affine, convessa. Dipendenza e indipendenza lineare e affine. Basi di IRn.
Esempi. Rappresentazione di un vettore in una base, teorema di unicità.
Martedì 23 marzo, 11:30-13:30
Teorema di sostituzione (Steinitz). Compatibilità di un sistema di disequazioni
lineari. Proiezione di un poliedro, Teorema di Fourier.
Lunedì 29 marzo, 11:30-13:30
Metodo di Fourier-Motzkin.
Applicazioni: calcolo di una soluzione di un sistema di disequazioni lineari,
soluzione di un problema di programmazione lineare.
Martedì 30 marzo, 11:30-13:30
Determinazione della forma
implicita dell’involucro conico, affine, convesso tramite il Metodo di Fourier-Motzkin. Esercitazione.
Lunedì 12 aprile, 11:30-13:30
Dal metodo di Fourier-Motzkin
ai Teoremi dell’Alternativa: Teorema di Gale, Lemma di Fàrkas. Esempi.
Martedì 13 aprile, 11:30-13:30
Teorema Forte della Dualità.
Esempi. Il problema duale.
Lunedì 19 aprile, 11:30-13:30
Teorema Debole della Dualità.
Condizioni di ortogonalità, corollari. Regole per la costruzione del duale.
Esercitazione: analisi di un sistema dinamico. Interpretazione del problema
duale.
Martedì 20 aprile, 11:30-13:30
Applicazione della teoria della
dualità: massimizzazione dei profitti con risorse limitate, prezzo implicito
delle risorse. Gestione di un portafoglio titoli: ripartizione ottimale del
rischio.
Lunedì 26 aprile, 11:30-13:30
Forma canonica di un problema di
programmazione lineare. Basi e soluzioni di base. Metodo del simplesso:
criterio di ottimalità.
Mercoledì 5 maggio, 15:00-17:40
Prova di esonero.
Lunedì 10 maggio, 11:30-13:30
Metodo del simplesso: criterio di
illimitatezza e aggiornamento della base corrente (operazione di pivot).
Esempi.
Martedì 11 maggio, 11:30-13:30
Riepilogo del metodo del
simplesso, esercitazione. Determinazione di una base iniziale: problema
ausiliario.
Lunedì 17 maggio, 11:30-13:30
Riepilogo del metodo del
simplesso, applicazione alla soluzione di un gioco a somma
zero.
Martedì 18 maggio
Lezione non tenuta
per impegni istituzionali del docente.
Lunedì 24 maggio, 11:30-13:30
Problemi di flusso ottimo in reti
conservative. Problemi single- e multi-commodity.
Distribuzione di flusso, vincoli di conservazione, vincoli di soglia/capacità.
Un modello lineare. Soluzioni intere. Casi particolari: problemi del (s, t)-cammino
minimo e dell’(s, t)-flusso massimo.
Martedì 25 maggio, 11:30-13:30
Problemi di flusso ottimo single-commodity
in reti conservative con costi lineari. Specializzazione del metodo del
simplesso: basi, determinazione di una soluzione (di base) ammissibile,
criterio di ottimalità, triangolarizzazione
della base, calcolo del potenziale e dei costi ridotti. Esempio.
Lunedì 31 maggio, 12:30-13:30
Esercitazione: determinazione di
una soluzione di base ammissibile per un problema di flusso ottimo single-commodity.
Lunedì 7 e martedì 8 giugno
Lezione non tenuta
per impegni di ricerca del docente.
Lunedì 14 maggio, 12:30-13:30
Problemi combinatorici
formulabili come problemi di flusso: matching
bipartito (perfetto/massimo), (s, t)-cammino di peso minimo.
Esercitazione.
Martedì 15 maggio, 11:30-13:30
Reti di attività (PERT, CPM).
Diagramma di Gantt e grafo di precedenze. Tempi di
raggiungimento, attività critiche. Calcolo del grafo dei cammini critici.
Determinazione delle durate ottimali: formulazione come PL.
Conclusione del corso.
Orario di
Ricevimento
|
Lunedì |
15.00 |
17.00 |
studio del docente |
Appelli
1. Prova scritta (fuori corso):
mercoledì 5 maggio ore 15.00, aula 1.7
Prova orale (fuori corso): mercoledì 12 maggio 2010 ore 10:00, aula da definire
2. Prova scritta: lunedì 5 luglio
ore 10.30, aula da definire
Prova orale: a seguire
3. Prova scritta: mercoledì 21
luglio ore 15.00, aula C1.9
Prova orale: lunedì 26 luglio ore 10:30,
studio del docente
4. Prova scritta: lunedì 13
settembre ore 15:00,
Facoltà di Scienze, aula 1.6
Prova orale: lunedì 20 settembre ore 10:30,
Facoltà di Scienze, studio del docente.
5. Prova scritta: lunedì 27
settembre ore 15:00,
Facoltà di Scienze
Prova orale: martedì 5 ottobre ore 14:30,
Facoltà di Scienze, studio del docente.
6. Prova scritta: mercoledì 24
novembre ore 15:00,
Facoltà di Scienze
Prova orale: a seguire.
7. Prova scritta: lunedì 31 gennaio
ore 15:00, Facoltà di
Scienze, aula 1.7
Prova orale: giovedì 3 febbraio ore 10:30,
Facoltà di Scienze, studio del docente.
8. Prova scritta: lunedì 21 febbraio
ore 15:00, Facoltà di
Scienze, aula 1.7
Prova orale: lunedì 28 febbraio ore 15:00,
Facoltà di Scienze, studio del docente.
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
7/2/06)
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 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 15
La discussione della prova scritta
e l’eventuale prova orale di ricerca
operativa si terranno lunedì 28 febbraio alle ore 15:00 nello studio del docente presso
|
Ricerca Operativa |
||
|
risultati prova scritta del 21 febbraio 2011 |
||
|
|
matricola |
voto |
|
1 |
140418 |
20 |
|
2 |
168150 |
23 |
|
3 |
181425 |
28 |
Avviso 14
La discussione della prova scritta
e l’eventuale prova orale di ricerca
operativa si terranno giovedì 3 febbraio alle ore 10:30
nello studio del docente presso
|
Ricerca Operativa |
||
|
risultati prova scritta del 31
gennaio 2011 |
||
|
|
matricola |
voto |
|
1 |
168141 |
20 |
|
2 |
181425 |
insufficiente |
|
3 |
182220 |
insufficiente |
Avviso 13
La discussione della prova scritta
e l’eventuale prova orale di ricerca
operativa si terranno mercoledì 1 dicembre alle ore
10:00 nello studio del docente presso
|
Ricerca Operativa |
|||
|
risultati prova scritta del 24
novembre 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
137678 |
A |
18 |
|
2 |
144674 |
A |
18 |
|
3 |
145285 |
B |
insufficiente |
|
4 |
146968 |
B |
21 |
|
5 |
147079 |
A |
22 |
|
6 |
151575 |
B |
20 |
|
7 |
168141 |
A |
insufficiente |
|
8 |
168150 |
A |
insufficiente |
|
9 |
168251 |
B |
26 |
|
10 |
174792 |
A |
23 |
Avviso 12
La discussione della prova scritta
e l’eventuale prova orale di ricerca operativa
si terranno martedì 5 ottobre alle ore 14:30
nello studio del docente presso
|
Ricerca Operativa |
|||
|
risultati prova scritta del 27
settembre 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
137678 |
A |
insufficiente |
|
2 |
143891 |
B |
20 |
|
3 |
144674 |
A |
insufficiente |
|
4 |
146725 |
A |
insufficiente |
|
5 |
147079 |
A |
insufficiente |
|
6 |
155644 |
B |
29 |
|
7 |
156739 |
B |
21 |
|
8 |
158965 |
A |
20 |
|
9 |
160571 |
A |
28 |
|
10 |
168150 |
B |
27 |
|
11 |
168251 |
B |
insufficiente |
|
12 |
172811 |
A |
insufficiente |
|
13 |
172933 |
B |
24 |
|
14 |
174792 |
B |
22 |
|
15 |
182220 |
A |
21 |
|
16 |
190729 |
A |
21 |
|
17 |
195392 |
B |
27 |
|
18 |
195846 |
A |
20 |
Avviso 11
La prova orale
di ricerca operativa si terrà lunedì 20 settembre alle
ore 10:30 nello studio del docente presso
|
Ricerca Operativa |
|||
|
risultati prova scritta del 13
settembre 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
147073 |
B |
insufficiente |
|
2 |
156739 |
B |
insufficiente |
|
3 |
158965 |
A |
insufficiente |
|
4 |
165541 |
A |
19 |
|
5 |
168760 |
B |
19 |
|
6 |
174793 |
B |
19 |
|
7 |
191929 |
A |
22 |
|
8 |
192510 |
A |
21 |
|
9 |
195392 |
B |
22 |
|
10 |
195407 |
B |
23 |
|
11 |
199313 |
B |
insufficiente |
Avviso 10
La prova
orale di ricerca operativa si terrà lunedì 26
luglio alle ore 10:30 nello studio del docente presso
|
Ricerca Operativa |
|||
|
risultati prova scritta del 21
luglio 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
139462 |
B |
23 |
|
2 |
143891 |
B |
insufficiente |
|
3 |
154635 |
A |
22 |
|
4 |
154657 |
B |
22 |
|
5 |
155644 |
A |
22 |
|
6 |
156739 |
B |
18 |
|
7 |
156841 |
A |
18 |
|
8 |
158965 |
B |
21 |
|
9 |
160297 |
A |
insufficiente |
|
10 |
160571 |
A |
18 |
|
11 |
166015 |
A |
23 |
|
12 |
168088 |
A |
26 |
|
13 |
168150 |
B |
insufficiente |
|
14 |
168760 |
B |
insufficiente |
|
15 |
172811 |
B |
insufficiente |
|
16 |
174041 |
A |
30 e lode |
|
17 |
184242 |
A |
24 |
|
18 |
187411 |
B |
23 |
|
19 |
188419 |
B |
30 |
|
20 |
190000 |
A |
19 |
|
Ricerca Operativa |
|||
|
risultati prova d'esonero del 21
luglio 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
187081 |
A |
23 |
Avviso 9
La prova scritta di ricerca operativa di mercoledì
21 luglio si terrà alle ore 15:00 e non alle 10:30 come inizialmente
riportato.
Avviso 8
La prova
orale di ricerca operativa si terrà mercoledì 14
luglio alle ore 10:30 nello studio del docente presso
|
Ricerca Operativa |
|||
|
risultati prova scritta del 5
luglio 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
123379 |
B |
26 |
|
2 |
154635 |
B |
insufficiente |
|
3 |
154657 |
B |
18 |
|
4 |
156841 |
B |
insufficiente |
|
5 |
158965 |
B |
insufficiente |
|
6 |
165541 |
A |
insufficiente |
|
7 |
168088 |
B |
insufficiente |
|
8 |
168251 |
A |
insufficiente |
|
9 |
172465 |
A |
27 |
|
10 |
172730 |
A |
25 |
|
11 |
174792 |
A |
19 |
|
12 |
184242 |
A |
insufficiente |
|
13 |
188198 |
A |
30 e lode |
|
14 |
190296 |
A |
30 e lode |
|
|
|
|
|
|
risultati II prova d'esonero del 5
luglio 2010 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
186748 |
A |
30 |
|
2 |
187193 |
A |
30 |
|
3 |
187411 |
A |
insufficiente |
|
4 |
188556 |
A |
30 |
|
5 |
190000 |
A |
insufficiente |
Avviso 7
Il ricevimento studenti del 21 giugno 2010 è spostato al pomeriggio, dalle ore
15:00 alle 17:00 presso
Avviso 6
Modalità d’esame. L’esame di ricerca operativa si svolge in
due parti, una prova scritta e una prova orale.
Fra la prova scritta e quella
orale intercorre il tempo necessario alla correzione degli elaborati e alla
pubblicazione dei risultati. I risultati sono di norma affissi in forma cartacea nelle apposite bacheche di facoltà o
all’ingresso dello studio del docente, e in questo caso sono completi di
cognome e nome dei candidati; sono anche pubblicati in
forma elettronica su questo sito, ma in questo caso per riservatezza
l’identificazione del candidato avviene attraverso il solo numero di
matricola.
Alla prova orale sono ammessi i soli candidati che hanno superato la prova
scritta con almeno 18/30. Votazioni inferiori a
questa non sono pubblicate. E’ possibile in ogni caso richiedere la
discussione dell’elaborato con il docente.
Il risultato della prova scritta può essere conservato per la durata dell’intera
sessione d’esami, fino al sostenimento della prima prova orale in un
appello scelto dallo studente tra quelli della sessione. Tuttavia in caso di
insuccesso all’orale dovrà essere sostenuta una nuova prova scritta. In
pratica, se uno studente supera la prova scritta al primo appello può decidere
se presentarsi all’orale al primo oppure al secondo appello: nel primo
caso però ove fallisse l’orale non potrà conservare il risultato dello
scritto, e dovrà ritentare la prova scritta all’appello successivo.
Avviso 5
Nell'ambito delle attività della Fondazione Space Academy (www.spaceacademy.it)
il dr. Mario Costantini di E-GEOS (www.e-geos.it)
terrà un seminario dal titolo:
Metodi di ottimizzazione per
l'elaborazione di segnali e il telerilevamento: un
algoritmo efficiente per lo "srotolamento"
della fase
Il seminario si terrà mercoledi 16 giugno
alle ore
Avviso 4
|
Ricerca Operativa |
|||
|
risultati prova d'esonero del 5
maggio 2009 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
172811 |
B |
18 |
|
2 |
174041 |
A |
20 |
|
3 |
178890 |
B |
23 |
|
4 |
181425 |
A |
18 |
|
5 |
186748 |
B |
28 |
|
6 |
187081 |
A |
18 |
|
7 |
187193 |
A |
19 |
|
8 |
187411 |
B |
25 |
|
9 |
188419 |
A |
25 |
|
10 |
188556 |
B |
26 |
|
11 |
190000 |
B |
23 |
|
12 |
190296 |
A |
19 |
Avviso 3
La lezione di martedì 18 maggio potrà subire ritardo o essere soppressa per impegni istituzionali del
docente
Avviso 2
Tesi di laurea
disponibile
(primo livello): movimentazione ottima di magazzini industriali, in
collaborazione con BLG Logistics
Avviso 1
|
Ricerca Operativa |
|||
|
risultati prova scritta del 5
maggio 2009 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
143546 |
B |
26 |
|
2 |
144674 |
B |
insufficiente |
|
3 |
148158 |
A |
insufficiente |
|
4 |
154637 |
A |
25 |
|
5 |
155644 |
B |
21 |
|
6 |
158965 |
B |
18 |
|
7 |
159524 |
B |
26 |
|
8 |
160297 |
B |
insufficiente |
|
9 |
165541 |
A |
18 |
|
10 |
174793 |
A |
21 |
|
11 |
175685 |
A |
insufficiente |
|
12 |
184242 |
A |
18 |