Faculdade de Engenharia - Campus de Guaratinguetá Pesquisa Operacional Livro: Introdução à Pesquisa Operacional Capítulo 3 - Teoria dos Grafos Fernando

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

Pesquisa Operacional - UNESP / Campus de Guaratinguetá

Sumário

•IntroduçãoHistóricoAplicações de grafos

•Conceitos e NotaçãoRepresentações de um grafo Tipos de grafos

• Problemas típicos e AlgoritmosCaminho Ótimo - Algoritmo de DjisktraÁrvore Ótima - Algoritmo de KruskalFluxo Máximo - Algoritmo de Ford - Fulkerson

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.3

Figura 2. Leonhard Euler.


Introdução

Figura 3. Königsberg -Kalinigrado nos tempos atuais.


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


Introdução

Aplicações de modelos em grafos

1. Grafos planares: problemas de montagens/ trevos

Figura 3. Um problema de montagem.

A, B, C : linhas de montagens/ rodovias principais

D1, D2, D3: departamentos/ rodovias secundárias

Ligações: esteiras/ viadutos ou túneis

6


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


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

8

1

2

3

a

b

c

Grafo

Não- orientado

Grafo Orientado

3

a

b c

d

e f

1

4

2


Notação

3. Matriz de adjacência (grafo não-orientado) A = (aij) =

9

j nó ao i nó do aresta se ,0

j nó ao i nó do aresta se 1,

1

2

3

0 1 1

1 0 1

1 1 0

1 2 3

1

2

3

a

b

c

A =


Notação

4. Matriz de incidência (grafos orientados) A = [aij] é a matriz (não necessariamente quadrada) de

incidência de G se

i nó ao incidente é não j arco o se 0,

i nó no chega j arco o se 1,-

i nó do sai j arco o se ,1

ija

3

a

b c

d

e f

1

4

2

10


Grafo Valorado

11

400 Rio de

JaneiroSão Paulo

Belo

Horizonte

700

1500

Brasília

Grafo com as distâncias de São Paulo a 3 capitais:


Grafos Especiais

12

Para o grafo G abaixo: árvore, cadeia, caminho, ciclo e circuito

a

b

c

e

f

g

h

j

l

i

d


Árvore

13

1. Árvore (arborescência): grafo conexo sem ciclos

a

b

d

h

j

g


Cadeia

14

2. Cadeia: seqüência de arcos com extremidade em comum

a

d

h

j

l


Caminho

15

3. Caminho: seqüência de arcos com mesma orientação

a

c

f

j


Ciclo e Circuito

16

4. Ciclo: cadeia fechada

a

d

l

ib g

5. Circuito: caminho fechadoa

b

c


Problemas e Algoritmos

17

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á18

Algoritmo de Kruskal

Figura 5. Joseph Kruskal.

Histórico

Em 1956 o matemático americano Joseph Kruskal (29/01/1928-19/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.


Algoritmo de Kruskal

19

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


Exemplo para o Algoritmo de Kruskal

20

Determinar uma árvore mínima

20

8

4

112

1

6

2

5

5

9

3

1

8 10

9 4

A

B C

D F

E

9

8

G

H I

J



21

Passo 1: Grafo trivial

21



22

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



23

Árvore parcial: colocar as arestas com custo 1

11

A

B C

D

E

23



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.

24



25

Árvore parcial: colocar as arestas com custo 2.

11

2

2

A

B C

D

E

25



26

Árvore parcial: colocar a aresta com custo 3.

11

2

2

A

B C

D

E

3

26



27

Árvore parcial: colocar as arestas com custo 4.

11

2

2

A

B C

D

E

3

4

4

27



28

Árvore parcial: colocar uma das duas arestas com custo 5, a outra será descartada.

11

2

2

A

B C

D

E

3

4

4

5

28



29

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:

3

4

2

1 2

5

1

8

4

Observe que esta é uma solução ótima do problema.Custo ótimo: 1 + 1 + 2 + 2 + 3 + 4 + 4 + 5 + 8 = 30.

29


Algoritmo de Dijsktra

30

Figura 6. Edsger Wybe Dijkstra.

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



31

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.



32

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.


Algoritmo de Djisktra

33

1. Inicialização2. Atualização dos rótulos temporários3. 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 .



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


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


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


Exemplo para Caminho Ótimo

37

Achar a distância mínima entre os nós S e T:

S

A C

D

T

7

1

32

4

3

4 7

1 2

10

28

2

B 6

E



38

0* 4* 1* 12 5* 4* 7*

Resolução completa do exemplo de caminho mínimoAplicação do Algoritmo de Djisktra - Tabela completa

Rótulos ExplicaçãoS A B C E D T Vetor com nós do grafo0* 0* 7 1 0* 7 1* 0* 4 1* 5 4 0* 4 1* 5 4* 0* 4 1* 14 5 4* 110* 4* 1* 14 5 4* 110* 4* 1* 12 5 4* 110* 4* 1* 12 5* 4* 110* 4* 1* 12 5* 4* 7

Passo 1 - Inicialização

Passo 2 com i = S

Passo 3 - Rot. Def. Nó B

Passo 2 com i = B

Passo 3 - Rot. Def. Nó D

Passo 2 com i = D

Passo 3 - Rot. Def. Nó A

Passo 2 com i = A

Passo 3 - Rot. Def. Nó E

Passo 2 com i = E

Passo 3 - Rot. Def. Nó T (parar!)



39

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 = EValor do rótulo definitivo do nó E = 5 sendo o nó i responsável = BValor do rótulo definitivo do nó B = 1 sendo o nó i responsável = S

T E B S2 4 1


Exercício

40

A

B

C

D

E

F

S T

1

3

4

2

6

4

5

4

1

6

32

3

4 2

10

Achar a distância mínima entre os nós S e T:


Análise de Redes: Problema do Fluxo Máximo

Figura 7. Lester Randolph Ford, Jr..

Figura 8. Delbert Ray Fulkerson..

Histórico

Em 1956 os matemáticos americanos Lester Randolph Ford (nascido em 23/09/1927) e Delbert Ray Fulkerson (14/08/1924-10/01/1976) propuseram em um trabalho conjunto o algoritmo para resolução do Problema de Fluxo Máximo.


Análise de Redes: Problema do Fluxo Máximo

42

Rede: Formada por duas entidades - Nós, Arcos

Interesse: Comportamento da Variável Fluxo

Exemplos:

Aplicação Nós Arcos Fluxo

Sistemas de comunicação

Satélites, computadores

Micro ondas, 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


Problema de Fluxo Máximo

43

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.



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)

