Problema del Flusso di Costo Minimo (MCF)
Il problema del Flusso di Costo Minimo è definito su una rete di flusso
rappresentata da un grafo orientato G = (N, A) in cui
ad ogni arco (i, j)  A sono associati
• cij : costo unitario di attraversamento dell’arco
• uij : capacità superiore (quantità massima di flusso che può transitare sull’arco)
ad ogni nodo i  N è associato un valore bi (detto bilancio del nodo)
i nodi con bilancio bi = 0 sono detti nodi di transito,
(non richiedono né offrono flusso)
i nodi con bilancio bi < 0 sono detti nodi origine (o sorgente)
(in essi deve essere “versato” flusso nella rete)
i nodi con bilancio bi > 0 sono detti nodi destinazione (o pozzo)
(in essi viene “prelevato” flusso dalla rete)
Partendo da un punto di vista “interno alla rete”
è possibile interpretare i valori bi come deficit dei nodi :
• i nodi sorgente hanno deficit negativo,
perché mettono a disposizione flusso ai nodi pozzo della rete
• i nodi pozzo hanno deficit positivo,
perché chiedono flusso ai nodi origine della rete
Il bilancio complessivo della rete (= somma dei bi) è nullo
b  0
iN
i
ossia
 b   b
iD
i
iO
i
Con opportuni accorgimenti ci si può sempre ricondurre
a un caso di rete a bilancio complessivo nullo.
uij , cij
origini (o sorgenti) (bi < 0) : nodi 1 e 3
bi
i
j
destinazioni (o pozzi) (bi > 0) : nodi 4 e 6
nodi di trasferimento (o transito) (bi = 0) : nodi 2 e 5
–5
2, 7
1
4
4, 3
3, 1
0
2
0
5
3, 1
3, 1
–5
3
4, 1
3
2, 4
6
7
bj
Nel caso di un problema di flusso di costo minimo
in cui la somma dei bilanci sia diversa da 0
la formulazione deve venire modificata.
Facendo l’ipotesi di avere un eccesso di offerta (somma dei bilanci negativa)
i vincoli di conservazione del flusso dei nodi sorgente
devono venire modificati in vincoli di maggiore o uguale,
infatti non tutto il flusso offerto riuscirà a partire dalle sorgenti.
Volendo ricondursi a un problema in cui tutti i vincoli sono di uguaglianza
dovremmo introdurre opportune variabili di scarto.
Dare una interpretazione in termini di flusso delle variabili di scarto
tenendo presente che nei problemi di flusso le variabili sono legate agli archi.
Problema di flusso di costo minimo :
determinare il flusso sugli archi della rete in modo che
•
dalle sorgenti parta tutto il flusso da esse messo a disposizione
•
alle origini arrivi tutto il flusso da esse richiesto
•
le capacità degli archi non siano superate
•
il costo complessivo del flusso sugli archi sia minimo
Utilizzando le variabili di flusso xij sugli archi,
la formulazione del problema è
T
min c x
Ex b
0 xu
Se in un problema di flusso di costo minimo bi = 0 per ciascun nodo i,
il problema è detto di circolazione.
In questo problema la quantità di flusso che circola nella rete
non è dettata dai bilanci, ma viene indotta dai costi sugli archi :
per indurre un flusso diverso da zero, il costo di qualche arco deve essere negativo.
Il problema dell’albero dei cammini minimi (SPT) è il caso particolare di MCF in cui
•
i costi degli archi sono dati dalle lunghezze
•
le capacità degli archi sono illimitate
•
i bilanci ai nodi sono
br = (n  1) per la radice dell’albero r (vi è un’offerta di n  1 unità di flusso)
bi = 1
per tutti gli altri nodi i (vi è una richiesta di 1 unità di flusso)
MF (massimo flusso) è caso particolare di MCF in cui
non vi sono costi di percorrenza
 (i, j)  A : uij , capacità superiore (0 < xij < uij)
