Problema de Fluxo Máximo - ufjf.br · Uma vez que o Problema de Fluxo Máximo em uma Rede pode ser formulado como um Problema de Programação Linear, o algoritmo Simplex pode ser

Fernando Nogueira Fluxo Máximo 1

Problema de Fluxo Máximo

The Maximum Flow Problem


O Problema de Fluxo Máximo (The Maximum Flow Problem)

Considere uma rede direcionada (dígrafo) conectada, com 2 nós especiais denominados Origem e Destino e ainda, associado a cada arco, uma distância não-negativa. O objetivo é encontrar o fluxo máximo na rede.

Exemplos de Aplicações:

1)Maximizar o fluxo de uma rede de distribuição (suprimentos) de uma companhia a partir de suas fábricas (fornecedores) para os seus (suas) clientes (fábricas).

2)Maximizar o fluxo de óleo (água) através de um sistema de oleodutos (aquedutos).

3)Maximizar o fluxo de veículos através de uma rede de transporte.


Exemplo

Maximizar o número de viagens para a rede do Parque Seervadade O para T, onde os valores dos arcos representam o fluxo máximo de cada arco.

Uma solução viável é enviar 7 bondes, sendo:5 usando a rota O⇒B⇒E⇒T1 usando a rota O⇒B⇒C ⇒ E⇒T e1 usando a rota O⇒B⇒C ⇒ E⇒D ⇒ T


A solução anterior é viável, porém não é a ótima.

Uma vez que o Problema de Fluxo Máximo em uma Rede pode ser formulado como um Problema de Programação Linear, o algoritmo Simplex pode ser utilizado para obtenção da solução ótima. Entretanto, existe um algoritmo mais eficiente para a solução deste problema denominado Algoritmo do Caminho de Aumento (Augmenting Path Algorithm).

O algoritmo do Caminho de Aumento é baseado em dois conceitos intuitivos: uma Rede Residual e um Caminho de Aumento (propriamente dito).


Rede Residual

Os valores dos arcos da rede da esquerda representam as capacidades máximas e seus respectivos fluxos (capacidade, fluxo). Os valores dos arcos da rede da direita representam os resíduos, ou seja, a diferença entre a capacidade e o fluxo do arco.


Caminho de Aumento

Um Caminho de Aumento é um caminho orientado (os arcos possuem sentidos) a partir da origem para o destino na Rede Residual tal que todo arco sobre este caminho possui resíduo estritamente positivo.

O mínimo destes resíduos é chamado de “Capacidade Residual do Caminho de Aumento”, uma vez que este representa a quantidade de fluxo que pode viavelmente ser adicionado ao caminho todo.

O caminho:

O ⇒C ⇒E ⇒D ⇒T é um Caminho de Aumento com Capacidade Residual 1 (menor resíduo neste caminho).


Existem algumas “versões” do Algoritmo do Caminho de Aumento. A mais conhecida é o Algoritmo de Ford-Fulkerson.

Algoritmo de Ford-Fulkerson

s = origem, t = destino, P = caminho, f = fluxo total, fij = fluxo do arco i para o arco j, cij = capacidade de fluxo do arco i para o arco j.

1. Designar um fluxo inicial fij (por exemplo, fij = 0, para todos os arcos). Compute f.

2. Rotular o nó 1 (s) por ∅. Marque os outros vértices como “não-rotulados”.


3. Encontrar um nó rotulado i que não tenha sido “scanned”. Scan i como:

Para todo nó adjacente não-rotulado j, se cij > fij, computar

e rotular j como um rótulo “para frente” (i+,∆j);

ou se fji>0, computar ∆j = min (∆i,fji) e rotular j como um rótulo “para trás” (i-,∆j);

Se não existir nenhum j, então SAI f. Pare. (f é o fluxo máximo).

4. Repita o passo 3 até o nó destino (t) ser alcançado (isto fornece um fluxo sobre um Caminho de Aumento)

Se é impossível alcançar o destino, então SAI f. Pare (f é o fluxo máximo).

( )⎪⎩

⎪⎨⎧

