Problema del massimo flusso - Ricerca operativa

CASO PIU’ ORIGINI-PIU’ DESTINAZIONI

Per il Problema del Massimo Flusso abbiamo supposto una singola origine e una singola

des nazione.

Vediamo cosa succede se viene fornita un’istanza del problema nella quale sono presen

più origini e des nazioni.

Consideriamo due nodi origine, un nodo di transito e due nodi pozzo:

Si definiscono tante variabili quante sono le coppie origine-des nazione:

Si u lizzano queste variabili in quanto ogni origine può distribuire del flusso ad ogni

des nazione.

Il modello diviene: max + + +

. . = +

= +

+ − − =0

− = − −

− = − −

0 ≤ ≤ ∀(, ) ∈

Consideriamo quest’altro esempio con una sola origine, due des nazioni e diversi nodi di

transito: 2,2

, ̅

11,11

Questa volta, piu osto che considerare le variabili e , modifichiamo la rete e

aggiungiamo un nodo des nazione fi zio collegando ogni des nazione al nodo fi zio,

cara erizzando i valori sugli archi:

= + = 8 + 2 = 10

= + = 4 + 11 = 15

Per i flussi, si ha una soluzione di flusso ammissibile iniziale, quindi calcoliamo sugli archi

fi zi quale è il flusso che da e va a

:

̅ = + =2+7=9

̅ = + =0+9=9

2,2

11,11

Ci siamo ricondo ad un’istanza con singola origine e singola des nazione, per cui è

possibile u lizzare la risoluzione del modello singola origine e singola des nazione.

La stessa procedura vale quando si hanno più origini: si aggiunge un’origine fi zia

ALGORITMO DEI CAMMINI AUMENTANTI

Si consideri la rete e i nodi sorgente e des nazione

= (, , ) .

Sia la distribuzione di flusso iniziale.

( )

Si costruisce la rete residua ausiliaria rela vamente alla distribuzione iniziale di

( )

flusso.

Si ricorda come si costruisce la rete residua ausiliaria: se c’è del flusso ( )

> 0, <

si inserisce un arco che va da a con il residuo pari a (cioè ci dice quanto

= −

altro flusso posso inviare su quell’arco rispe ando il vincolo di capacità). Ma l’arco lo

(, )

si può percorrere anche in senso inverso e cioè togliere flusso su quell’arco (quindi se sulla

rete di partenza si ha l’arco sulla rete ausiliaria potrebbero esserci gli archi (,

(, ) )

e (, )).

Si inizializza un contatore di iterazioni: =0

ℎ …

( )

Finché esiste un cammino orientato nella rete ausiliaria , si determina:

( )

( )

= min ̅

( , )∈

Quindi è il minimo valore dei residui sugli archi appartenen al cammino orientato

determinato.

Questo residuo ci pere e di modificare il flusso della rete, in par colare il flusso sugli archi

appartenen a questo cammino. Questo cammino, se esiste, perme e di inviare ulteriore

quan tà di flusso da a quindi va ad aumentare il flusso uscente da ed entrante in

,

( )

Modifica di del flusso lungo in questo modo:

( ) ( ) (,

= + ) ∈ (1)

( )

∀(, ) ∈ → ( ) ( ) (,

= − ) ∉ (2)

Se l’arco presente nella rete ausiliaria è presente anche nella rete di partenza,

(, )

bisognerà aumentare il flusso sulla rete di partenza. Se quest’arco non è presente nella

rete di partenza vuol dire che è un arco che viene inserito in senso inverso (e cioè

e quindi bisogna decrementare il flusso dalla rete di partenza)

(, ) ∈

Sia il nuovo flusso allora si costruisce la nuova rete residua rela va al nuovo flusso

( )

determinato ( )

Si incrementa l’iteratore: =+1

ℎ

Dato che l’obie vo è determinare il cammino aumentante, si determina la procedura per

fare ciò:

Si consideri la rete residua/ausiliaria ad una certa iterazione dell’algoritmo visto

̅,

precedentemente e da sempre nodo origine e des nazione e

) (, )

