Problema de Fluxo Maximo

Prévia do material em texto

Considere a rede representada por um grafo 
direcionado com m nós, em especial, um nó Fonte 
ou Origem e um Sumidouro ou Destino. Suponha 
ainda que tenhamos limites de capacidades de fluxo 
associadas a cada arco do grafo.
Problema de Fluxo Máximo
(The Maximal Flow Problem)
Aplicações: 
-Maximizar o fluxo de produtos na rede de comercialização.
-Maximizar o fluxo de materiais diversos em uma rede de dutos.
-Maximizar o fluxo de veículos em uma malha viária.
O
D
C
A
B
E
T
5OAu
3ADu
9DTu
7OBu
4OCu
4CEu
4BDu
2BCu
5BEu
1EDu
6ETu
1ABu
j)(i, arco no fluxo de max. limiteu 
j);(i, arco no fluxo de mín. limite 
 j);(i, arco no fluxox
Destino; de nóT 
Origem; de nóO 
A);(N,G de arcos de conj.A 
:que Em
j)(i, max. fluxo j)(i, fluxoj)(i, min. fluxoA j)(i, 
 
) i nó no chega que fluxoi nó do sai que fluxo( TO,i 0xx
T) em chega que fluxoO de sai que fluxo( 0xx
 /
x Z.
:FORMULAÇÃO
ij
ij
ij
ij
Aj)(i, Ai)(k,
kiij
AT)(i,
iT
Aj)(O,
Oj
Aj)(O,
Oj


















 


 


l
uxl
as
Max
ijij
0ij l
Exemplo: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre os arcos representam o 
fluxo máximo de cada arco. Não há, neste exemplo, fluxo mínimo estabelecido .
O
D
C
A
B
E
T
5OAu
3ADu
9DTu
7OBu
4OCu
4CEu
4BDu
2BCu
5BEu
1EDu
6ETu
1ABu
SUB = Simple Upper Bound
SLB = Simple Lower Bound
Exemplo:
SOLUÇÃO 
PELO 
LINDO:
O
D
C
B
E
T
4 3
8
7
3
3
4
4
1
6
114
14
A
Resposta do Exemplo:
SOLUÇÃO PELO LINDO:
Embora o Problema de Fluxo Máximo possa ser resolvido pelo simplex existem 
outros algoritmos mais eficientes, entre eles: o dos Caminhos Aumentados, 
The Aumenting Path Algorithm
Algoritmo dos Caminhos Aumentados (ACA) (The Aumenting Path Algorithm)
Este algoritmo se embasa nos conceitos de rede residual e caminho aumentado.
Rede residual: Após a inserção de algum fluxo em uma rede, a rede residual será aquela que 
exibe as capacidades remanescentes dos arcos (capacidades residuais), disponíveis para designar 
outros fluxos adicionais.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
Rede residual resultante da designação de um fluxo 5 por: O→B→E→T.
Exemplo: 
O
D
C
A
B
E
T
5
3
9
2
4
4
4
2
0
1
1
1
5
0
0
5
0
0
0
5
0
5
0
5
0
0
0
0
Rede residual resultante da designação de um fluxo 5 por: O→B→E→T.
O
D
C
A
B
E
T
5
3
9
2
4
4
4
2
0
1
1
1
5
0
0
5
0
0
0
5
0
5
0
5
Exemplo: 
Capacidade residual 
de 2 para qualquer 
designação futura 
de fluxo de O→B. 
Fluxo corrente ou 
capacidade residual de 
5 para qualquer 
designação futura de 
fluxo de B→O, ou 
seja, para qualquer 
cancelamento de fluxo 
de designação feita 
anteriormente de 
O→B.
Caminho aumentado : É um caminho direcionado da Fonte (origem) para o 
Sumidouro (destino) na rede residual de modo que todo arco, nele contido, tenha 
capacidade residual estritamente positiva. A capacidade de menor valor de todos 
os arcos do caminho aumentado é denominada de capacidade residual do 
caminho aumentado pois representa a capacidade de fluxo que pode ser adicionada 
em todo caminho de maneira viável.
OBS: 1) O algoritmo seleciona um dos caminhos aumentados e adiciona um fluxo
à rede de valor igual a capacidade residual do caminho aumentado selecionado.
Este procedimento é repetido até que não exista mais nenhum caminho aumentado
partindo da Fonte (origem) e chegando no Sumidouro (destino) que permita fluxo
adicional , ou seja, que permita o fluxo ser aumentado.
2) A garantia de que a solução final seja a solução ótima associa-se ao fato que a
seleção de caminhos aumentados permite o cancelamento de fluxos já designados
anteriormente não impedindo a obtenção de combinações melhores de
designações fluxos.
3) No início, em geral, existirão várias opções para a escolha do caminho
aumentado a ser selecionado. Aqui a escolha será arbitrária , no entanto na
solução de problemas de grande porte pode-se usar estratégias de escolha dos
caminhos aumentados que procuram maior eficiência na aplicação do algoritmo.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
0ij l
Exemplo: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre 
os arcos representam as capacidades de fluxo máximo de cada arco. Não há, 
neste exemplo, capacidade de fluxo mínimo estabelecido .
1º Passo: Transforme os arcos direcionados da rede original em não direcionados.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
0
0
1ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→E→T que tem 
como capacidade residual o min [7,5,6]=5. Fazendo fluir 5 no caminho escolhido tem-se:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
O
D
C
A
B
E
T
5
3
9
2
4
4
4
2
0
1
1
1
5
0
0
5
0
0
0
5
0
5
0
5
2º Passo: 
0
0
0
0
1ª Opção.
2ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→D→T que tem 
como capacidade residual o min [5,3,9]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
6
2
4
4
4
2
0
1
1
1
835 
3
3
5
0
0
0
5
0
5
3
8
0
0
O
D
C
A
B
E
T
5
3
9
2
4
4
4
2
0
1
1
1
5
0
0
5
0
0
0
5
0
5
0
5
0
0
3ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→B→D→T que tem 
como capacidade residual o min [2,1,4,6]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
5
2
4
4
3
2
0
1
1
0
918 
4
3
5
1
0
1
5
0
5
4
9
0
0
O
D
C
A
B
E
T
2
0
6
2
4
4
4
2
0
1
1
1
8
3
3
5
0
0
0
5
0
5
3
0
0
8
4ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→D→T que tem 
como capacidade residual o min [2,3,5]=2. Fazendo fluir 2 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
3
0
4
4
1
2
0
1
1
0
1129 
4
3
7
1
0
3
5
0
5
6
11
0
0
O
D
C
A
B
E
T
1
0
5
2
4
4
3
2
0
1
1
0
9
4
3
5
1
0
1
5
0
5
4
9
0
0
5ª iteração: Escolha arbitrariamenteum dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→D→T que tem 
como capacidade residual o min [4,4,1,3]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
2
0
3
3
1
2
0
0
1
0
12111 
4
3
7
1
1
3
5
1
5
7
12
1
0
O
D
C
A
B
E
T
1
0
3
0
4
4
1
2
0
1
1
0
11
4
3
7
1
0
3
5
0
5
6
11
0
0
6ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→T que tem 
como capacidade residual o min [3,3,1]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13112 
4
3
7
1
2
3
5
2
6
7
13
1
0
O
D
C
A
B
E
T
1
0
2
0
3
3
1
2
0
0
1
0
12
4
3
7
1
1
3
5
1
5
7
12
1
0
7ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→B→D→T que
tem como capacidade residual o min [2,2,5,1,2]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
1
0
1
1
0
2
1
0
0
0
14113 
4
3
7
1
3
4
4
3
6
8
14
1
0
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13
4
3
7
1
2
3
5
2
6
7
13
1
0
Refinamento: Cancelamento do fluxo de uma unidade, designado em iteração 
anterior, para obter uma combinação melhor de designação de fluxos.
Isto justifica 
transformar os 
arcos em não 
direcionados. 
O
D
C
A
B
E
T
14
4 3
7
1
3
4
4
3
6
8
14
1
0
O
D
C
A
B
E
T
1
0
1
0
1
1
0
2
1
0
0
0
14
4
3
7
1
3
4
4
3
6
8
14
1
0
Resposta:
Fluxo: 













































