Il problema di flusso massimo,
nella seconda e più generale formulazione proposta precedentemente,
è un problema di circolazione, infatti tutti i bilanci ai nodi sono zero.
Ciò che rende conveniente far circolare flusso rispetto ad una soluzione nulla
è la funzione obiettivo.
Nel caso del flusso massimo possiamo fissare il costo di tutti gli archi a 0
tranne che per l’arco fittizio di ritorno (t, s) per cui fissiamo il costo a 1.
Progetto di una rete di comunicazione
Un insieme di n terminali devono essere collegati al computer centrale.
Per ogni terminale vi sono due possibilità:
• costruire una linea diretta verso il computer centrale
• collegare il terminale tramite un concentratore
Sono a disposizione p concentratori;
ad ogni concentratore possono venire collegati al più k terminali.
La linea che connette il concentratore con il computer centrale è già presente.
Il costo di costruzione delle linee per ogni terminale i è dato da
ci0 per la linea diretta dal terminale al computer centrale
cih per la linea che collega il terminale al concentratore h.
Il problema di progettare la rete di comunicazione di costo minimo
può essere formulato come un problema di flusso su rete.
I nodi di tale rete sono
• nodo 0, che rappresenta il computer centrale :
è un nodo pozzo che richiede esattamente n unità di flusso
• nodi 1,…, p, che rappresentano i concentratori : sono nodi di transito
• nodi p + 1,…, p + n, che rappresentano i terminali :
hanno bilancio 1 (ogni nodo offre 1 unità di flusso)
Per ogni nodo-terminale i vi sono p + 1 archi uscenti :
• un arco diretto verso il nodo 0, di costo ci0
• p archi diretti verso i concentratori, di costo cih, h = 1,…, p
Un arco collega ogni concentratore h con il nodo 0, la cui capacità uh0 è uguale a k.
Le capacità degli altri archi sono poste a infinito.
Una soluzione ottima “intera” (ovvero in cui i flussi assumono tutti valore 0 o 1)
corrisponde al progetto ottimo della rete di comunicazione.
In questo caso il flusso sui singoli archi rappresenta una variabile decisionale:
se è uguale a 1 si costruisce la linea corrispondente,
se è uguale a 0 no.
Se esiste una soluzione ottima non intera,
è sempre possibile trovarne una equivalente intera.
Vi sono 2 classi di algoritmi per MCF
1) algoritmi ad eliminazione di cicli negativi (algoritmi primali)
si parte da una soluzione x ammissibile
ad ogni iterazione si riduce il costo totale della soluzione x
mantenendo soddisfatta la condizione di ammissibilità
2) algoritmi a sequenza di cammini minimi (algoritmi duali)
si parte da una soluzione x non ammissibile
che soddisfa la condizione di ottimo
ad ogni iterazione si riduce la non ammissibilità della soluzione x
mantenendo soddisfatta la condizione di ottimalità
Algoritmo primale:
determinazione di una soluzione ammissibile iniziale
Equivale al problema
“è possibile inviare dai nodi origine ai nodi destinazione un flusso di valore v
v   bi   bi
iO
?"
iD
Per rispondere alla domanda dobbiamo risolvere il problema di
determinare il flusso massimo inviabile
sul grafo G = (N, A), con capacità (superiori) degli archi uij ,
dalle sorgenti i  S (i nodi origine) ai pozzi j  T (i nodi destinazione)
aventi capacità finita ui =  bi , i  S , e uj = bj , j  T
I costi degli archi non sono tenuti in considerazione!
Ciò è fatto determinando il MF sul grafo ampliato G’ = (N’, A’)
• N’ = N  {s, t}
s e t sono la “super-sorgente” ed il “super-pozzo”
• A’ = A  {(s, i) : i  S}  {(j, t) : j  T}
gli archi che collegano la “super-sorgente” ai nodi di S = {i : bi < 0}
hanno capacità usi = – bi ;
gli archi che collegano i nodi di T = {j : bj > 0} al “super-pozzo”
hanno capacità ujt = bj ;
Se il flusso massimo “satura” tutte le sorgenti (tutti gli archi (s, i))
e, di conseguenza, tutti i pozzi (tutti gli archi (j, t)),
allora il flusso è ammissibile per il problema del flusso di costo minimo ;
altrimenti non esistono flussi ammissibili
La procedura Flusso-Ammissibile restituisce
vero ed il flusso ammissibile x , se esiste un flusso ammissibile
falso , altrimenti
Tale problema è equivalente al problema di flusso massimo
sul grafo ampliato con una super-sorgente s ed un super-pozzo t
2
1
5
4
3
2
s
5
4
5
t
3
3
4
3
3
2
7
6
capacità dell’arco dalla super-sorgente s alla sorgente i : usi =  bi
capacità dell’arco dalla destinazione j alla super-destinazione t : ujt = bj
Cicli aumentanti
Utilizzati per costruire, a partire da un flusso ammissibile x,
un diverso flusso ammissibile.
Ciclo aumentante : cammino aumentante in cui s = t
su esso il verso di percorrenza viene arbitrariamente fissato
Capacità (C, x) del ciclo C :
(C, x) = min { min{uij – xij : (i, j)  C+}, min{xij : (i, j)  C–} }
Il ciclo C è detto aumentante se la sua capacità (C, x) è positiva.
Dato un flusso ammissibile x,
l’invio di una quantità di flusso  lungo C, con 0    (C, x),
è rappresentato dall’operazione di composizione x() = x  C
 xij  θ se i, j   C 

dove xij θ    xij  θ se i, j   C 
x
altrimenti
 ij
 inviare flusso lungo un ciclo aumentante
 non modifica lo sbilanciamento di alcun nodo
 (restano tutti invariati, ossia nulli)
c(C) : il costo di una unità di flusso inviata lungo C secondo il verso fissato
cC  
c
i , j P

ij

c
i , j P

ij
• se (i, j) è un arco diretto di C
l’unità di flusso viene sommata a quelle esistenti,
sostenendo un costo aggiuntivo pari a cij
• se (i, j) è un arco inverso di C
l’unità di flusso viene sottratta a quelle esistenti,
sostenendo un “costo aggiuntivo” pari a – cij
Per determinare cicli aumentanti su G
si usa il grafo residuo Gx = (N, Ax) rispetto al flusso x, dove
Ax   i, j  : i, j   A, xij  uij  
  j, i  : i, j  A,
