La seguente matrice è una matrice delle distanze di un’istanza del

problema del Commesso Viaggiatore.

-2411127

2-313326

43-32415

113-3344

1323-123

13431-22

221422-1

7654321

Calcolare

1.Il valore del rilassamento che si ottiene determinando l’1-albero di costo minimo.

ESERCIZIO 1: Punto 1

Disegniamo il grafo G = (V, E) associato alla matrice delle

distanze.

1

3

45

6

72

2

24122

3

14

3

1

3

23

1

3

11

3

4

2

G

ESERCIZIO 1: Punto 1

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero

ricoprente su G utilizzando l’algoritmo di Prim.

3

45

6

72

3

14

3

1

T = {2}; V–T = {3, 4, 5, 6, 7}

c*2i = min {c2i : i∈V–T} = c23 = c27 = 1

ESERCIZIO 1: Punto 1

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero

ricoprente su G utilizzando l’algoritmo di Prim.

3

45

6

72

3

4

3

T = {2}; V–T = {3, 4, 5, 6, 7}

c*2i = min {c2i : i∈V–T}

1

1

= c27 = 1 T = {2, 7}; V–T = {3, 4, 5, 6}

7

1

14

2

ESERCIZIO 1: Punto 1

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero

ricoprente su G utilizzando l’algoritmo di Prim.

3

45

6

72

3

4

3

T = {2, 7}; V–T = {3, 4, 5, 6}

c*2i = min {c2i : i∈V–T}

1

1

= c23 = 1

T = {2, 7,4};

V–T = {3, 5, 6}

7

c*7i = min {c7i : i∈V–T} = c73 =c74 = 1

4

21

1

4

3

3

1

= c74 = 1

ESERCIZIO 1: Punto 1

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero

ricoprente su G utilizzando l’algoritmo di Prim.

3

45

6

72

3

4

3

T = {2, 7, 4}; V–T = {3, 5, 6}

c*2i = min {c2i : i∈V–T}

1

1

= c23 = 1

T = {2, 7, 4, 6};

V–T = {3, 5}

7

c*7i = min {c7i : i∈V–T} = c73 = 1

4

21

1

4

3

3

c*4i = min {c4i : i∈V–T} = c46 = 1

1

6

3

3

ESERCIZIO 1: Punto 1

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero

ricoprente su G utilizzando l’algoritmo di Prim.

3

45

6

72

3

4

3

T = {2, 7, 4, 6}; V–T = {3, 5}

c*2i = min {c2i : i∈V–T}

1

1

= c23 = 1

T = {2, 7, 4, 6, 3};

V–T = {5}

7

c*7i = min {c7i : i∈V–T} = c73 = 1

4

21

1

4

3

3

c*4i = min {c4i : i∈V–T} = c43 = c45 = 3

1

6

3

c*6i = min {c6i : i∈V–T} = c63 = c65 = 3

3

23

ESERCIZIO 1: Punto 1

A questo punto, l’arco che dista meno dal nodo 5 è l’arco (3,5).

3

45

6

72

T = {2, 7, 4, 6, 3, 5}; V–T = ∅

17

1

4

1

6

3

4

3

1

4

21

3

3

3

3

3

2

Minimo albero ricoprente = {27, 74, 46, 73, 35}

5

ESERCIZIO 1: Punto 1

Per calcolare l’1-abero, re-introduciamo il nodo 1 e prendiamo i

due archi di costo minimo uscenti da tale nodo.

3

45

6

721

7

1

4

1

6

32

12

24122

1-albero = {15, 16, 27, 74, 46, 73, 35}

C(1-albero) = 9 = LOWER BOUND1

1

12

5

ESERCIZIO 1: Punto 1

La seguente matrice è una matrice delle distanze di un’istanza del

problema del Commesso Viaggiatore.

-2411127

2-313326

43-32415

113-3344

1323-123

13431-22

221422-1

7654321

Calcolare

3. Il valore di una soluzione euristica calcolata con l’algoritmo Double Tree.

ESERCIZIO 1: Punto 2

Calcoliamo il minimo albero ricoprente sul grafo di partenza G =

(V, E) utilizzando l’algoritmo di Prim.

1

3

45

6

72

2

24122

3

14

3

1

3

23

1

3

11

3

4

2

G

ESERCIZIO 1: Punto 2

1

3

45

6

72

2

2422

1

5

4

3

3

4

2

T = {1}; V–T = {2, 3, 4, 5, 6, 7}

c*1i = min {c1i : i∈V–T} = c15 = 1

T = {1, 5};

V–T = {2, 3, 4, 6, 7}

ESERCIZIO 1: Punto 2

1

3

45

6

72

41

5

4

3

3

4

c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2

T = {1, 5, 3};

V–T = {2, 4, 6, 7}

c*5i = min {c5i : i∈V–T} = c53 = 2

2

222

2

3

1

3

3

1

