DEIG – Manuel Pina Marques Problemas de Fluxo Máximo Objecto de Aprendizagem 2010

DEIG – Manuel Pina Marques

Problemas de Fluxo Máximo

Objecto de Aprendizagem

2010


Problemas de Fluxo Máximo

Modelo:

xij – fluxo que passa no ramo (i, j), de i para jcij – capacidade do ramo (i, j)Nó 1 – nó de entradaNó t – nó de saída

Sujeito a:(equilíbrio de fluxos nos nós)

(restrições de capacidade)

i

itj

j xx1max

kj

kji

ik xx ,

jiijij cx ,,

jiijx ,,0

Definição: Dada uma rede, com um nó de entrada e um nó de saída, com capacidades associadas a cada ramo, pretende-se saber qual é o fluxo máximo, de um certo bem, que se pode enviar da entrada para a saída.


1

2

3

4

(9) (7)

(8) (9)

Exemplo de um problema de Fluxo Máximo

Nó de entrada =

Capacidades totais dos ramos:

(3)

Ramo 1 3 = 8Ramo 2 3 = 3

Ramo 2 4 = 7

Ramo 3 4 = 9

Ramo 1 2 = 9

nó 1

nó 4Nó de saída =


Algoritmo de fluxo máximo

1. Injectar um fluxo nulo (f = 0) no nó de entrada;

2. Fixar as capacidades utilizadas dos ramos em 0 (zero);

3. Seleccionar um caminho não saturado (caminho com capacidade 0) entre o nó de entrada e o nó de saída. Se não existir nenhum, foi encontrada a solução óptima;.

4. Somar ao fluxo de entrada um fluxo igual à capacidade do caminho seleccionado;

5. Alterar as capacidades utilizadas dos ramos do caminho seleccionado, somando-lhes o fluxo injectado;

6. Voltar ao ponto 3.

1

2

3

4

(0, 9) (7)

(8) (9)

(3)f = 0 f = 0

Capacidade utilizada do ramoCapacidade total do ramo

(9) (0, 7)

(0, 9)(0, 8)

(0, 3)

Caminho: conjunto de ramos unindo o nó de entrada ao nó de saída, e que não passa duas vezes pelo mesmo nó.

Capacidade de um caminho: menor capacidade disponível de entre todos os ramos que fazem parte do caminho.

Caminho saturado: caminho com capacidade disponível nula

Caminho 1: capacidade = 7



Vamos, por exemplo, seleccionar o caminho não saturado 1 3 4, com capacidade disponível = min (8; 9) = 8

f = 0+8 = 8 f = 0+8 = 8

(8, 8) (8, 9)


Algoritmo de fluxo máximo (cont.)





1

2

3

4

(0, 7)

(0, 3)

Vamos seleccionar o caminho não saturado 1 2 3 4, com capacidade disponível = min (9; 7) = 7

f = 8 f = 8

(8, 8) (8, 9)

(0, 9)

f = 8+7 = 15

(7, 9) (7, 7)

f = 8+7= 15







1

2

3

4(0, 3)

Vamos, seleccionar o caminho não saturado 1 2 3 4

(8, 8) (8, 9)

f = 15

(7, 9) (7, 7)

f = 15

ramo 1 2: capacidade = 9 – 7 = 2



Capacidade disponível do caminho1 2 3 4 = min (2; 3; 1) =1

Capacidades disponíveis dos ramos deste caminho:

f = 15+1 = 16

(8, 9)

(1, 3)

(9, 9)

f =15+1=16

Não existe nenhum caminho não saturado.Logo, foi encontrada a solução óptima

f = 16 f = 16


1. Injectar um fluxo nulo (f = 0) no nó de entrada;

2. Fixar as capacidades utilizadas dos ramos em 0 (zero);





1

2

3

4

(0, 9) (7)

(8) (9)

(3)f = 0 f = 0

(9) (0, 7)

(0, 9)(0, 8)

(0, 3)

Vamos seleccionar o caminho não saturado 1 2 3 4, com capacidade disponível = min (9; 3; 9) = 3

f = 0+3 = 3 f = 0+3 = 3

(3, 9)

Algoritmo de fluxo máximo (cont.) Vamos agora saturar os caminhos por uma ordem

diferente. O que acontecerá?

(3, 9)

(3, 3)






1

2

3

4

(0, 9) (7)

(8) (9)

(3)f = 3 f = 3

(9) (0, 7)

(0, 9)(0, 8)

(0, 3)

Vamos seleccionar, por exemplo, o caminho não saturado 1 2 4

(3, 9)


(3, 9)

(3, 3)


Capacidades disponíveis dos ramos deste caminho:


Capacidade disponível do caminho 1 2 4 = min (6; 7) = 6

f = 3+6 = 9

(9, 9) (6, 7)

f = 3+6= 9



1

2

3

4

(0, 9) (7)

(8) (9)

(3) f = 9

(9) (0, 7)

(0, 9)(0, 8)

(0, 3)

Aparentemente não há nenhum caminho não saturado, mas o fluxo máximo agora obtido (f = 15) é menor do que no caso anterior (f = 16).

(3, 9)