• un arco (i, j) non saturo e non vuoto in G (0 < xij < uij)
è rappresentato in Gx da una coppia di archi opposti
– un arco (i, j) di capacità uij – xij e costo cij’ = cij
– un arco (j, i) di capacità xij e costo cij’ = – cij
• un arco (i, j) vuoto in G (xij = 0)
è rappresentato in Gx da un arco (i, j) di capacità uij e costo cij’ = cij
• un arco (i, j) saturo in G (xij = uij)
è rappresentato in Gx da un arco (j, i) di capacità uij e costo cij’ = – cij
xij  0
Vale infatti la seguente condizione necessaria e sufficiente:
comunque fissati s e t,
per ogni cammino aumentante da s a t rispetto ad x in G
esiste uno ed un solo
cammino orientato da s a t in Gx ,
e i due cammini hanno lo stesso costo.
Algoritmo ad eliminazione di cicli
Dato un flusso ammissibile iniziale,
si costruisce una sequenza di flussi ammissibili di costo decrescente.
Ciascun flusso è ottenuto dal precedente flusso ammissibile x
redistribuendo il flusso (che soddisfa i bilanci ai nodi)
mediante un ciclo C di costo negativo
aumentante rispetto al flusso ammissibile x ;
la quantità di flusso redistribuita è pari alla capacità (C, x) del ciclo
rispetto al flusso ammissibile x ;
il nuovo flusso determinato è un flusso ammissibile di costo inferiore.
Determinazione di un ciclo di costo negativo
aumentante rispetto al flusso ammissibile x
(procedura Trova-Ciclo)
Determinare in G un ciclo di costo negativo aumentante rispetto ad x
equivale
a determinare nel grafo residuo G(x) un ciclo orientato di costo negativo
A tal fine si risolve con l’algoritmo di Bellman (SPT.L con Q implementato come fila)
il problema di determinare, sul grafo residuo G(x) associato ad x ,
un albero di cammini minimi da un insieme di radici R = N
(si considera il grafo residuo ampliato G’(x) ottenuto da G aggiungendo
• una radice fittizia r
• un arco orientato (r, j), di costo crj = 0, per ogni nodo j  N )
Proprietà dell’algoritmo di Bellman utilizzata :
in assenza di cicli negativi, l’algoritmo di Bellman
non può estrarre da Q lo stesso nodo più di n – 1 volte.
Si tiene allora un contatore del numero di volte in cui ogni nodo è estratto da Q :
l’estrazione di un nodo per l’nesima volta indica che
tale nodo appartiene ad un ciclo negativo,
che viene identificato mediante il vettore p dei predecessori
a partire dal nodo estratto n volte.
in assenza di cicli negativi l’algoritmo di Bellman
determina un albero dei cammini minimi,
il che prova che il flusso x è ottimo
(test di ottimalità sul flusso ammissibile corrente).
Se la procedura Trova-Ciclo individua sul grafo residuo G(x)
un ciclo orientato di costo negativo,
restituisce vero ed il ciclo individuato C,
con il suo verso e la sua capacità  = (C, x),
altrimenti restituisce falso.
La procedura Cambia-Flusso costruisce il nuovo flusso x() = x   C.
L’operazione di far circolare sugli archi di C un flusso pari a (C, x)
(= saturare un ciclo aumentante C) è detta “cancellazione del ciclo”
perché tale ciclo non è più aumentante per il flusso x() ;
tale ciclo può però tornare ad essere aumentante
per flussi generati successivamente.
L’algoritmo termina quando non esistono più cicli aumentanti
di costo negativo: il flusso ammissibile corrente è di costo minimo.
Procedure Cancella-Cicli (G, c, b, u, x, caso) :
begin
if Flusso -Ammissibile(G, c, b, u, x)
then begin
while Trova-Ciclo (G, c, u, x, C, ) do
Cambia-Flusso (x, C, ) ;
caso := “ottimo”
end
else caso := “vuoto”
end.
Nota:
l’algoritmo basato sulla cancellazione di cicli
è un algoritmo di ricerca locale :
l’intorno di x è dato da tutti i flussi ottenibili da x
inviando flusso lungo un ciclo aumentante semplice
Risolvere con l’algoritmo per cancellazione di cicli
il problema di flusso di costo minimo
2
(7, 1)
b1 = – 10
(10, 10)
1
3
(10, 10)
(4, 3)
4
bi
i
(uij ,cij)
j
b 2 = b3 = b4 = 0
5
b5 = 10
Fase di ammissibilità:
problema di flusso massimo sul grafo ampliato
uij
i
2
j
7
s
10
1
10
3
10
5
10
4
4
In questa istanza è facile determinare che il flusso massimo di valore 10
percorre gli archi (1, 3), (3, 5).
s
Soluzione iniziale dell’algoritmo per cancellazione di cicli :
bi
xij, (uij, cij)
i
2
0, (7, 1)
b1 = – 10
1
10, (10, 10)
3
10, (10, 10)
0, (4, 3)
4
Costo del flusso x1 : c13 x13 + c35 x35 = 200
5
b5 = 10
j
G(x1) : 13 archi; ciclo C = { (1, 4), (4, 5), (5, 3), (3, 1) } di costo 13 e capacità 2
G(x2) : 16 archi; ciclo C = { (3, 4), (4, 5), (5, 3) } di costo 1 e capacità 3
G(x3) : 16 archi; ciclo C = { (1, 2), (2, 5), (5, 3), (3, 1) } di costo 12 e capacità 2
G(x4) : 17 archi; ciclo C = { (2, 5), (5, 3), (3, 2) } di costo 4 e capacità 3
G(x5) : 17 archi; ciclo C = { (2, 5), (5, 4), (4, 3), (3, 2) } di costo 3 e capacità 1
G(x6) : 17 archi; determina un albero di cammini orientati :
il flusso x6 è un flusso di costo minimo
Algoritmo di eliminazione dei cicli negativi
Per dare un algoritmo è di grande aiuto caratterizzare le soluzioni ottime.
Sia x un flusso ammissibile per il problema.
Il grafo residuale GR(x ) associato al flusso ammissibile x
fornisce le informazioni necessarie a valutare le possibili variazioni di flusso.
Per decidere se una variazione di flusso è vantaggiosa
la componente costo è l’elemento essenziale :
ad ogni arco del grafo residuale associamo un costo residuale gij
che quantifica l’effetto sulla funzione obiettivo
di una variazione unitaria del flusso corrispondente all’arco del grafo residuale
gi , j
 ci , j

 ci , j
