Ricerca Operativa (Informatica, Matematica)

(Prof. Claudio Arbib)


Orario

Lezioni

Orario di Ricevimento

Appelli

Programma

Testi di Riferimento

Materiale Didattico Integrativo

Temi di Esame ed Esercizi Proposti

Bacheca

 


Orario

Martedì

11:30

13:30

Aula Magna

Mercoledì

15:00

17:00

Aula Magna

Giovedì

15:00

17:00

Aula Magna

Top

 


Lezioni

11 gennaio 2007

Introduzione al corso, origini e applicazioni della ricerca operativa

16 gennaio 2007

Esempi di modelli e problemi di ottimizzazione: gestione di una centrale termoelettrica

17 gennaio 2007

Esempi di modelli e problemi di ottimizzazione: realizzazione di una funzione booleana tramite matrice logica programmabile. Elementi di teoria dei grafi: definizioni generali; clique e insieme stabile.

18 gennaio 2007

Elementi di teoria dei grafi: passeggiate, cammini, circuiti, percorsi e cicli; grafi d-regolari, esempi; grafi bipartiti; caratterizzazione dei grafi bipartiti (enunciato).

23 gennaio 2007

Caratterizzazione dei grafi bipartiti (dimostrazione). Esempi: grafi privi di cicli, grafi d-regolari bipartiti. Grafi simmetrici connessi. Colorazione. Grafi planari e teorema dei 4 colori (enunciato). Numero cromatico e numero di clique.

25 gennaio 2007

Altri invarianti: numero di stabilità, diametro, indice cromatico. Calcolare un invariante significa risolvere un problema di ottimizzazione combinatoria. Esempio: numero di clique. Trovare una clique massima risolvendo un problema di programmazione lineare intera.

30 gennaio 2007

Problemi di ottimizzazione combinatoria, definizioni generali ed esempi: insieme stabile, matching, edge cover, insieme dominante, knapsack 0-1. Algoritmo universale. Limiti dell’algoritmo universale.

31 gennaio 2007

L’algoritmo greedy: codifica incrementale e decrementale, problemi subclusivi e non. Limiti dell’algoritmo greedy. Esempi: knapsack 0-1, insieme stabile, matching, albero ricoprente. Proprietà di scambio e insiemi massimali. Teorema di Rado, matroidi. Esempi di matroide: matroide grafico, matroide partizione.

1 febbraio 2007

Esercitazione su grafi. Combinazione lineare, affine, conica e convessa di vettori di IRn. Involucro affine, conico e convesso di un insieme di vettori di IRn. Basi. Rappresentazione di un vettore in una data base, teorema di unicità della rappresentazione. Teorema di sostituzione.

6 febbraio 2007

Richiami su combinazione lineare, dipendenza e indipendenza lineare. Teorema di Steinitz, matroide vettoriale. Esercitazione: formulazione di insieme stabile, clique, colorazione ed edge-cover come programmazione lineare 0-1.

7 febbraio 2007

Formulazione di problemi di programmazione lineare 0-1: albero ricoprente, commesso viaggiatore.

8 febbraio 2007

Formulazione di problemi di programmazione lineare 0-1: alcuni temi d’esame. Poliedri di IRn: poliedri compatibili, diseguaglianze implicate. Proiezione di un poliedro: definizione ed esempi.

15 febbraio 2007

Prova intermedia di autovalutazione.

20 febbraio 2007

Proiezione di un poliedro: Teorema di Fourier. Come stabilire se un poliedro è vuoto: il metodo di Fourier-Motzkin.

21 febbraio 2007

Esercitazione sul metodo di Fourier-Motzkin. Determinazione di una soluzione di un sistema di disequazioni lineari; soluzione di un problema di programmazione lineare.

22 febbraio 2007

Uso del metodo di Fourier-Motzkin per il calcolo della forma implicita di conv(S), per S finito in IRn.

27 febbraio 2007

Teoremi dell’alternativa: dal Teorema di Fourier al Teorema di Gale. Lemma di Farkas. Esempi.

28 febbraio 2007

Teorema forte della dualità, il problema duale. Esempi. Teorema di reciprocità, teorema debole della dualità.

1 marzo 2007