6
1
8
3
0
4
4
3
1
3
7
4
x
x
x
x
x
x
x
x
x
x
x
x
*
ET
ED
DT
CE
BC
BE
BD
AD
AB
OC
OB
OA
X
14MAXz
Não há mais nenhum caminho aumentado.
Solução 
Ótima:
Valor máximo
da função:
Método para encontrar um caminho aumentado:
1) Identifique todos os nós que possam atendidos pelo nó de origem através de um 
arco com capacidade estritamente positiva.
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13
4
3
7
1
2
3
5
2
6
7
13
1
0
2) Repita sucessivamente procedimento a partir dos novos nós alcançados até que 
se obtenha um caminho aumentado.
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13
4
3
7
1
2
3
5
2
6
7
13
1
0
Aplicação para encontrar um caminho
aumentado para a 7ª iteração, do ex. Anterior:
O
C
E
B D
A
T
Teorema do corte mínimo e fluxo máximo:
Um corte é um conjunto de arcos direcionados que contenha pelo menos um arco de 
cada caminho possível da Fonte até o Sumidouro.
Seleção de um dos cortes possíveis. 
Valor do corte = Soma das capacidades residuais dos arcos 
levando-se em conta a direção dos fluxos nos mesmos.
No ex.: Vl. do corte = 3+4+1+6 = 14
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
0
0
Corte mínimo: 
É o corte de menor valor na rede.
Vl. do corte 
mínimo = 14
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
zerofluxo 
zerofluxo 
Vl. do corte = 15
Vl. do corte = 16
Vl. do corte = 16
Vl. do corte = 15
Vl. do corte = 18
Teorema: Para redes de uma Fonte e um Sumidouro, o fluxo máximo será igual ao 
corte mínimo entre todos os cortes da rede.
Rede inicial: 
O
D
C
A
B
E
T
1
0
1
0
1
1
0
2
1
0
0
0
14
4
3
7
1
3
4
4
3
6
8
14
1
0
Corte na rede residual final igual a zero: 
7ª iteração: 
OBS: A otimalidade ocorre quando existir um corte na rede de valor zero.
Vl. do corte = 0
Rede Final: 
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
0ij l
Exemplo: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre 
os arcos representam as capacidades de fluxo máximo de cada arco. Não há, 
neste exemplo, capacidade de fluxo mínimo estabelecido .
1º Passo: Transforme os arcos direcionados da rede original em não direcionados.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
0
0
Outro modo
de resolução.
1ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→D→T que tem 
como capacidade residual o min [5,3,9]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
O
D
C
A
B
E
T
2
0
6
7
4
4
4
2
5
1
6
1
3
3
3
0
0
0
0
0
0
0
3
3
2º Passo: 
0
0
0
0
2ª Opção.
2ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→D→T que tem 
como capacidade residual o min [7,4,6]=4. Fazendo fluir 4 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
6
7
4
4
4
2
5
1
6
1
3
3
3
0
0
0
0
0
0
0
3
3
0
0
O
D
C
A
B
E
T
2
0
2
3
4
4
0
2
5
1
6
1
743 
3
3
4
0
0
4
0
0
0
7
7
0
0
3ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→T que tem 
como capacidade residual o min [4,4,6]=4. Fazendo fluir 4 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
2
3
4
4
0
2
5
1
6
1
7
3
3
4
0
0
4
0
0
0
7
7
0
0
O
D
C
A
B
E
T
2
0
2
3
0
0
0
2
5
1
2
1
1147 
3
3
4
0
4
4
0
4
4
7
11
0
0
4ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→B→ E→T que tem 
como capacidade residual o min [2,1,5,2]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
2
3
0
0
0
2
4
1
1
0
12111 
4
3
4
1
4
4
1
4
5
7
12
0
0
O
D
C
A
B
E
T
2
0
2
3
0
0
0
2
5
12
1
1147 
3
3
4
0
4
4
0
4
4
7
11
0
0
5ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→E→T que tem 
como capacidade residual o min [3,4,1]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
2
2
0
0
0
2
3
1
0
0
13112 
4
3
5 1
4
4
2
4
6
7
13
0
0
O
D
C
A
B
E
T
1
0
2
3
0
0
0
2
4
1
1
0
12111 
4
3
4
1
4
4
1
4
5
7
12
0
0
6ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→E→D → T que
tem como capacidade residual o min [2,3,1,2]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
1
1
0
0
0
2
2
0
0
0
14113 
4
3
6
1
4
4
3
4
6
8
14
1
0
O
D
C
A
B
E
T
1
0
2
2
0
0
0
2
3
1
0
0
13112 
4
3
5
1
4
4
2
4
6
7
13
0
0
O
D
C
A
B
E
T
1
0
1
1
0
0
0
2
2
0
0
0
14113 
4
3
6
1
4
4
3
4
6
8
14
1
0
O
D
C
A
B
E
T
1
0
1
1
0
0
0
2
2
0
0
0
14
4
3
6
1
4
4
3
4
6
8
14
1
0
Não há mais nenhum caminho aumentado.
Vl. do corte = 0
O
D
C
A
B
E
T
14
4
3
6
1
4
4
3
4
6
8
14
1
0
Resposta:
Fluxo:














































































