Laboratorio 5 Fondamenti di Ricerca Operativa Prof. E. Amaldi
Affidabilit`a di rete
Si consideri la rete che consiste di undici siti connessi da linee bidirezionali per la trasmissione dei dati, mostrata sotto.
1
3
11
4
5 9
6 7
10
2 8
Per ragioni di affidabilit`a, le specifiche di rete richiedono che i due siti 10 e 11 rimangano comunicanti anche se altri tre nodi siano malfunzionanti. La rete mostrata sopra soddisfa a queste specifiche?
Documento preparato da Leo Liberti 1
Laboratorio 5 Fondamenti di Ricerca Operativa Prof. E. Amaldi
Soluzione
Questo problema si pu`o vedere come un problema di flusso massimo su un grafo diretto con capacit`a unitarie sugli archi. In particolare, si richiede che i cammini tra i nodi di sorgente e di destinazione siano disgiunti (cosicch´e se un nodo dovesse rompersi, esso distruggerebbe al massimo un solo cammino esistente). Questo si ottiene assegnando capacit`a unitarie ai nodi (in modo che se un cammino passa dal nodo i, nessun altro cammino vi possa passare). NB La trasformazione di un problema di cammini in uno di flussi `e simile a quella che si effettua per la determinazione del matching bipartito (si vedano i lucidi delle lezioni).
Formulazione
• Parametri
1. N ⊆ N: insieme dei nodi del grafo;
2. s: nodo sorgente;
3. t: nodo destinazione;
4. A ⊆ N × N: insieme degli archi del grafo.
• Variabili. Per ogni (i, j) ∈ A: xij = flusso sull’arco (i, j) (0 ≤ xij ≤1).
• Funzione obiettivo.
max X
(s,i)∈A
xsi
• Vincoli
1. (conservaz. flusso): ∀ n ∈ N : n 6= s, n 6= t: P
(i,n)∈A
xin = P
(n,i)∈A
xni; 2. (cammini disgiunti): ∀ n ∈ N , n 6= s, n 6= t: P
(n,i)∈A
xni ≤1;
3. (no riflusso): P
(i,s)∈A
xis = 0.
Documento preparato da Leo Liberti 2
Laboratorio 5 Fondamenti di Ricerca Operativa Prof. E. Amaldi
File modello in AMPL
# modello AMPL per il problema di network reliability param nodi >= 0, integer;
set N := 1..nodi;
param s >= 0, integer;
param t >= 0, integer;
set lati within {N,N};
set A := {i in N, j in N : (i,j) in lati or (j,i) in lati};
var x { A } >= 0, <= 1;
maximize flusso: sum{(s,j) in A} x[s,j];
subject to conservazione {n in N : n != s and n != t}:
sum{(i,n) in A} x[i,n] = sum{(n,i) in A} x[n,i];
subject to camminidisgiunti {n in N : n != s and n != t}:
sum{(n,i) in A} x[n,i] <= 1;
subject to noriflusso: sum{(i,s) in A} x[i,s] = 0;
File dati in AMPL
# dati AMPL per il problema di network reliability param nodi := 11;
param s := 10;
param t := 11;
set lati :=
1 2 1 3 1 11 2 3 2 8 2 9 3 4 3 9 3 10 3 11 4 5 4 6 4 11 5 9 5 11 6 7
Documento preparato da Leo Liberti 3
Laboratorio 5 Fondamenti di Ricerca Operativa Prof. E. Amaldi
6 9 6 10 7 8 7 10 8 10 9 10 ;
File netwrely.run per lanciare AMPL
model netwrely.mod;
data netwrely.dat;
option solver cplexstudent;
solve;
display flusso;
display x;
Soluzione numerica
CPLEX 7.1.0: optimal solution; objective 4 11 simplex iterations (0 in phase I)
flusso = 4 x [*,*]
: 1 2 3 4 5 6 7 8 9 10 11 :=
1 . 0 0 . . . 1
2 1 . 0 . . . . 0 0 . .
3 0 0 . 0 . . . . 0 0 1
4 . . 0 . 0 0 . . . . 1
5 . . . 0 . . . . 0 . 1
6 . . . 1 . . 0 . 0 0 .
7 . . . 0 . 0 . 0 .
8 . 1 . . . . 0 . . 0 .
9 . 0 0 . 1 0 . . . 0 .
10 . . 1 . . 1 0 1 1 . .
11 0 . 0 0 0 . . . .
;
Documento preparato da Leo Liberti 4
