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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 2 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 3 Introdução Figura 2. 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 4 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 5 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 6 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 Grafo c Não- orientado 1 b a 3 4 c b d 1 2 f e 3 Pesquisa Operacional - UNESP / Campus de Guaratinguetá Grafo Orientado 7 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 8 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 9 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 10 Grafos Especiais Para o grafo G abaixo: árvore, cadeia, caminho, ciclo e circuito d e l a j c f h b i g Pesquisa Operacional - UNESP / Campus de Guaratinguetá 11 Árvore 1. Árvore (arborescência): grafo conexo sem ciclos d a j h b g Pesquisa Operacional - UNESP / Campus de Guaratinguetá 12 Cadeia 2. Cadeia: seqüência de arcos com extremidade em comum d l a j h Pesquisa Operacional - UNESP / Campus de Guaratinguetá 13 Caminho 3. Caminho: seqüência de arcos com mesma orientação a j c f Pesquisa Operacional - UNESP / Campus de Guaratinguetá 14 Ciclo e Circuito 4. Ciclo: cadeia fechada d l a i b 5. Circuito: caminho fechado g a c b Pesquisa Operacional - UNESP / Campus de Guaratinguetá 15 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 16 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 17 Exemplo para o Algoritmo de Kruskal Determinar uma árvore mínima 6 A 9 B 2 11 E 1 9 C J 10 8 3 9 D 5 1 4 G F 2 8 5 8 H Pesquisa Operacional - UNESP / Campus de Guaratinguetá 4 I 18 Exemplo para o Algoritmo de Kruskal Passo 1: Grafo trivial Pesquisa Operacional - UNESP / Campus de Guaratinguetá 19 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). Pesquisa Operacional - UNESP / Campus de Guaratinguetá 20 Exemplo para o Algoritmo de Kruskal Árvore parcial: colocar as arestas com custo 1 A D 1 1 B C E Pesquisa Operacional - UNESP / Campus de Guaratinguetá 21 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á 22 Exemplo para o Algoritmo de Kruskal Árvore parcial: colocar as arestas com custo 2. A D 1 2 1 B C 2 E Pesquisa Operacional - UNESP / Campus de Guaratinguetá 23 Exemplo para o Algoritmo de Kruskal Árvore parcial: colocar a aresta com custo 3. A D 1 2 1 B C 2 3 E Pesquisa Operacional - UNESP / Campus de Guaratinguetá 24 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 25 Exemplo para o Algoritmo de Kruskal Árvore parcial: colocar uma das duas arestas com custo 5, a outra será descartada. 5 A D 4 1 2 1 B C 2 3 E 4 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 26 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 27 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 28 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 29 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 . Pesquisa Operacional - UNESP / Campus de Guaratinguetá 30 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 31 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 32 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 33 Exemplo para Caminho Ótimo Achar a distância mínima entre os nós S e T: 2 A 7 S C 8 2 1 2 3 2 E 4 1 B 4 3 Pesquisa Operacional - UNESP / Campus de Guaratinguetá T 10 7 6 D 34 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!) Pesquisa Operacional - UNESP / Campus de Guaratinguetá 35 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 2 E 4 Pesquisa Operacional - UNESP / Campus de Guaratinguetá B 1 S 36 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 37 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 38 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) Cij ou 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 39 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 40 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 41 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 42 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: seqüê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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 43 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 44 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). Pesquisa Operacional - UNESP / Campus de Guaratinguetá 45 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 46 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 47 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. Um nó j pode ser rotulado a partir de S se um fluxo positivo pode ser enviado de S para j. 2. Em geral, a partir de qualquer nó i (S) pode-se rotular um nó j se uma das condições abaixo ocorre: a) O arco que conecta os nós i e j é do tipo Forward para o nó i 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 para o nó i 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. 48 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. Ir à Etapa 2. 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 49 Algoritmo do fluxo máximo 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. 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: 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 os arcos. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 51 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 para o nó S e 0 = FS1 ≤ CS1 = 7 a seguir, do nó 1 pode-se rotular o nó 2 pois o arco (1,2) é do tipo Forward para o nó 1 e 0 = F12 ≤ C12 = 3. Finalmente rotula-se o nó destino T pois o arco (2,T) é do tipo Forward para o nó 2 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* Figura 1 Pesquisa Operacional - UNESP / Campus de Guaratinguetá T* F=0 (0,8) 52 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) 53 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) 54 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 para S 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 55 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 é Backward para o nó 2, 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 56 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 57 Exemplo Completo (7,7) F = 15 S* 1 (0,3) 2* T F = 15 (8,8) Figura 6 Considere o corte que separa os nós rotulados (S e 2) dos não rotulados (1 e T) na última etapa 2, ele é formado pelos arcos (S,1) 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. Pesquisa Operacional - UNESP / Campus de Guaratinguetá 58 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á 59 Extensões para o problema de Fluxo Máximo Trabalhar com modelo equivalente de redes: 40 1 15 15 S 30 2 30 3 20 20 50 50 T 25 25 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) Pesquisa Operacional - UNESP / Campus de Guaratinguetá 60 Extensões para o problema de Fluxo Máximo Múltiplas fontes e múltiplos destinos: B 10 C A 5 20 C 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 Pesquisa Operacional - UNESP / Campus de Guaratinguetá 10 C H 10 G (Oferta Total = 40) (Demanda Total = 35) 61 Extensões para o problema de Fluxo Máximo O problema é viável ? C B 10 A C 20 20 sC 5 C 5 20 C D 15 10 5 5 5 C E 15 20 5 C F 10 f C fictícia T 10 HC 10 C G f fictícia MAXIMIZAR f fMAX = 30 < 35 = Demanda Total Problema Inviável Pesquisa Operacional - UNESP / Campus de Guaratinguetá 62