6
1
8
4
0
3
4
3
1
4
6
4
x
x
x
x
x
x
x
x
x
x
x
x
*
ET
ED
DT
CE
BC
BE
BD
AD
AB
OC
OB
OA
X
14MAXz
OUTRA
Solução 
Ótima:
Valor máximo
da função:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
0ij l
Exemplo: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre 
os arcos representam as capacidades de fluxo máximo de cada arco. Não há, 
neste exemplo, capacidade de fluxo mínimo estabelecido .
1º Passo: Transforme os arcos direcionados da rede original em não direcionados.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
0
0
Mais outro 
modo
de resolução.
1ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B → C→E → D→T que
tem como capacidade residual o min [7,2,4,1,9]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
O
D
C
A
B
E
T
5
3
8
6
4
3
4
1
5
0
6
1
1
0
0
1
0
0
0
0
1
0
1
1
2º Passo: 
1
0
0
1
3ª Opção.
2ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A → B→C → E→T que
tem como capacidade residual o min [5,1,1,3,6]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
5
3
8
6
4
3
4
1
5
0
6
1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
O
D
C
A
B
E
T
4
3
8
6
4
2
4
0
5
0
5
0
211 
1
0
1
1
0
0
0
2
1
1
2
1
2
3ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→E→T que tem 
como capacidade residual o min [6,5,5]=5. Fazendo fluir 5 no caminho escolhido tem-se:
O
D
C
A
B
E
T
4
3
8
6
4
2
4
0
5
0
5
0
2
1
0
1
1
0
0
0
2
1
1
2
1
2
O
D
C
A
B
E
T
4
3
8
1
4
2
4
0
0
0
0
0
752 
1
0
6
1
0
0
5
2
6
1
7
1
2
4ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→D→ T que tem 
como capacidade residual o min [4,3,8]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
4
3
8
1
4
2
4
0
0
0
0
0
7
1
0
6
1
0
0
5
2
6
1
7
1
2
O
D
C
A
B
E
T
1
0
5
1
4
2
4
0
0
0
0
0
1037 
4
3
6
1
0
0
5
2
6
4
10
1
2
5ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→B→D → T que
tem como capacidade residual o min [4,2,4,5]=2. Fazendo fluir 2 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
5
1
4
2
4
0
0
0
0
0
10
4
3
6
1
0
0
5
2
6
4
10
1
2
O
D
C
A
B
E
T
1
0
3
1
2
2
2
2
0
0
0
0
12210 
4
3
6
1
2
2
5
2
6
6
12
1
0
Refinamento: Cancelamento do fluxo de uma unidade, designado em iteração 
anterior, para obter uma combinação melhor de designação de fluxos.
Isto justifica 
transformar em 
não 
direcionados. 
6ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→D → T que tem 
como capacidade residual o min [1,2,3]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
3
1
2
2
2
2
0
0
0
0
12
4
3
6
1
2
2
5
2
6
6
12
1
0
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13112 
4
3
7
1
2
3
5
2
6
7
13
1
0
7ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→D→T que tem 
como capacidade residual o min [2,2,5,1,2]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
1
0
2
0
2
2
1
2
0
0
0
0
13
4
3
7
1
2
3
5
2
6
7
13
1
0
O
D
C
A
B
E
T
1
0
1
0
1
1
0
2
1
0
0
0
14113 
4
3
7
1
3
4
4
3
6
8
14
1
0
O
D
C
A
B
E
T
14
4
3
7
1
3
4
4
3
6
8
14
1
0
Resposta:
Fluxo:
Não há mais nenhum caminho aumentado.














































