xi , j  ui , j
xi , j  0
Un percorso sul grafo residuale corrisponde ad una possibile variazione del flusso x,
ovvero ad una variazione
in positivo per le variabili di flusso corrispondenti ad archi di A+( –x )
in negativo per le variabili di flusso corrispondenti ad archi di A-( –x ).
Esempio: grafo residuale
Si consideri il problema di flusso di costo minimo rappresentato in fig. 29,
in cui abbiamo indicato anche una soluzione ammissibile.
Una variazione di flusso su un percorso che non si chiude su se stesso
porta ad una violazione dei vincoli di conservazione di flusso
(soddisfatti dal flusso originale x)
per modificare la soluzione senza violare i vincoli di conservazione del flusso
occorre variare il flusso su un ciclo (o su un insieme di cicli) di una stessa quantità 
Considerato un ciclo C, la massima variazione di flusso attuabile è data da:
 = min { { uij  xij : (i, j)  A+(x)  C}, {xij : (i, j)  A–(x)  C } }
Per come è stato costruito il grafo residuale,  > 0
Il flusso viene aggiornato secondo le seguenti regole:
 xi , j  

'
xi , j   xi , j  
x
 i, j
i, j   A  x   C
i, j   A  x   C
altrimenti
La variazione della funzione obiettivo è pari a
 g i , j  
i , j C
'
c

x
 i, j i, j 
i , j A
c

 
i , j A
i, j
 xi , j
 vi è un miglioramento nel valore della soluzione
solo se il ciclo C ha somma dei costi residuali negativi
Possiamo anche provare il viceversa,
ovvero che se non esistono cicli negativi nel grafo residuale
allora il flusso non è migliorabile,
come ci viene suggerito dal seguente teorema di decomposizione del flusso.
Prima di discutere del teorema introduciamo una definizione.
un flusso x è una circolazione
se la quantità di flusso entrante in ogni nodo è pari a quella uscente
cioè se
x

 
 j ,i BS
j ,i
i

x

 
i, j
i , j FS i
0
i  N
Una circolazione x è detta semplice
se gli archi (i, j) in cui xij > 0 individuano un ciclo.
Si noti che la quantità di flusso sugli archi di una circolazione semplice è costante,
a causa della conservazione del flusso.
Algoritmo a sequenza di cammini minimi
Funziona in modo incrementale,
cioè, invece che partire da una soluzione ammissibile,
tenta di costruire direttamente la soluzione ottima
inviando il flusso dai nodi sorgente ai nodi destinazione.
L’algoritmo si basa su di una diversa condizione di ottimalità,
ma comunque equivalente a quella vista in precedenza.
Richiamiamo il concetto di costo ridotto,
già visto nel caso dell’albero dei cammini minimi.
Dato un potenziale π associato ai nodi del grafo,
il costo ridotto di un arco (i, j)  A è definito come segue:
ci , j  ci , j   i   j
Dato un cammino Pxy tra il nodo x e il nodo y,
la somma dei costi ridotti è data da:
Algoritmi duali :
algoritmi a sequenza di cammini minimi
Pseudoflusso : vettore x  Rm che
 soddisfa i vincoli di capacità degli archi
0  xij  uij
 (i, j)  A
 qualche nodo i non soddisfa il vincolo di conservazione di flusso
i  N
Si definisce
ei (x ) 
 j ,i
 j ,i
x  x  b

    
BS i
ji
ij
i , j FS i
i
x  x b

    
BS i
ji
ij
i , j FS i
i
ei(x) : sbilanciamento del nodo i rispetto allo pseudoflusso x
(violazione del vincolo di conservazione di flusso al nodo i)
ei ( x) 
 j ,i
x  x b  0

    
BS i
ji
ij
i , j FS i
: nodo bilanciato
i
la somma dei flussi entranti nel nodo è uguale alla somma dei flussi uscenti
Infatti :
se i è nodo di offerta (bi < 0),
 j ,i
x b  x

 
  
BS i
ji
i
ij
i , j FS i
x

 
se i è nodo di trasferimento (bi = 0),
 j ,i
se i è nodo di domanda (bi > 0),
x

 
 j ,i
BS i
BS i
ji
ji


x

 
ij
i , j FS i
x b

 
ij
i , j FS i
i
ei ( x) 
 j ,i
