ALCUNI ESERCIZI SUL FLUSSO DI COSTO MINIMO IN PRESENZA DI CAPACIT `A SUGLI ARCHI.
CORSO DI RICERCA OPERATIVA II
ESERCIZIO 1. Per ognuno dei grafi di Figura 1, per i quali sono specificati sia costi (cij) che capacit`a (dij), determinare una soluzione ottima per il problema di flusso di costo minimo, partendo dalle rispettive basi iniziali.
(a) B0= {(1, 3), (1, 4), (3, 6), (4, 6), (5, 6)}, N10= {(1, 3), (2, 5), (3, 2)}.
(b) B0= {(1, 2), (1, 4), (2, 3), (3, 5), (5, 6)}, N10= {(2, 5), (4, 6)}.
(c) B0= {(1, 2), (2, 3), (2, 5), (3, 4), (4, 6), (6, 7)}, N10= {(1, 3), (3, 6)}.
(a) 1
2
3
4
5
6 2
3
1 4
5 1
2 2
3 b1= 7
b5= −2
b6= −5 1
2
3
4
5
6 6
7
5 5
2 5
9 7
9
cij dij
(b) 1
2
3
4
5
6 2
5 1
2 2
1 13
7 b1= 10
b5= −5
b6= −5 1
2
3
4
5
6 8
5 7
5 8
3 73
7
cij dij
(c) 1
2
3
4
5
6 7
5 2
1 4
1 3 4
1
2 3
b1= 10 3
b5= −5
b7= −5 1
2
3
4
5
6 7
7 5
8 9
6 5 4
2
2 9
7
cij dij
Figura 1. Reti di flusso con costi (cij) e capacit`a (dij).
1
2 CORSO DI RICERCA OPERATIVA II
1.(a) Dati B = {(1, 3), (1, 4), (3, 6), (4, 6), (5, 6)} e N1 = {(1, 3), (2, 5), (3, 2)}, per determinare i flussi xij si impostano i vincoli di conservazione del flusso, con xij= 0 se (i, j) /∈ B ∪ N1, xij = dij se (i, j) ∈ N1. Risulta quindi (si noti che l’ultima equazione `e ridondante) quanto segue.
(Nodo 1) x12+ 7 + x14= 7 (Nodo 2) −x12− 5 + 5 = 0 (Nodo 3) −7 + x36+ 5 = 0 (Nodo 4) x46− x14= 0
(Nodo 5) x56− 5 = −2
(Nodo 6) −x36− x46− x56= −5
=⇒
x12= 0 x14= 0 x36= 2 x46= 0 x56= 3
x13= 7 x25= 5 x32= 5
Valutando i costi ridotti si ottiene
1
2
3
4
5
6 0
0
2 0
3
δ ¯c13= 2
¯ c25= 3
¯ c32= 3
¯ c43= 5
Le condizioni di ottimalit`a sono violate dagli archi (1, 3), perch´e (1, 3) ∈ N1 e ¯c13> 0, (2, 5), perch´e (2, 5) ∈ N1 e ¯c25> 0, (3, 2), perch´e (3, 2) ∈ N1 e ¯c32> 0.
L’arco (3, 2) `e quindi idoneo ad entrare in base; esso individua il ciclo {(3, 2), (1, 2), (1, 4), (4, 6), (3, 6)}.
L’ammontare della variazione di flusso sugli archi del ciclo `e data da δ = min{x32, d12− x12, x14, x46, d36− x36}
= min{5, 6, 0, 0, 7} = 0.
Gli archi candidati a lasciare la base sono (1, 4) e (4, 6); arbitrariamente, si `e scelto B1= B0+ (3, 2) − (1, 4). Si passa quindi alla nuova soluzione di base degenere
B1= {(1, 2), (3, 2), (3, 6), (4, 6), (5, 6)}, N11= {(1, 3), (2, 5)}.
1
2
3
4
5
6
0 5
2 0
3 δ
¯ c14= 3
¯ c13= 5
¯ c25= 6
¯ c43= 5
L’arco (2, 5) ∈ N11viola le condizioni di ottimalit`a (x25= d25, ¯c25> 0), e pu`o quindi entrare in base. Esso induce il ciclo {(2, 5), (5, 6), (3, 6), (3, 2)}, con
δ = min{x25, x56, d36− x36, x32}
= min{5, 3, 7, 5} = 3.
ALCUNI ESERCIZI SUL FLUSSO DI COSTO MINIMO IN PRESENZA DI CAPACIT `A SUGLI ARCHI.3
Si ottiene quindi
B2= B1− (3, 6) + (2, 5) = {(1, 2), (2, 5), (3, 2), (3, 6), (4, 6)}
N12= {(1, 3)}.
1
2
3
4
5
6
0 2
2
5 0 δ
¯ c13= 5
¯ c14= 3
¯ c43= 5
¯ c56= 6
Entra quindi in base l’arco (1, 3) mentre esce (2, 3) (δ = 2).
B3= {(1, 2), (1, 3), (2, 5), (3, 6), (4, 6)}
N13= ∅
1
2
3
4
5
6 2
5
2
5 0 δ
¯ c14= −2
¯ c32= 5
¯ c43= 5
¯ c56= 1
Infine si ottiene, con δ = 5,
B4= B5+ (1, 4) − (3, 6) = {(1, 2), (1, 3), (1, 4), (2, 5), (4, 6)}
N14= ∅.
1
2
3
4
5
6 2
0
5
2
5
¯ c32= 5
¯ c36= 2
¯ c43= 3
¯ c56= 3.
La soluzione risulta ottima, poich´e tutte le condizioni di ottimalit`a sono rispettate.
(b) Valutando i costi ridotti rispetto alla base B0si ottiene quanto segue.
B0= {(1, 2), (1, 4), (2, 3), (3, 5), (3, 6)}, N10= {(2, 5), (4, 6)}
1
2
3
4
5
6 7
3
20 2 δ
¯ c25= −1
¯ c43= 3
¯ c46= 4
¯ c56= 8
4 CORSO DI RICERCA OPERATIVA II
L’arco saturo (4, 6) viola le condizioni di ottimalit`a, e pu`o quindi entrare in base.
B1= B0+ (4, 6) − (3, 6) = {(1, 2), (1, 4), (2, 3), (3, 5), (4, 6)}
N11= {(2, 5), (3, 6)}
1
2
3
4
5
6 8
2
30
2
¯ c25= −1
¯ c36= −4
¯ c43= 3
¯ c56= 4
La nuova soluzione rispetta le condizioni di ottimalit`a.
(c) Base ottima B∗= {(1, 2), (1, 3), (2, 5), (3, 4), (3, 6), (6, 7)}, N1∗= {(4, 7)}.