6
1
8
3
0
4
4
31
3
7
4
x
x
x
x
x
x
x
x
x
x
x
x
*
ET
ED
DT
CE
BC
BE
BD
AD
AB
OC
OB
OA
X
14MAXz
OUTRA
Solução 
Ótima 
(igual a 1ª opção):
O
D
C
A
B
E
T
1
0
1
0
1
1
0
2
1
0
0
0
14
4
3
7
1
3
4
4
3
6
8
14
1
0
Vl. do corte = 0
Valor máximo
da função:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
0ij l
Exemplo: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre 
os arcos representam as capacidades de fluxo máximo de cada arco. Não há, 
neste exemplo, capacidade de fluxo mínimo estabelecido .
1º Passo: Transforme os arcos direcionados da rede original em não direcionados.
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
0
0
Mais outro 
modo
de resolução.
1ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→A→D→T que tem como 
capacidade residual o min [5,3,9]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
5
3
9
7
4
4
4
2
5
1
6
1
Rede inicial: 
zerofluxo 
zerofluxo 
0
0
0
0
0
0
0
0
0
0
2º Passo: 
0
0
4ª Opção.
O
D
C
A
B
E
T
2
0
6
7
4
4
4
2
5
1
6
1
3
3
3
0
0
0
0
0
0
0
3
0
0
3
2ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→D→T que tem como 
capacidade residual o min [7,4,6]=4. Fazendo fluir 4 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
6
7
4
4
4
2
5
1
6
1
3
3
3
0
0
0
0
0
0
0
3
0
0
3
O
D
C
A
B
E
T
2
0
2
3
4
4
0
2
5
1
6
1
743 
3
3
4
0
0
4
0
0
0
7
0
0
7
3ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→B→E→T que tem 
como capacidade residual o min [3,5,6]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
2
3
4
4
0
2
5
1
6
1
7
3
3
4
0
0
4
0
0
0
7
0
0
7
O
D
C
A
B
E
T
2
0
2
0
4
4
0
2
2
1
3
1
1037 
3
3
7
0
0
4
3
0
3
7
0
0
10
4ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→D→T que tem 
como capacidade residual o min [4,4,1,2]=1. Fazendo fluir 1 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
2
0
4
4
0
2
2
1
3
1
10
3
3
7
0
0
4
3
0
3
7
0
0
10
O
D
C
A
B
E
T
2
0
1
0
3
3
0
2
2
0
3
1
11110 
3
3
7
0
1
4
3
1
3
8
1
0
11
5ª iteração: Escolha arbitrariamente um dos possíveis caminhos aumentados de O para T ( arcos 
com capacidades residuais estritamente positivas). Aqui escolheremos O→C→E→T que tem 
como capacidade residual o min [3,3,3]=3. Fazendo fluir 3 no caminho escolhido tem-se:
O
D
C
A
B
E
T
2
0
1
0
3
3
0
2
2
0
3
1
11
3
3
7
0
1
4
3
1
3
8
1
0
11
O
D
C
A
B
E
T
2
0
1
0
0
0
0
2
2
0
0
1
14311 
3
3
7
0
4
4
3
4
6
8
1
0
14
O
D
C
A
B
E
T
2
0
1
0
0
0
0
2
2
0
0
1
14
3
3
7
0
4
4
3
4
6
8
1
0
14
Não há mais nenhum caminho aumentado.
O
D
C
A
B
E
T
14
3 3
7
0
4
4
3
4
6
8
14
1
0
Resposta:
Fluxo:
OUTRA
Solução 
Ótima 













































































