COMPITO DI RICERCA OPERATIVA II
ESERCIZIO 1. (7 punti) Sia data la rete G = (V, A) con V = {S, 1, 2, 3, 4, 5, 6, 7, D}
e
A = {(S, 1), (S, 2), (S, 3), (1, 4), (1, 5), (2, 4), (3, 5), (3, 6), (4, 7), (5, 6), (5, 7), (5, D), (6, D), (7, D)}
con le capacit`a
cS1= 9 cS2= 7 cS3= 8 c14= 5 c15= 2 c24= 1
c35= 2 c36= 8 c47= 3 c56= 2 c57= 2 c5D= 8 c6D= 2 c7D= 3.
Supponendo di partire dal flusso ammissibile iniziale
xS1= 2 xS2= 0 xS3= 2 x14= 0 x15= 2 x24= 0
x35= 2 x36= 0 x47= 0 x56= 2 x57= 2 x5D= 0 x6D= 2 x7D = 2.
si determini il flusso massimo e il taglio minimo per questa rete.
ESERCIZIO 2. (7 punti) Sia dato il problema KNAPSACK con capacit`a dello zaino b = 9 e con 5 oggetti aventi i seguenti valori vi e pesi pi
i 1 2 3 4 5
vi 583 692 325 100 908
pi 2 3 4 5 6
Si determinino tutte le soluzioni ottime di questo problema utilizzando l’algoritmo di programma- zione dinamica.
ESERCIZIO 3. (7 punti) Sia dato il problema TSP con la seguente tabella delle distanze
1 2 3 4 5
1 − 8 7 9 3
2 5 − 4 3 2
3 7 9 − 6 6
4 11 12 3 − 6
5 6 14 9 7 −
Si consideri il sottinsieme della regione ammissibile S(A0, A1) con A0= ∅ A1= {(1, 2), (5, 1)}.
Si calcoli un lower bound per tale sottinsieme; sulla base del risultato ottenuto si effettui il branching del sottinsieme stesso; si calcoli il lower bound anche per i nodi figli, individuando eventuali circuiti hamiltoniani.
ESERCIZIO 4. (4 punti) Si spieghi in cosa consiste il principio di ottimalit`a nella programma- zione dinamica e si dica perch´e esso vale nel caso del problema KNAPSACK.
ESERCIZIO 5. (5 punti) Si definisca il problema di ε-approssimazione per problemi di minimo e si definiscano le quattro categorie in cui abbiamo distinto i problemi di ottimizzazione NP-completi sulla base della difficolt`a dei corrispondenti problemi di approssimazione.
ESERCIZIO 6. (3 punti) Sia dato un problema KNAPSACK con n oggetti aventi pesi p1, . . . , pn
e valori v1, . . . , vn. La capacit`a dello zaino `e indicata con b. Si supponga che dati tre oggetti i, j, k, si abbia pi+ pj ≤ pk e vi+ vj> vk. Si spieghi perch´e il vincolo xi+ xj≥ xk `e certamente soddisfatto da ogni soluzione ottima del problema.
1
2 COMPITO DI RICERCA OPERATIVA II
Soluzioni
1.Applicando l’algoritmo di Ford-Fulkerson si ottengono i seguenti risultati intermedi.
S 1
2 3
4
5 6
7
D 2
2 2
2 2 2
2 2
Cammino aumentante: (S, 1, 4, 7, D)
S 1 2
3 4 5
6 7
D 3
2 1 2
2 1
2 2
2 3
Cammino aumentante: (S, 3, 6, 5, D)
S 1
2 3
4
5 6
7
D 3
4 1 2 2 2
1 2
2 2
3
Cammino aumentante: (S, 1, 4, 7, 5, D)
S 1 2
3 4 5
6 7
D 5
4 3 2
2 2
3 4 2
3
Ottimo (flusso=9).
Un taglio di capacit`a minima `e identificato da U = {S, 1, 2, 3, 4, 6}
con capacit`a del taglio
C(U ) = c15+ c35+ c47+ c6D= 2 + 2 + 3 + 2 = 9.
2.Per il problema dato si calcolano le fk∗(s) e d∗k(s) come segue.
fk∗(s)
k\s 0 1 2 3 4 5 6 7 8 9
1 1600
2 0 0 0 692 692 692 908 1017 1017 1600
3 0 0 0 0 325 325 908 908 908 908
4 0 0 0 0 0 100 908 908 908 908
5 0 0 0 0 0 0 908 908 908 908
d∗k(s)
k\s 0 1 2 3 4 5 6 7 8 9
1 s/n
2 n n n s s s n s s s
3 n n n n s s n n n n
4 n n n n n s n n n n
5 n n n n n n s s s s
Le due soluzioni ottime sono
x2= x5= 1, x1= x3= x4= 0,
COMPITO DI RICERCA OPERATIVA II 3
e
x1= x2= x3= 1, x4= x5= 0,
3. Eliminando (riga 1 e colonna 2) e (riga 5 e colonna 1) per tenere conto di A1 si lavora sulla sottomatrice {2, 3, 4} × {3, 4, 5}, riducendola:
3 4 5
2 4 3 2
3 ∞ 6 6
4 3 ∞ 6
=⇒
3 4 5
2 1 0 0
3 ∞ 3 4
4 0 ∞ 4
=⇒
3 4 5
2 1 0 0
3 ∞ 0 1
4 0 ∞ 4
La soluzione ottima del corrispondente assegnamento 3×3, di costo pari a 11, `e M = {(4, 3), (3, 4), (2, 5)}.
Il lower bound del sottoinsieme `e quindi LB = 8 + 6 + 11 = 25.
Il sottociclo 1 → 2 → 5 → 1 ha il solo arco (2, 5) al di fuori di A1, quindi in questo caso avremo un solo nodo figlio
Nodo:A0= {(2, 5)} , A1= {(1, 2), (5, 1)} . Per tale nodo si lavora sulla sottomatrice
3 4 5
2 1 0 ∞
3 ∞ 0 1
4 0 ∞ 4
=⇒
3 4 5
2 1 0 ∞
3 ∞ 0 0
4 0 ∞ 3
L’assegnamento {(2, 4), (3, 5), (4, 3)} corrisponde al ciclo completo {(1, 2), (2, 4), (4, 3), (3, 5), (5, 1)}
di costo 26.
4.Si vedano gli appunti del corso.
5.Si vedano gli appunti del corso.
6. Si supponga per assurdo di avere una soluzione ottima x∗ nella quale x∗i + x∗j < x∗k. Poich´e le variabili sono binarie, si deve allora avere x∗i = x∗j = 0, x∗k = 1; allora la soluzione ¯x definita da
¯
xr= x∗r (r 6= i, j, k)
¯ xk= 0
¯
xi= ¯xj = 1
`e ammissibile perch´e ha peso pari a
n
X
t=1
ptx¯t=
n
X
t=1
prx∗r+ (pi+ pj) − pk≤
n
X
t=1
prx∗r≤ b.
Inoltre ¯x ha valore
n
X
t=1
vtx¯t=
n
X
t=1
vrx∗r+ (vi+ vj) − vk>
n
X
t=1
vrx∗r, contraddicendo l’ottimalit`a di x∗.
