Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 19.Ottimizzazione su rete: Problemi di flusso


Schema della lezione

In questa lezione si descrivono i problemi di flusso su rete, con particolare riferimento al problema generale di flusso Single-Commodity, con costi costanti e costi variabili. Per introdurre il concetto di configurazione dei flussi si presenta un semplice problema di flusso con due variabili. Si presentano quindi la struttura e le proprietà del modello di flusso Single-Commodity e l’algoritmo del Simplesso su rete che da esse scaturisce. Si descrivono poi il problema di flusso Multi-Commodity e il problema del Massimo Flusso. Si descrive infine un quadro dei problemi di flusso e di percorso su rete.

Il problema di flusso Single-Commodity con costi costanti

Assegnata una rete orientata R (V, A, C) si indichi con:

O l’insieme dei vertici origine di flusso, F l’insieme dei vertici destinazione di flusso, mij la capacità dell’arco ij, gi il flusso generato da un vertice i,ai il flusso attratto da un vertice i, fij il flusso totale su ij; cij il costo costante di utenza per unità di flusso sull’arco ij. Si assuma che alcuni vertici sono origine di un flusso gi (generato), altri vertici sono destinazione di un flusso aj (attratto) ed altri ancora sono vertici di attraversamento. Si assuma infine che la somma dei flussi generati sia pari alla somma dei flussi attratti: iO gi = jF aj.

Si vuol determinare la configurazione dei flussi sugli archi della rete che soddisfi i vincoli di generazione e di attrazione al costo minimo.

Nel seguito si formula il modello di ottimizzazione e si presenta un semplice problema con due variabili al fine di dare una rappresentazione grafica del dominio di ammissibilità del problema, senza e con vincoli di capacità.

Il modello di flusso single – commodity

La funzione obiettivo esprime la minimizzazione del costo totale sulla rete. I vincoli esprimono il bilancio dei flussi in ciascun vertice. Se il vertice è generatore di flusso il bilancio è pari al flusso generato. Se il vertice è attrattore di flusso il bilancio è pari al flusso attratto. Altrimenti, cioè se non è né generatore né attrattore il bilancio è pari a 0.

\text{Min  }z=\sum_{ij\in A}c_{ij}f_{ij}

