COMPITO DI RICERCA OPERATIVA II

COMPITO DI RICERCA OPERATIVA II

ESERCIZIO 1. (7 punti) Sia data la rete G = (V, A) con V = {1, 2, 3, 4, 5}

e

A = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (5, 2), (5, 4)}

con i seguenti costi unitari di trasporto c ij e capacit` a d ij

arco (1, 2) (1, 3) (2, 3) (2, 4) (3, 5) (5, 2) (5, 4)

c ij 2 2 5 5 3 7 1

d ij 5 11 7 3 8 3 1

e i seguenti valori b i associati ai nodi

nodo 1 2 3 4 5

b i 8 −4 0 −2 −2

Determinare una soluzione ottima e il valore ottimo per questo problema di flusso a costo minimo, partendo dalla base

B 0 = {(1, 2), (1, 3), (2, 4), (3, 5)} , N 0 = {(2, 3), (5, 4)} , N 1 = {(5, 2)} .

ESERCIZIO 2. (7 punti) Sia dato il problema TSP simmetrico con la seguente tabella delle distanze

1 2 3 4 5 6

1 − 1 2 9 9 8

2 − 4 4 2 1

3 − 5 9 8

4 − 6 9

5 − 7

6 −

Se ne risolva il duale lagrangiano basato sugli 1-tree utilizzando sempre come nodo a il nodo 1.

ESERCIZIO 3. (7 punti) Sia dato il problema KNAPSACK con capacit` a dello zaino b = 8 e con 5 oggetti aventi i seguenti valori v i e pesi p i

i 1 2 3 4 5

v i 3 8 5 7 12 p i 1 2 3 3 6

Si determini una soluzione ottima e il valore ottimo di questo problema utilizzando la program- mazione dinamica.

ESERCIZIO 4. (4 punti) Si descriva il problema di taglio a costo minimo su una rete e si spieghi la relazione che tale problema ha con quello di flusso massimo sulla stessa rete.

ESERCIZIO 5. (3 punti) Si indichino quali sono le propriet` a di un problema TSP metrico. ` E vero che l’algoritmo Double Spanning Tree restituisce un circuito hamiltoniano solo se tali propriet` a sono soddisfatte? (giustificare la risposta)

ESERCIZIO 6. (2 punti) Dire se `e vero o falso (giustificando la risposta) che lo schema di approssimazione completamente polinomiale per il problema KNAPSACK visto a lezione, si basa sulla risoluzione di un problema KNAPSACK modificato con gli stessi valori degli oggetti e la stessa capacit` a dello zaino del problema originario, ma con diversi pesi degli oggetti.

ESERCIZIO 7. (3 punti) Dato un problema di minimo min x∈S f (x), definire quali devono essere le propriet` a di f ^′ e S ^′ in modo tale che il problema min x∈S

f ^′ (x) sia un rilassamento del problema di minimo attraverso cui calcolarne un lower bound.

1

2 COMPITO DI RICERCA OPERATIVA II

Soluzioni 1. La base specificata `e ammissibile. Si ottiene quanto segue.

1 2

3 4

5 3

5 2

5

B 0 = {(1, 2), (1, 3), (2, 4), (3, 5)}

N 1 = {(5, 2)}

¯ c 23 = 5

¯ c 52 = 10

¯ c 54 = 1

1 2

3 4

3 5 1 2

3

B 1 = {(1, 3), (2, 4), (3, 5), (5, 2)}

N 1 = {(1, 2)}

¯

c 12 = −10

¯ c 23 = 15

¯

c 54 = −11

1 2

3 4

3 5 1

3 1

B 2 = {(1, 3), (2, 4), (3, 5), (5, 4)}

N 1 = {(1, 2)}

¯ c 12 = 1

¯ c 23 = 4

¯ c 52 = 11

1 2

3 4

3 5 1

3 5

B 3 = {(1, 2), (1, 3), (2, 4), (3, 5)}

N 1 = {(5, 4)}

¯ c 23 = 5

¯ c 52 = 10

¯

c 54 = −1 Il costo minimo `e z ^∗ = 31.