x  x b  0

    
BS i
ji
ij
i , j FS i
i
: nodo con eccedenza di flusso
la somma dei flussi entranti nel nodo è maggiore della somma dei flussi uscenti
Infatti :
se i è nodo di offerta (bi < 0),
se i è nodo di trasferimento (bi = 0),
se i è nodo di domanda (bi > 0),
 j ,i
 j ,i
x b  x

 
  
BS i
ji
x

 
BS i
 j ,i
ji
x

 
BS i
ji
i


ij
i , j FS i
x

 
ij
i , j FS i
x b

 
ij
i , j FS i
i
ei ( x) 
 j ,i
x  x b  0

    
BS i
ji
ij
i , j FS i
: nodo con difetto di flusso
i
la somma dei flussi entranti nel nodo è minore della somma dei flussi uscenti
Infatti :
se i è nodo di offerta (bi < 0),
 j ,i
se i è nodo di trasferimento (bi = 0),
se i è nodo di domanda (bi > 0),
x b  x

 
  
BS i
i
ij
i , j FS i
x

 

x

 

 j ,i
 j ,i
ji
BS i
BS i
ji
ji
x

 
ij
i , j FS i
x b

 
ij
i , j FS i
i
insieme Ox dei nodi con eccedenza di flusso : Ox = { i  N : ei (x) > 0 }
insieme Dx dei nodi con difetto di flusso : Dx = { i  N : ei (x) < 0 }
sbilanciamento complessivo g(x) :
somma degli sbilanciamenti dei nodi con eccedenza di flusso
gx 
 e ( x)
iO x
i


    ei ( x ) 
 iD

x


coincide con la somma cambiata di segno
degli sbilanciamenti dei nodi con difetto di flusso)
e(x)  Rn : vettore degli sbilanciamenti ai nodi rispetto al pseudoflusso x
Pseudoflusso con sbilanciamento ai nodi :
xij
bi , ei
–5,5
0 – (– 5) – 0 = 5
i
3, – 3
0
1
0, 0
0
2
0, 0
5
0–0=0
0
0
0 – (– 5) – 2 = 3
0–0–3=–3
4
0
0–0=0
j
0
3
– 5, 3
2
6
7, – 5
2–0–7=–5
bj , ej
È uno pseudoflusso,
perché tutti i vincoli di capacità degli archi sono soddisfatti (0  xij  uij)
Vincoli di conservazione di flusso : vi sono
 2 nodi con eccedenza di flusso
nodo 1: e1(x) = (0 – 0) – (– 5) = 5
nodo 3: e3(x) = – 2 – (– 5) = 3
 2 nodi con difetto di flusso
nodo 4: e4(x) =
nodo 6: e6(x) =
0
2
– 3
– 7
=–3
=–5
 2 nodi bilanciati: 2 e 5
Lo sbilanciamento complessivo dello pseudoflusso è g(x) = 5 + 3 = 8
Flusso ammissibile x :
oltre ai vincoli di nonnegatività e di capacità degli archi  xij
soddisfa anche i vincoli di conservazione di flusso  i  N
(tutti i nodi sono bilanciati)
i
ei(x) = 0

D x = Ox = 
Un flusso ammissibile è caratterizzato
da uno sbilanciamento complessivo nullo:
x è flusso ammissibile
se e solo se
g(x) = 0
Flussi ammissibili ottimi e pseudoflussi minimali
Un flusso ammissibile ottimo è definito come
• un flusso con vettore di sbilanciamento nullo (e(x) = 0 )
• di minimo costo tra tutti i flussi con vettore di sbilanciamento e(x) = 0
Generalizzando questa definizione al caso e(x)  0 ,
si introduce il concetto di pseudoflusso minimale
Definizione
Si dice pseudoflusso minimale con sbilanciamento e(x)
uno pseudoflusso x di costo minimo
tra tutti gli pseudoflussi con vettore di sbilanciamento e(x)
Flussi ammissibili ottimi e pseudoflussi minimali:
loro caratterizzazione
Teorema
Un flusso ammissibile (uno pseudoflusso) x è ottimo (minimale)
se e solo se
non esiste un ciclo di costo negativo aumentante rispetto a x
Ciclo aumentante :
ciclo che può essere percorso da un numero positivo di unità di flusso
Algoritmo basato su cammini minimi successivi (SSPT):
inizializzazione
L’algoritmo SSPT è inizializzato con uno pseudoflusso x minimale
ottenuto con la seguente procedura (procedura Inizializza) :
se non esistono archi con costo negativo e capacità infinita,
uno pseudoflusso x minimale si ottiene attribuendo
• ad ogni arco di G con costo nonnegativo un flusso nullo:
se cij  0  xij = 0
• ad ogni arco di G con costo negativo un flusso pari alla capacità:
se cij < 0  xij = uij
Tale pseudoflusso è minimale, perché nell’associato grafo residuo Gx
non vi sono cicli orientati di costo negativo
(essendo i costi degli archi tutti nonnegativi):
quindi per lo pseudoflusso in G non esistono cicli aumentanti di costo negativo
Infatti:
nel grafo G esiste un ciclo aumentante di costo negativo rispetto a x
se e solo se
nel grafo residuo Gx rispetto ad x esiste un ciclo orientato di costo negativo
Ma un ciclo orientato di costo negativo non può esistere in Gx
perché in esso non vi sono, per costruzione, costi negativi:
• all’arco (i, j) di G al quale, essendo cij  0, è stato attribuito flusso nullo
corrisponde in Gx un unico arco (i, j), orientato come in G,
con costo cij’ = cij , quindi nonnegativo
• all’arco (i, j) di G al quale, essendo cij < 0, è stato attribuito flusso xij = uij
corrisponde in Gx un unico arco (j, i)
con costo cji’ = – cij , quindi positivo
Algoritmo basato su cammini minimi successivi (SSPT):
processo iterativo
Algoritmo Cammini-Minimi-Successivi :
processo iterativo in ogni iterazione del quale
• all’inizio si dispone di uno pseudoflusso minimale x (g(x)  0)
• si determina un cammino aumentante di costo minimo
tra un nodo s  Ox ed un nodo t  Dx
e, per un valore di   (P, x) opportunamente scelto,
si determina il nuovo pseudoflusso
con l’operazione di composizione x() = x   P
• il nuovo pseudoflusso determinato è uno pseudoflusso minimale
in forza del seguente teorema.
Teorema
Siano
• x uno pseudoflusso minimale
• P un cammino aumentante rispetto a x di costo minimo
tra tutti i cammini che uniscono
un dato nodo s  Ox ad un dato nodo t  Dx
Allora,
comunque si scelga 0 <   (P, x),
lo pseudoflusso risultante dall’operazione di composizione
x() = x  C
è uno pseudoflusso minimale.
La procedura Trova-Cammino-Minimo
deve fornire un cammino aumentante di costo minimo P
da un qualsiasi nodo s  Ox ad un qualsiasi nodo t  Dx :
 risolvere su Gx un problema di albero dei cammini minimi (SPT)
 con insieme di nodi radice Ox
