ESERCIZIO 1: Punto 1

(1)

La seguente matrice è una matrice delle distanze di un’istanza del problema del Commesso Viaggiatore.

- 2

4 1

1 1

2 7

2 -

3 1

3 3

2 6

4 3

- 3

2 4

1 5

1 1

3 -

3 3

4 4

1 3

2 3

- 1

2 3

1 3

4 3

1 -

2 2

1 4

2 2

- 1

7 6

5 4

3 2

1

Calcolare

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

ESERCIZIO 1: Punto 1

(2)

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

1

3

4 5

6

7 2

2 4 2 1

2 2

3 4 1

3 1

3 2

3

1

3

1 1 3

4

2

G

ESERCIZIO 1: Punto 1

(3)

Non consideriamo il nodo v = 1 e calcoliamo il minimo albero ricoprente su G utilizzando l’algoritmo di Prim.

3

5 4 6

7 2

3 4 1

3 1

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

c*_2i = min {c_2i : i∈V–T} = c₂₃ = c₂₇ = 1

ESERCIZIO 1: Punto 1

(4)

3

5 4 6

7 2

3 4

3

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

c*_2i = min {c_2i : i∈V–T}

1

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

7

1

4 1

2

ESERCIZIO 1: Punto 1

(5)

3

5 4 6

7 2

3 4

3

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

c*_2i = min {c_2i : i∈V–T}

1

= c₂₃ = 1

T = {2, 7,4};

V–T = {3, 5, 6}

7

c*_7i = min {c_7i : i∈V–T} = c73 =c₇₄ = 1

4

2 1

1

4 3

3

1

= c₇₄ = 1

ESERCIZIO 1: Punto 1

(6)

3

5 4 6

7 2

3 4

3

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

c*_2i = min {c_2i : i∈V–T}

1

= c₂₃ = 1

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

V–T = {3, 5}

7

c*_7i = min {c_7i : i∈V–T} = c73 = 1

4

2 1

1

4 3

3

c*_4i = min {c_4i : i∈V–T} = c46 = 1

1 6

3

ESERCIZIO 1: Punto 1

(7)

3

5 4 6

7 2

3 4

3

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

c*_2i = min {c_2i : i∈V–T}

1

= c₂₃ = 1

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

V–T = {5}

7

c*_7i = min {c_7i : i∈V–T} = c73 = 1

4

2 1

1

4 3

3

c*_4i = min {c_4i : i∈V–T} = c43 = c₄₅ = 3

1 6

3

c*_6i = min {c_6i : i∈V–T} = c63 = c₆₅ = 3

3 2

3

ESERCIZIO 1: Punto 1

(8)

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

3

5 4 6

7 2

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

7 1

1

4 1

6

3 4

3

1

4

2 1

3

3 3

3

3 2

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

5

ESERCIZIO 1: Punto 1

(9)

Per calcolare l’1-abero, re-introduciamo il nodo 1 e prendiamo i due archi di costo minimo uscenti da tale nodo.

3

5 4 6

7 1 2

7

1

4 1

6

3 2

1 2

4 2 1

2 2

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

C(1-albero) = 9 = LOWER BOUND ¹

1 1

2

5

ESERCIZIO 1: Punto 1

(10)

- 2

4 1

1 1

2 7

2 -

3 1

3 3

2 6

4 3

- 3

2 4

1 5

1 1

3 -

3 3

4 4

1 3

2 3

- 1

2 3

1 3

4 3

1 -

2 2

1 4

2 2

- 1

7 6

5 4

3 2

1

Calcolare

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

ESERCIZIO 1: Punto 2

(11)

Calcoliamo il minimo albero ricoprente sul grafo di partenza G = (V, E) utilizzando l’algoritmo di Prim.

1

3

4 5

6

7 2

2 4 2 1

2 2

3 4 1

3 1

3 2

3

1

3

1 1 3

4

2

G

ESERCIZIO 1: Punto 2

(12)

1

3

4 5

6

7 2

2 4 2 2 2

1

5

4

3 3

4

2

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

c*_1i = min {c_1i : i∈V–T} = c₁₅ = 1

T = {1, 5};

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

ESERCIZIO 1: Punto 2

(13)

1

3

4 5

6

7 1 4 2

5

4

3 3

4

c*_1i = min {c_1i : i∈V–T} = c₁₂ = c₁₃ = c₁₆ = c₁₇ = 2

T = {1, 5, 3};

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