Alcuni corollari: condizioni di complementarità primale-duale. Come scrivere il duale di un generico problema di programmazione lineare. Esempi.

6 marzo 2007

Giochi a somma zero. Formulazione max-min e interpretazione del problema duale. Programmazione lineare: direzione di miglioramento in un poliedro.

7 marzo 2007

Teorema fondamentale della programmazione lineare. Il metodo del simplesso: soluzioni di base (ammissibili), criterio di ottimalità.

8 marzo 2007

Il metodo del simplesso: miglioramento della base corrente, operazione di pivot. Criterio di illimitatezza. Un esempio.

13 marzo 2007

Esercitazione sul metodo del simplesso. Fase I del metodo: determinazione di una base ammissibile iniziale attraverso il problema ausiliario.

14 marzo 2007

Esercitazione: formulazione di problemi di programmazione lineare. Acquistare l’auto ideale: calcolo di iperpiani di regressione. Programmazione di un palinsesto televisivo.

 

Top

 


Orario di Ricevimento

Mercoledì dalle 17:30 alle 18:30

Top

 


Appelli

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

(Argomenti complementari: 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. Base per un insieme di vettori. Teorema di rappresentazione. Teorema di Steinitz.

 

Problemi combinatorici e di ottimizzazione combinatorica

Definizioni fondamentali. L’algoritmo (enumerativo) universale e la sua complessità. Problemi subclusivi e superclusivi. Esempi: knapsack 0-1, edge-cover, insieme stabile, albero ricoprente, matching (perfetto) etc. L’algoritmo ingordo: pseudocodice per problemi subclusivi e superclusivi. Proprietà di scambio e sue implicazioni sulla cardinalità delle soluzioni massimali. Limiti dell’algoritmo ingordo. Teorema di Rado, matroidi. Esempi: matroide banale, matroide grafico, matroide partizione, matroide vettoriale.

 

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.

Top


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)

C.H. Papadimitriou, K.E. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover Publications (1999), cap. 12 "Spanning Trees and Matroids"

Top

 


Materiale Didattico Integrativo

1.                Introduzione al corso

2.                Ottimizzazione combinatoria (aggiornato al 31/1/06)

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

4.                Modelli di ottimizzazione

a.      Layout ottimo di circuiti VLSI

b.      Gestione ottima di una centrale termoelettrica (aggiornato al 26/1/06)

5.                Basi di IRn

6.                Poliedri in IRn: il metodo di Fourier-Motzkin (aggiornato al 7/2/06)

7.                Teoria della dualità (aggiornato al 1/3/06)

8.                Geometria della programmazione lineare (aggiornato al 14/3/06)

9.                Il metodo del simplesso (aggiornato al 16/3)

10.            Approfondimenti

a.      Geometria del simplesso (aggiornato al 16/3)

b.      Esercitazione sugli iperpiani di regressione (aggiornato al 17/3)

c.      Esercitazione sui giochi a somma zero (aggiornato al 17/3)

 

Top

 


Temi di Esame ed Esercizi Proposti

Soluzioni prova scritta del 05 Febbraio 2008 Gruppo A (!! aggiornato al 06/02/08)

Soluzioni prova scritta del 05 Febbraio 2008 Gruppo B (!! aggiornato al 06/02/08)

Soluzioni prova scritta del 22 Gennaio 2008 Gruppo A (!! aggiornato al 24/01/08)

Soluzioni prova scritta del 22 Gennaio 2008 Gruppo B (!! aggiornato al 24/01/08)

Soluzioni prova scritta del 22 Novembre 2007  (!! aggiornato al 28/11/07)

Soluzioni prova scritta del 3 luglio 2007 Gruppo A (!! aggiornato al 03/07/07)

Soluzioni prova scritta del 3 luglio 2007 Gruppo B (!! aggiornato al 03/07/07)

Soluzioni prova scritta del 22 marzo 2007 Gruppo A (!! aggiornato al 26/3/07)

Soluzioni prova scritta del 22 marzo 2007 Gruppo B (!! aggiornato al 06/6/07)

Prova intermedia del 15 febbraio 2007 Gruppo A

Prova intermedia del 15 febbraio 2006 Gruppo B

Soluzioni prova scritta del 21 dicembre 2006 Gruppo A

