Risultati prova scritta del 9 se

Formulazione del problema del percorso più breve in termini di programmazione lineare intera. Decisori, variabili di decisione, obiettivi e vincoli. Discussione.

Lunedì 10 marzo, 14:00-16:00

Problema del percorso più sicuro, riduzione dal problema del percorso più breve. Cammini hamiltoniani, esempio di applicazione. Altri esempi di applicazione: gestione ottima di un magazzino industriale, dispatching di energia termoelettrica, taglio ottimo di materiali.

Martedì 15 marzo, 14:00-16:00

Elementi di geometria di IRⁿ: richiami sulle operazioni tra vettori, combinazione lineare, affine, conica e convessa; involucri. Esempi. Norma euclidea. Frontiera di un insieme di punti di IRⁿ, insiemi chiusi.

Lunedì 17 marzo, 14:00-16:00

Rette, segmenti, sfere, iperpiani e semispazi in IRⁿ, rappresentazione algebrica. Insiemi convessi e poliedri convessi. Facce e vertici. Esempi.

Martedì 22 marzo, 14:00-16:00

Un problema di PL in IR². Regione ammissibile e direzione di miglioramento. Poliedri illimitati e problemi di PL illimitati. Direzioni di un poliedro, cono di recessione, raggi estremi. Esempi. Rappresentazione algebrica del cono di recessione. Teorema di Weyl (enunciato). Esempi. Teorema fondamentale della PL (enunciato).

Lunedì 28 marzo, 14:00-16:00

Teorema fondamentale della PL (dimostrazione). Punti estremi di un insieme convesso, identità di punti estremi e vertici (enunciato), caratterizzazione dei punti estremi di un poliedro (enunciato e dimostrazione). Dipendenza e indipendenza lineare, rango di un insieme di vettori e di una matrice, determinante, basi per un insieme di IRⁿ.

Martedì 29 marzo, 14:00-16:00

Riepilogo della lezione precedente. 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.

Lunedì 4 aprile, 14:00-16:00

Miglioramento della base corrente tramite operazione di pivot. Schema del metodo del simplesso (Fase II), esempi. Soluzioni di base degeneri.

Martedì 5 aprile, 14:00-16:00

Ancora sulle basi degeneri: esempi. Convergenza finita del metodo del simplesso, il problema della degenerazione. Complessità del metodo, cenni sulla complessità della PL. Determinazione di una soluzione di base iniziale (Fase I): problema ausiliario.

Lunedì 11 aprile, 11:30-13:30

Esistenza di una soluzione ammissibile e condizioni di ottimalità del problema ausiliario. Esercitazione. Giochi a somma zero: truccare un dado, selezionare un portafoglio titoli; formulazione come programmazione lineare.

Martedì 12 aprile, 14:00-16:00

Esercitazione sul metodo del simplesso.

Lunedì 18 aprile, 11:30-13:30

Soluzione di un sistema di disequazioni lineari. Proiezione di un insieme di IRⁿ. Teorema di Fourier. Esempi di applicazione.

Martedì 19 aprile, 14:00-16:00

Metodo di Fourier-Motzkin, esempi ed esercitazione numerica.

Martedì 26 aprile, 14:00-16:00

Applicazioni del metodo di Fourier-Motzkin. Esempi ed esercizi.

Lunedì 2 maggio, 15:00-17:30

Prova di esonero.

Martedì 3 maggio, 14:00-16:00

Soluzione degli esercizi proposti. Teoremi dell’alternativa: dal Teorema di Fourier al Teorema di Gale. Lemma di Fàrkas.

Martedì 10 maggio, 14:00-16:00

Teoria della dualità: Teorema forte della dualità teoremi di reciprocità e dominanza (dualità debole), condizioni di ortogonalità, inammissibilità e illimitatezza. Esempi.

Lunedì 16 maggio, 14:00-16: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.

Martedì 17 maggio, 14:00-16:00

Richiami di ottimizzazione combinatoria: problema del matching, dell’insieme stabile, della copertura con archi/nodi, dello zaino. Problemi di ottimizzazione combinatoria, algoritmo universale e algoritmo greedy. Limiti dell’algoritmo universale e dell’algoritmo greedy. Sub-ottimalità dell’algoritmo greedy, costruzione di un’istanza mal condizionata. Caratterizzazione dell’algoritmo greedy: Teorema di Rado (enunciato).

Lunedì 23 maggio, 14:00-16:00

Dimostrazione del Teorema di Rado. Casi particolari: matroide grafico, banale, partizione. Un’applicazione del matroide partizione a un problema di produzione industriale.

Martedì 24 maggio, 14:00-16:00

Problemi di flusso ottimo. Divergenza e potenziale. Reti conservative. Relazioni fondamentali: differenza di potenziale. Funzione costo separabile. Problemi lineari e relativi parametri: vettore di domanda, matrice di incidenza nodi-archi della rete, soglia e capacità. Rango della matrice di incidenza, caratterizzazione degli insiemi di colonne linearmente indipendenti (dimostrazione).

Lunedì 30 maggio, 14:00-16:00

Problema di flusso a costo minimo su rete conservativa. Problemi non capacitati: calcolo di una soluzione ammissibile, trasformazione in soluzione di base, calcolo dei potenziali e dei costi ridotti fuori base.

Martedì 31 maggio, 14:00-16:00

Problemi di flusso a costo minimo su rete conservativa. Problemi non capacitati: aggiornamento della base corrente. Esercizi ed esempi. Formulazione del problema dell’(s, t)-cammino di peso minimo come ottimo su reti. Condizione sul peso dei circuiti.

Lunedì 6 giugno, 14:00-16:00

