IL PROBLEMA DEL FLUSSO DI COSTO MINIMODANIEL BUCCARELLA – 698102 – danielbuccarella@virgilio.it

1. Definizione del Problema

Spesso i problemi di ottimizzazione sono caratterizzati da una struttura di grafo. In alcuni casi questa struttura nasce dal particolare modo in cui un problema viene modellato, in altri emerge in modo del tutto naturale. Si pensi, ad esempio, ad una rete stradale. Essa è rappresentabile naturalmente come un grafo in cui i nodi sono gli incroci e gli archi le strade.Nel seguito studieremo un problema di base definito su reti, enunciandone le proprietà e introducendo un semplice algoritmo risolutivo.

Con il termine “rete” indichiamo un grafo G=N , A orientato e pesato. Ai nodi e agli archi del grafo, infatti, sono associati dei valori numerici chiamati, appunto, “pesi”.Possiamo interpretare gli archi della rete come canali attraverso cui fluiscono dei beni, rappresentabili per mezzo di grandezze discrete (pensiamo al numero di messaggi attraverso una rete di comunicazione) o continue (quantità di petrolio che fluisce in un oleodotto). I beni, inoltre, possono rappresentare valori assoluti oppure valori relativi, ad esempio, ad unità di tempo.Proviamo a pensare ai pesi dei nodi come la quantità dei beni che in quei nodi entrano nella rete o ne escono. Ad ogni nodo i∈N è associato un valore reale b i

(bilancio o afflusso netto nel nodo), che può essere:

● Positivo: b i viene detto domanda del nodo, in quanto rappresenta la quantità del bene che esce dalla rete al nodo i . Il nodo viene detto destinazione, pozzo o nodo di output.

● Negativo: ­ b i viene detto offerta del nodo, in quanto rappresenta la quantità del bene che entra nella rete al nodo i . Il nodo viene detto origine, sorgente o nodo di input.

● Nullo: i viene detto nodo di trasferimento.

Pensando invece ai pesi degli archi come capacità e costi abbiamo che ad ogni arcoak=i , j sono associati un costo ck (o c ij ), indicante il costo che viene pagato per 

ogni unità del bene che attraversi l'arco, ed una capacità inferiore l k ( lij ) e superiore uk ( uij ), indicanti rispettivamente il minimo e massimo numero di unità di bene che possono attraversare l'arco.Un flusso ammissibile in una rete è una funzione f : N×N R che assegna ad ogni arco i , j un valore reale x ij che soddisfa i seguenti requisiti:

● Requisito di Capacità: ∀ i , j∈N , lij≤x ij≤u ij

● Requisito di Simmetria: ∀ i , j∈N , x ij = ­ x ji

● Requisito di Bilancio: ∀ i∈N ,∑ j∈Nx ij=bi

Il bilancio rappresenta la differenza tra il flusso entrante e il flusso uscente da un nodo; se il bilancio di un nodo i è nullo ( b i=0 ), si parla di equazione di conservazione del flusso in quanto, in questo caso, il nodo produce la stessa quantità di flusso che consuma.

Nei problemi di flusso la somma di tutte le domande (domanda globale) è uguale alla somma, cambiata di segno, di tutte le offerte (offerta globale). Definiti, cioè, gli insiemi D dei nodi di domanda e O dei nodi di offerta:

D={i∈N :bi0} ,O={i∈N : bi0},

si ha che:

∑i∈Dbi = ­∑i∈O

b i

Da ciò è facile dedurre che ∑i∈Nb i=0 .

Il costo di un flusso ammissibile è definito come:

costox = ∑i , j∈A

c ij x ij

Il problema del flusso di costo minimo: è data una rete G=N , A , con ∣A∣=m . Ad ogni arco i , j ∈A sono associati un costo c ij , una capacità inferiore lij=0 ed una capacità superiore uij . Ad ogni nodo i∈N è associato un bilancio b i . Intendiamo trovare, fra tutti i flussi ammissibili in G , il flusso (un vettore x∈Rm contenente i valori del flusso su ogni arco) che rende minimo costox .

2. Condizioni di Ottimo

Lo studio delle condizioni di ottimo, cioè delle proprietà che ci permettono di verificare se una data soluzione è ottima per il problema, costituisce il primo passo per lo sviluppo di un algoritmo. Introduciamo quindi i concetti che ci torneranno utili durante la trattazione.

Un vettore x∈Rm che rispetta tutti i vincoli di capacità sugli archi, cioè tale che0≤x≤u , è detto pseudoflusso.