2. Impostando inizialmente λ 1 , . . . , λ 6 = 0, si ottiene l’1-albero iniziale T = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (2, 6)} , di costo 14.

Hanno grado diverso da 2 i nodi 2 (deg(2) = 5), 4, 5 e 6 (tutti con grado 1). Aggiornando i moltiplicatori si ottiene

λ 1 = λ 3 = 0, λ 2 = −3, λ 4 = λ 5 = λ 6 = 1, e quindi i costi modificati ¯ v ij = v ij − λ i − λ j

¯ v ij =

















1 2 3 4 5 6

1 − 4 2 8 8 7

2 − 7 6 4 3

3 − 4 8 7

4 − 4 7

5 − 5

6 −















 con 1-albero di costo minimo

T = {(1, 2), (1, 3), (2, 5), (2, 6), (3, 4), (4, 5)} di costo 21.

Si noti che il termine P

i∈V λ i `e nullo. Il nodo 2 ha grado 3, mentre il nodo 6 ha grado 1, quindi

λ 1 = λ 3 = 0, λ 2 = −4, λ 4 = λ 5 = 1, λ 6 = 2.

COMPITO DI RICERCA OPERATIVA II 3

Sui costi modificati

¯ v ij =

















1 2 3 4 5 6

1 − 5 2 8 8 6

2 − 8 7 5 3

3 − 4 8 6

4 − 4 6

5 − 4

6 −















 si ottiene l’1-albero

T = {(1, 2), (1, 3), (2, 6), (3, 4), (4, 5), (5, 6)}

di costo 22. Poich´e tutti i nodi hanno ora grado 2, la procedura non prosegue oltre.

3. Calcolando i valori della f _k ^∗ (s), per k = 1, . . . , 5 e s = 0, . . . , 8 si ottiene quanto segue.

k

s

0 1 2 3 4 5 6 7 8

1 20

2 0 0 8 8 8 15 15 15 20

3 0 0 0 7 7 7 12 12 12

4 0 0 0 7 7 7 12 12 12

5 0 0 0 0 0 0 12 12 12

f k ^∗ (s)

k

s

0 1 2 3 4 5 6 7 8

1 N

2 N N S S S S S S S

3 N N N N N N s /n s/n s/n

4 N N N S S S N N N

5 N N N N N N S S S

d ^∗ _k (s)

La soluzione ottima `e x <sup>∗</sup> 1 = 0, x <sup>∗</sup> 2 = 1, x <sup>∗</sup> 3 = 0, x <sup>∗</sup> 4 = 0, x <sup>∗</sup> 5 = 1, di valore z <sup>∗</sup> = 20. Si noti che per lo stato (k = 3, s = 6) `e ottima anche la decisione d ^∗ 3 (6) = S; questa porta alla soluzione ottima alternativa x ^∗ 1 = 0, x ^∗ 2 = 1, x ^∗ 3 = 1, x ^∗ 4 = 1, x ^∗ 5 = 0.

4. Si vedano gli appunti del corso.

5. Nel TSP metrico valgono:

d ij = d ji per ogni i, j ∈ V ; (1)

d ij ≥ 0 per ogni i, j ∈ V ; (2)

d ij + d jk ≥ v ik per ogni i, j, k ∈ V . (3)

Se la matrice d ij `e completa, l’algoritmo double spanning tree `e comunque in grado di generare un circuito hamiltoniano; ci`o che si perde `e la garanzia sull’errore relativo massimo. Se la matrice d ij non `e completa — cio`e esistono d ij = ∞ fuori diagonale — non `e detto che il double spanning tree garantisca di trovare un circuito hamiltoniano. Si noti che nel caso metrico la (3) garantisce che se l’istanza ammette soluzioni ammissibili, la matrice d ij `e completa.

6. Falso. Per costruzione, M n contiene la soluzione ottima per il knapsack con gli oggetti 1, . . . , n, con pesi p 1 , . . . , p n e capacit` a b pari agli originali e valori modificati v i = ⌊ ₁₀ ^v

⌋10 ^t .

7. Deve valere:

S ⊆ S ^′ e f ^′ (x) ≤ f (x) per ogni x ∈ S.