6
1
8
4
0
3
4
3
0
4
7
3
x
x
x
x
x
x
x
x
x
x
x
x
*
ET
ED
DT
CE
BC
BE
BD
AD
AB
OC
OB
OA
X
14MAXz
Valor máximo
da função:
Vl. do corte = 0
O
D
C
A
B
E
T
4 3
8
7
3
3
4
4
1
6
1
14
14
LINDO 1
O
D
C
A
B
E
T
3 3
8
7
4
4
4
3
1
6
14
14
LINDO 2
O
D
C
A
B
E
T
3 3
8
7
4
4
4
3
1
6
14
14
O A B C D E T
O
A
B
C
D
E
T
LINDO 2
(ACA)
(feito em sala)
2ª Opção
O
D
C
A
B
E
T
3 3
8
7
4
4
4
3 1
6
14
14
O
D
C
A
B
E
T
4 3
8
6
4
4
4
3
1
6
1
14
14
O
D
C
A
B
E
T
4 3
8
7
3
3
4
4
1
6
1
14
14
(ACA)
(feito em sala)
LINDO 1
1ª e 3ª Opções
(ACA)
(feito em sala)
4ª Opção
Algoritmo do Caminho Aumentado (ACA)
3ADu 0ij l
Problema proposto: Maximizar o fluxo de O para T, na rede a seguir, onde os valores sobre os 
arcos representam máxima capacidade de fluxo de cada arco. Não há, neste exemplo, 
capacidade mínima de fluxo estabelecida para os arcos.
O E
C
A
B
F
T
4OAu
3ETu3OBu
4OCu
6CEu
9BDu
2BFu
5FTu
3EGu
7AEu
D G
3CFu
5DGu
3DTu
8GTu
O E
C
A
B
F
T
4
03
4 1
1
2
5
3
2
D G
3
0
3
3
2