Lo sbilanciamento di un nodo i rispetto a x è la quantità

ex i =∑ j∈Nx ij ­ b i

Definiamo poi

O x={i∈N : ex i0}, D x={i∈N :e x i 0}

rispettivamente l'insieme dei nodi con eccedenza di flusso e quello dei nodi con difetto di flusso. Se risulta D x=Ox=∅ , se tutti i nodi sono, cioè, bilanciati, il vettore

x rispetta il Requisito di Bilancio.Indicando con ex il vettore degli sbilanciamenti del vettore x ,

gx =∑i∈O

x

ex i

rappresenta lo sbilanciamento complessivo, calcolabile anche con la formula

gx = ­∑ j∈Dxex j

Possiamo dunque affermare che x rispetta il Requisito di Bilancio se e solo segx =0 .

Dato un qualsiasi cammino P tra una qualunque coppia di nodi s e t del grafo, consideriamo il verso di P quello che va da s a t . Gli archi del cammino risultano, quindi, partizionati nei due insiemi degli archi concordi ( P ) e discordi( P ) col verso del cammino. La capacità del cammino P rispetto al flusso x è data da:

P , x =min { min { uij ­ x ij : i , j ∈P } , min { x ij : i , j ∈P }}

Questa formula rappresenta la quantità massima di flusso che non produce flussi maggiori delle capacità se aggiunta agli archi di P e non produce flussi negativi se sottratta agli archi di P . Se accade che almeno uno degli archi di P è saturo oppure che almeno uno degli archi di P è vuoto, allora P , x =0 . Se, invece,P , x 0 , ciò significa che lungo P può essere inviata una quantità positiva di 

flusso da s verso t . P In questo caso è detto cammino aumentante.Dato uno pseudoflusso x , è possibile inviare lungo P una quantità di flusso

0≤P , x mediante l'operazione di composizione (⊕) nel modo seguente:

x ij ={ x ij + , se i , j∈P

x ij ­ , se i , j∈P

x ij , altrimenti

Lo pseudoflusso ottenuto ( x =x ⊕ P ) è tale che:

ex i ={ ex s ­ , se i=sex t + , se i=tex i , altrimenti

Inviare flusso lungo un cammino aumentante modifica, quindi, solo lo sbilanciamento dei nodi estremi del cammino, lasciando invariato quello di tutti i nodi intermedi.Il caso in cui s= t è un caso particolare di cammino aumentante: il cammino è, cioè, un ciclo aumentante C  su cui fissiamo arbitrariamente un verso di percorrenza. L'invio di flusso attraverso un tale cammino aumentante, non modificherebbe, ovviamente, lo sbilanciamento di alcun nodo. In particolare, a partire da un flusso ammissibile x , l'operazione di composizione con un ciclo aumentante C permette di costruire un diverso flusso ammissibile. In altre parole, se x è un flusso ammissibile, allora, per 0≤≤C , x , ogni flusso x =x⊕C è ancora un flusso ammissibile.Il costo di un cammino (o di un ciclo) P è il costo di un'unità di flusso inviata, secondo il verso fissato, lungo P :

c P=∑i , j∈P cij ­∑i , j∈P cij

mentre il costo del nuovo pseudoflusso è dato da

(1) cx =c x⊕ P=cxc P

Per determinare cammini o cicli aumentanti, si può utilizzare il grafo residuoG x=N , Ax rispetto allo pseudoflusso x : per ogni arco i , j ∈A poniamo i , j inAx , con costo c ij '=c ij , se e solo se x iju ij , mentre poniamo j , i in A x , con costoc ji ' = ­ c ji , se e solo se x ij0 .

In base a questa costruzione, comunque si fissino s e t , per ogni cammino aumentante da s a t rispetto a x in G , esisterà uno e un solo cammino orientato da s a t in G x . Il cammino in G e quello in G x avranno lo stesso costo.

Teorema 1: Dati due pseudoflussi qualunque x ' ed x ' ' , esistono k≤nm

cammini o cicli aumentanti per x ' , P1 , ... , P k , di cui al più m sono cicli, tali chex1=x ' , x i1

=x i⊕i Pi , per i=1, ... , k , xk1= x ' ' , dove 0i=Pi , x i

, i=1, ... , k . In  particolare, gli estremi di tutti i cammini aumentanti sono nodi in cui lo  sbilanciamento di x ' è diverso dallo sbilanciamento di x ' ' , per cui se x ' ed x ' 'hanno lo stesso vettore di sbilanciamenti, allora tutti i Pi sono cicli.

Dimostrazione: la nostra dimostrazione è di tipo costruttivo: manteniamo uno pseudoflusso x , inizialmente pari a x ' , e lo rendiamo uguale a x ' ' , utilizzando cammini e cicli aumentanti per x ' , in un numero finito di passi.Per far questo definiamo il grafo G x=N , Ax

, Ax , dove Ax

={i , j : x ij

' ' x ij} e

Ax={ j ,i : x ij

' ' x ij} . Possiamo affermare che G x descrive la differenza tra x e x ' ' . 

E', infatti, immediato verificare che A x=Ax

=∅ se e solo se x ' '=x . Associamo ora 

ad ogni arco i , j∈A x la quantità d x i , j =x ij

' ' ­ x ij0 e ad ogni arco j , i∈Ax la 

quantità d x j ,i =x ij ­ x ij' '0 e definiamo gli insiemi

O x={i∈N : ex iex ' ' i }, D x={i∈N :ex i ex ' ' i}

contenenti rispettivamente i nodi che hanno sbilanciamento rispetto a x maggiore dello sbilanciamento rispetto a x ' ' e i nodi per i quali avviene l'opposto.Avviene allora che:

● O x=Dx=∅ se e solo se x ed x ' ' hanno lo stesso vettore di sbilanciamento● tutti i nodi in O x hanno almeno un arco uscente in G x , tutti i nodi in Dx

hanno almeno un arco entrante in G x , mentre tutti i nodi in N ∖O x∪D x o non hanno né archi entranti né archi uscenti oppure hanno sia almeno un arco entrante che almeno un arco uscente.

Abbiamo ora la possibilità di costruire iterativamente i cicli e i cammini richiesti, utilizzando G x . Se A x

=Ax

=∅ , ossia x= x ' ' , il procedimento termina, altrimenti 

prendiamo in considerazione i due insiemi O x e D x : se O x≠∅ selezioniamo un nodo s∈O x , altrimenti, per costruire un ciclo, selezioniamo un qualsiasi nodo s che abbia almeno un arco uscente (e quindi almeno uno entrante). Visitiamo, dunque,

G x  a partire da s , nodo che ha sicuramente un arco uscente. Siccome, poi, ogni nodo, tranne al più quelli in Dx , ha almeno un arco uscente, in un numero finito di passi, la visita:

● o raggiunge un nodo t∈D x

● oppure torna su un nodo già precedentemente visitato.

Nel primo caso determiniamo un cammino P in G x tra un nodo s∈O x e un nodot∈D x . Su questo cammino viene inviata una quantità di flusso pari a

=min { min { d x i , j : i , j ∈P } , ex s ­ ex ' ' s , ex ' ' t ­ ex t }

Nel secondo caso determiniamo un ciclo C in G x . Su questo ciclo viene inviata una quantità di flusso pari a

=min {d x i , j : i , j ∈C }

In entrambi i casi otteniamo un nuovo pseudoflusso x che potremmo definire “più simile” ad x ' ' rispetto al precedente, in quanto, per ogni i , j di P (o C ),

d x i , j diminuisce della quantità 0 . In particolare, se si determina un cammino, si avrà che o d x i , j =0 per almeno un i , j ∈P , oppure lo sbilanciamento rispetto ad x di almeno uno tra s e t diventa pari allo sbilanciamento rispetto ad x ' ' , e quindi almeno uno tra s e t non comparirà più in O x o in D x ; se invece si determina un ciclo, allora si avrà d x i , j =0 per almeno un i , j ∈C , e quindi tale arco non comparirà più in G x .

E' da notare che il flusso può solo aumentare sugli archi di A x ' , mentre può solo 

diminuire sugli archi di A x . Non appena x ij=x ij

' ' , il flusso su i , j non viene più modificato, perciò in G x non può essere creato nessun nuovo arco.Possiamo allora concludere che ogni grafo G x è un sottografo del grafo residuo iniziale G x ' , e perciò un qualunque cammino o ciclo che viene utilizzato è aumentante rispetto allo pseudoflusso iniziale x ' .Ad ogni passo cancelliamo o almeno un nodo da O x∪D x o almeno un aro da G x , quindi, tutti gli archi di G x vengono cancellati in al più nm passi.  ◊

Il Teorema appena dimostrato ci permette di dare una caratterizzazione degli pseudoflussi ottimi e quindi dei flussi ottimi. Definiamo minimale uno pseudoflusso

x di costo minimo tra tutti gli pseudoflussi aventi lo stesso vettore di sbilanciamento ex . La soluzione ottima al nostro problema del flusso di costo minimo è un flusso ammissibile minimale, un flusso, cioè, che ha costo minimo tra tutti gli pseudoflussi aventi ex=0 .

Lemma 1: Uno flusso ammissibile (pseudoflusso) x è ottimo (minimale) se e solo  se non esistono cicli aumentanti rispetto ad x il cui costo sia negativo.

Dimostrazione: Se esiste un ciclo aumentante C rispetto ad x il cui costo c C è negativo, allora x non è minimale: per ogni 0≤C , x , lo pseudoflusso

x =x⊕C ha lo stesso vettore di sbilanciamento di x , ma, ricordando (1),cx cx .

Viceversa, sia x uno pseudoflusso tale che non esistono cicli aumentanti di costo negativo rispetto ad x . Supponiamo che esista uno pseudoflusso x ' con lo stesso vettore di sbilanciamento tale che cx 'cx , ossia supponiamo che x non sia minimale. Allora per il Teorema 1:

x '=x⊕1C 1⊕ ...⊕k C k

dove C i sono cicli aumentanti per x . Ma i i sono tutti numeri positivi, quindi, il fatto che sia cx 'cx e (1) implicano che c C i0 per un qualche i , il che contraddice l'ipotesi.

3. Soluzione Basata su Cammini Minimi Successivi

L'algoritmo basato su cammini minimi successivi sfrutta l'idea seguente: ad ogni passo mantiene uno pseudoflusso minimale x e per diminuire lo sbilanciamento di

x , al minor costo possibile, determina un cammino aumentante di costo minimo tra un nodo s∈O x e un nodo t∈D x . La minimalità degli pseudoflussi è conservata grazie all'utilizzo di cammini aumentanti di costo minimo, come dimostra il seguente

Teorema 2: Sia x uno pseudoflusso minimale e, tra tutti i cammini che uniscono un  dato nodo s∈O x ad un dato nodo t∈D x , sia P il cammino aumentante rispetto a

x di costo minimo. In qualsiasi modo venga scelto ≤P , x , x ⊕P è uno  pseudoflusso minimale.

Dimostrazione: Fissato ≤P , x , sia x ' uno pseudoflusso qualsiasi e sia ex il suo vettore di sbilanciamento. Esistono, per il Teorema 1, k cammini aumentanti

P1 , ... , P k da s a t (essendo s e t gli unici nodi per i quali differiscono ex edex ) e h cicli aumentanti C1 , ... ,Ch rispetto ad x tali che

x '=x⊕1 P1⊕ ...⊕k Pk⊕k1C1⊕ ...⊕ khCh

Inoltre, deve sicuramente essere 1...k= . x è minimale, perciò ciasuno deglih cicli aumentanti deve avere costo non negativo; inoltre P ha costo minimo tra 

tutti cammini aumentanti tra s e t , quindi si ha c P≤c Pi , i=1, ... , k . Allora:

cx '=cx1 c P1...k c Pk k1 c C1...khc Ch≥cx cP=cx

Quindi, x è minimale.                                                                                          ◊

Ricordiamo che ex s0 e che ex t 0 . L'operazione di composizione tra lo pseudoflusso x e il cammino P permette, con un'opportuna scelta di , di diminuire lo sbilanciamento complessivo. Infatti per

(2) =min { P , x , ex s , ­ ex t } > 0

x è uno pseudoflusso minimale con sbilanciamento complessivogx =g x ­ gx . Tale scelta di corrisponde alla maggiore diminuzione 

possibile dello sbilanciamento complessivo corrispondente al cammino P e allo pseudoflusso x .L'algoritmo, mostrato qui di seguito, termina se lo pseudoflusso minimale corrente ha sbilanciamento nullo (è un flusso ottimo), oppure se non esistono più cammini aumentanti tra nodi in O x e nodi in Dx (il problema non ha soluzioni ammissibili).

Algoritmo camminiMinimiSuccessivi( G , c , b , u , x , caso ){   inizializza( x );    caso := “ottimo”;   while ( gx != 0) and ( caso != “vuoto”) do      if trovaCamminoMinimo( G x , O x , D x , P , )         then aumentaFlusso( x , P , );         else caso := “vuoto”;}

Partendo dal presupposto che non esistano archi con costo negativo e capacità infinita, la procedura inizializza costruisce uno pseudoflusso x minimale nel modo seguente:

x ij ={ 0, se c ij≥0uij , altrimenti

I costi degli archi in G x risultano, così, tutti non negativi e perciò non esistono cicli orientati in G x (e cioè cicli aumentanti rispetto a x in G ) di costo negativo. x è allora minimale.La procedura trovaCamminoMinimo risolve il problema dell'albero dei cammini minimi con insieme di nodi radice O x su G x , determinando, quindi, un cammino aumentante P di costo minimo da un qualsiasi nodo s∈O x a un qualsiasi nodo

t∈D x . Se, cioè, ∣O x∣1 , essa aggiunge a G x un nodo “radice” r collegato con archi a costo nullo a tutti i nodi in O x e risolve il problema dell'albero dei cammini minimi di radice r sul grafo così ottenuto; altrimenti utilizza come radice l'unico nodo in O x . Se la procedura restituisce falso, il nostro algoritmo restituisce “vuoto” (non esiste nessuna soluzione ammissibile per il nostro problema). In caso contrario, la procedura restituisce un cammino aumentante P che unisce un nodo s∈O x a un nodo t∈D x insieme alla quantità di flusso , definita in (2), che deve essere inviata 

lungo P , invio del quale si occupa la procedura aumentaFlusso implementando l'operazione di composizione  . Se⊕ =ex s , allora il nodo s risulterà bilanciato rispetto al nuovo flusso, e lo stesso discorso vale per il nodo t se = ­ ex t ; altrimenti, è determinato dalla capacità del cammino e ciò vuol dire che almeno un arco di P diviene vuoto oppure saturo.

Se l'algoritmo descritto termina con gx =0 , allora x è un flusso ottimo. Per il Teorema 2, infatti, ad ogni passo lo pseudoflusso x è minimale in quanto l'algoritmo usa sempre cammini aumentanti di costo minimo. Nel caso in cui b e u siano interi possiamo facilmente provare la terminazione dell'algoritmo. Lo pseudoflusso iniziale, in questo caso, è anch'esso intero, e lo sono, quindi, la quantità a quell'iterazione e lo pseudoflusso x ottenuto al termine dell'iterazione. Ad ogni iterazione, di conseguenza, x è intero, ≥1 e gx diminuisce almeno di un'unità. L'algoritmo termina, perciò, in un numero finito di iterazioni. Da quanto detto segue il

Teorema 3: Per qualsiasi scelta dei costi degli archi, se le capacità degli archi ed i  bilanci dei nodi sono interi, allora esiste almeno una soluzione ottima intera per il  problema MCF.

Lo sbilanciamento complessivo dello pseudoflusso x costruito dalla procedura 

inizializza è limitato superiormente da g=∑c

ij0

uij∑b

i0

b i . Il numero delle 

iterazioni non potrà eccedere g dato che gx diminuisce di almeno un'unità ad ogni iterazione. Inoltre, si vede chiaramente che tutte le operazioni effettuate durante una singola iterazione hanno complessità al più On , esclusa l'invocazione della procedura trovaCamminoMinimo. Se per tale procedura utilizziamo un algoritmo di costruzione dell'albero dei cammini minimi che ha complessità O mn , la complessità totale di camminiMinimiSuccessivi risulta essere Og mn .

Data l'istanza del problema sopra mostrata, descriviamo, con l'aiuto della prossima figura, il funzionamento dell'algoritmo basato su cammini minimi successivi.Tutti i costo sono non negativi, quindi la procedura inizializza costruisce uno pseudoflusso iniziale identicamente nullo. Mostriamo, per ogni iterazione, sulla sinistra il grafo residuo G x e a destra lo pseudoflusso ottenuto al termine dell'iterazione. Nel grafo residuo risulta evidenziato l'albero dei cammini minimi con i valori delle corrispondenti etichette e viene mostrato il valore del flusso inviato lungo il relativo cammino aumentante da 1 a 5. I valori del flusso e gli sbilanciamenti non visualizzati sono da considerare pari a zero.Al termine della quarta iterazione tutti i nodi hanno sbilanciamento nullo e la soluzione è, perciò, ottima.

4. Bibliografia

● R. K. Ahuja, T. L. Magnanti, J. B. Orlin ­ “Network flows. Theory, algorithms and applications” ­ Prentice Hall – 1993

● M. S. Bazaraa, J. J. Jarvis, H. D. Sherali ­ “Linear programming and network flows” ­ Wiley ­ 1990