Soluzioni prova scritta del 21 dicembre 2006 Gruppo B

Soluzioni prova scritta del 19 settembre 2006 Gruppo A 

Soluzioni prova scritta del 19 settembre 2006 Gruppo B

Soluzioni prova scritta del 12 luglio 2006 Gruppo A

Soluzioni prova scritta del 12 luglio 2006 Gruppo B

Soluzioni prova scritta del 22 marzo 2006 Gruppo A

Soluzioni prova scritta del 22 marzo 2006 Gruppo B

Prova intermedia del 16 febbraio 2006 Gruppo A (solo testo)

Prova intermedia del 16 febbraio 2006 Gruppo B (solo testo)

Soluzioni prova intermedia del 16 febbraio 2006 Gruppo A

Soluzioni prova intermedia del 16 febbraio 2006 Gruppo B

Soluzioni prova scritta del 12 dicembre 2005 Gruppo A

Soluzioni prova scritta del 12 dicembre 2005 Gruppo B

Soluzioni prova scritta del 20 settembre 2005 Gruppo A

Soluzioni prova scritta del 20 settembre 2005 Gruppo B

Soluzioni prova scritta del 6 luglio 2005 Gruppo A

Soluzioni prova scritta del 6 luglio 2005 Gruppo B

Soluzioni prova scritta del 5 aprile 2005 Gruppo A

Soluzioni prova scritta del 5 aprile 2005 Gruppo B

Soluzioni prova intermedia del 17 febbraio 2005 Gruppo A

Soluzioni prova intermedia del 17 febbraio 2005 Gruppo B

Soluzioni prova scritta del 6 dicembre 2004 Gruppo A

Soluzioni prova scritta del 6 dicembre 2004 Gruppo B

Soluzioni prova scritta del 22 settembre 2004 Gruppo A

Soluzioni prova scritta del 22 settembre 2004 Gruppo B

Soluzioni prova scritta del 13 luglio 2004 Gruppo A

Soluzioni prova scritta del 13 luglio 2004 Gruppo B

Soluzioni prova scritta del 13 luglio 2004 Gruppo C

Soluzioni prova scritta del 13 luglio 2004 Gruppo D

Soluzioni prova scritta del 31 marzo 2004 Gruppo A I parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo A II parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo B I parte  

Soluzioni prova scritta del 31 marzo 2004 Gruppo B II parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo C I parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo C II parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo D I parte

Soluzioni prova scritta del 31 marzo 2004 Gruppo D II parte

Soluzioni prova scritta intermedia del 19 febbraio 2004 GRUPPO A

Soluzioni prova scritta intermedia del 19 febbraio 2004 GRUPPO B

Soluzioni prova scritta intermedia del 19 febbraio 2004 GRUPPO C

Soluzioni prova scritta intermedia del 19 febbraio 2004 GRUPPO D

Soluzioni prova scritta del 23 Settembre 2003

Soluzioni prova scritta finale del 22 Luglio 2003 Gruppo A

Soluzioni prova scritta finale del 22 Luglio 2003 Gruppo B

Soluzioni prova scritta finale del 22 Luglio 2003 Gruppo C

Soluzioni prova scritta finale del 22 Luglio 2003 Gruppo D

Soluzioni prova scritta finale del 25 Marzo 2003 Gruppo A

Soluzioni prova scritta finale del 25 Marzo 2003 Gruppo B

Soluzioni prova scritta finale del 25 Marzo 2003 Gruppo C

Soluzioni prova scritta finale del 25 Marzo 2003 Gruppo D

Soluzioni prova scritta intermedia del 12 febbraio 2003 Gruppo A

Soluzioni prova scritta intermedia del 12 febbraio 2003 Gruppo B

Soluzioni prova scritta intermedia del 12 febbraio 2003 Gruppo C

Soluzioni prova scritta intermedia del 12 febbraio 2003 Gruppo D

 

Altri esercizi proposti

20 marzo 2003

Soluzione 20 marzo 2004

12 marzo 2003

Soluzione 12 marzo 2003

4 marzo 2003

Soluzione 4 marzo 2003

25 febbraio 2003

Soluzione 25 febbraio 2003

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 1998
02 giugno 1998
25 febbraio 1998