Se | Ox | > 1 :
si aggiunge a Gx un nodo “radice” r
collegato a tutti i nodi in Ox con archi a costo nullo
(grafo ampliato Gx’)
e si risolve un problema SPT di radice r su Gx’
Se | Ox | = 1 :
si usa come radice l’unico nodo in Ox.
Per determinare cammini aumentanti
si usa il grafo residuo Gx = (N, Ax) rispetto allo pseudoflusso x, dove
Ax   i, j  : i, j   A, xij  uij  
  j, i  : i, j  A,
• un arco (i, j) non saturo e non vuoto in G (0 < xij < uij)
è rappresentato in Gx da una coppia di archi opposti
– un arco (i, j) di capacità uij – xij e costo cij’ = cij
– un arco (j, i) di capacità xij e costo cij’ = – cij
• un arco (i, j) vuoto in G (xij = 0)
è rappresentato in Gx da un arco (i, j) di capacità uij e costo cij’ = cij
• un arco (i, j) saturo in G (xij = uij)
è rappresentato in Gx da un arco (j, i) di capacità uij e costo cij’ = – cij
xij  0
In generale:
su un grafo contenente un ciclo negativo la procedura SPT non termina
In particolare:
quando applicata come passo interno di un algoritmo SSPT
la procedura termina individuando un albero dei cammini minimi,
perché essendo x minimale, non esistono in Gx cicli negativi.
Si possono utilizzare:
• algoritmo SPT.S :
ad ogni iterazione si estrae da Q un elemento di etichetta minima
Proprietà:
su grafi con costi nonnegativi
ogni nodo è inserito in (ed estratto da) Q al più una volta
• algoritmo di Bellman:
Q è una fila,
ossia strategia FIFO: inserimento in coda - estrazione in testa
Proprietà:
anche in presenza di archi con costo negativo,
purché in assenza di cicli di costo negativo,
la strategia FIFO garantisce che
ogni nodo sia inserito in Q al più n – 1 volte
Cammini aumentanti
Utilizzati per l’invio di quantità aggiuntive di flusso
Sia P un cammino (anche non orientato) sul grafo G
da un qualunque nodo s ad un qualunque nodo t
Sia (P+, P– ) la partizione degli archi di P in cui
P+ : insieme degli archi concordi del cammino P
P– : insieme degli archi discordi del cammino P
Capacità del cammino P :
(P, x) = min { min{uij – xij : (i, j)  P+}, min{xij : (i, j)  P–} }
Il cammino P è detto aumentante se la sua capacità (P, x) è positiva.
Dato uno pseudoflusso x,
l’ invio di una quantità di flusso  lungo P, con 0    (P, x),
è rappresentato dall’operazione di composizione x() = x  P
 xij  θ se i, j   P 

dove xij θ    xij  θ se i, j   P 
x
altrimenti
 ij
per lo pseudoflusso x() così ottenuto vale che
es  x   θ

ei  x θ   et  x   θ
e  x 
i
 l’invio di flusso lungo un cammino aumentante modifica solo
 lo sbilanciamento degli estremi del cammino ;
 lo sbilanciamento di tutti gli altri nodi è invariato
c(P) : costo di una unità di flusso inviata lungo P secondo il verso fissato
c P  
c
i , j P

ij

c
i , j P