c*_5i = min {c_5i : i∈V–T} = c₅₃ = 2

2 2 2 2

2

3 1

3 3

1

ESERCIZIO 1: Punto 2

(14)

1

3

4 5

6

7 1 4 2

5

4

c*_1i = min {c_1i : i∈V–T} = c₁₂ = c₁₃ = c₁₆ = c₁₇ = 2

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

V–T = {4, 6, 7}

c*_5i = min {c_5i : i∈V–T} = c₅₄ = c₅₆ = 2

2 2 2

2

3

3 3

c*_3i = min {c_3i : i∈V–T} = c₃₂ = c₃₇ = 1

3 3

1 1

2

3 3

2 1

1

ESERCIZIO 1: Punto 2

(15)

1

3

4 5

6

7 1 4 2

5 4 4

c*_1i = min {c_1i : i∈V–T} = c₁₂ = c₁₃ = c₁₆ = c₁₇ = 2

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

V–T = {4, 6}

c*_5i = min {c_5i : i∈V–T} = c₅₄ = c₅₆ = 2

2 2 2

2

3

3 3

c*_3i = min {c_3i : i∈V–T} = c₃₇ = 1

3 3

1 1

2

3 3

2 1

c*_2i = min {c_2i : i∈V–T} = c₂₇ = 1

7 1

2

1

ESERCIZIO 1: Punto 2

(16)

1

3

4 5

6

7 1 4 2

5 4 4

c*_1i = min {c_1i : i∈V–T} = c₁₂ = c₁₃ = c₁₆ = c₁₇ = 2

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

V–T = {6}

c*_5i = min {c_5i : i∈V–T} = c₅₄ = c₅₆ = 2

2 2 2

2

3

3 3

c*_3i = min {c_3i : i∈V–T} = c₃₇ = 1

3 3

1 1

2

3 3

2 1

c*_2i = min {c_2i : i∈V–T} = c₂₁ = 2

7 1

2

c*_7i = min {c_7i : i∈V–T} = c₇₄ = 1

1

4 1

ESERCIZIO 1: Punto 2

(17)

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

4 5

6

7 1 4 2

5 4 4

2 2

2

3

3 3

1 1

2

3 3

1 2 7 1

2

1

4 1

6

ESERCIZIO 1: Punto 2

(18)

Raddoppiamo gli archi dell’albero ricoprente

1

3

4 5

6

7 2

1

5

2

3 1 2 1

7 1

1

4 1

6

Il percorso euleriano sul multigrafo ottenuto è dato da:

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

Ricaviamo il

cammino hamiltoniano P_H = {1, 5, 3, 2, 7, 4, 6, 1}

C(P_H) = 9 = UPPER BOUND

2

ESERCIZIO 1: Punto 2

(19)

- 2

4 1

1 1

2 7

2 -

3 1

3 3

2 6

4 3

- 3

2 4

1 5

1 1

3 -

3 3

4 4

1 3

2 3

- 1

2 3

1 3

4 3

1 -

2 2

1 4

2 2

- 1

7 6

5 4

3 2

1

Calcolare

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

ESERCIZIO 1: Punto 3

(20)

Ereditiamo il minimo albero ricoprente dal punto precedente

1

3

4 5

6

7 2

5

2

3 1 2 1

7 1

1

4 1

6

Individuiamo i nodi di grado dispari:

V_d = {1, 6}

Sottografo

completo indotto da V_d.

ESERCIZIO 1: Punto 3

2

Matching perfetto sul sottografo indotto: M = {16}

(21)

Consideriamoil grafo euleriano dato da M ∪ T

1

3

4 5

6

7 2

5

2

3 1 2 1

7 1

1

4 1

6

ESERCIZIO 1: Punto 3

2

Il percorso euleriano sul multigrafo ottenuto è dato da:

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

In questo caso P_H = P_E.

C(P_H) = 9 = UPPER BOUND

(22)

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 a_ie un profitto (atteso) p_i. 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.

240 42

82 160

120 170

125 96

Profitto

22 24

41 40

12 30

12 16

Peso

8 7

6 5

4 3

2 Progetto 1

(23)

ESERCIZIO 2

Il problema può essere formulato come segue:

Variabili di decisione:

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

z* = max (96x₁ + 125x₂ + 170x₃ + 120x₄ + 160x₅ + 82x₆ + 42x₇ + 240x₈) 16x₁ + 12x₂ + 30x₃ + 12x₄ + 40x₅ + 41x₆ + 24x₇ + 22x₈ < 170