Top

 


Bacheca

 

Avviso 19

Le prove orali si terranno mercoledì 20 Febbraio 2008 alle 10:00 in aula da definire.

 

Avviso 18

 

Elenco ammessi all'appello del 5 Febbraio 2008
n. Matricola Gruppo Voto
1 150411 B 20
2 150610 B 21
3 136520 B 20
4 151107 A 22
5 155448 B 21
6 156073 A 20
7 166657 B 21
8 150324 A 22
9 144272 A 21
10 155779 A 20
11 150989 B 18
12 143733 A 20
13 147606 A 22

 

Avviso 17

 

Risultati prova scritta del 22 gennaio 2008
n. matricola gruppo voto
1 119375 A insuff
2 136520 A insuff
3 142317 B 21
4 144272 B insuff
5 146496 A insuff
6 147606 A insuff
7 150169 B insuff
8 150401 B insuff
9 150411 B insuff
10 150610 B insuff
11 150989 A insuff
12 151365 B 24
13 152324 B insuff
14 152945 A 25
15 153008 B insuff
16 154583 A 18
17 154847 A 25
18 155474 B insuff
19 155641 B insuff
20 155774 B insuff
21 155858 A 23
22 156073 B insuff
23 166657 A insuff
24 177164 A 22

 

Avviso 16

Le prove orali si terranno mercoledì 30 Gennaio 2008 alle 10:00 in aula da definire.

 

Avviso 15

 

Risultati prova scritta del 22 novembre 2007

n.

matricola

voto

1

146437

insufficiente

2

152481

23

3

154583

insufficiente

4

133120

23

5

155551

26

 

 

Avviso 14

Le prove orali si terranno mercoledì 28 novembre 2007 alle 16:00 in aula da definire.

 

Avviso 13

 

 

Risultati prova scritta del 19 settembre 2007

n.

Matricola

Gruppo

Voto

1

133120

A

insuff

2

136057

A

insuff

3

140713

B

insuff

4

142363

B

19

5

143618

B

24

6

143631

A

18

7

144276

B

22

8

146437

B

insuff

9

146456

A

insuff

10

146725

B

insuff

11

147029

B

24

12

147986

A

18

13

148436

A

23

14

150069

A

28

15

151054

B

20

16

151474

A

26

17

152481

B

23

18

152945

B

insuff

19

153183

A

insuff

20

154564

B

22

21

154657

A

18

22

155448

B

22

23

155779

B

insuff

24

155858

A

insuff

25

156073

B

22

26

156085

B

insuff

27

159739

A

24

28

160041

B

25

29

165541

A

insuff

30

166657

A

23

31

171513

A

insuff

32

177164

A

insuff

 

Avviso 12

Le prove orali si terranno martedì 25 settembre 2007 alle 10:00 in aula da definire. I risultati della prova scritta del 19 settembre 2007 saranno resi noti in serata di oggi.

 

Avviso 11

Risultati prova scritta del 3 luglio 2007

n.

Matricola

Gruppo

Voto

1

133120

A

insuff

2

139211

A

26

3

140713

A

insuff

4

141730

A

18

5

142363

B

insuff

6

143096

A

24

7

143618

B

insuff

8

143631

B

insuff

9

144184

B

20

10

144460

B

19

11

146437

A

insuff

12

146496

A

insuff

13

146725

A

insuff

14

146882

B

22

15

147986

B

insuff

16

148858

B

26

17

149023

B

21

18

149838

A

insuff

19

150069

A

insuff

20

150305

B

20

21

151054

B

18

22

151229

A

21

23

151443

B

20

24

151603

B

20

25

152224

A

insuff

26

152481

A

insuff

27

152726

A

25

28

152913

B

20

29

153008

B

insuff

30

153090

A

insuff

31

153183

A

insuff

32

154527

A

18

33

154604

A

19

34

154650

A

20

35

154657

A

insuff

36

155551

B

18

37

155779

B

insuff

38

155858

B

insuff

39

156073

A

20

40

156950

B

20

41

157840

A

24

42

159611

B

insuff

43

159653

A

30

44

161481

A

26

45

162488

B

23

46

171513

B

insuff

47

171518

A