>∆∆

=∆=∆−=∆

1ise,min

1iseefc

iji

j1jijijij


5. Determine o caminho P usando os rótulos.

6. Aumente o fluxo existente em P por ∆t. Faça f = f + ∆t.

7. Remover os rótulos dos nós 2, 3,..., t. Volte para o passo 3.

Obs: dever-se utilizar BFS (Breadth First Search) que foi sugerido para ser utilizado neste algoritmo por Edmonds & Karp em 1972. A técnica BFS, neste algoritmo, consiste em, antes de scannear um nói, scannear todos os nós que foram rotulados antes de i.

O próximo exemplo mostra a execução deste algoritmo para o problema de maximizar o fluxo de bondes nas rodovias do Parque Seervada.

O fluxo inicial adotado foi zero.


1. Fluxo inicial f = 0

2. Rotular O por ∅. Marcar A, B, C, D, E, T “não-rotulado”.

3. Scan O

Computar ∆OA = 5-0 = 5. ∆A = 5. Rotular A por (O+, 5).

Computar ∆OB = 7-0 = 7. ∆B = 7. Rotular B por (O+, 7).

Computar ∆OC = 4-0 = 4. ∆C = 4. Rotular C por (O+, 4).


4. Scan B

Computar ∆BD = 4-0 = 4. ∆D = min(∆B, ∆BD) = 4 . Rotular D por (B+, 4).

Computar ∆BE = 5-0 = 5. ∆E = min(∆B, ∆BE) = 5. Rotular E por (B+, 5).


Scan DComputar ∆DT = 9-0 = 9. ∆T = min(∆D, ∆DT) = 4 . Rotular T por (D+, 4).

5. Caminho: O – B – D – T é um Caminho de Aumento.6. ∆T = 4. Aumentando o fluxo de ∆T resulta em:

fOB = fBD = fDT = 0 + 4 = 4. Outros fluxos continuam sem mudanças.Fluxo total f = 4.

7. Remover todos os rótulos sobre os vértices A,B,C,D,E,T e voltar para o passo 3.


3. Scan O


Computar ∆OB = 7-4 = 3. ∆B = 3. Rotular B por (O+, 3).



4. Scan B

Computar ∆BD = saturado (não computar).

Computar ∆BE = 5-0 = 5. ∆E = min(∆B, ∆BE) = 3. Rotular E por (B+, 3).


Scan EComputar ∆ED = 1-0 = 1. ∆D = min(∆E, ∆ED) = 1 . Rotular D por (E+, 1).Computar ∆ET = 6-0 = 6. ∆T = min(∆E, ∆ET) = 3 . Rotular T por (E+, 3).

5. Caminho: O – B – E – T é um Caminho de Aumento.6. ∆T = 3. Aumentando o fluxo de ∆T resulta em:

fOB = 4 + 3 = 7, fBE = 0 + 3 = 3, fET = 0 + 3 = 3. Outros fluxos continuam sem mudanças. Fluxo total f = 4 + 3 = 7.



3. Scan O


Computar ∆OB = saturado (não computar)



4. Scan A

Computar ∆AD = 3-0 = 3. ∆D = min(∆A, ∆AD) = 3. Rotular D por (A+, 3).

Computar ∆AB = 1-0 = 1. ∆B = min(∆A, ∆AB) = 1. Rotular B por (A+, 1).


Scan DComputar ∆DT = 9-4 = 5. ∆T = min(∆D, ∆DT) = 3 . Rotular T por (D+, 3).Computar ∆E = min(∆D, fED) = 1 . Rotular E por (D-, 1).

5. Caminho: O – A – D – T é um Caminho de Aumento.6. ∆T = 3. Aumentando o fluxo de ∆T resulta em:

fOA = 0 + 3 = 3, fAD = 0 + 3 = 3, fDT = 4 + 3 = 7. Outros fluxos continuam sem mudanças. Fluxo total f = 7 + 3 = 10.



3. Scan O





4. Scan A

Computar ∆AD = saturado (não computar).

