Questo metodo consente di determinare il valore massimo del flusso entrante trasferibile in una rete dal nodo di origine al nodo terminale. In riferimento al caso in esame i nodi sono assimilabili alle distinte fasi di processo di un ciclo produttivo, e gli archi sono assimilabili a percorsi di flusso dotati di capacità limitata inferiormente e superiormente determinata dalla tecnologia del processo produttivo. Come si vedrà nei prossimi sotto paragrafi, si dimostra che se esiste un certo flusso il cui valore totale è uguale alla capacità di una certa sezione, allora tale flusso ha un valore totale massimo e quella sezione una capacità minima.
Reti di flusso
Un grafo orientato G=(N,A) è definito dall’insieme finito N di elementi detti nodi e dall’insieme A di coppie ordinate di nodi dette archi
i, j , dove il nodo di partenza viene chiamato nodo sorgente, mentre il nodo di arrivo viene denominato nodo pozzo. Si definisce flusso sulla rete o sul grafo la funzione x:A0 in cui xijè dettoflusso sull’arco (i,j) e sono soddisfatti i vincoli di capacità degli archi e i vincoli di bilanciamento ai nodi (legge di Kirchoff). Si definisce capacità dell’arco la funzione
0
:A
c in cui cijè detto capacità dell’arco (i,j). L’arco (i,j) è detto saturo se vale xij= cij.
Figura 73 – Coppia di nodi legati da un arco attraverso il quale passa un flusso
Valgono le seguenti definizioni e regole:
vincoli di capacità degli archi:
x
ijc
ij i ,
j
A
vincoli di bilanciamento ai nodi: j
i ij j
i ij 0 x x
è detto pozzo il nodo in cui non escono archi; è detto sorgente il nodo in cui non entrano archi;
per ogni nodo di transito la somma dei flussi degli archi entranti è pari alla somma degli archi uscenti:
i j ij i j ijx
x
per ogni nodo pozzo la somma dei flussi degli archi entranti meno la somma dei flussi degli archi uscenti è uguale alla domanda del nodo:
i j iij i j ij
b
x
x
domanda del nodo
: 0
i
N
b
iD
insieme dei nodi di domanda per ogni nodo sorgente la somma dei flussi degli archi uscenti meno la somma dei flussi degli archi entranti è uguale alla disponibilità (offerta) del nodo:
i j i ij i j ij
b
x
x
offerta del nodo
: 0
i
N
b
iO
insieme dei nodi di offerta tutti i flussi degli archi sono non negativi: xij 0.
Funzione obiettivo
Il problema è quello di determinare l’ammontare massimo di flusso che può essere inviato dal nodo sorgente al nodo pozzo rispettando i vincoli di capacità degli archi e le leggi di Kirchoff (bilanciamento ai nodi):
maximaze
i j i j i jx
c
z
, ,
i , j A
j i ij i j ijx
x
z i = 0 (nodo sorgente)subject to 0 i0,n (nodo di transito)
i j A xi,j 0, , Taglio minimo
Sia G
N,A
un grafo e S un sottoinsieme di N tale chesS
tS
(s nodo sorgente e t nodo pozzo). L’insieme di archi HS di archi di G aventi un estremo in S e l’altro estremo inT
N
\S
viene chiamato taglio. Si definiscono le seguenti partizioni di HS:
F
S: insieme degli archi in avanti al taglio, ossia gli archi diretti da S a T (archi forward);
B
S: insieme degli archi indietro al taglio, ossia gli archi diretti da T a S (archi backward).La capacità del taglio si definisce come:
S F j i i j S c H c , ,Figura 75 – Esempio di rete di flusso con taglio Hs
Nel caso in figura si ha:
2,4
,
3,4
,
7,3
SH
;
2,4, 3,4
S F ;
7,3 S B .Per ogni taglio, il valore del flusso massimo nella rete non può superare quello del costo del taglio: i j F ij i j B ij
SH
c
x
x
v
S S
, ,Se la diseguaglianza precedente diventa un’uguaglianza, allora v è massimo e HS è un
taglio a capacità minima.
Il problema del taglio a costo minimo consiste nel determinare, tra tutti i tagli possibili all’interno di una rete quello il cui costo sia il più piccolo possibile, ovvero
min
S F j i i j S c H c , ,Il problema può anche essere interpretato come l’individuazione dei colli di bottiglia (bottle necks) della rete.
Cammino aumentante
Sia P un cammino, ossia una catena orientata tra i e j da s a t non orientato, ossia tale che possa contenere archi (i, j) presi sia nel verso originale del grafo G che in quello opposto (si definisce catena tra i e j la sequenza di archi che collega i a j:
i,k1 , k1,k2
,.., km,j
con kiN, i 1,.., N ). Siano F gli archi in avanti i primi e Bgli archi all’indietro i secondi del cammino P. Il cammino P è detto aumentante rispetto al flusso v se:
F valeP x ij cij, ossia F possiede una capacità residua > 0, dunque può
ulteriormente essere caricato;
B valeP xij 0, ossia B P ha il flusso che lo attraversa positivo,
dunque può essere scaricato.
Dato un cammino aumentante P, la quantità di flusso che può percorrere il cammino è:
1, 2
min dove: 1min
cijxij:
i,j PF
2 min
xij :
i, j PB
Individuato un cammino aumentante P si può osservare che il flusso v può essere aumentato di aumentando di tale quantità il flusso su tutti gli F di P e diminuendo ugualmente diil flusso sugli archi di B di P.
Il valore v del flusso è massimo se e solo se non esistono cammini aumentanti da s a t relativamente a tale flusso.
Se tutte le capacità assegnate agli archi della rete sono intere, allora esiste un flusso di valore massimo con flussi interi sugli archi.
Grafo residuale o residuo (grafo incrementale)
Sia G
N,A
un grafo. E’ detto grafo residuo, o residuo G
N,A
il grafo ottenuto da G assegnando ad ogni arco di G al più due archi. Ad ogni arco generico (i,j) A attraversato da un flusso xijavente capacità cijcorrispondono i seguenti archi: arco a+da i a j se x
ij< cij;
arco a-da j a i se xij> 0.
A tali archi viene assegnata una lunghezza definita come: per gli archi a+: r
ij= cij– xij;
per gli archi a-: r
ji= xij.
Figura 76 – Corrispondenza degli archi tra il grafo e il residuo
Il flusso rij cij xij rappresenta la quantità ancora trasferibile nella direzione i j
fino al raggiungimento della saturazione della capacità. La definizione di r ji xij
prende spunto dalla seguente considerazione: ipotizzando di voler trasferire un flusso lungo un percorso di direzione opposta a quella dell’orientamento dell’arco
i,j , affinché la distribuzione di flusso sia ammissibile è necessario ridurre di il flusso trasferito nella direzione j i in modo da assicurare il soddisfacimento dei vincoli di bilanciamento di flusso in corrispondenza dei nodi i e j.Figura 77 – Interpretazione grafica del flusso nel grafo residuo
Teorema del maxflow – min cut
Il valore massimo di un flusso da s a t è uguale alla capacità di un taglio di minima capacità:
L’algoritmo con cui viene risolto il problema di flusso massimo fornisce immediatamente anche una soluzione per il problema di taglio a costo minimo. Il problema di taglio a costo minimo è un problema duale del problema di flusso massimo. Teorema del cammino aumentante
Considerato un flusso v il suo valore è massimo se e solo se il grafo residuo non contiene cammini aumentanti.
Algoritmo di Folk – Fulkerson
L’algoritmo di Folk – Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo.
I passi dell’algoritmo sono i seguenti: 1) porre v0, xij 0
i, j A; 2) porre A
;costruire il grafo residuale G
N,A
;per ogni arco
i,j A, nel grafo residuale corrisponderanno: A A
i,j ,
i,j vero, rij cij xij se x ij cij; A A
j,i ,
j ,i falso, r ji xij se xij 0;3) cercare un cammino aumentante P tra s e t sul grafo residuale G
N,A
; se non esiste nessun cammino allora stop vmax altrimenti P costituisce un cammino aumentante sul grafo G
N,A
4) calcolare min
cijxij:
i, j P
5) sul grafo G
N,A
i, j P porre xij xij se
i, j vero; xij xij se
i, j falso;6) porre vv e tornare al passo 2).
A titolo di esempio nelle figure che seguono è illustrata l’applicazione del metodo su una rete di flusso caratterizzata dai nodi s, t, A, B, C, D, E, D e relativi archi di capacità nota.
Problema multi sorgenti e multi pozzi
In alcuni casi può capitare che il diagramma reticolare presenti più sorgenti e più pozzi. In questo caso, al fine di impostare correttamente il problema matematico, devono essere inserite una meta sorgente (super sorgente) e un meta pozzo (super pozzo), a cui vanno collegate le sorgenti e i pozzi. Ad ogni ramo di collegamento tra super sorgente e sorgenti e super pozzo e pozzi, va assegnata una capacità infinita. Nel caso pratico è sufficiente assegnare un valore di capacità molto superiore alle capacità di tutti i rami presenti nel diagramma.
Figura 78 – Rete di flusso multi sorgente e multi pozzo