25

 

 

 

 

 

Avviso 10

Le prove orali si terranno venerdì 6 luglio 2007 alle 10:00 in aula da definire.

 

Avviso 9

Le prove orali si terranno mercoledì 28 marzo alle 10:00 in aula da definire.

 

Avviso 8

 

Risultati prova scritta del 22 marzo 2007

n.

Matricola

Gruppo

Voto

1

133120

B

insuff

2

138469

A

insuff

3

140569

B

24

4

140713

B

insuff

5

143618

B

insuff

6

144048

A

20

7

144184

B

insuff

8

144276

B

insuff

9

144460

B

18

10

144530

B

24

11

146387

B

insuff

12

146725

B

insuff

13

146891

A

21

14

146999

B

19

15

147029

A

insuff

16

147070

A

19

17

149023

B

insuff

18

150125

B

22

19

150169

B

insuff

20

150279

B

insuff

21

150297

B

23

22

150303

A

insuff

23

150305

B

insuff

24

150610

B

insuff

25

150989

A

insuff

26

151107

B

20

27

151229

B

21

28

151443

B

insuff

29

151469

A

21

30

151474

B

insuff

31

151522

A

20

32

151603

A

insuff

33

151780

B

19

34

152324

A

insuff

35

152481

A II parte

27

36

152726

B

20

37

152873

A

20

38

152913

A

insuff

39

153090

B

insuff

40

153183

A

insuff

41

154527

B

19

42

154604

A

20

43

154657

B

insuff

44

154779

B

23

45

154849

B

25

46

155134

B

22

47

155262

B

20

48

155414

B

18

49

155641

B

insuff

50

155779

B

insuff

51

155858

B

insuff

52

156073

B

insuff

53

156950

A

insuff

54

156970

A

insuff

55

157603

B

26

56

157639

B

25

57

157907

A

insuff

58

159026

B

21

59

159512

A

25

60

159631

B II parte

26

61

159654

A II parte

24

62

165421

B

insuff

63

165541

A

insuff

64

165569

B II parte

insuff

65

165727

A II parte

18

66

165770

A

insuff

67

165991

A

insuff

68

166657

A II parte

insuff

69

168088

B

insuff

70

171513

B

insuff

71

171518

A

insuff

72

177164

A

insuff

73

177488

B

20

 

Avviso 7

Martedì 20 marzo dalle 15:00 alle 17:00 si terrà in aula magna unesercitazione straordinaria propedeutica alla prova scritta. Il ricevimento studenti del 21 marzo è anticipato al 20 marzo, dalle 17:00 alle 18:30.

 

Avviso 6

Valutazione del corso da parte degli studenti (sommario su 67 risposte, A.A. 2006-07)

 

 

Avviso 5

La prova scritta di ricerca operativa valida per l’a.a. 2006/07 si terrà il giorno 22 marzo 2007 alle ore 15:00 in aula magna. Si raccomanda di prenotarsi per tempo in modo da facilitare la gestione della prova. Le prove orali avranno luogo immediatamente dopo la correzione degli elaborati, in aula da definire.

 

Avviso 4

Risultati della prova scritta del 15 Febbraio u.s.    

Matricola

Voto

152481

29

159611

19

159631

25

159653

18

159657

30 lode

162488

insuff

165421

insuff

165425

insuff

165541

insuff

165569

20

165727

19

165753

19

165991

insuff

166657

18

168088

insuff

168640

insuff

171518

insuff

 

 

Avviso 3

Ascolta il Lemma di Fàrkas! http://www.aardvarks.org/index.php?id=115

 

Avviso 2

La prova di autovalutazione intermedia del corso di ricerca operativa si terrà giovedì 15 febbraio 2007 alle ore 15 nelle aule 2.4 e 2.5 (salvo diverso avviso).

La prova può essere sostenuta solamente da studenti in corso nell’A.A. 2006-07, ovvero da studenti trasferiti da corsi di laurea di altre facoltà che non abbiano acquisito la frequenza del corso di ricerca operativa presso la facoltà di Scienze dell’Università di L’Aquila.

 

Avviso 1

Il giorno 24 gennaio le lezioni saranno sospese per consentire lo svolgimento della sessione di laurea.

 

Top