\sum_kf_{jk}-\sum_if_{ij}=\left[\begin{array}{lll}g_i\hspace{1,5cm}\forall j\in O\\-a_j\hspace{1,3cm}\forall j\in F\\0\hspace{1,7cm}\text{  altrimenti}\end{array}

f_{ij}\geq 0\\;\;\;\forall ij\in A

Un problema di flusso con 2 variabili

Si consideri la rete di figura costituita da due vertici (1 e 2) e dai due archi che li congiungono, (1-2)’ e (1-2)”. Il vertice 1 è generatore ( g1 = 1000), il vertice 2 è attrattore (a2 = 1000). Si vuol determinare la configurazione dei flussi sui due archi (cioè i valori di f(1-2)’ ed f(1-2)”) che minimizzi il costo totale sostenuto dalle 1000 unità di flusso.

Si supponga che il costo di spostamento per unità di flusso sugli archi sia costante, cioè non dipendente dal flusso (c(1-2)’ = 10 e c(1-2)” = 5) e che la capacità degli archi sia infinita (non ci siano vincoli di capacità sugli archi).

Si può formulare per questo problema un modello di flusso single-commodity.


Dominio di ammissibilità del modello senza vincoli di capacità

Il modello di flusso single-commodity presenta in questo caso semplice la seguente formulazione: Min z = 10 f(1-2)’ + 5 f(1-2)” …. s.a. f(1-2)’ + f(1-2)” = 1000

Il dominio di ammissibilità, riportato in figura, è costituito dal segmento CD. Il vertice ottimo è C, corrispondente alla soluzione, ovvia, f(1-2)’ = 0, f(1-2)” = 1000. Infatti se il costo sugli archi è indipendente dal flusso e la capacità degli archi infinita, tutto il flusso generato nel vertice 1 utilizzerà l’arco di costo minimo.

La funzione obiettivo, lineare, esprime il costo totale sulla rete e c’è un solo vincolo che esprime il bilancio nel vertice 1 (o nel vertice 2). Il modello presenta dunque la seguente formulazione:

Min z = 10 f(1-2)’ + 5 f(1-2)”

s.a. f(1-2)’ + f(1-2)” = 1000

Il dominio di ammissibilità, riportato in figura, è costituito dal segmento CD. Il vertice ottimo è C, corrispondente alla soluzione f(1-2)’ = 0, f(1-2)” = 1000. Infatti se il costo sugli archi è indipendente dal flusso e la capacità degli archi infinita, tutto il flusso generato nel vertice 1 utilizzerà l’arco di costo minimo.


Problema di flusso single commodity con vincoli di capacità

Si supponga ora che le capacità dei due archi siano finite e siano rispettivamente pari a 600 e 800. Il modello deve contenere ora i vincoli di capacità sui due archi, f(1-2)’ ≤ 600 e f(1-2)” ≤ 800. Mantenendo la stessa funzione obiettivo il sistema dei vincoli sarà:

f(1-2)’ + …. f(1-2)” = 1000
f(1-2)’ ≤ 600
f(1-2)”  ≤ 800

Il dominio di ammissibilità, riportato in figura, è costituito ora dal segmento EF. Il vertice ottimo è E, corrispondente alla soluzione f(1-2)’ = 200, f(1-2)’ = 800. In questo caso il flusso con origine nel vertice 1 viene assegnato all’arco di costo minimo, fino al limite della sua capacità, e poi al secondo arco per la parte di flusso rimanente. La configurazione dei flussi risultante è riportata nella figura della slide successiva.


Configurazione dei flussi di costo minimo


Struttura e proprietà del modello di flusso single commodity

Il modello di flusso single-commodity ha la stessa struttura del modello di minimo percorso. Le righe corrispondono ai vertici del grafo e le colonne corrispondono agli archi. Si consideri la rete R (V, A, C) con 4 vertici e 7 archi riportata in figura. La matrice A dei coefficienti associata ai vincoli del modello corrisponde alla matrice di incidenza vertice-arco e dunque ha dimensioni v a = 4×7 (Tabella). La riga corrispondente al vertice i contiene +1 nelle colonne corrispondenti agli archi ik uscenti da i, -1 nelle colonne corrispondenti agli archi ji entranti in i, 0 altrove. Pertanto ogni colonna, corrispondente all’arco ij, ha soltanto due elementi non nulli, +1 e -1, +1 nella riga i, -1 nella riga j, 0 altrove.

Proprietà della Matrice A dei coefficienti del modello
Il rango di A non è massimo perché la somma di tutte le righe è il vettore nullo. Si può dimostrare che il rango di A è pari ad v-1, se v è il numero dei vertici . Per fare ciò è necessario individuare in essa un minore di dimensioni (v-1)·(v-1) che sia non singolare. Questo risultato si ottiene dimostrando che la sottomatrice di A costituita dalle colonne corrispondenti agli archi di un albero estratto dalla rete R ha rango (v-1). Ciò equivale in pratica a dimostrare che un albero estratto dalla rete G corrisponde ad un insieme di colonne linearmente indipendenti cioè ad una soluzione basica ammissibile. La dimostrazione è riportata sul testo di riferimento.

Corrispondenza tra albero e soluzione basica ammissibile


Algoritmo del Simplesso su rete

La struttura e le proprietà del modello di flusso single-commodity con costi costanti e senza vincoli di capacità, consente una particolare applicazione dell’algoritmo del Simplesso. È possibile infatti sviluppare l’algoritmo senza costruire le tabelle, ma utilizzando la struttura dei dati della rete. L’algoritmo presenta gli stessi passi del simplesso tabellare. Esso si articola dunque in:

  • determinazione di una prima soluzione basica ammissibile
  • calcolo dei coefficienti di costo modificati cij
  • test di ottimalità
  • determinazione della nuova soluzione basica ammissibile, cioè
    • determinazione della variabile entrante
    • determinazione della variabile uscente
    • modifica della composizione della base

Per illustrare i passi dell’algoritmo si utilizzerà la rete in figura nella slide successiva sulla quale si riporta per ciascun vertice la quantità di flusso generata o attratta e per ciascun arco ij il costo cij. La tabella iniziale del Simplesso relativa al modello di flusso single-commodity è riportata nella slide successiva.

Prima soluzione basica ammissibile

Si è detto che una soluzione basica ammissibile del modello di flusso single-commodity corrisponde ad un albero. Quindi una prima soluzione basica ammissibile può essere determinata direttamente sulla rete, costruendo un albero compatibile con il problema, cioè avente almeno un arco uscente da un vertice generatore di flusso ed almeno un arco entrante in un vertice attrattore. In un qualunque vertice foglia l’equazione di continuità contiene soltanto una incognita e quindi può essere agevolmente risolta calcolando il valore di flusso sull’arco incidente nel vertice foglia. Si risale dunque lungo l’albero, risolvendo i vertici con due soli archi incidenti (uno in ingresso ed uno in uscita) e dunque con una sola variabile di flusso incognita, fino ad incontrare un vertice (con più di due archi incidenti) in cui l’equazione di continuità contiene più di una variabile flusso incognita. A questo punto si riparte da un altro vertice foglia e si effettua la procedura descritta, calcolando i valori di flusso sugli archi. Sul testo di riferimento è riportato un esempio numerico.

Rete e costi cij, Prima s.b.a., Tabella iniziale del Simplesso

Rete e costi cij

Rete e costi cij

Prima s.b.a.

Prima s.b.a.

Tabella iniziale del Simplesso

Tabella iniziale del Simplesso


Calcolo dei coefficienti di costo modificati cij

Il calcolo dei coefficienti di costo modificati si effettua con una semplice procedura di tipo reticolare. Infatti i coefficienti di costo modificati delle variabili non basiche corrispondono agli archi delle rete non appartenenti all’albero associato alla prima soluzione basica ammissibile, costituenti cioè il cosiddetto co-albero dell’albero stesso.

Il calcolo di questi coefficienti può essere effettuato sulla rete con la procedura seguente:

  • si individua il circuito determinato dall’arco non basico ij con l’albero-base, e si assegna ad esso una orientazione coerente con ij
  • si sommano i costi sugli archi del circuito, con il proprio segno o con il segno opposto, rispettivamente se l’arco è equiverso o controverso all’orientazione scelta

Lo sviluppo di questa procedura equivale in pratica alla effettuazione delle operazioni del simplesso tabellare. È facile infatti verificare la corrispondenza tra le operazioni sviluppate su rete e le operazioni di tipo algebrico descritte nella lezione sull’algoritmo del simplesso revisionato.


Calcolo dei coefficienti di costo modificati cij


Calcolo dei coefficienti di costo modificati cij


Determinazione della variabile entrante e uscente e seconda soluzione basica ammissibile

La variabile entrante, corrispondente al valore minimo dei cij‘, c13‘ = 6 è la f13. La variabile uscente deve essere determinata tra le variabili basiche corrispondenti agli archi costituenti ciclo con l’arco 1-3 cui è associata la variabile f13. Infatti, se f13 entra in base, è necessario che una di queste variabili basiche si annulli, per mantenere la configurazione ad albero corrispondente ad una soluzione basica ammissibile. Si individua quindi il ciclo determinato dall’arco 1-3 con gli archi dell’albero e lo si percorre in senso equiverso ad esso, aggiungendo flusso agli archi equiversi e sottraendo flusso agli archi controversi. Per rispettare il bilancio nei vertici, se la variabile f13 aumenta di una quantità δ è necessario decrementare f23 ed f12 dello stesso ammontare. Poiché il minimo tra i valori di flusso degli archi del circuito è f23 = 1, questa sarà la prima variabile ad annullarsi ed è dunque la variabile uscente. Si ha dunque δ = 1.
La composizione della nuova soluzione basica ammissibile corrispondente all’albero riportato in figura è dunque la seguente: f13 = 1, f12 = 3, f23 = 0, f24 = 5.


Determinazione della terza s.b.a.


Determinazione della quarta s.b.a.


Test di ottimalità


Il problema del trasporto

Con l’espressione “problema del trasporto” si indica tradizionalmente un problema di flusso single-commodity a costi costanti definito su una rete bipartita (vedi slide successiva). A ciascun arco ij è associato un costo per unità di flusso pari a cij. I vertici origine degli archi sono generatori di flusso. I vertici destinazione sono attrattori di flusso. Sia gi la disponibilità in ciascun vertice i generatore di flusso (gi > 0). Sia aj la richiesta in ciascun vertice j attrattore (aj>0). Sia O l’insieme dei vertici generatori ed F l’insieme dei vertici attrattori. Si assume che sia soddisfatta la condizione ∑i∈O gi = ∑j∈F aj.

Con queste assunzioni il modello di flusso single-commodity descritto assume dunque la seguente configurazione:

Min z = ∑ij∈A cijfij

s.a ……

j∈F fij = gi  iO
i∈O fij = aj . jF
fij ≥ 0

Problema del trasporto


Metodo dell’angolo di Nord – Ovest per la prima s.b.a.


Il problema dell’assegnamento

Il problema dell’assegnamento è un classico problema di ottimizzazione combinatoria che viene formulato con un modello che può essere derivato dal modello del trasporto già descritto. Il problema può essere schematizzato nel modo seguente:

  • è necessario assegnare n addetti a n mansioni
  • ciascuno addetto i è in grado di svolgere ciascuna mansione j con un costo cij noto
  • ciascun addetto può essere assegnato ad una sola mansione e ciascuna mansione può essere svolta da un solo addetto
  • si vuole determinare l’insieme di accoppiamenti addetto-mansione che realizzi il costo di assegnamento minimo

Il valore cij è una misura del costo di assegnamento dell’addetto i alla mansione j. Il problema è dunque individuato da una matrice dei costi cij positivi, C = {cij}, di dimensioni [nxn]. Per formulare il modello si può associare una variabile xij binaria a ciascun accoppiamento ij:

  • xij= 1 se l’addetto i è assegnato alla mansione j
  • xij= 0 se l’addetto i non è assegnato alla mansione j

Il modello dell’assegnamento

Il modello assume dunque la seguente configurazione:

Min z = ∑ij=1,n cijxij

s.a

jxj = i = 1, …, n
jxj = 1 j = 1, …, n
xij ≥ 0/1 ij, i = 1, …, n,  j = 1, …, n

Il primo gruppo di vincoli esprime la condizione che ciascun addetto deve essere assegnato ad una sola mansione, il secondo che ogni mansione deve essere svolta da un solo addetto.

Per la soluzione del problema dell’assegnamento si possono utilizzare versioni specializzate dell’algoritmo del Simplesso. Il problema può anche essere risolto in modo approssimato con un algoritmo euristico molto semplice, che genera rapidamente una soluzione ammissibile:

1. Si individui un elemento ij della matrice C dei costi cij
2. Si ponga xij = 1
3. Si elimini la riga i e la colonna j nelle matrici X e C
4. Se la matrice C residua contiene almeno un elemento si torni al passo 1. Altrimenti STOP.

Problema di flusso single-commodity con costi variabili

Il modello di flusso single-commodity a costi costanti già descritto è un modello lineare. La linearità della funzione obiettivo dipende dalla ipotesi che i costi di spostamento per unità di flusso cij siano costanti. Questa ipotesi è poco aderente alla realtà perché la movimentazione dei flussi su una rete è in generale caratterizzata dal fenomeno della congestione, cioè della variazione del costo di spostamento per unità di flusso in funzione del flusso stesso. È opportuno quindi assumere che il costo cij sia funzione del flusso fij. In questo modo la f.o. è almeno quadratica (nel caso in cui la relazione cij(fij) sia lineare).

In figura si riporta una funzione di costo cij = cij (fij), classicamente utilizzata per esprimere la variazione del costo unitario su un con il flusso sull’arco stesso.

Il modello di flusso single-commodity a costi variabili presenta quindi gli stessi vincoli lineari del modello a costi costanti e funzione obiettivo non lineare:

Min z = ∑ij∈A [cij ( fij)] fij

Un modello di flusso single-commodity non lineare

È opportuno illustrare graficamente gli effetti di questa variazione di funzione obiettivo. Con riferimento all’esempio già illustrato si supponga che il costo unitario di spostamento sui due archi sia variabile con il flusso secondo le seguenti relazioni lineari:

c(1-2)‘ = 10 + 0.02 f(1-2)

c(1-2)” = 5 + 0.02 f(1-2)

Il modello presenta quindi la seguente formulazione:

Min z = (10 + 0.02 f(1-2)‘) f(1-2)‘ + (5 + 0.02 f(1-2)) f(1-2)
Min z = 10 f(1-2)‘ + 0.02 f(1-2)2 + 5 f(1-2) + 0.02 f(1-2)2

s.a f(1-2)‘ + f(1-2) = 1000
f(1-2)‘  ≤ 600
f(1-2) ≤ 800

In figura è riportato il dominio di ammissibilità del problema, costituito dal segmento EF, ed i contorni dalla funzione z non lineare.

Il punto di ottimo è il punto G, nel quale: f(1-2)‘ = 437 ,f(1-2) = 563, z = 17343.76.

Funzione di costo cij=cij(fij)- Dominio di ammissibilità con vincoli di capacità e funzione obiettivo non lineare

Funzione di costo cij = cij( fij )

Funzione di costo cij = cij( fij )

Dominio di ammissibilità con vincoli di capacità e
funzione obiettivo non lineare

Dominio di ammissibilità con vincoli di capacità e funzione obiettivo non lineare


Il problema di flusso multicommodity

Quando si dispone delle informazioni relative alla domanda di spostamento Dod per un insieme di coppie di vertici origine/destinazione non è possibile assumere che il flusso sulla rete sia di un solo tipo. Per riportare nel modello i valori della domanda Dod è necessario che i vincoli di bilancio nel vertice j si riferiscano alle componenti di flusso con specificata origine. Per simulare quindi il funzionamento di una rete è necessario formulare un modello più articolato, basato sull’uso di una variabile di flusso fijo, che esprime la componente di flusso sull’arco ij proveniente dal vertice origine o. È necessario inoltre aggiungere al modello per ciascun arco un vincolo di additività che esprime la condizione che il flusso totale su un arco sia la somma delle componenti di flusso con specificata origine. La funzione obiettivo resta immutata ed esprime la minimizzazione del costo totale di una rete. Nell’ipotesi che il costo cij sia variabile con il flusso il modello assumerà la configurazione:

\text{Min  }z=f_{ij}=\sum_{ij\in A}c_{ij}(f_{ij})f_{ij}

f_{ij}=\sum_{0\in O}f_{ij}^\circ\hspace{2cm}\text{per  }ij\in A

\sum_{k\in v}f_{jk}^\circ\sum_{i\in v}f_{ij}^\circ=\left[\begin{array}{lll}-D\hspace{1,8cm}j:\exists D'_{oj}\\ \sum_{d^\in F}D_{jd}\hspace{1cm}j\equiv o\\o \hspace{2cm}\text{altrimenti}\end{array}\right]\forall j0,\;\forall o

Il problema del massimo flusso

Si consideri una rete R = (V, A, C, M) connessa e orientata, in cui V, A, e C assumono i significati noti e sia M = {mij} l’insieme delle capacità sugli archi. Si supponga che sulla rete ci sia un solo vertice origine (o) nel quale sia disponibile una quantità illimitata di flusso (persone, materiali, informazioni), ed un solo vertice destinazione (d) nel quale trasportare questo flusso. Poiché c’è un vincolo di capacità sugli archi ( fij ≤ mij, ∀ij∈ A), sarà possibile trasportare dall’origine o alla destinazione d soltanto una parte della risorsa disponibile. Si configura pertanto un problema di determinazione del massimo flusso che può spostarsi da o a d nel rispetto dei vincoli di capacità. Questo problema può essere formulato in programmazione lineare con un modello di flusso che assume la configurazione in figura.

La funzione obiettivo esprime la massimizzazione del flusso uscente dall’origine o, oppure, equivalentemente, del flusso entrante nella destinazione d. I vincoli esprimono la condizione di continuità dei flussi, tipica dei modelli di flusso, ed il limite superiore posto dalla capacità dell’arco ij al flusso fij sull’arco stesso.

\text{Max  }z=\sum_jf_{0j}

s.a.

\sum_kf_{jk}-\sum_kf_{ij}=0\hspace{1,5cm}\forall j \neq o,d

f_{ij}\leq m_{ij}

f_{ij}\geq 0

Un semplice problema di massimo flusso su una rete con tre archi

Si consideri la rete con tre archi riportata in figura. I tre archi hanno capacità m12=2, m13=5, m23=3. Si vuol determinare il massimo flusso che può essere trasportato da 1 a 3 nel rispetto dei vincoli di capacità degli archi. Si può formulare il seguente modello, con un vincolo di bilancio nel vertice 2 e tre vincoli di capacità sui tre archi:

Max z = f12 + f13

s.a ….

f23f12 = 0

f12 2, f13 5, f23 3


Un semplice problema di massimo flusso su una rete con tre archi

I tre vincoli di capacità del modello generano un parallelepipedo. Il vincolo di continuità corrisponde ad un piano la cui intersezione con il parallelepipedo genera il dominio di ammissibilità costituito dal rettangolo OABC. Con la funzione obiettivo z = f12 + f13 il punto di ottimo è costituito dal vertice B, cui corrisponde la soluzione f12 = 2, f13 = 5, f23 = 2. L’arco 2-3 presenta una capacità residua pari a 1, mentre gli archi 1-2 e 1-3 sono al limite della loro capacità. Questi due archi costituiscono un “taglio” (t1) della rete. La capacità di un taglio è pari alla somma delle capacità degli archi che lo costituiscono. Il taglio t1 ha capacità m12 + m13 = 7. L’altro taglio possibile (t2) è costituito dall’insieme di archi {1-3, 2-3}. La sua capacità è pari a m13 + m23 = 8. Dunque, il flusso massimo dal vertice 1 al vertice 3 corrisponde al taglio t1, cioè al taglio della rete che presenta la capacità minima.

Nel seguito si darà una definizione più rigorosa di taglio di una rete e si illustreranno i teoremi fondamentali del massimo flusso.
Si introdurrà poi il concetto di percorso aumentante flusso, necessario per la descrizione dell’algoritmo di Ford e Fulkerson.


Taglio di una rete e Teoremi del massimo flusso

Si consideri una coppia di vertici origine/destinazione (o, d) e si considerino due sottoinsiemi disgiunti dei vertici della rete, N1 ed N2 (N1N2 = N, N1N2 = ∅), tali che o ∈ N1 e dN2. L’insieme degli archi ij con iN1 e jN2 è definito taglio della rete [t(N1/N2)]. Assegnati due insiemi N1 ed N2 esiste un solo taglio t(N1/N2).

Si definisce capacità di un taglio t(N1/N2) la somma delle capacità degli archi costituenti il taglio: mt (N1/N2) = ∑i_N1j_N2 mij. Assegnati due vertici o e d sulla rete, esiste una grande quantità di tagli t(o/d) corrispondenti alle partizioni N1/N2 di N che è possibile effettuare. Il taglio di capacità minima si indica con l’espressione “taglio minimo”.

La capacità di un qualunque taglio t(N1/N2) è un limite superiore per il massimo flusso. Poiché la scelta di N1 ed N2 è arbitraria si può affermare che il flusso massimo da o a d non può superare la capacità di uno qualunque dei tagli individuabili tra o e d e quindi in particolare dal taglio di capacità minima.

Teorema del massimo flusso in forma debole
Il flusso massimo da o a d non può superare la capacità del taglio minimo.

Teorema del massimo flusso in forma forte
Il flusso massimo da o a d è pari alla capacità del taglio minimo tra o e d.

Percorsi aumentanti flusso (p.a.f.) equiversi

Il calcolo del massimo flusso non si effettua esaminando in maniera esaustiva tutti i tagli della rete, ma indirettamente, attraverso la individuazione di percorsi sui quali sia possibile, in relazione alle capacità disponibili, trasferire flusso dall’origine o alla destinazione d. Nel caso in figura esistono 3 percorsi che portano flusso dal vertice 1 al vertice 6. Il massimo flusso che è possibile trasportare su ognuno di essi è dato dal valore minimo di capacità sugli archi che lo costituiscono.


Utilizzazione dei p.a.f. equiversi e Percorso aumentante flusso controverso

(a) Se si utilizzano i percorsi p1 e p2 si trasportano 3 unità di flusso, cioè il massimo flusso, da 1 a 6. Il taglio minimo è costituito dagli archi 4-6 e 5-6.

(b) Se si utilizza il percorso p3 si trasportano solo 2 unità di flusso. E’ necessario allora utilizzare anche il p.a.f. p4 controverso. L’utilizzazione dei percorsi p3 e p4 consente di trasportare 3 unità di flusso, com’è indicato nella slide successiva.

Utilizzazione dei p.a.f. equiversi

Utilizzazione dei p.a.f. equiversi

Percorso aumentante flusso controverso

Percorso aumentante flusso controverso


Configurazione finale dei flussi e delle capacità residue


Algoritmo di Ford e Fulkerson

L’algoritmo di Ford e Fulkerson si basa sulla applicazione sistematica di una procedura per la individuazione di percorsi aumentanti flusso, basato su una procedura di visita della rete e un opportuno etichettamento dei vertici, descritto in dettaglio nel testo di riferimento.

L’algoritmo costruisce una sequenza di p.a.f. equiversi e, se necessario, controversi, la cui sovrapposizione determina il massimo flusso sulla rete. Esso verrà descritto di seguito prima in modo sintetico e poi in dettaglio.

Si assegnano inizialmente agli archi ij flussi fij nulli e capacità “residue” rij pari alle capacità iniziali mij. L’algoritmo opera attraverso step successivi. In ciascuno step si sviluppa il processo di etichettamento, che parte dalla origine o e cerca di raggiungere la destinazione d, individuando un percorso aumentante flusso da o a d sul quale sia possibile trasportare una certa quantità di flusso δ.

Quando viene raggiunta la destinazione d lo step termina e si aggiornano i valori di flusso e di capacità residua sugli archi che costituiscono il percorso individuato. Nello step successivo viene ripetuto il processo di etichettamento da o a d, determinando un nuovo percorso sul quale sia possibile trasportare una nuova quantità di flusso δ‘.

La procedura si itera fino a quando non è più possibile raggiungere la destinazione d. Il flusso massimo è pari alla somma delle quantità δ trasportate da o a d.

Applicazione dell’algoritmo di Ford e Fulkerson


Applicazione dell’algoritmo di Ford e Fulkerson


Algoritmo Ford e Fulkerson


Algoritmo di Ford e Fulkerson


Quadro riassuntivo dei problemi di flusso su rete


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion