Faculdade de Engenharia - Campus de Guaratinguetá
Pesquisa Operacional
Livro: Introdução à Pesquisa Operacional
Capítulo 3 - Teoria dos Grafos
Fernando Marins – [email protected]
Departamento de Produção
1
Sumário
•Introdução
Histórico
Aplicações de grafos
•Conceitos e Notação
Representações de um grafo
Tipos de grafos
• Problemas típicos e Algoritmos
Caminho Ótimo - Algoritmo de Djisktra
Árvore Ótima - Algoritmo de Kruskal
Fluxo Máximo - Algoritmo de Ford - Fulkerson
2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Introdução
Histórico
Euler resolveu o problema das pontes de Königsberg do rio Pregel, em
1736, utilizando um modelo de grafos: partir de uma das 4 regiões,
atravessar cada ponte uma única vez e retornar à região de partida.
Figura 1. Rio Pregel e suas sete pontes.
Figura 2. Leonhard Euler.
3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Introdução
Figura 3. Königsberg -Kalinigrado nos tempos atuais.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Introdução
Figura 4. Modelo de Grafo para o Rio Pregel e suas sete pontes.
Modelo de grafos utilizado por Euler para demonstrar que o
problema não tem solução.
Para haver solução é necessário que cada região tenha um
número par de pontes associadas.
5
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Introdução
Aplicações de modelos em grafos
1.
Grafos planares: problemas de montagens/ trevos
A, B, C : linhas de montagens/
rodovias principais
D1, D2, D3: departamentos/
rodovias secundárias
Ligações: esteiras/ viadutos ou
túneis
Figura 3. Um problema de montagem.
6
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Introdução
2.
Problemas de Localização
Existindo n cidades consumidoras do produto fabricado
por uma determinada empresa, deseja-se saber onde seria o
melhor local para a instalação de uma filial desta empresa que
atendesse as n cidades com menor custos de distribuição do
produto.
Existem algoritmos próprios para este problema, além de
várias heurísticas que possuem bom desempenho.
7
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Notação
Representações de um grafo G
1. G(V, A) onde:
V = Conjunto de vértices ou nós do grafo
A = Conjunto de arcos ou arestas do grafo
2. Diagramas e tipos de grafos
2
a
a
Grafo
c Não- orientado
4
c
b
d
1
1
b
3
2
f
e
3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Grafo Orientado
8
Notação
3. Matriz de adjacência (grafo não-orientado)
1, se  aresta do nó i ao nó j
A = (aij) = 
0, se  aresta do nó i ao nó j
2
a
c
1
b
3
1  0 1 1


A = 2  1 0 1


3  1 1 0
1 2 3
9
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Notação
4. Matriz de incidência (grafos orientados)
A = [aij] é a matriz (não necessariamente quadrada) de
incidência de G se  1, se o arco j sai do nó i

aij  - 1, se o arco j chega no nó i
 0, se o arco j não é incidente ao nó i

a
4
c
b
d
1
2
f
e
3
10
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Grafo Valorado
Grafo com as distâncias de São Paulo a 3 capitais:
400
700
Belo
São Paulo
Rio de
Janeiro
1500
Horizonte
Brasília
11
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Grafos Especiais
Para o grafo G abaixo: árvore, cadeia, caminho, ciclo e circuito
d
e
l
a
j
c
f
h
i
b
g
12
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Árvore
1. Árvore (arborescência): grafo conexo sem ciclos
d
a
j
h
b
g
13
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Cadeia
2. Cadeia: seqüência de arcos com extremidade em comum
d
l
a
j
h
14
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Caminho
3. Caminho: seqüência de arcos com mesma orientação
a
j
c
f
15
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo e Circuito
4. Ciclo: cadeia fechada
d
l
a
i
b
g
5. Circuito: caminho fechado
a
c
b
16
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problemas e Algoritmos
Otimização em grafos
1. Determinação de Árvores ótimas: Algoritmo de Kruskal
2. Determinação de Caminhos Ótimos: Algoritmo de Djisktra
3. Determinação de Fluxo Máximo: Algoritmo de Ford &
Fulkerson
17
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Kruskal
Histórico
Em 1956 o matemático americano
Joseph
Kruskal
(29/01/192819/09/2010) propôs um algoritmo
para resolução do Problema da
Árvore Mínima.
Ele completou seu Ph.D. na
Universidade de Princeton em
1954.
Figura 5. Joseph Kruskal.
18
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Kruskal
Determinação de uma árvore mínima num grafo G (V, A)
Para cada aresta (i, j) existe um custo associado Cij.
|V| = cardinalidade do conjunto de nós V = número de nós.
Passo 1. Considerar o grafo trivial formado apenas pelos nós de G
Passo 2. Construção da Árvore
Acrescentar ao grafo trivial a aresta (i, j) associada ao menor valor
de custo Cij.
Repetir o procedimento respeitando a ordem crescente de valores de
Cij, desde que a aresta analisada não forme ciclo com as arestas já
incorporadas à árvore.
Após incorporar |V| - 1 arestas  Parar! A árvore mínima foi obtida.
19
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Determinar uma árvore mínima
6
A
4
9
B
2
9
9
C
J
10
8
3
11
1
5
1
E
D
F
2
8
G
5
8
H
4
I
20
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Passo 1: Grafo trivial
21
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Passo 2:
A primeira aresta a ser incorporada será a aresta associada ao valor
de custo = 1. Observe-se que há duas arestas nestas condições:
aresta (a, b) e aresta (c, d).
Pode-se escolher arbitrariamente qual delas será incorporada
primeiro ao grafo trivial.
A seguir incorpore a outra (observe que elas não formam ciclo).
22
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Árvore parcial: colocar as arestas com custo 1
A
D
1
1
B
C
E
23
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
A seguir tem-se as arestas (b, e) e (b, f)
correspondentes aos custo com valor 2.
Analogamente ao caso anterior pode-se optar por
qualquer uma elas para ser analisada primeiro.
Ambas serão incorporadas ao grafo resultante da
operação anterior, pois também não formam ciclo.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
24
Exemplo para o Algoritmo de Kruskal
Árvore parcial: colocar as arestas com custo 2.
A
D
1
2
1
B
C
2
E
25
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Árvore parcial: colocar a aresta com custo 3.
A
D
1
2
1
B
C
2
3
E
26
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Árvore parcial: colocar as arestas com custo 4.
A
D
1
2
1
4
B
C
2
3
E
4
27
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Árvore parcial: colocar uma das duas arestas com custo 5, a outra
será descartada.
5
A
D
1
2
1
4
B
C
2
3
E
4
28
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para o Algoritmo de Kruskal
Como o número de nós é 10 prossegue-se neste processo até que sejam
incorporadas 10 - 1 = 9 arestas, sendo obtida uma árvore mínima:
5
1
2
1
4
2
8
3
4
Observe que esta é uma solução ótima do problema.
Custo ótimo: 1 + 1 + 2 + 2 + 3 + 4 + 4 + 5 + 8 = 30.
29
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Dijsktra
Histórico
Em 1956 o cientista da computação
holandês Edsger Wybe Dijkstra concluiu o
desenvolvimento do algoritmo para o
problema do caminho mínimo mas
somente em 1959 foi publicado seu
trabalho.
Este algoritmo foi o seu primeiro trabalho
e o mais conhecido.
Edsger Wybe Dijkstra nasceu em 11 de
maio de 1930 e morreu em 6 de agosto de
2002.
“ Ciência não estuda ferramentas,
mas o que fazemos e o que
descobrimos com elas.” Edsger Dijkstra
Figura 6. Edsger Wybe Dijkstra
.
30
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Dijsktra
Problema do Caminho Ótimo
• Determinação de caminhos mínimos em grafos valorados.
• Princípio de Otimalidade de Bellman:
“Um caminho mínimo é constituído de sub-caminhos mínimos”
• Aplica-se a grafos valorados onde não há laços, arcos paralelos e
todos valores associados aos arcos são não-negativos.
• Achar caminho ótimo entre dois nós (origem = S e destino = T)
de um grafo.
31
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Dijsktra
Aspectos Gerais
Adota a técnica de rotulação dos nós, havendo dois tipos de
rótulos: rótulos temporários e rótulos definitivos.
•
• A cada iteração, alguns nós são rotulados temporariamente e
apenas um nó é rotulado definitivamente.
• O valor
do rótulo
definitivo associado a um nó j
corresponde ao valor da distância mínima entre o nó origem S e o
nó j.
• A execução do algoritmo termina quando se consegue rotular
definitivamente o nó destino T.
32
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Djisktra
1. Inicialização
2. Atualização dos rótulos temporários
3. Rotulação Definitiva de um nó
4. Passo geral
1. Inicialização
Rotular definitivamente o nó origem S com valor 0.
Rotular temporariamente os demais nós com valor .
33
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Djisktra
2. Atualização dos rótulos temporários
Todo nó j ainda não rotulado definitivamente deve receber
novo valor de rótulo dado por
Min {rótulo atual do nó j, rótulo do nó i + cij},
onde,
i = último nó rotulado definitivamente
cij = valor associado ao arco que liga os nós i e j.
34
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Djisktra
3. Rotulação definitiva
Comparar os rótulos temporários e escolher para ser
rotulado definitivamente o nó j associado ao menor
valor.
4. Passo geral
Repetir sucessivamente os passos 2 e 3 até rotular
definitivamente o nó destino T.
O valor da distância mínima entre os nós S e T é o
valor do rótulo definitivo do nó destino T.
35
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Obtenção dos nós do caminho mínimo
• A partir do nó t achar qual foi o nó i do passo 2 responsável
pelo valor de seu rótulo definitivo. Suponha que tenha sido o
nó k.
• A partir do nó k achar qual foi o nó i do passo 2 responsável
pelo valor de seu rótulo definitivo. Suponha que tenha sido o
nó h.
• Repetir este processo até que o nó i seja o nó origem s
• Os nós i encontrados em cada etapa deste processo de busca
serão os nós intermediários do caminho mínimo entre s e t.
36
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo para Caminho Ótimo
Achar a distância mínima entre os nós S e T:
A
2
C
8
7
2
1
2
S
3
2
E
4
1
4
B
3
T
10
7
6
D
37
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Djisktra
Resolução completa do exemplo de caminho mínimo
Aplicação do Algoritmo de Djisktra - Tabela completa
Rótulos
Explicação
S A B C E D T
Vetor com nós do grafo
0*      
Passo 1 - Inicialização
0* 7 1    
Passo 2 com i = S
0* 7 1*    
Passo 3 - Rot. Def. Nó B
0* 4 1*  5 4 
Passo 2 com i = B
0* 4 1*  5 4* 
Passo 3 - Rot. Def. Nó D
0* 4 1* 14 5 4* 11
Passo 2 com i = D
0* 4* 1* 14 5 4* 11
Passo 3 - Rot. Def. Nó A
0* 4* 1* 12 5 4* 11
Passo 2 com i = A
0* 4* 1* 12 5* 4* 11
Passo 3 - Rot. Def. Nó E
0* 4* 1* 12 5* 4* 7
Passo 2 com i = E
0* 4* 1* 12 5* 4* 7*
Passo 3 - Rot. Def. Nó T (parar!)
38
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo de Djisktra
Distância mínima entre os nós S e T = 7 = Rótulo definitivo do nó T.
Recuperação do caminho mínimo (ótimo):
Valor do rótulo definitivo do nó T = 7 sendo o nó i responsável = E
Valor do rótulo definitivo do nó E = 5 sendo o nó i responsável = B
Valor do rótulo definitivo do nó B = 1 sendo o nó i responsável = S
T
E
2
4
B
1
S
39
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercício
Achar a distância mínima entre os nós S e T:
6
A
D
3
1
1
2
2
3
S
4
4
B
E
5
4
6
C
4
3
T
2
F
10
40
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Análise de Redes: Problema do Fluxo
Máximo
Histórico
Em
1956
os
matemáticos
americanos Lester Randolph Ford
(nascido em 23/09/1927) e Delbert
Ray
Fulkerson
(14/08/192410/01/1976) propuseram em um
trabalho conjunto o algoritmo para
resolução do Problema de Fluxo
Máximo.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Figura 7. Lester Randolph Ford, Jr.
.
Figura 8. Delbert Ray Fulkerson.
41
.
Análise de Redes: Problema do Fluxo
Máximo
Rede: Formada por duas entidades - Nós, Arcos
Interesse: Comportamento da Variável Fluxo
Exemplos:
Aplicação
Sistemas de
comunicação
Nós
Arcos
Fluxo
Satélites,
Micro ondas,
computadores fibra ótica
Mensagens,
dados
Sistemas
hidráulicos
Estação de
bombeamento,
reservatório
Tubos
Água, gás,
petróleo
Sistemas de
transportes
Interseções,
aeroportos
Estradas,
rotas aéreas
Veículos,
passageiros
42
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Notação:
Nó fonte: S
Nó destino: T
Fluxo no arco (i,j): Fij = quantidade de produto no arco (i,j)
Kij = capacidade do arco (i,j) = maior fluxo possível no arco (i,j)
Restrições envolvidas:
Há conservação de fluxo nos nós.
Há limitação do valor de fluxo nos arcos.
Observações:
O método simplex resolve este problema.
Método mais eficiente: Ford &Fulkerson.
43
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Seja a rede abaixo. Deseja-se achar o valor do fluxo máximo que
pode ser enviado do nó S ao nó T, respeitando as restrições de
capacidade nos arcos e a conservação de fluxo nos nós.
Sejam Kij (ou Cij) as restrições de fluxo (capacidade) no arco (i, j)
1
F
S
T
F
2
44
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Programação Linear
Max Z = F
s. a:
F S1 + FS2 = F
F12 + F 1T = FS1 + F21
F21 + F2T = FS2 + F12
F1T + F2T = F
0 ≤ Fij ≤ Kij
(1)
(2)
(3)
(4)
(5)
• Restrição (1) representa a conservação de fluxo no nó fonte S.
• Restrições (2) e (3) representam a conservação de fluxo nos nós
intermediários 1 e 2.
• Restrição (4) representa a conservação de fluxo no nó destino T.
• Restrição (5) restringe os fluxos a serem não-negativos e
respeitarem os limites de capacidade nos arcos.
45
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Dada uma rede orientada formada por arcos onde há
restrições de capacidade, deseja-se enviar a maior quantidade
(fluxo) possível de um produto a partir de um nó fonte (S) para um
nó destino (T).
Fluxo de produto pode ser fluxo de eletricidade, de água,
de informação, ou de veículos, entre outros.
Extensões:
Rede não-orientada
Múltiplas fontes e múltiplos destinos
46
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Conceitos Básicos
• Arcos Forward para o nó i: todo arco que sai do nó i.
• Arcos Backward para o nó i: todo arco que entra no nó i.
• Caminho entre o nó fonte e o nó destino: sequência de arcos que
se inicia no nó fonte S e termina no nó destino T.
• Ciclo é um caminho cujos nós inicial e final são os mesmos.
• Seja N = conjunto de todos os nós da rede. Um Corte separando a
fonte S do destino T é uma partição dos nós da rede em dois
subconjuntos denotando por S aquele que contém o nó S e por S
aquele que contém o nó T.
47
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Exemplos:
Seja a rede anteriormente considerada:
1
F
S
T
F
2
Nó 1: arcos Forward = {(1,2),(1,T)}, arcos Backward = {(S,1),(2,1)}
Caminho: (S,1),(1,2),(2,T)
Corte: S = {S,1,2}, S = {T} capacidade = K1T + K2T
S = {S,2}, S = {1,T} capacidade = KS1 + K21 + K2T
48
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Resultados Importantes:
• O corte mínimo é aquele corte com o menor valor de
capacidade associado.
• Excluindo os arcos de um corte da rede  não há caminho
entre os nós S e T  nenhum fluxo ocorrerá entre S e T.
• Todo fluxo entre S e T deve se dar pelos arcos de um corte o
valor do fluxo é limitado pela capacidade do corte.
Lema 1:
Se F é o fluxo da fonte ao destino e (S,S) é um corte  o valor de
F é menor ou igual a capacidade daquele corte (S,S).
49
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Consequências:
Todo fluxo viável da fonte ao destino não pode exceder a
capacidade de um corte qualquer.
O fluxo máximo na rede é limitado pela capacidade do
corte mínimo.
Teorema do Fluxo Máximo e do Corte Mínimo
O valor do fluxo máximo numa rede é igual a capacidade
do corte mínimo.
Usando o teorema do fluxo máximo e corte mínimo podese obter o valor do fluxo máximo. Basta encontrar as capacidades
de todos os cortes existentes na rede e escolher o menor valor de
capacidade.
50
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Princípios Básicos do Algoritmo do Fluxo Máximo:
Encontrar um caminho pelo qual um fluxo positivo possa ser
enviado da fonte S ao destino T.
Este caminho é denominado Flow Augmenting Path = caminho
com fluxo crescente – CFC.
O CFC é usado para enviar a maior quantidade de fluxo possível
de S para T.
Repete-se o processo até que nenhum CFC possa ser obtido.
51
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Problema de Fluxo Máximo
Rotina de rotulação adotada pelo algoritmo:
Usada para achar CFC de S para T.
1.Iniciar com o nó fonte S. Dizemos que o nó j pode ser rotulado se um
fluxo positivo pode ser enviado a partir de S para j.
2.Em geral a partir de qualquer nó i pode-se rotular um nó j se uma das
condições abaixo se verifica:
a)O arco que conecta os nós i e j é do tipo Forward e o fluxo Fij neste
arco (i,j) é menor que o valor da sua capacidade Kij.
b)O arco que conecta os nós i e j é do tipo Backward e o fluxo Fij neste
arco (j,i) é maior que zero.
3. O processo continua até que o nó destino T é rotulado. Tem-se então
um CFC.
52
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmo do fluxo máximo
1. Inicialização
Obter um fluxo viável em todos os arcos da rede. Este fluxo deve satisfazer as
restrições de conservação de fluxo nos nós e as restrições de capacidade nos
arcos. Inicialmente adotar fluxo nulo em todos os arcos.
2. Procura de um caminho de fluxo crescente – CFC de S para T
Usar o procedimento de rotulação de nós, iniciando com o nó origem e
terminando com o nó destino T.
Se não for possível obter um CFC Parar! Uma solução ótima foi obtida
o fluxo atual é máximo.
Caso contrário ir a etapa 3.
3. Aumento no valor do fluxo entre S e T
Calcular o valor máximo δ de fluxo que pode ser enviado pela CFC obtida na
etapa anterior.
Nos arcos Forward do CFC aumentar o fluxo de δ.
Nos arcos Backward do CFC diminuir o fluxo de δ.
Voltar à etapa 2.
53
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo Completo
Determinar o fluxo máximo F da fonte S ao destino T, na rede a seguir.
Os números ao lado dos arcos representam suas capacidades Cij.
1
7
F
9
3
S
T
9
F
8
2
Notação: Nas próximas figuras os números ao lado dos arcos
representam (Fij, Cij), onde Fij é o fluxo no arco (i, j). Nós rotulados
serão marcados por asteriscos.
Etapa 1 – Inicialização: Fazer Fij = 0 em todos as arcos.
54
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo Completo
Etapa 2 – (Figura 1) Para achar um CFC de S para T: Rotular
inicialmente S. Deste nó S pode-se rotular o nó 1 pois o arco (S,1) é do
tipo Forward e 0 = FS1 ≤ CS1 = 7 a seguir, do nó 1 pode-se rotular o nó 2
pois o arco (1,2) é do tipo Forward e 0 = F12 ≤ C12 = 3. Finalmente
rotula-se o nó destino T pois o arco (2,T) é do tipo Forward e 0 = F2T ≤
C2T = 8. Isto resulta num valor de fluxo F = 0.
(0,7)
F=0
1*
(0,9)
(0,3)
S*
(0,9)
2*
T*
F=0
(0,8)
Figura 1
55
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo Completo
Desta forma foi obtida uma CFA formada por arcos do tipo Forward,
(S,1), (1,2), (2,T).
Etapa 3
O fluxo máximo neste CFC é dado por min {(7 - 0), (3 - 0), (8 - 0)} = 3.
Assim pode-se aumentar o fluxo entre S e T de δ = 3.
Os novos fluxos estão na Figura 2.
(3,7)
F=3
1
(0,9)
(3,3)
S
(0,9)
2
Figura 2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
T
F=3
(3,8)
56
Exemplo Completo
Etapa 2 – Repetindo o processo de rotulação de nós para a configuração da
Figura 2 obtém-se um novo CFC dado por:
v
T*
1*
S*
Etapa 3 – O fluxo máximo permitido neste CFC = min {(7 -3), (9 -0)}= 4.
Isto aumenta o fluxo pela rede para F = 3 + 4 = 7.
A nova configuração de fluxos fica sendo a da Figura 3.
(7,7)
F=7
1
(4,9)
(3,3)
S
(0,9)
2
Figura 3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
T
F=7
(3,8)
57
Exemplo Completo
Etapa 2 – Na busca de um novo CFC, o nó 1 não pode ser rotulado a partir do
nó S pois o arco (S,1) é Forward e agora FS1 = CS1 = 7. Mas um novo CFC
pode ser obtido rotulando-se o nó 2 e depois o nó T:
v
T*
2*
S*
Etapa 3 – Neste CFC o fluxo pode ser aumentado de min {(9 -0), (8 -3)} = 5, o
que resulta na configuração dada pela Figura 4:
(7,7)
F = 12
1
(4,9)
(3,3)
S
(5,9)
2
T
F = 12
(8,8)
Figura 4
58
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo Completo
Etapa 2: Partindo-se do nó S pode-se rotular o nó 2, a seguir rotula-se o nó 1, pois o
arco (1,2) contém um fluxo positivo de 3 unidades e fica sendo Backward neste
novo CFC, finalmente a partir do nó 1, pelo arco (1,T) rotula-se o nó destino T:
1*
S*
v
T*
2*
Etapa 3 – Neste CFC pode-se aumentar o fluxo na rede de min{(9 -5),3,(9 -4)} = 3,
pois o arco (1,2) é Backward e pode ter o fluxo de 3 diminuído até zero. A nova
configuração de fluxos está na Figura 5:
(7,7)
F = 15
1
(7,9)
(0,3)
S
(8,9)
2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
T
F = 15
(8,8)
Figura 5
59
Exemplo Completo
Etapa 2: O nó 2 pode ser rotulado a partir do nó S, mas nenhum outro
nó pode ser rotulado a partir do nó 2, ou seja, não há nenhum CFC
adicional.
Logo obteve-se o fluxo máximo de S para T dado por 15 unidades de
fluxo.
Observação: Pode-se usar o teorema de Ford & Fulkerson para provar
que o fluxo máximo é de fato 15. Veja a Figura 6.
60
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo Completo
(7,7)
F = 15
S*
1
(0,3)
T
F = 15
(8,8)
2*
Figura 6
Considere o corte que separa os nós rotulados dos não rotulados na
última etapa 2, ele é formado pelos arcos (S,1),(1,2) e (2,T), tendo
capacidade = 15 e separa o nó S do nó T.
Pelo Teorema de F & F o fluxo não pode exceder a capacidade de
nenhum corte que separe o nó S do nó T, logo o corte em questão é o
corte mínimo e o fluxo máximo = 15 é igual a capacidade deste corte
mínimo.
61
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Extensões para o problema de Fluxo
Máximo
Rede não-orientada: considere a rede urbana abaixo:
1
30
3
40
50
20
15
S
T
25
30
50
2
30
4
Maximizar o fluxo de tráfego de S até T.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
62
Extensões para o problema de Fluxo
Máximo
Trabalhar com modelo equivalente de redes:
1
30
3
40
15 15
S
50
20
20
T
25 25
30
2
50
4
30
Aplicar o algoritmo apresentado e achar Fluxo Máximo.
Se arco (i,j) não é direcionado e fij > fji  fluxo = (fij – fji) será
enviado de i para j.
(Adequar mão de trânsito no arco i  j)
63
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Extensões para o problema de Fluxo
Máximo
Múltiplas fontes e múltiplos destinos:
B
10
5
CA
20
CC
5
D
15
E
10
Capacidade
do arco
5
5
F
5
10
5
Nó A = Fonte com oferta produto = 20
Nó D = Fonte com oferta produto = 20
Nó E = Destino com demanda produto = 15
Nó H = Destino com demanda produto =20
10
CH
10
G
(Oferta Total = 40)
(Demanda Total = 35)
64
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Extensões para o problema de Fluxo
Máximo
O problema é viável ?
CB
10
15
10
5
A
C
20
20
Cs
CC
5
20
CE
15
CD
20
5
5
5
5
CF
10
f
CT fictícia
10
HC
10
G
C
f
fictícia
MAXIMIZAR f  fMAX = 30 < 35 = Demanda Total
Problema Inviável
65
Pesquisa Operacional - UNESP / Campus de Guaratinguetá