ESERCIZIO 1: Punto 2

1

3

45

6

72

41

5

4

4

c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2

T = {1, 5, 3, 2};

V–T = {4, 6, 7}

c*5i = min {c5i : i∈V–T} = c54 = c56 = 2

2

22

2

3

3

3

c*3i = min {c3i : i∈V–T} = c32 = c37 = 1

3

3

11

2

3

3

21

1

ESERCIZIO 1: Punto 2

1

3

45

6

72

41

5

44

c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2

T = {1, 5, 3, 2, 7};

V–T = {4, 6}

c*5i = min {c5i : i∈V–T} = c54 = c56 = 2

2

22

2

3

3

3

c*3i = min {c3i : i∈V–T} = c37 = 1

3

3

11

2

3

3

21

c*2i = min {c2i : i∈V–T} = c27 = 1

17

2

1

ESERCIZIO 1: Punto 2

1

3

45

6

72

41

5

44

c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2

T = {1, 5, 3, 2, 7, 4};

V–T = {6}

c*5i = min {c5i : i∈V–T} = c54 = c56 = 2

2

22

2

3

3

3

c*3i = min {c3i : i∈V–T} = c37 = 1

3

3

11

2

3

3

21

c*2i = min {c2i : i∈V–T} = c21 = 2

17

2

c*7i = min {c7i : i∈V–T} = c74 = 1

1

4

1

ESERCIZIO 1: Punto 2

A questo punto, l’arco che dista meno dal nodo 6 è l’arco (4,6).

T = {1, 5, 3, 2, 7, 4, 6}; V–T = ∅

Minimo albero ricoprente = {15, 53, 32, 27, 74, 46}

1

3

45

6

72

41

5

44

2

22

2

3

3

3

3

3

11

2

3

3

21

17

2

1

4

1

6

ESERCIZIO 1: Punto 2

Raddoppiamo gli archi dell’albero ricoprente

1

3

45

6

72

1

5

2

3

1

2

1

17

1

4

1

6

Il percorso euleriano sul multigrafo ottenuto è dato da:

PE = {1, 5, 3, 2, 7, 4, 6, 4, 7, 2, 3, 5, 1}

Ricaviamo il

cammino hamiltoniano

PH = {1, 5, 3, 2, 7, 4, 6, 1}

C(PH) = 9 = UPPER BOUND

2

ESERCIZIO 1: Punto 2

La seguente matrice è una matrice delle distanze di un’istanza del

problema del Commesso Viaggiatore.

-2411127

2-313326

43-32415

113-3344

1323-123

13431-22

221422-1

7654321

Calcolare

4. Il valore di una soluzione euristica calcolata con l’algoritmo di Christofides.

ESERCIZIO 1: Punto 3

Ereditiamo il minimo albero ricoprente dal punto precedente

1

3

45

6

72

5

2

3

1

2

1

17

1

4

1

6

Individuiamo i nodi di grado dispari:

Vd = {1, 6}

Sottografo

completo indotto

da Vd.

ESERCIZIO 1: Punto 3

2

Matching perfetto

sul sottografo

indotto: M = {16}

Consideriamoil grafo euleriano dato da M ∪ T

1

3

45

6

72

5

2

3

1

2

1

17

1

4

1

6

ESERCIZIO 1: Punto 3

2

Il percorso euleriano sul multigrafo ottenuto è dato da:

PE = {1, 5, 3, 2, 7, 4, 6, 1}

In questo caso PH = PE.

C(PH) = 9 = UPPER BOUND

ESERCIZIO 2

La tabella che segue contiene una lista di progetti che possono

essere attivati nel prossimo anno. Il budget totale a disposizione

è 170mila euro.

Ogni progetto ha un costo ai e un profitto (atteso) pi. Dopo aver formulato il problema di selezionare un sottoinsieme di progetti in

modo da massimizzare il profitto finale e rispettare il vincolo di

budget, determinare un upper bound per il profitto massimo

ottenibile.

240428216012017012596Profitto

2224414012301216Peso

87654321Progetto

ESERCIZIO 2

Il problema può essere formulato come segue:

Variabili di decisione:

xi = 1 se e solo se il progetto i-esimo è attivato.

z* = max (96x1 + 125x2 + 170x3 + 120x4 + 160x5 + 82x6 + 42x7 + 240x8)

16x1 + 12x2 + 30x3 + 12x4 + 40x5 + 41x6 + 24x7 + 22x8 < 170

x ∈ {0,1}8

ESERCIZIO 2

Consideriamo il rilassamento lineare del problema che

corrisponde ad un Knapsack continuo

z*RL = max (96x1 + 125x2 + 170x3 + 120x4 + 160x5 + 82x6 + 42x7 + 240x8)

16x1 + 12x2 + 30x3 + 12x4 + 40x5 + 41x6 + 24x7 + 22x8 < 170

x > 0

Riordiniamo i progetti in modo tale che

n

