Ricerca Operativa (Ingegneria)
(Prof.
Claudio Arbib)
Materiale
Didattico Integrativo
Temi
di Esame ed Esercizi Proposti
Orario
Martedì
11,00
13.00
I.30
Giovedì
14.00
17.00
I.30
Lezioni
A.A. 2009-2010
Martedì 1 marzo, 11:00-13:00
Introduzione al corso. Origini
della ricerca operativa. Primi problemi e modelli di ottimizzazione: copertura
radar, problema della dieta: formulazione di un modello di programmazione
lineare (PL).
Giovedì 3 marzo, 14:00-15:00
Decisori, variabili di decisione,
obiettivi e vincoli. Il problema del percorso più breve. Formulazione con uso
di variabili binarie, esempio di applicazione.
Martedì 8 marzo, 11:00-13:00
Il problema del percorso più
sicuro, riduzione dal problema del percorso più breve. Cammini hamiltoniani,
esempio di applicazione.
Giovedì 10 marzo, 14:00-17:00
Esempio di applicazione: gestione
ottima di un magazzino industriale. Elementi di geometria di IRn:
richiami sulle operazioni tra vettori, combinazione lineare, affine, conica e convessa;
involucri. Esempi. Norma euclidea. Frontiera di un insieme di punti di IRn,
insiemi chiusi.
Martedì 15 marzo, 11:00-13:00
Rette, segmenti, sfere, iperpiani
e semispazi in IRn, rappresentazione
algebrica. Insiemi convessi e poliedri convessi. Facce e vertici. Esempi. Un
problema di PL in IR2.
Regione ammissibile e direzione di miglioramento.
Giovedì 17 marzo, 14:00-17:00
Poliedri illimitati e problemi di
PL illimitati. Direzioni di un poliedro, cono di recessione, raggi estremi.
Esempi. Rappresentazione algebrica del cono di recessione.
Martedì 22 marzo, 11:00-13:00
Teorema di Weyl (enunciato).
Teorema fondamentale della PL. Esempi.
Giovedì 24 marzo, 14:00-16:00
Punti estremi di un poliedro.
Teorema di caratterizzazione.
Martedì 29 marzo, 11:00-13:00
Riepilogo delle lezioni
precedenti. Forma standard di un problema di PL, base di un problema di PL,
matrice di base, soluzione di base (ammissibile), forma canonica. Esempio: una
fabbrica di tessuti. Criterio di ottimalità della base corrente. Criterio di
illimitatezza. Esempio di miglioramento della base corrente tramite pivot.
Giovedì 31 marzo, 14:00-17:00
Metodo del simplesso, riepilogo ed
esempi.
Martedì 5 aprile, 11:00-13:30
Esercitazione sul metodo del
simplesso. Soluzioni di base degeneri, corrispondenza basi-vertici (enunciato),
esempi. Convergenza finita del metodo: il problema della degenerazione.
Complessità del metodo, cenni sulla complessità della PL.
Giovedì 7 aprile, 14:00-17:00
Proiezione di un poliedro di IRn
in uno spazio di dimensione inferiore. Disuguaglianze implicate.
Martedì 12 aprile, 11:00-13:30
Esercitazione: giochi a somma
zero, formulazione come programmazione lineare.
Giovedì 14 aprile, 14:00-17:00
Soluzione di un sistema di disequazioni
lineari: Teorema di Fourier. Esempi di applicazione.
Martedì 19 aprile, 11:00-13:30
Metodo di Fourier-Motzkin, esempi
ed esercitazione numerica.
Giovedì 28 aprile, 14:00-17:00
Esercitazione sulla formulazione
di problemi di programmazione lineare. Introduzione alla teoria della dualità:
dal Teorema di Fourier al Teorema di Gale. Lemma di Fàrkas. Teorema forte della
dualità.
Lunedì 2 maggio, 15:00-17:30
Prova di esonero.
Martedì 3 maggio, 11:00-13:30
Soluzione degli esercizi proposti.
Riepilogo della lezione precedente. Problema primale e problema duale. Teoremi
di reciprocità, dualità debole, ortogonalità. Problemi inammissibili e
illimitati.
Giovedì 5 maggio, 14:00-17:00
Applicazioni della teoria della
dualità. Modello di sistema di produzione, interpretazione economica del duale,
prezzi impliciti delle risorse; condizioni di ortogonalità e risorse critiche.
Minimizzazione di energia potenziale in un sistema dinamico, il duale come
calcolo della reazione vincolare. Giochi a somma zero e prospettiva
dell’antagonista.
Applicazioni del Metodo di
Fourier-Motzkin: soluzione di un problema di PL. Esercizio numerico.
Martedì 10 maggio, 11:00-13:30
Calcolo dei costi ridotti tramite
il problema duale. Problemi di flusso ottimo, definizioni generali:
distribuzione di flusso, circolazione, divergenza e vettore domanda. Gerarchia
dei problemi di flusso ottimo: funzione obiettivo separabile/lineare. Matrice
di incidenza nodi-archi di un grafo orientato. Rango.
Giovedì 12 maggio, 14:00-17:00
Problema di flusso ottimo con
funzione costo lineare. Teorema di caratterizzazione delle basi. Soluzioni di
base ammissibili. Calcolo di una soluzione iniziale tramite problema ausiliario
(flusso massimo). Determinazione di una prima base e operazione di pivot.
Esempi.
Martedì 17 maggio, 11:00-13:30
Criterio di ottimalità della base
corrente. Calcolo dei costi ridotti tramite i potenziali duali.
Triangolarizzazione della base tramite visita in post-ordine. Esercizio
numerico.
Giovedì 19 maggio, 14:00-17:00
Matrici unimodulari e totalmente
unimodulari. Teorema di interezza delle soluzioni di base. Un criterio di
unimodularità totale. Applicazioni: problemi di flusso ottimo intero, problema
del matching bipartito. Esempi.
Martedì 24 maggio, 11:00-13:30
Algoritmo di Ford-Fulkerson per la
determinazione del massimo (s, t)-flusso. Derivazione
dell’algoritmo dal metodo del simplesso. Capacità del taglio.
Considerazioni sulla natura del problema duale. Esercizio numerico.
Giovedì 26 maggio, 14:00-17:00
Formulazione del problema
dell’(s, t)-cammino di peso minimo come flusso a costo minimo. Condizioni
sul peso dei circuiti. Esempi numerici: effetti della degenerazione.
Martedì 31 maggio, 11:00-13:30
Esercitazione: calcolo della forma
implicita di un involucro tramite il Metodo di Fourier-Motzkin. Calcolo del
duale di un PL. Soluzione di un problema di PL tramite il Metodo di Fourier-Motzkin. Esercizi di
formulazione di PL e PL intera.
Orario di
Ricevimento
Giovedì 10.30-12.30, studio del docente
Appelli
Calendario prove scritte della sessione estiva 2010-2011
|
appello n. |
data |
ora |
aula |
|
1 |
23 giugno 2011 |
15:00 |
1.7 facoltà di Scienze |
|
2 |
7 luglio 2011 |
15:00 |
1.7 facoltà di Scienze |
|
3 |
21 luglio 2011 |
15:00 |
1.7 facoltà di Scienze |
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, percorso critico. Metodo del simplesso su reti.
Applicazioni ed esempi.
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)
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.
Modelli di ottimizzazione
a.
Layout ottimo di circuiti VLSI
b.
Gestione ottima di una centrale termoelettrica
(aggiornato al 26/1/06)
3.
Programmazione lineare
a.
Basi di IRn
b.
Poliedri in IRn (aggiornato al 24/3/11)
c.
Il metodo di Fourier-Motzkin (aggiornato al
7/2/06)
d.
Teoria della dualità (aggiornato al 1/3/06)
e.
Geometria della programmazione lineare (aggiornato
al 14/3/06)
f.
Il metodo del simplesso (aggiornato al 16/3/06)
4.
Programmazione lineare intera
a.
Matrici totalmente unimodulari (aggiornato al
15/5/10)
5.
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.
Metodo del cammino critico (aggiornato
al 25/5/10)
6.
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)
7.
Esercitazioni
a.
Esempi di problemi combinatorici
b.
Sobillazione! (aggiornato al 25/5/10)
c.
Alcuni esercizi svolti (aggiornato al
9/2/06)
d.
Esercitazione sulle formulazioni di PL 0-1 (aggiornato all’8/2/07)
e.
Soluzione degli esercizi non svolti
Temi di
Esame ed Esercizi Proposti
Soluzioni prova scritta del 21 febbraio 2012 (aggiornato al 22 febbraio 2012)
Soluzioni prova scritta del 31 gennaio 2012
Soluzioni prova scritta del 28 settembre 2011
Soluzioni prova scritta del 14 settembre 2011
Soluzioni prova scritta del 23 giugno 2011
Soluzioni prova di esonero del 2 maggio 2011
Soluzioni prova scritta del 24 gennaio 2011
Soluzioni prova scritta del 10 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 21 Giugno 2010 Gruppo A
Soluzioni prova scritta del 21 Giugno 2010 Gruppo B
Soluzioni prova scritta del 12 Febbraio 2009 Gruppo A
Soluzioni prova scritta del 12 Febbraio 2009 Gruppo B
Soluzioni prova scritta del 22 Gennaio 2009 Gruppo A
Altri esercizi proposti
4 febbraio 2002
18 settembre 2001
26 giugno 2001
21 febbraio 2001
5 febbraio 2001
16 gennaio 2001
22 giugno 2000
1 giugno 2000
24 febbraio 2000
20 gennaio 2000
15 settembre 1999
12 luglio 1999
4 giugno 1999
18 febbraio 1999
27 gennaio 1999
16 settembre 1998
21 luglio 1998
30 giugno 1998
2 giugno 1998
25 febbraio 1998
Bacheca
Avviso 13
La prova orale dell’appello
del 21 febbraio 2012 si terrà il giorno mercoledì 29 febbraio 2012 alle ore 11:00
presso lo studio del docente.
|
|
|
|
|
Ricerca Operativa |
||
|
risultati prova scritta del 21
febbraio 2012 |
||
|
|
matricola |
voto |
|
1 |
157395 |
26 |
|
2 |
172567 |
20 |
|
3 |
192535 |
26 |
|
4 |
193435 |
insufficiente |
|
5 |
193878 |
26 |
|
6 |
194791 |
insufficiente |
|
7 |
201513 |
22 |
Avviso 12
La prova orale prevista per lunedì 6 febbraio 2012 è rinviata al 16 febbraio 2012, ore 10:00, presso lo studio del docente.
Avviso 11
Vista la sospensione delle
attività didattiche la prova orale prevista per lunedì 6
febbraio 2012 è rinviata a data da definire.
Avviso 10
La prova orale dell’appello
del 31 gennaio 2012 si terrà il giorno lunedì 6
febbraio 2012 alle ore 11:00 presso lo
studio del docente.
Avviso 9
La prova orale dell’appello
del 7 luglio 2011 si terrà il giorno giovedì 14
luglio 2011 alle ore 10:30 presso
l’aula C1.12 (Coppito2) della Facoltà di Scienze MM.FF.NN.
|
Ricerca Operativa |
|||
|
risultati prova scritta del 7
luglio 2011 |
|||
|
|
matricola |
gruppo |
voto |
|
1 |
179066 |
A |
23 |
|
2 |
184549 |
B |
insufficiente |
|
3 |
188025 |
A |
insufficiente |
Avviso 8
La prova orale dell’appello del 23 giugno 2011 si terrà il giorno mercoledì 29 giugno 2011 alle ore 10:30 presso lo studio del docente in Facoltà di Scienze MM.FF.NN.
|
Ricerca Operativa |
|||
|
risultati prova scritta del 23
giugno 2010 |
|||
|
|
|
|
|
|
|
matricola |
gruppo |
voto |
|
1 |
180339 |
B |
insufficiente |
|
2 |
186675 |
B |
insufficiente |
|
3 |
188025 |
A |
insufficiente |
|
4 |
190725 |
A |
23 |
|
5 |
191107 |
B |
23 |
|
6 |
192046 |
A |
23 |
|
7 |
199203 |
B |
23 |
|
8 |
204203 |
A |
30 |
|
9 |
206889 |
B |
29 |
|
10 |
207339 |
A |
28 |
|
11 |
207421 |
B |
28 |
|
12 |
209700 |
B |
30 |
|
13 |
209737 |
A |
29 |
|
14 |
209879 |
A |
24 |
Avviso 7
Il ricevimento studenti prima della prova parziale si terrà il giorno mercoledì 22 giugno 2011 alle ore 15:00.
Avviso 6
Il calendario degli esami della sessione estiva è disponibile nella
sezione appelli. Per maggiori informazioni consultare il sito http://informatica.di.univaq.it/
Avviso 5
|
Ricerca Operativa |
||
|
risultati prova d'esonero del 2
maggio 2011 |
||
|
n. |
matricola |
voto |
|
1 |
188025 |
insufficiente |
|
2 |
192046 |
insufficiente |
|
3 |
206889 |
18 |
|
4 |
207588 |
25 |
|
5 |
209737 |
19 |
|
6 |
209879 |
insufficiente |
Avviso 4
La prima prova d’esonero si
terrà il giorno 2 maggio 2011 alle ore 15:00 in aula 1.7 (Facoltà di Scienze MM.FF.NN.).
Avviso 3
La lezione del giorno giovedì 7
aprile sarà limitata a un’ora (dalle 14:00 alle 15:00) per impegni
istituzionali del docente.
Avviso 2
La lezione del giorno giovedì 3
marzo sarà limitata a un’ora (dalle 14:00 alle 15:00) per impegni
istituzionali del docente.
Avviso 1
Le lezioni del corso di ricerca
operativa inizieranno martedì 1° marzo.