( = ̅

Definiamo delle e che e e predecessori

= 0 [] = ∀ ∈ \{}

Si pongono: = +∞

[] =

Si inizializza anche la lista: = {}

E si considera l’insieme dei nodi estra da

:

= {∅}

(

ℎ ≠ ∅ ∉ ) …

Estrai il nodo da e inseriscilo in (si può estrarre qualsiasi nodo):

= \{}

= ∪ {} = min { , ̅ }

̅ (

∀(, ) ∈ → è ℎ ∉ ∪ ) → [] =

= ∪ {}

L’algoritmo parte dal nodo e verifica se è possibile andare al nodo successivo

a raverso qualche arco (, )

Se al nodo non è stato determinato un cammino, allora ci si va e il dice

= min { , ̅ }

che se si arriva al nodo con una certa quan tà di flusso residuo e sull’arco si ha una certa

capacità residua, se si vuole generare un nuovo cammino che va da ad più l’arco

(, ),

il flusso che si può inviare sarà il minimo delle due quan tà (perché si deve rispe are la

capacità residua).

Per tale mo vo, alla fine, il sarà il minimo di tu gli archi del cammino.

̅

Alla fine dell’algoritmo: =

Questo perché alla fine verrà e che ato il nodo pozzo e quindi si avrà determinato il

cammino aumentante.

Una volta terminata questa procedura e determinato il cammino aumentante, è possibile

aggiornare il flusso e tornando all’algoritmo precedente:

==

Si con nua con i passi dell’algoritmo precedente

Si nota che non ci sono condizioni di o malità: se ad esempio si è preso il nodo e bisogna

andare al nodo non si verifica se esiste già un cammino e se questo è migliora vo o meno

,

(e quindi tu o il ragionamento visto per il percorso o mo nel quale si dovevano

minimizzare i cos ). In questo caso se è possibile arrivare al nodo questo verrà

,

e che ato.

Questo perché se ad esempio esistono tre cammini aumentan sulla rete, con questa

procedura si determina il primo, il secondo o il terzo cammino in base all’estrazione su .

Ad esempio, alla prima iterazione si determina il primo cammino: questo perme e di

modificare uil flusso sulla rete. I cammini che c’erano prima (il secondo e il terzo) con nuano

ad esserci sulla rete e si troveranno poi all’iterazione successiva. Magari alla seconda

estrazione si troverà il terzo cammino aumentante, ma il secondo cammino aumentante

con nua a rimanere sulla rete e lo si troverà alla terza iterazione. Ora tu e tre i cammini

aumentan sono sta trova e alla quarta iterazione non se ne trovano e si ferma

l’algoritmo.

Non è quindi importante stabilire il miglior cammino aumentante, cioè quello che perme e

di mandare il maggior flusso; è d’interesse solamente trovare uno dei cammini aumentan

perché se ce ne sono altri ques verranno trova alle iterazioni successive.

ESERCIZIO , ̅

15,8

7,7

12,9 3,3

3,1 8,2

5,0

9,0 8,2

6,4

Bisogna sempre prima verificare che la distribuzione di flusso iniziale sia ammissibile (in

questo caso lo è).

Ci è stata fornita un’istanza del modello del massimo flusso e una soluzione ; possiamo

anche determinare: ̅ = ̅ + ̅ = 9 + 0 = 9

Questo flusso che viene inviato dal nodo deve arrivare al nodo quindi:

, ,

̅ = ̅ + ̅ = 9 + 0 = 9 = ̅ + ̅ =7+2=9

La seconda verifica è andata a buon fine.

Ora resta da verificare per ogni nodo se il flusso uscente meno il flusso entrante è uguale a 0

(vincoli di conservazione del flusso). Questa condizione per la rete proposta è verificata.

Questo ci garan sce che, applicando l’algoritmo, si o errà non solo una soluzione

ammissibile ma proprio la soluzione o ma.

Si costruisce quindi la rete residua o ausiliaria: ̅,

) (, )

( = ̅

8

7

3 7

3

5

9

6

2

1

2

9 6 2

8

4

Per costruire tale rete par amo dall’arco e no amo che il flusso è 9 ma la capacità è

(, 1)

12, per cui è possibile inviare ulteriore quan tà di flusso dal nodo al nodo 1: l’arco

(, 1)

sarà anche presente nella rete ausiliaria.

Sarà possibile inviare unità di flusso.

− ̅ = 12 − 9 = 3

Siccome sull’arco della rete originaria c’è del flusso, in prospe va è anche possibile

(, 1)

evitare di inviare il flusso nella rete ausiliaria e quindi è possibile far tornare queste unità

9

di flusso al nodo (le unità che si erano inviate precedentemente), mo vo per cui si può

considerare anche l’arco con capacità pari a

(1, ) ̅ = 9

L’arco è invece un arco scarico, quindi, è possibile solamente inviare del flusso (mo vo

(, 2)

per cui l’arco non si troverà nella rete ausiliaria): sarà presente l’arco con

(2, ) (, 2)

capacità residua pari a − ̅ = 9

L’arco invece è un arco saturo; quindi, non è possibile inviare ulteriore flusso dal nodo

(3, )

al nodo nella rete ausiliaria esisterà solamente l’arco perché sarà possibile

3 : (, 3)

solamente tornare indietro il flusso che a ualmente passa da a

3

Si costruisce secondo ques ragionamen il resto della rete.

Costruita la rete residua, ora si determina il cammino aumentante sulla rete