n

a

p

a

p

a

p≥≥≥ ...

2

2

1

1

ESERCIZIO 2p1/a1 = 96/16 = 6 ⇒ y4

p2/a2 = 125/12 = 10,41 ⇒ y2

p3/a3 = 170/30 = 5,6 ⇒ y5

p4/a4 = 120/12 = 10 ⇒ y3

p5/a5 = 160/40 = 4 ⇒ y6

p6/a6 = 82/41 = 2 ⇒ y7

p7/a7 = 42/24 = 1,75 ⇒ y8

p8/a8 = 240/22 = 10,9 ⇒ y1

z*RL = max (240y1 + 125y2 + 120y3 + 96y4 + 170y5 + 160y6 + 82y7 + 42y8)

22y1 + 12y2 + 12y3 + 16y4 + 30y5 + 40y6 + 41y7 + 24y8 < 170

y > 0

ESERCIZIO 2

Individuiamo il progetto h per cui ∑=

>h

j

j ba1

y1 = 1 ⇒ 170221

1

1 <=∑=j

a

y1 = y2 = 1 ⇒

y1 = y2 = y3 = 1 ⇒

y1 = y2 = y3 = y4 = 1 ⇒

y1 = y2 = y3 = y4 = y5 =1 ⇒

y1 = y2 = y3 = y4 = y5 = y6 = 1 ⇒

y1 = y2 = y3 = y4 = y5 = y6 = y7 = 1 ⇒ ⇒ h = 7

170342

1

<=∑=j

ja

170463

1

<=∑=j

ja

170624

1

<=∑=j

ja

170925

1

<=∑=j

ja

1701326

1

<=∑=j

ja

1701737

1

>=∑=j

ja

ESERCIZIO 2

Per il progetto h fissiamo la variabile yh:

92,041

38

41

132170

1

1

7 ==−

=

−

=

∑−

=

h

h

j

j

a

ab

y

La restante variabile y8 = 0.

Il valore della funzione obiettivo è pari a z*RL = 986,44 e

corrisponde ad un UPPER BOUND per il valore ottimo z* del

problema iniziale.

ESERCIZIO 3

Siano U, A1, ..., An insiemi finiti, e a1, ..., an � IR+. Sia

ℑ={X ⊆ U : |X ∩ Ak| < ak per ciascun k = 1, ..., n}.

Dire se la coppia (U,ℑ) individua o meno un matroide motivando la risposta.

A1

A2

A3U

X

a1

= 3

a2

= 1

a3

= 1

ESERCIZIO 3

Ricordiamo che la coppia (U,ℑ) è un matroide se valgono le seguenti condizioni:

1. ∅∈ℑ

2. Per ogni Y⊆ X, X∈ℑ ⇒Y∈ℑ.

3. Dati X, Y∈ℑ, con |X|<|Y|, esiste y∈Y tale che X ∪ {y} ∈ℑ.

Banalmente ∅∈ℑ.

Supponiamo che X∈ℑ. Allora |X ∩ Ak| < ak, per ciascun k = 1, ..., n.

Se Y⊆ X, allora |Y|<|X|. Pertanto|Y ∩ Ak| < |X ∩ Ak| < ak.

Possiamo quindi concludere che la coppia è subclusiva.

ESERCIZIO 3

Resta da verificare se la coppia (U,ℑ) soddisfa la proprietà di scambio.

Se pensiamo che tale proprietà sia soddisfatta dobbiamo

dimostrarlo in maniera formale.

Viceversa, se pensiamo che la proprietà di scambio non sia soddisfatta dobbiamo cercare un controesempio in cui essa non

vale.

ESERCIZIO 3

Consideriamo la seguente situazione:

A1

A2

A3U

a1

= 2

a2

= 1

a3

= 1

1

23

4 7

5 6

78

910

11

Siano: Y = {1, 4, 7, 11} e X = {1, 3, 8}. Entrambi gli insiemi

appartengono a ℑ. Infatti:

Y ∩ A1= {1, 4} ⇒|Y ∩ A

1|= 2 < a

1X ∩ A

1= {1, 3} ⇒|X ∩ A

1|= 2 < a

1

Y ∩ A2= {7} ⇒|Y ∩ A

2|= 1 < a

2X ∩ A

2= {8} ⇒|X ∩ A

2|= 1 < a

2

Y ∩ A3= {11} ⇒|Y ∩ A

3|= 1 < a

3X ∩ A

3= {8} ⇒|X ∩ A

3|= 1 < a

3

ESERCIZIO 3

Consideriamo la seguente situazione:

A1

A2

A3U

a1

= 2

a2

= 1

a3

= 1

1

23

4 7

5 6

78

910

11

Tuttavia è immediato osservare che, per ogni y ∈Y\X, l'insieme X ∪

{y} ∉ℑ.

Pertanto la proprietà di scambio non è verificata e la coppia (U,ℑ) non è un matroide.