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ì

9:30

11:30

Aula Magna

Mercoledì

15:00

17:00

Aula Magna

Giovedì

17:00

19:00

Aula Magna

Top


Lezioni

mercoledì 11 gennaio 2006

Introduzione al corso: origini della ricerca operativa, problemi logistici, problemi e modelli di ottimizzazione. Esempi.

giovedì 12 gennaio 2006

Campi di applicazione della ricerca operativa.

martedì 17 gennaio 2006

Un modello di ottimizzazione: layout di matrici logiche programmabili, dal problema concreto al suo modello matematico

mercoledì 18 gennaio 2006

Problemi combinatorici e problemi di ottimizzazione combinatoria. Esempi: knapsack 0-1, insieme stabile, edge-cover, insieme dominante, albero ricoprente, matching. Applicazioni.

giovedì 19 gennaio 2006

Altri esempi di problemi di ottimizzazione combinatoria: il problema del cammino minimo. Applicazioni: pianificazione della produzione di energia elettrica, il problema generale.

martedì 24 gennaio 2006

Pianificazione della produzione di energia elettrica, gestione di una singola centrale termoelettrica. Algoritmi elementari per problemi di ottimizzazione combinatoria. L’algoritmo universale e i suoi limiti. L’algoritmo greedy. Esempi.

mercoledì 25 gennaio 2006

Limiti dell’algoritmo greedy. Problemi subclusivi e superclusivi. Esempi. Proprietà di scambio.

giovedì 26 gennaio 2006

Caratterizzazione dell’algoritmo greedy. Matroidi. Esempi di matroide: matroide banale, matroide grafico.

martedì 31 gennaio 2006

Applicazione dell’algoritmo greedy: un problema di ottimizzazione nella fabbricazione di cristalli automobilistici. Il problema dell’assegnamento di peso minimo: matroide partizione. Esercizi.

mercoledì 1 febbraio 2006

Combinazione lineare, affine, conica e convessa di vettori in IRn. Esempi. Basi in IRn. Teorema di rappresentazione. Teorema di Steinitz.  Matroide vettoriale.

giovedì 2 febbraio 2006

Esercitazione: matroidi, formulazione di problemi di ottimizzazione combinatoria come programmazione lineare 0-1.

martedì 7 febbraio 2006

Iperpiani, semispazi chiusi e poliedri in IRn. Diseguaglianze implicate, combinazione conica di diseguaglianze. Proiezione di un poliedro. Teorema di Fourier (enunciato).

mercoledì 8 febbraio 2006

Dimostrazione del Teorema di Fourier. Applicazioni: metodo di eliminazione di Fourier-Motzkin. Un esempio.

giovedì 9 febbraio 2006

Esercizi di applicazione del metodo di Fourier-Motzkin: decidere se un poliedro è vuoto oppure no, risolvere un problema di programmazione lineare, calcolare la forma implicita di conv(S) per un insieme finito S di IRn.

giovedì 23 febbraio 2006

Forma standard di un problema di programmazione lineare. Riduzione a forma standard; esempi. Teorema di dualità forte (enunciato).

martedì 28 febbraio 2006

Esercitazione sul teorema di dualità forte; il problema della dieta.

mercoledì 1 marzo 2006

Dimostrazione del teorema di dualità forte. Teorema di reciprocità. Teorema di dualità debole. Corollari e condizioni di complementarità. Problemi illimitati.

martedì 7 marzo 2006

Iperpiani in IRn: analisi di alcune proprietà geometriche. Analisi di un sistema dinamico (caduta di un grave in uno spazio soggetto a vincoli) come problema di programmazione lineare; il problema duale. Direzioni di un poliedro, cono di recessione, descrizione algebrica ed esempi.

mercoledì 8 marzo 2006

Teorema di Weyl (enunciato). Teorema fondamentale della programmazione lineare. Esempi.

giovedì 9 marzo 2006

Basi e soluzioni (ammissibili) di base. Problema in forma standard e problema associato in forma generale. Metodo del simplesso: forma canonica, criteri di ottimalità e illimitatezza. Esempi.

martedì 14 marzo 2006

Geometria del metodo del simplesso. Corrispondenza basi-vertici. Miglioramento della base corrente: operazione di pivot e corrispondente geometrico.

mercoledì 15 marzo 2006

Determinazione di una base ammissibile iniziale (Fase I del metodo del simplesso) tramite soluzione del problema ausiliario. Esempi.

giovedì 16 marzo 2006

Formulazione di problemi di programmazione lineare e risoluzione tramite il metodo del simplesso: giochi a somma zero (gestione di un portafoglio di titoli); iperpiani di regressione (scelta dell’auto ideale).

Top


Orario di Ricevimento

Mercoledì dalle 17:30 alle 18:30

Top


Appelli

I appello (inizio prove): mercoledì 22 marzo 2006, ore 10:30, aula da definire

 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)

3.                Esercitazioni

a.      Esempi di problemi combinatorici

b.      Alcuni esercizi svolti (aggiornato al 9/2)

4.                Modelli di ottimizzazione

a.      Layout ottimo di circuiti VLSI

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

5.                Basi di IRn

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

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

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

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 19 settembre 2006 Gruppo A (!! Aggiornato al 20/09)

Soluzioni prova scritta del 19 settembre 2006 Gruppo B (!! Aggiornato al 20/09)

Soluzioni prova scritta del 12 luglio 2006 Gruppo A (!! Aggiornato al 13/07)

Soluzioni prova scritta del 12 luglio 2006 Gruppo B (!! Aggiornato al 13/07)

Soluzioni prova scritta del 22 marzo 2006 Gruppo A (!! Aggiornato al 24/03)

Soluzioni prova scritta del 22 marzo 2006 Gruppo B (!! Aggiornato al 24/03)

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 7

La prova orale si terrà martedì 26 settembre con inizio alle ore 10:00 in aula da definire

Avviso 1

La prova scritta intermedia si terrà il giorno giovedì 16 febbraio alle ore 15:00. Possono sostenere la prova:

a)                      gli studenti in corso;

b)                      degli studenti fuori corso, solo quelli che in passato non hanno sostenuto la prova consegnando l’elaborato.

In altre parole, uno studente fuori corso che si fosse iscritto a suo tempo a una prova scritta intermedia ma non avesse consegnato il proprio elaborato può iscriversi alla prova di quest’anno come se fosse in corso.

Avviso 2

Le prove d’esame di fine corso inizieranno il giorno mercoledì 22 marzo alle ore 10:30.

Avviso 3

                                 Risultati della prova d’esame intermedia del 16 febbraio

n.

matricola

traccia

voto

 

n.

matricola

traccia

voto

1

120949

B

18

 

42

154952

B

insuff

2

133714

B

19

 

43

155116

A

25

3

134328

A

insuff

 

44

155945

B

18

4

136057

B

18

 

45

155533

B

20

5

139700

A

insuff

 

46

155572

A

23

6

140563

A

insuff

 

47

156102

B

18

7

143628

B

insuff

 

48

156234

A

27

8

143816

B

insuff

 

49

156950

A

insuff

9

144276

A

22

 

50

156993

B

19

10

144320

A

22

 

51

157578

A

30 lode

11

144530

A

insuff

 

52

157603

A

25

12

144857

A

29

 

53

157907

A

insuff

13

146573

A

25

 

54

158542

A

30 lode

14

146591

B

insuff

 

55

158578

B

19

15

146745

A

30 lode

 

56

159515

A

22

16

146809

B

18

 

57

159639

A

19

17

146987

A

insuff

 

58

159691

B

18

18

147435

B

18

 

59

159739

A

19

19

147590

B

insuff

 

60

159852

B

30 lode

20

147875

A

22

 

61

160041

B

25

21

148833

B

insuff

 

62

160100

A

insuff

22

149023

B

insuff

 

63

160297

B

18

23

150174

A

insuff

 

64

160638

A

25

24

150269

A

19

 

65

160669

A

25

25

150303

B

insuff

 

66

160680

A

insuff

26

151107

A

insuff

 

67

160681

B

22

27

151151

B

insuff

 

68

160909

B

30 lode

28

151154

A

insuff

 

69

161481

B

23

29

151276

A

insuff

 

70

161770

B

18

30

151443

B

27

 

71

162069

A

19

31

151469

B

insuff

 

72

162145

A

19

32

151517

B

27

 

73

162439

B

insuff

33

151692

A

22

 

74

162531

A

25

34

152288

B

insuff

 

75

162750

A

insuff

35

152324

A

insuff

 

76

162761

A

insuff

36

153166

A

25

 

77

165036

B

18

37

153212

A

insuff

 

78

165057

A

insuff

38

154312

B

insuff

 

79

165066

A

insuff

39

154527

A

insuff

 

80

165076

B

18

40

154602

A

insuff

 

81

165112

A

20

41

154657

A

insuff

 

82

170828

B

30 lode

Avviso 4

La prova orale dell’esame si terrà il giorno mercoledì 29 marzo a partire dalle ore 10:00.

 

Avviso 5

                                 Risultati della prova d’esame del 22 Marzo

 

n.

matricola

traccia

voto

 

n.

matricola

traccia

voto

1

120949

B

insuff

 

69

150269

B

insuff

2

133120

A

insuff

 

70

150303

B

insuff

3

133714

A

20

 

71

150989

A

insuff

4

134328