x ∈ {0,1}8

(24)

ESERCIZIO 2

Consideriamo il rilassamento lineare del problema che corrisponde ad un Knapsack continuo

z*_RL = max (96x₁ + 125x₂ + 170x₃ + 120x₄ + 160x₅ + 82x₆ + 42x₇ + 240x₈) 16x₁ + 12x₂ + 30x₃ + 12x₄ + 40x₅ + 41x₆ + 24x₇ + 22x₈ < 170

x > 0

Riordiniamo i progetti in modo tale che

n n

a p a

p a

p ≥ ≥ ...≥

2 2 1

1

(25)

ESERCIZIO 2

p₁/a₁ = 96/16 = 6 ⇒ y₄

p₂/a₂ = 125/12 = 10,41 ⇒ y₂ p₃/a₃ = 170/30 = 5,6 ⇒ y₅ p₄/a₄ = 120/12 = 10 ⇒ y₃ p₅/a₅ = 160/40 = 4 ⇒ y₆

p₆/a₆ = 82/41 = 2 ⇒ y₇

p₇/a₇ = 42/24 = 1,75 ⇒ y₈ p₈/a₈ = 240/22 = 10,9 ⇒ y₁

z*_RL = max (240y₁ + 125y₂ + 120y₃ + 96y₄ + 170y₅ + 160y₆ + 82y₇ + 42y₈) 22y₁ + 12y₂ + 12y₃ + 16y₄ + 30y₅ + 40y₆ + 41y₇ + 24y₈ < 170

y > 0

(26)

ESERCIZIO 2

Individuiamo il progetto h per cui

∑

=

>

h

j

j b

a

1

y₁ = 1 ⇒ ²² ¹⁷⁰

1

1 = <

∑

j=

a

y₁ = y₂ = 1 ⇒

y₁ = y₂ = y₃ = 1 ⇒

y₁ = y₂ = y₃ = y₄ = 1 ⇒

y₁ = y₂ = y₃ = y₄ = y₅ =1 ⇒

y₁ = y₂ = y₃ = y₄ = y₅ = y₆ = 1 ⇒

y₁ = y₂ = y₃ = y₄ = y₅ = y₆ = y₇ = 1 ⇒ ⇒ h = 7 170

34

2

1

<

∑

=

j=

aj

170 46

3

1

<

∑

=

j=

aj

170 62

4

1

<

∑

=

j=

aj

170 92

5

1

<

∑

=

j=

aj

170 132

6

1

<

∑

=

j=

aj

170 173

7

1

>

∑

=

j=

aj

(27)

ESERCIZIO 2

Per il progetto h fissiamo la variabile y_h:

92 , 41 0

38 41

132 170

1

7 − = =

=













−

=

∑

⁻

= h h

j

a a b

y

La restante variabile y₈ = 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.

(28)

ESERCIZIO 3

Siano U, A₁, ..., A_n insiemi finiti, e a₁, ..., a_n IR⁺. Sia

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

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

A₁ A₂

A₃ U

X a₁ = 3

a₂ = 1

a₃ = 1

(29)

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 ∩ A_k| < a_k, per ciascun k = 1, ..., n.

Se Y⊆ X, allora |Y|<|X|. Pertanto

|Y ∩ A_k| < |X ∩ A_k| < a_k.

Possiamo quindi concludere che la coppia è subclusiva.

(30)

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.

(31)

ESERCIZIO 3

Consideriamo la seguente situazione:

A₁ A₂

A₃ a₁ = 2 U

a₂ = 1

a₃ = 1 1

2 3

4 7

5 6

7 8

10 9 11

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

Y ∩ A₁= {1, 4} ⇒|Y ∩ A₁|= 2 < a₁ X ∩ A₁= {1, 3} ⇒|X ∩ A₁|= 2 < a₁ Y ∩ A₂= {7} ⇒|Y ∩ A₂|= 1 < a₂ X ∩ A₂= {8} ⇒|X ∩ A₂|= 1 < a₂

Y ∩ A₃= {11} ⇒|Y ∩ A₃|= 1 < a₃ X ∩ A₃= {8} ⇒|X ∩ A₃|= 1 < a₃

(32)

ESERCIZIO 3

Consideriamo la seguente situazione:

A₁ A₂

A₃ a₁ = 2 U

a₂ = 1

a₃ = 1 1

2 3

4 7

5 6

7 8

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