(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 15

(6, 8) (9, 9)

f =15

Como é que isto é possível , já que o algoritmo é de optimização?


1

2

3

4

(0, 9)

(9)

f = 9

(9)

(0, 9)(3, 9)


(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 15

(6, 8) (9, 9)

f =15

De facto, o exemplo anterior não está completamente resolvido (até à optimalidade) porque existe ainda um caminho não saturado.

Para se encontrar esse caminho não saturado é necessário considerar o conceito de “fluxo negativo", isto é, fluxo que atravessa os ramos no sentido contrário à sua orientação.

Uma das restrições apresentadas no modelo do problema de fluxo máximo impunha que todos os fluxos fossem positivos ou nulos (xij 0). E de facto, na solução final, tal terá sempre que acontecer. No entanto, essa solução final obtém-se pela adição dos vários fluxos que vamos injectando na rede.

Alguns desses fluxos poderão atravessar algum ramo no sentido contrário ao indicado, devendo nesse caso ser contabilizados como negativos. O resultado final (soma de todos os fluxos que foram injectados nesse ramo) é que terá que ser positivo ou nulo.

No fundo, um “fluxo negativo" mais não é do que deixar de fazer passar fluxo por esse ramo.

Observando a rede deste ponto de vista, verifica-se queo caminho 1 3 2 4 não está saturado, pois:

o ramo 1 3 tem uma capacidade de 2 = (8 – 6).

o ramo 2 3 está saturado no sentido do nó 2 para o nó 3;

mas no sentido do nó 3 para o nó 2 tem uma capacidade de 3 (igual à capacidade que está a ser utilizada no sentido do nó 2 para o nó 3)

isto é, podemos deixar de fazer passar, do nó 2 para o nó 3, até 3 unidades (que é fluxo actual).

o ramo 2 4 tem uma capacidade de 1 = (7 – 6).

Logo, a capacidade do caminho 1 3 2 4 é de 1 = min (2; 3, 1)


1

2

3

4

(0, 9)

(9)

(9)

(0, 9)(3, 9)


(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 15

(6, 8) (9, 9)

f =15

Seleccionamos então o caminho não saturado 1 3 2 4 (com capacidade = 1)





f = 15+1 =16

(7, 8)

(2, 3)

(7, 7)

f =15+1=16

Vejamos com maior detalhe o que realmente se

passa nesta iteração


1

2

3

4

(0, 9)

f = 9

(9)


(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 15

(6, 8) (9, 9)

f =15

Como se viu antes, a capacidade do caminho 1 3 2 4 é de 1 unidade. Vai-se então enviar uma unidade por esse caminho:

1º Enviar 1 unidade do nó 1 para o nó 3.

Então que fazer?

A única forma de ultrapassar este problema é fazer com que uma das unidades que é presentemente enviada por 2 3 4, passe a ser enviada por 2 4, de forma a libertar uma unidade da capacidade do ramo 3 4.

(7, 8)

Essa unidade enviada do nó 1 para o nó 3, não pode depois ser enviada pelo ramo 3 4, pois este ramo está saturado neste sentido.

f = 15+1=16

Utiliza-se depois essa unidade, assim libertada (da capacidade do ramo 3 4), para fazer fluir do nó 3 para o nó 4 a unidade que enviamos antes do nó 1 para o nó 3.



Corrigindo as capacidades utilizadas dos ramos obtém-se:

(2, 3)

(8, 9)

(7, 7)

(9, 9)

O procedimento descrito é equivalente a:


1

2

3

4

(0, 9)

f = 16

(9)

Teorema do Fluxo Máximo – Corte Mínimo:

(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 16

(6, 8) (9, 9)

Como saber se a rede está na situação de fluxo máximo? (ou seja, se a solução em presença é óptima)

(7, 8)

(2, 3)

(8, 9)

(7, 7)

(9, 9)

através do Teorema do Fluxo Máximo – Corte Mínimo:

Uma rede está na situação de fluxo máximo se existir um corte mínimo, isto é, que separa a entrada da saída da rede, e que só atravessa:- ramos orientados da entrada para a saída saturados, e- ramos orientados da saída para a entrada com fluxo nulo

O fluxo máximo é, nestas condições, igual à capacidade do corte mínimo

corte mínimo

Capacidade do corte mínimo = 7 + 9 = 16

Como a capacidade do corte mínimo (16) é igual ao fluxo actual (f =16) a solução é óptima

Ver conceitos


1

2

3

4

(0, 9) (7)

(8) (9)

(3)

(9) (0, 7)

(0, 9)(0, 8)

(0, 3)

(3, 9)

(3, 9)

(3, 3)

(9, 9) (6, 7)

f = 15

(6, 8) (9, 9)

Teorema do Fluxo Máximo – Corte Mínimo

f = 15

Se analisarmos a solução anterior à óptima (com f = 15), podemos verificar que é impossível definir um corte mínimo

Note-se que o corte abaixo representado, não é um corte mínimo, pois o fluxo do nó 2 para o nó 3 não é nulo.

Ver explicação detalhada

Documents

DEIG – Manuel Pina Marques Problemas de Fluxo Máximo Objecto de Aprendizagem 2010