ij
• se (i, j) è un arco diretto di P
l’unità di flusso viene sommata a quelle esistenti,
sostenendo un costo aggiuntivo pari a cij
• se (i, j) è un arco inverso di P
l’unità di flusso viene sottratta a quelle esistenti,
sostenendo un “costo aggiuntivo” pari a – cij
Costo dello pseudoflusso (flusso)
ottenuto con l’operazione di composizione
cTx() = cT(x  P) = cTx +  c(P)
Terminazione dell’algoritmo Cammini-Minimi-Successivi
L’algoritmo Cammini-Minimi-Successivi termina
quando si verifica una delle due seguenti condizioni
1) lo sbilanciamento complessivo di x è nullo:
x è un flusso ammissibile di costo minimo (ottimo)
2) non esiste alcun cammino aumentante
tra qualsiasi nodo s  Ox e un nodo t  Dx :
non esiste nessuna soluzione ammissibile
per il problema di flusso di costo minimo
Vale infatti la seguente condizione necessaria e sufficiente:
comunque fissati s e t,
per ogni cammino aumentante da s a t rispetto ad x in G
esiste uno ed un solo
cammino orientato da s a t in Gx ,
e i due cammini hanno lo stesso costo.
Calcolato l’albero dei cammini minimi con un algoritmo SPT,
si seleziona un qualsiasi nodo t  Dx
e si esamina il valore della sua etichetta.
 dt = M :
non esiste alcun cammino aumentante tra qualsiasi nodo s  Ox e t
 Trova-Cammino-Minimo restituisce falso
 Cammini-Minimi-Successivi restituisce caso = “vuoto”:
il problema di flusso di costo minimo non ha soluzioni ammissibili
 dt < M :
Trova-Cammino-Minimo restituisce
 vero
 il cammino aumentante P che unisce un nodo s  Ox
al nodo t  Dx selezionato,
 la quantità di flusso  che deve essere inviata lungo P
  min   P, x , es  x ,  et  x  
Procedura Aumenta-Flusso: implementa l’operazione di composizione 
• se  = es(x): il nodo s risulterà bilanciato rispetto al nuovo flusso
• se  = – et(x): il nodo t risulterà bilanciato rispetto al nuovo flusso
• se  = (P, x): almeno un arco di P diviene saturo o vuoto
Siccome l’algoritmo usa sempre cammini aumentanti di costo minimo,
ad ogni passo lo pseudoflusso x è minimale:
quindi, se l’algoritmo termina con g(x) = 0, allora x è un flusso ottimo.
Proprietà di integralità della soluzione:
se le capacità uij degli archi ed i deficit bi dei nodi sono interi,
allora per qualsiasi scelta dei costi cij degli archi
esiste almeno una soluzione ottima intera per il problema MCF.
Procedure Cammini-Minimi-Successivi (G, c, b, u, x, caso):
begin
Inizializza(x) ;
caso := “ottimo” ;
while g(x)  0 and caso  “vuoto” do
if Trova-Cammino-Minimo(Gx , Ox , Dx , P , )
then Aumenta-Flusso(x , P, )
else caso := “vuoto”
end.
Risolvere con l’algoritmo per cancellazione di cicli
il problema di flusso di costo minimo
2
(7, 1)
b1 = – 10
(10, 10)
1
3
(10, 10)
(4, 3)
4
bi
i
(uij ,cij)
j
b 2 = b3 = b4 = 0
5
b5 = 10
Fase di ammissibilità:
problema di flusso massimo sul grafo ampliato
uij
i
2
j
7
s
10
1
10
3
10
5
10
s
4
4
In questa istanza è facile determinare che il flusso massimo di valore 10
percorre gli archi (1, 3), (3, 5).
Soluzione iniziale dell’algoritmo per cancellazione di cicli :
bi
xij, (uij, cij)
i
2
0, (7, 1)
b1 = – 10
1
10, (10, 10)
3
10, (10, 10)
0, (4, 3)
4
Costo del flusso x1 : c13 x13 + c35 x35 = 200
5
b5 = 10
j
Determinare in G un ciclo di costo negativo aumentante rispetto ad x1
è equivalente a
determinare nel grafo residuo G(x1) un ciclo orientato di costo negativo :
cij’
i
2
0
1
1
–10
3
3
4
–10
5
j
L’algoritmo di Bellman individua sul grafo residuo G(x1)
il ciclo orientato di costo negativo C = { (1, 4), (4, 5), (5, 3), (3, 1) }
2
bi
i
(uij’, cij’)
j
(7, 1)
b1 = – 10
1
(10, –10)
3
(10, –10)
5
b5 = 10
(4, 3)
4
Costo c(C) del ciclo C : costo dell’invio di un’unità di flusso lungo C
cC  
c

 
i , j C
ij
 1  6  10  10  13
Capacità (C, x1) del ciclo C rispetto al flusso x1 : min {2, 5, 10, 10} = 2
Il nuovo flusso ammissibile x2 è
bi
2
xij, (uij, cij)
i
0, (7, 1)
b1 = – 10
1
8, (10, 10)
3
8, (10, 10)
0, (4, 3)
4
Costo del flusso x2 : 200 – 13 · 2 = 174
5
b5 = 10
j
Test di ottimalità :
? = esiste in G un ciclo di costo negativo aumentante rispetto ad x2 ?
Per rispondere a questa domanda cerchiamo nel grafo residuo G(x2)
un ciclo orientato di costo negativo :
cij’
i
0
j
2
1
1
10
–10
3
3
4
10
–10
5
L’algoritmo di Bellman individua sul grafo residuo G(x2)
il ciclo orientato di costo negativo C = { (3, 4), (4, 5), (5, 3)}
2
bi
(7, 1)
b1 = – 10
1
(2, 10)
(8, –10)
3
(2, 10)
(8, –10)
i
5
(uij’, cij’)
j
b5 = 10
(4, 3)
4
Costo c(C) del ciclo C : costo dell’invio di un’unità di flusso lungo C
cC  
c

 
i , j C
ij
 3  6  10  1