A

18

 

72

151151

A

insuff

5

135029

B

18

 

73

151154

A

18

6

135520

B

insuff

 

74

151295

B

insuff

7

136057

B

insuff

 

75

151298

B

insuff

8

138995

A

18

 

76

151307

B

22

9

139000

B

18

 

77

151322

B

insuff

10

139221

B

insuff

 

78

151336

B

insuff

11

139459

A

insuff

 

79

151516

B

24

12

139747

A

insuff

 

80

151517

B

insuff

13

140563

A

20

 

81

151692

B

insuff

14

140713

A

insuff

 

82

151913

A

18

15

141193

A

insuff

 

83

152288

A

18

16

141236

A

23

 

84

152321

B

insuff

17

141493

B

18

 

85

152913

A

insuff

18

141552

A

18

 

86

153090

B

insuff

19

141614

A

18

 

87

153166

B

22

20

141928

A

insuff

 

88

153317

A

insuff

21

141932

B

30

 

89

153389

A

20

22

143401

B

20

 

90

154527

A

insuff

23

143618

A

insuff

 

91

154657

B

insuff

24

143628

A

insuff

 

92

155014

A

18

25

143737

A

18

 

93

155116

B

27

26

144036

A

21

 

94

155345

A

18

27

144149

A

22

 

95

155448

B

18

28

144269

A

27

 

96

155533

A

insuff

29

144320

A

18

 

97

155551

B

insuff

30

144324

B

21

 

98

155572

B

22

31

144344

B

insuff

 

99

156102

B

18

32

144460

A

insuff

 

100

156234

B

insuff

33

144530

B

insuff

 

101

156914

A

18

34

144611

A

insuff

 

102

156950

B

insuff

35

144674

B

insuff

 

103

156993

B

insuff

36

144797

B

insuff

 

104

157578

A

insuff

37

144857

B

18

 

105

157603

B

insuff

38

145322

B

insuff

 

106

157907

A

insuff

39

145381

B

18

 

107

158542

A

insuff

40

146127

A

insuff

 

108

158578

B

18

41

146437

B

insuff

 

109

159515

A

21

42

146496

B

insuff

 

110

159639

A

18

43

146573

B

insuff

 

111

159691

B

23

44

146595

A

insuff

 

112

159739

B

insuff

45

146666

B

21

 

113

159852

B

18

46

146745

B

18

 

114

160041

A

insuff

47

146809

A

insuff

 

115

160100

B

insuff

48

146842

A

insuff

 

116

160297

A

18

49

146923

A

21

 

117

160311

B

24

50

146924

A

insuff

 

118

160355

B

insuff

51

146968

B

insuff

 

119

160638

A

insuff

52

146999

A

insuff

 

120

160669

B

18

53

147071

B

18

 

121

160680

A

insuff

54

147130

B

insuff

 

122

160681

B

insuff

55

147348

B

18

 

123

160909

B

20

56

147435

A

21

 

124

161481

A

insuff

57

147875

A

insuff

 

125

161770

A

18

58

147990

B

insuff

 

126

162069

A

22

59

148113

A

insuff

 

127

162145

B

18

60

148158

A

insuff

 

128

162439

A

insuff

61

148311

A

insuff

 

129

162531

A

insuff

62

148436

B

insuff

 

130

162761

A

insuff

63

148561

B

18

 

131

164966

A

insuff

64

148800

B

insuff

 

132

165036

A

insuff

65

148833

A

insuff

 

133

165057

B

insuff

66

148840

B

18

 

134

165076

B

insuff

67

149023

B

insuff

 

135

165112

A

18

68

150221

B

insuff

 

136

170828

A

insuff

 

 

Avviso 6

La prova orale dell’esame si terrà il giorno venerdì 14 luglio a partire dalle ore 10:00. 

 

Risultati prova del 12 luglio 2006

 

Matricola

Gruppo

Voto

1

116461

A

insuff

2

130116

A

insuff

3

136057

A

insuff

4

138995

A

19

5

139459

A

insuff

6

140713

B

insuff

7

141928

B

19

8

142317

A

20

9

143618

B

insuff

10

143698

A

19

11

144530

A

insuff

12

146809

B

20

13

146842

B

23

14

146846

B

24

15

148436

B

19

16

150221

A

28

17

150269

B

18

18

151107

B

20

19

151322

A

insuff

20

151652

A

18

21

151692

B

23

22

154527

A

insuff

23

155418

B

20

24

155462

A

25

25

155533

B

19

26

155869

B

insuff

27

157578

A

21

28

158893

A

19

29

160638

B

insuff

30

162531

A

20

31

164966

A

26

32

165036

B

19

33

165066

B

19

34

165076

B

20

35

170828

A

28

 

 

Top