Problema di flusso a costo minimo su rete conservativa con soglie e capacità. Trasformazione in problemi con soglia nulla. Forma standard e soluzioni di base. Calcolo dei costi ridotti e criterio di ottimalità. Esempio numerico.

Martedì 7 giugno, 14:00-16:00

Problemi di (s, t)-cammino minimo e (s, t)-flusso massimo: soluzione tramite simplesso su reti, semplificazioni nel calcolo. Relazioni con algoritmi noti (Dijkstra, Ford-Fulkerson). Interpretazione del duale del problema di flusso massimo. Effetti della degenerazione.

Lunedì 13 giugno, 14:00-16:00

Diagrammi di Gantt e reti di attività. Tempi di raggiungimento dei nodi. Attività critiche e cammini critici. Calcolo del cammino critico. Assegnazione di risorse ad attività con vincolo temporale sul completamento del programma: formulazione come programmazione lineare.

Esercitazione sul metodo di Fourier-Motzkin: come decidere se un poliedro è o no incompatibile, calcolo di una soluzione ove esista, corrispondenza geometrica; soluzione di un problema di programmazione lineare; calcolo della forma implicita di un involucro. Esempi numerici.

Top

Orario di Ricevimento

Giovedì

10.30

12.30

studio del docente

Top

Appelli

Calendario prove scritte della sessione estiva 2010-2011

appello n.	data	ora	aula
1	23 giugno 2011	15:00	1.7
2	7 luglio 2011	15:00	1.7
3	21 luglio 2011	15:00	1.7

Top

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 IRⁿ: 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.

Top

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, Belmont, Massachusetts (1997)

Top

Materiale Didattico Integrativo

1. Introduzione al corso

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 IRⁿ

b. Poliedri in IRⁿ (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)

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)

Top

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 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

Top

Bacheca

Avviso 14

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 13

La prova orale prevista per lunedì 6 febbraio 2012 è rinviata al 16 febbraio 2012, ore 10:00, presso lo studio del docente.

Avviso 12

Vista la sospensione delle attività didattiche la prova orale prevista per lunedì 6 febbraio 2012 è rinviata a data da definire.

Avviso 11

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.

Ricerca Operativa
risultati prova scritta del 31 gennaio 2012
	matricola	voto
1	146725	18
2	172913	21
3	187123	19
4	195953	25

Avviso 10

La prova orale dell’appello del 21 novembre 2011 si terrà il giorno lunedì 28 novembre 2011 alle ore 15:00 presso lo studio del docente.

Avviso 9

La prova orale dell’appello del 28 settembre 2011 si terrà il giorno mercoledì 5 ottobre 2011 alle ore 10:30 presso lo studio del docente.

Ricerca Operativa
risultati prova scritta del 28 settembre 2011
n.	matricola	voto
1	146725	insufficiente
2	157292	19
3	165541	18
4	168202	insufficiente
5	172811	insufficiente
6	173469	19
7	175685	18
8	186868	27
9	188786	20
10	189426	18
11	195953	19
12	200449	24

Avviso 8

La prova orale dell’appello del 14 settembre 2011 si terrà il giorno giovedì 22 settembre 2011 alle ore 10:30 presso lo studio del docente.

Ricerca Operativa
risultati prova scritta del 14 settembre 2011
	matricola	gruppo	voto
1	157292	B	insufficiente
2	187192	A	18
3	188786	A	insufficiente
4	194791	A	insufficiente

Avviso 7

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	I prova	II prova	voto
1	207588	B	25	23	24
1	150863	A			21
2	160967	A			21
3	165541	B			23
4	168202	B			insufficiente
5	172811	A			insufficiente
6	172985	B			18
7	173106	A			22
8	173469	A			18
9	175685	B			22
10	176928	A			20
11	179066	A			23
12	180339	B			24
13	186675	B			19
14	188826	B			insufficiente
15	189898	B			20
16	190725	A			18
17	193386	B			19
18	193401	A			20
19	193438	B			21
20	196139	A			18
21	197252	A			21
22	200910	A			19

Avviso 6

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.

Ricerca Operativa
risultati prova scritta del 23 giugno 2010
	matricola	gruppo	I prova	II prova	voto
1	179233	A	30 e lode	30	30 e lode
2	193474	B	30 e lode	28	30 e lode
3	193387	A	28	28	29
4	197606	B	18	30	27
5	151275	B	28	30	30 e lode
6	193466	A	24	30	28
7	193116	B	26	21	24
1	148158	A		18
2	150863	B		insufficiente
3	154919	A		19
4	156169	B		27
5	159936	B		26
6	165541	A		insufficiente
7	168045	A		18
8	176928	B		insufficiente
9	188786	B		insufficiente
10	188826	A		insufficiente
11	189891	B		26
12	193386	A		19
13	193401	A		19
14	195352	A		21
15	197640	A		25
16	200972	B		28
17	207427	B		28

Avviso 5

Il ricevimento studenti prima della prova parziale si terrà il giorno mercoledì 22 giugno 2011 alle ore 15:00.

Avviso 4

Il calendario degli esami della sessione estiva è disponibile nella sezione appelli. Per maggiori informazioni consultare il sito http://informatica.di.univaq.it/

Avviso 3

Ricerca Operativa
prova d'esonero del 2 maggio 2011
n.	matricola	voto
1	151275	28
2	172985	insuff
3	173106	21
4	179233	30 lode
5	180583	insuff
6	193116	26
7	193387	28
8	193466	24
9	193474	30 lode
10	197606	18
11	197640	insuff
12	207427	insuff

Avviso 2

La prima prova d’esonero si terrà il giorno 2 maggio 2011 alle ore 15:00 in aula 1.7.

Avviso 1

Le lezioni del corso di ricerca operativa inizieranno lunedì 7 marzo 2011.

Top


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