Capacità (C, x2) del ciclo C rispetto al flusso x2 : min {8, 4, 3} = 3
Il nuovo flusso ammissibile x3 è
bi
2
xij, (uij, cij)
i
0, (7, 1)
b1 = – 10
1
8, (10, 10)
3
5, (10, 10)
3, (4, 3)
4
Costo del flusso x3 : 174 – 1 · 3 = 171
5
b5 = 10
j
Test di ottimalità :
? = esiste in G un ciclo di costo negativo aumentante rispetto ad x3 ?
Per rispondere a questa domanda cerchiamo nel grafo residuo G(x3)
un ciclo orientato di costo negativo :
bi
0
cij’
i
2
1
1
10
–10
3
4
10
–10
5
j
L’algoritmo di Bellman individua sul grafo residuo G(x3)
il ciclo orientato di costo negativo C = { (1, 2), (2, 5), (5, 3), (3, 1) }
2
bi
(7, 1)
b1 = – 10
1
(2, 10)
(8, –10)
3
(5, 10)
(5, –10)
5
i
(uij’, cij’)
j
b5 = 10
4
Costo c(C) del ciclo C : costo dell’invio di un’unità di flusso lungo C
cC  
c

 
i , j C
ij
 3  5  10  10  12
Capacità (C, x3) del ciclo C rispetto al flusso x3 : min {2, 6, 5, 8} = 2
Il nuovo flusso ammissibile x4 è
bi
2
xij, (uij, cij)
i
0, (7, 1)
b1 = – 10
1
6, (10, 10)
3
3, (10, 10)
3, (4, 3)
4
Costo del flusso x4 : 171 – 12 · 2 = 147
5
b5 = 10
j
Test di ottimalità :
? = esiste in G un ciclo di costo negativo aumentante rispetto ad x4 ?
Per rispondere a questa domanda cerchiamo nel grafo residuo G(x4)
un ciclo orientato di costo negativo :
cij’
i
0
2
1
1
10
–10
3
4
10
–10
5
j
L’algoritmo di Bellman individua sul grafo residuo G(x4)
il ciclo orientato di costo negativo C = { (2, 5), (5, 3), (3, 2) }
2
bi
i
(uij’, cij’)
j
(7, 1)
b1 = – 10
1
(4, 10)
(6, –10)
3
(7, 10)
(3, –10)
5
b5 = 10
4
Costo c(C) del ciclo C : costo dell’invio di un’unità di flusso lungo C
cC  
c

 
i , j C
ij
 10  1  5  4
Capacità (C, x4) del ciclo C rispetto al flusso x4 : min {4, 3, 7} = 3
Il nuovo flusso ammissibile x5 è
bi
2
xij, (uij, cij)
i
3, (7, 1)
b1 = – 10
1
6, (10, 10)
3
0, (10, 10)
3, (4, 3)
4
Costo del flusso x5 : 147 – 4 · 3 = 135
5
b5 = 10
j
Test di ottimalità :
? = esiste in G un ciclo di costo negativo aumentante rispetto ad x5 ?
Per rispondere a questa domanda cerchiamo nel grafo residuo G(x5)
un ciclo orientato di costo negativo :
cij’
i
0
2
1
10
–10
3
4
10
5
j
L’algoritmo di Bellman individua sul grafo residuo G(x5)
il ciclo orientato di costo negativo C = { (2, 5), (5, 4), (4, 3), (3, 2) }
2
b1 = – 10
1
(4, 10)
(6, –10)
bi
3
(10, 10)
5
i
(uij’, cij’)
j
b5 = 10
4
Costo c(C) del ciclo C : costo dell’invio di un’unità di flusso lungo C
cC  
c

 
i , j C
ij
 5  6  3  1  3
Capacità (C, x5) del ciclo C rispetto al flusso x5 : min {1, 5, 3, 4} = 1
Il nuovo flusso ammissibile x6 è
bi
2
xij, (uij, cij)
i
4, (7, 1)
b1 = – 10
1
6, (10, 10)
3
0, (10, 10)
2, (4, 3)
4
Costo del flusso x6 : 135 – 3 · 1 = 132
5
b5 = 10
j
Test di ottimalità :
? = esiste in G un ciclo di costo negativo aumentante rispetto ad x6 ?
Per rispondere a questa domanda cerchiamo nel grafo residuo G(x6)
un ciclo orientato di costo negativo :
0
i
2
1
10
–10
4
cij’
3
10
j
5
Sul grafo residuo G(x6) l’algoritmo di Bellman
determina un albero dei cammini minimi,
anziché un ciclo orientato di costo negativo :
2
d1 = – 19
1
10
–10
d2 = – 8
d3 = – 9
3
10
5
d5 = 0
d4 = – 6 4
Poiché in G(x6) non esistono cicli orientati di costo negativo,
allora in G non esistono cicli di costo negativo aumentanti rispetto ad x6,
quindi il flusso x6 è un flusso di costo minimo.