S T

1

2

FF


Modelo de Programação Linear

45

Max Z = F

F S1 + FS2 = F (1) F12 + F 1T = FS1 + F21 (2)s. a: F21 + F2T = FS2 + F12 (3) F1T + F2T = F (4) 0 ≤ Fij ≤ Kij (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.



46

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-orientadaMúltiplas fontes e múltiplos destinos



47

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.



48

S T

1

2

FF

Exemplos:Seja a rede anteriormente considerada:

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



49

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).



50

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 pode-se 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.



51

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.



52

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.


Algoritmo do fluxo máximo

53

1. InicializaçãoObter 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 TUsar 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 TCalcular 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.


Exemplo Completo

54

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.

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.

S T

1

2

FF

7 9

9 8

3


Exemplo Completo

55

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.

Figura 1

S* T*

1*

2*

F = 0F = 0

(0,7) (0,9)

(0,9) (0,8)

(0,3)


Exemplo Completo

56

Desta forma foi obtida uma CFA formada por arcos do tipo Forward, (S,1), (1,2), (2,T).

Etapa 3O 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.

Figura 2

S T

1

2

F = 3F = 3

(3,7) (0,9)

(0,9)

(3,3)

(3,8)


Exemplo Completo

57

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:

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.

Figura 3

vS* 1* T*

S T

1

2

F = 7F = 7

(7,7) (4,9)

(0,9)

(3,3)

(3,8)


Exemplo Completo

58

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:

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:

Figura 4

vS* 2* T*

S T

1

2

F = 12F = 12

(7,7) (4,9)

(5,9)

(3,3)

(8,8)


Exemplo Completo

59

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:

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:

Figura 5

vS*

2*

T*1*

S T

1

2

F = 15F = 15

(7,7) (7,9)

(8,9)

(0,3)

(8,8)


Exemplo Completo

60

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.


Exemplo Completo

61

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.

S* T

1

2*

F = 15F = 15

(7,7)

(0,3)

(8,8)

Figura 6


Extensões para o problema de Fluxo Máximo

62

Rede não-orientada: considere a rede urbana abaixo:

Maximizar o fluxo de tráfego de S até T.

S T

1 3

2 4

40

30

15

30

20

50

25

50

30



63

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)

Trabalhar com modelo equivalente de redes:

S T

1 3

2 4

40

3015

30

20

50

25

50

30

15 2520



64

Nó A = Fonte com oferta produto = 20 (Oferta Total = 40)Nó D = Fonte com oferta produto = 20Nó E = Destino com demanda produto = 15 (Demanda Total = 35)Nó H = Destino com demanda produto =20

Múltiplas fontes e múltiplos destinos:

CC C

10 10

10

1010

5

5

5

5

5 5

15

20A

B

C

D

E

F

G

H

Capacidade do arco



65

C

C

C

C

C

CC

C

CC

20

20

20

10 10

10

10 10

5

5 5

5

55

15 15

20

ffictícia

ffictícia

A

B T

H

G

F

E

D

C

s

O problema é viável ?

MAXIMIZAR f fMAX = 30 < 35 = Demanda Total

Problema Inviável

Documents

Faculdade de Engenharia - Campus de Guaratinguetá Pesquisa Operacional Livro: Introdução à Pesquisa Operacional Capítulo 3 - Teoria dos Grafos Fernando