Computar ∆AB = 1-0 = 1. ∆B = min(∆A, ∆AB) = 1. Rotular B por (A+, 1).


Scan BComputar ∆BE = 5-3 = 2. ∆E = min(∆B, ∆BE) = 1. Rotular E por (B+, 1).Computar ∆BD = saturado (não computar).


Scan EComputar ∆ED = 1-0 = 1. ∆D = min(∆E, ∆ED) = 1. Rotular D por (E+, 1).Computar ∆ET = 6-3 = 3. ∆T = min(∆E, ∆ET) = 1. Rotular T por (E+, 1).


5. Caminho: O – A – B – E –T é um Caminho de Aumento.6. ∆T = 1. Aumentando o fluxo de ∆T resulta em:fOA = 3 + 1 = 4, fAB = 0 + 1 = 1, fBE = 3 + 1 = 4, fET = 3 + 1 = 4 . Outros fluxos continuam sem mudanças. Fluxo total f = 10 + 1 = 11.7. Remover todos os rótulos sobre os vértices A,B,C,D,E,T e voltar para o passo 3.


3. Scan O

Computar ∆OA = 5-4 = 1. ∆A = 1. Rotular A por (O+,1).




4. Scan A


Computar ∆AB = saturado (não computar).


Scan CComputar ∆CE = 4-0 = 4. ∆E = min(∆C, ∆CE) = 4. Rotular E por (C+, 4).Computar ∆B = min(∆C, fBC) = 2 . Rotular B por (C-, 2).


Scan EComputar ∆ED = 1-0 = 1. ∆D = min(∆E, ∆ED) = 1. Rotular D por (E+, 1).Computar ∆ET = 6-4 = 2. ∆T = min(∆E, ∆ET) = 2. Rotular T por (E+, 2).


5. Caminho: O – C – E –T é um Caminho de Aumento.6. ∆T = 2. Aumentando o fluxo de ∆T resulta em:fOC = 0 + 2 = 2, fCE = 0 + 2 = 2, fET = 4 + 2 = 6. Outros fluxos continuam sem mudanças. Fluxo total f = 11 + 2 = 13.7. Remover todos os rótulos sobre os vértices A,B,C,D,E,T e voltar para o passo 3.


3. Scan O

Computar ∆OA = 5-4 = 1. ∆A = 1. Rotular A por (O+,1).




4. Scan A


Computar ∆AB = saturado (não computar).


Scan CComputar ∆CE = 4-2 = 2. ∆E = min(∆C, ∆CE) = 2. Rotular E por (C+, 2).Computar ∆B = min(∆C, fBC) = 2 . Rotular B por (C-, 2).


Scan EComputar ∆ED = 1-0 = 1. ∆D = min(∆E, ∆ED) = 1. Rotular D por (E+, 1).Computar ∆ET = saturado (não computar).


Scan DComputar ∆DT = 9-7 = 2. ∆T = min(∆D, ∆DT) = 1. Rotular T por (D+, 1).


5. Caminho: O – C – E – D – T é um Caminho de Aumento.6. ∆T = 1. Aumentando o fluxo de ∆T resulta em:fOC = 2 + 1 = 3, fCE = 2 + 1 = 3, fED = 0 + 1 = 1, fDT = 7 + 1 = 8. Outros fluxos continuam sem mudanças. Fluxo total f = 12 + 1 = 14.7. Remover todos os rótulos sobre os vértices A,B,C,D,E,T e voltar para o passo 3.


A priori, deveríamos retornar ao passo 3, porém todos os arcos que chegam em D estão saturados (não há como enviar mais nada para D) e portanto, não é possível enviar mais nada para T a partir de D.

Uma vez que o arco que chega em T, a partir de E, também está saturado, não é possível melhorar a solução. Portanto, a solução acima é ótima.


A figura abaixo representa a solução ótima apenas com os fluxos (sem as capacidades).

Documents

Problema de Fluxo Máximo - ufjf.br · Uma vez que o Problema de Fluxo Máximo em uma Rede pode ser formulado como um Problema de Programação Linear, o algoritmo Simplex pode ser