Buscar

01 TEORIA DOS GRAFOS E OTIMIZAÇÃO EM REDES

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
1. TEORIA DOS GRAFOS E OTIMIZAÇÃO EM REDES 
 
 
Pontes de Königsberg na Prússia que cruzam o rio Pregel (atual Kalingrado na 
Rússia). 
Seria possível percorrer todas as quatro seções e voltar ao local de partida 
cruzando uma ponte de cada vez? 
 
 
 
 
 
Resolvido por Leonhard Euler XVIII, resposta: NÃO É POSSÍVEL REALIZAR TAL 
PERCURSO! 
 
A Teoria dos Grafos auxilia na solução de problemas similares, podendo ser 
aplicada em várias situações onde se pretende obter por exemplo: 
 A melhor maneira de interligar lugares onde é necessário uma conexão 
eficiente e/ou mais econômica entre eles; 
 O menor caminho possível; 
 O maior fluxo de materiais, insumos e/ou produtos; 
 O funcionamento de atividades em rede e identificação de gargalos. 
 
 
1.1. A TEORIA DOS GRAFOS 
 
De uma forma geral, os grafos podem ser vistos como 
modelos de rede que são utilizados em casos 
especiais de problemas de programação linear (PPL) 
dos quais podem ser representados melhor de forma 
gráfica. Importantes problemas de otimização tais 
como problemas de distribuição logística e energia, 
produção e outros, são eficientemente resolvidos se 
modelados como problema de rede. 
 
1.1.1. Definição de Grafos 
 
Um grafo é uma noção simples e abstrata utilizada 
para representar a ideia de relação entre elementos. 
Tais elementos podem ser entendidos como cidades, 
máquinas, postos de trabalho, fábricas entre outros. 
 
 Definição Matemática 
 
Os grafos podem ser definidos por 
)A;V(G 
, onde 
V é o conjunto de vértices e A é o conjunto de ligações 
entre vértices. 
 
 Grafos Não-Orientados: 
 
Ligações do tipo aresta, onde as ligações que 
representam os pares de vértice (i,j) não possuem 
uma ordem ou um sentido obrigatório., ou seja, (i,j) = 
(j,i) = [i,j]. 
 
 
 
Características do Grafo G. 
V = (1, 2, 3, 4, 5) 
A = ([1,2], [1,3], [1,5], [2,3], [2,4], [3,4], [3,5[, [4,5]) 
n = 5 (número de vértices) 
m = 8 (número de arestas) 
 
 Grafos Orientados ou Dígrafos 
 
Ligações do tipo arco, onde a ordem dos pares de 
vértice (i,j) importa, sendo assim (i,j) ≠ (j,i). 
 
 
 
Características do Grafo G 
V = (A, B, C, D, E) 
A = ((A,B), (A,C), (A,D), (B,C), (C,E), (D,E), (E,D)) 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
n = 5 (número de vértices) 
m = 7 (número de arestas) 
 
1.1.2. Representação de um Grafo 
 
 Listas de Adjacências 
 
Armazena o relacionamento entre os vértices em uma 
estrutura de listas. Trata-se de uma estrutura 
econômica do ponto de vista computacional. 
Para grafos orientados há 2 listas: 
1. origem-destinos 
2. destino-origens 
 
 Matriz de Adjacências 
Dois vértices são adjacentes se estão unidos por uma 
aresta ou arco. Matriz Mnxn (n = total de vértices) 
 Matriz de Adjacências Valorada 
 
Trata-se de uma matriz que atribui valores as arestas 
ou arcos, sendo estes valores relacionados a 
distâncias, custos, capacidade etc. São valores 
associados a matriz D. 
 









A)j,i(d
A)j,i(cd
ji0d
D
ij
ijij
ij
 
 
Exemplo: 
 
 
 
1.1.3. O Problema do Caixeiro Viajante 
 
Trata-se de um percurso Hamiltoniano, onde cada 
vértice deve ser visitado uma única vez. 
 
 Conceito Histórico 
 
Antigamente muitos vendedores, chamados de 
caixeiros viajantes, ganhavam a vida oferecendo seus 
produtos em diferentes cidades. Imagine que um 
caixeiro viajante escolhesse algumas cidades e 
precisasse encontrar o caminho mais curto para suas 
andanças. Em que ordem ele deveria percorrer as 
cidades escolhidas? Se fossem poucas cidades, seria 
fácil descobrir. 
 
 
 
Objetivo: O caixeiro viajante deve percorrer todas as 
cidades (vértices) passando por cada uma delas 
apenas UMA vez. 
 
 Contextualizando ... 
 
Mas e se o caixeiro estivesse em Brasília e quisesse 
percorrer as capitais de todos os 26 estados 
brasileiros? Em que ordem ele deveria visitar essas 
cidades? Como descobrir qual o caminho mais curto? 
Uma opção seria considerar todas as possíveis 
ordenações das 26 cidades. Mas são tantas, que se 
levássemos apenas 1 segundo para calcular a 
distância total de cada possível percurso, levaríamos 
cerca de um bilhão de vezes a idade do universo para 
encontrar a resposta. Isso acontece porque o número 
de percursos alternativos cresce assustadoramente 
quando aumentamos o número de cidades. 
 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
Esse é o chamado Problema do Caixeiro Viajante, 
uma questão matemática muito importante para a 
indústria. Quem encontrar um método eficiente para 
resolvê-lo pode ganhar uma verdadeira fortuna! 
 
1.1.4. O Problema do Carteiro Chinês 
 
Trata-se de um percurso Euleriano, onde cada arco ou 
aresta devem ser visitados uma única vez. 
 
 Conceito Histórico 
 
A literatura relata um grande número de otimização 
combinatória associadas aos percursos desenvolvidos 
sobre as arestas de um grafo G. 
O Problema do Carteiro Chinês foi relatado 
inicialmente por Kwan Mei-Ko em 1962, na revista 
Chinese Mathematics. 
O problema consiste em determinar um caminho 
fechado (circuito) de custo mínimo que passe por cada 
aresta de um grafo G conectado pelo menos uma vez. 
 
 
 
Objetivo: O carteiro chinês deve percorrer todas as 
ruas (arestas e arcos) passando por cada uma delas 
apenas UMA vez. 
 
 Contextualizando 
 
Se o carteiro chinês, estivesse em Volta Redonda na 
Vila Santa Cecília? Como ele poderia entregar as 
correspondências, passando apenas uma vez em 
cada rua ou avenida. 
E se ele estiver em um veículo automotor? Terá de 
respeitar as leis de trânsito, ou seja, a mão da via. 
 
 
 
1.2. A ÁRVORE GERADORA MÍNIMA 
 
1.2.1. Como Assim? Árvore? 
 
A árvore geradora mínima está relacionada a 
combinação de menor custo relacionada a um grafo 
G. 
O formato de árvore refere-se às conexões entre os 
vértices que são o suficiente para conectar todos eles. 
Normalmente tem o formato de árvore (tronco + 
galhos). 
 
 Grafo Conexo 
 
Quando existe pelo menos um percurso (sequência) 
entre cada par de vértices. 
 
 
 
 Árvore Geradora 
 
É um subgrafo de G que contém todos os vértices de 
G. 
 
 
 
1.2.2. Algoritmo de Prim 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
O algoritmo de Prim segue as seguintes etapas: 
1. Selecionar qualquer vértice (o vértice pertence 
à árvore geradora) 
2. Adicionar o vértice mais próximo à árvore, 
caso o vértice forme um ciclo, deve-se 
selecionar o seguinte. 
Exemplo: 
 
Dado o grafo G a seguir, determine sua AGM, pelo 
algoritmo de Prim. 
 
 
1.2.3. Algoritmo de Kruskal 
 
O algoritmo de Kruskal segue as seguintes etapas: 
1. Selecionar as arestas por ordem crescente de 
custo; 
2. Caso a aresta forme um ciclo, deve-se 
selecionar a seguinte. 
Exemplo: 
 
Dado o grafo G a seguir, determine sua AGM, pelo 
algoritmo de Prim. 
 
 
1.3. O PROBLEMA DO CAMINHO MÍNIMO 
 
O Problema de Caminho Mínimo tem como principal 
objetivo minimizar o custo de percurso entre 2 
vértices, custo este dado pela soma dos custos de 
cada aresta percorrida. Modelando conforme um PPL, 
obtem-se o seguinte modelo: 
 
m1,2,...,ji, 1;ou 0x
mi se,1
m1ou i se,0
1i se,1
xx
:a sujeito
xcMin
ij
m
1j
m
1j
kjij
m
1i
m
1j
ijij








 

 
 
 
 
 Função Objetivo de minimização de custos 
 Restrições: conservação de fluxo 
 Variáveis binárias 
 
Observação: trata-se de um problema de 
programação linear binária. 
 
Para a determinação exata deste problema, serão 
abordados 2 algoritmos: Djikstra e Floyd. 
 
1.3.1. Algoritmo de Dijkstra 
 
Seja ui a distância mais curta do nó de origem ao nó i, 
e defina-se dij (≥0) como o comprimento do arco (i,j). 
Então, o algoritmo define o rótulo para um nó 
imediatamente posterior, j, como: 
 
0d],i,du[]i,u[ ijijij 
 
 
Observação: o algoritmo de Djikstra determina o custo 
mínimo ou distância mínima entre uma origem e um 
destino. 
 
Etapas do Algoritmo 
 
1. Para cada vértice, usa-se a notação [c,j] X, 
chamada de rótulo. Onde c é o custo 
(acumulado) até o momento e j é o vértice 
precedente. Quanto ao X, este pode assumir a 
condição T (temporário) ou P (permanente) 
2. O vértice da origem começará por [0,-] P 
3. Analisar os vértices adjacentes e colocar 
rótulos temporários (T) alocando o custo ou 
distância acumulada nos mesmos 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
4. Para cada vértice, escolhe-se o menor custo 
ou distância. Para o rótulo de menor custo 
atribui-se o rótulo permanente (P) 
5. Caso todos os rótulos estejam como 
permanente (P), pare. Se não, escolha o de 
menor custo voltando ao passo anterior. 
Exemplos: 
 
São obtidas tiras de alumínio de 2 cm a partir de 
outras de 12 cm de espessura por meio de um 
processo de redução. A tabela descreve os custos de 
redução para cada 100 metros de alumínio. Determine 
a forma mais econômica de se obter tiras de 2 cm. 
Espessura Redução em cm 
2 4 6 
12 6,2 7,2 8,5 
10 6,8 7,4 9,2 
08 7,1 12,8 15,2 
06 8,2 14,6 
04 10,5 - 
 
 
12 cm 10 cm 8 cm 6 cm 4 cm 2 cm 
(0,-)P 
origem 
 
 [6,2;12] 
P 
[7,2;12] 
P 
[8,5;12] 
P 
∞ ∞ 
 [13,0;10] 
T 
[13,6;10] 
T 
[15,4;10] 
P 
∞ 
 [14,3;8] 
T 
[20,0;8] 
T 
[22,4;8] 
P 
 [16,7;6] 
T 
[23,1;6] 
T 
 [25,9;4] 
T 
Lendo de trás para frente, ou seja, do destino para a 
origem tem-se: 
 
12 cm  8cm  2 cm 
 
Resposta: A redução ideal deve ocorrer em duas 
etapas. A 1ª etapa ocorre de 12 para 8 centímetros (-
4) e 2ª etapa ocorre de 8 para 2 centímetros (-6). 
 
Uma empresa está planejando a substituição de sua 
frota de veículos para o período de 2006 – 2011. No 
início de cada ano toma-se a decisão de se manter a 
frota operando ou se ela deve ser substituída. Essa 
substituída pode ocorrer no máximo após três anos de 
compra da frota. A tabela mostra o custo de 
substituição da frota como função do ano em que ela 
foi adquirida e número de anos em operação. 
Determine o planejamento ótimo para a substituição 
da frota. 
Ano em que a 
frota foi 
adquirida 
Custo de substituição 
por anos de operação 
1 2 3 
2006 3800 4100 6800 
2007 4000 4800 7000 
2008 4200 5100 7200 
2009 4800 5700 - 
2010 5300 - - 
 
 
 
200
6 
2007 2008 2009 2010 2011 
(0,-
)P 
 
 [3800;200
6] 
P 
[4100;200
6] 
P 
[6800;2006
] 
P 
∞ ∞ 
 [7800;200
7] 
T 
[11600;200
7] 
T 
[10800;200
7] 
T 
∞ 
 [8300;2008
] 
T 
[9200;2008
] 
P 
[11300;200
8] 
P 
 [11600;200
9] 
T 
[12500;200
9] 
T 
 [14500;201
0] 
T 
Lendo de trás para a frente obtém-se que 
2006  2008  2011 
Resposta: A melhor estratégia de renovação da frota 
dos veículos adquiridos no ano de 2006 é trocar a 
frota no ano de 2008, tendo como horizonte de tempo 
o ano de 2011. 
 
1.3.2. Algoritmo de Floyd 
 
O algoritmo representa uma rede de n nós como uma 
matriz uma matriz quadrada com n linhas e n colunas. 
A entrada (i.j) da matriz dá a distância (ou custo), dij, 
do nó i ao nó j, que é finita se i estiver ligado 
diretamente a j, caso contrário, é infinita. 
 
Observação: o algoritmo de Floyd determina os 
custos ou distâncias mínimas entre todos os pares de 
vértices. 
 
A Operação Tripla de Floyd 
 
O conceito do algoritmo de Floyd é objetivo. Dados 3 
nós i, j e k, o caminho mais curto de ir i até j passando 
por k. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
 
 
Ou seja, busca situações onde: 
 
ijkjik ddd 
 
 
No caso, é ótimo substituir a rota direta de i  j pela 
rota indireta i  k  j. Essa operação tripla de troca é 
aplicada sistematicamente à rede. 
 
Etapas do Algoritmo 
 
0. Defina a matriz de distâncias D
0
 e a matriz de 
relações dos nós R
0
. Os elementos da 
diagonal são marcados com – para indicar 
que estão bloqueados. Determine k = 1. 









A)j,i(d
A)j,i(cd
ji0d
D
ij
ijij
ij
0 







contrário caso0r
djr
R
ij
0
ijij0
 
1. Defina a linha k e a coluna k como a linha pivô 
e coluna pivô (travar). Aplique a operação 
tripla a cada elemento dij em D
k-1
 para todo i e 
j. Se a condição for satisfeita, faça as 
seguintes mudanças: 
a. Crie D
k
 substituindo dij em D
k-1
 por dik 
+ dkj 
b. Crie R
k
 substituindo rij em R
k-1
 por k. 
Determine k = k+1. Se k = n+1, pare; 
caso contrário, repita a etapa k. 
Reduzindo o Trabalho... 
 
1. A diagonal não muda 
2. Na k-ésima iteração, não haverá mudança na 
linha pivô (linha k) e na coluna pivô (coluna k) 
3. Na k-ésima iteração, caso exista na linha pivô 
(linha k) algum elemento onde dkj = ∞ então a 
coluna j não irá variar nesta iteração 
4. Na k-ésima iteração, caso exista na coluna 
pivô (coluna k) algum elemento onde dik = ∞ 
então a linha i não irá variar nesta iteração 
Exemplos: 
 
Para a rede apresentada, encontre os caminhos mais 
curtos entre todos os conjuntos de 2 nós. As 
distâncias em milhas são dadas nos arcos. O arco 
(3,5) é direcional, de modo que nenhum tráfego é 
permitido do nó 5 para o nó 3. Todos os outros nós 
permitem tráfego no dois sentidos. 
 
Etapa 0: 
Obtendo a Matriz D
0 
 
54321
 






















4
465
15610
53
103
5
4
3
2
1
D0
 
Obtendo a Matriz R
0
 
 
54321
 






















4321
5321
5421
5431
5432
5
4
3
2
1
R 0
 
Etapa 1: 
Obtendo a Matriz D
1
 
k. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
54321
 






















4
465
1561310
5133
103
5
4
3
2
1
D1
 
Obtendo a Matriz R
1
 
 
54321
 






















4321
5321
5411
5411
5432
5
4
3
2
1
R1
 
Etapa 2: 
Obtendo a Matriz D
2
 
 
54321
 






















4
4658
1561310
5133
8103
5
4
3
2
1
D2
 
Obtendo a Matriz R
2 
 
54321
 






















4321
5322
5411
5411
5232
5
4
3
2
1
R 2
 
Etapa 3: 
Obtendo a Matriz D
3
 
 
54321
 





















4
4658
1561310
285133
258103
5
4
3
2
1
D2
 
Obtendo a Matriz R
3 
 
54321
 






















4321
5322
5411
3411
3232
5
4
3
2
1
R 2
 
Etapa 4: 
Obtendo a Matriz D
4
 
 
54321
 






















410912
4658
1061110
95113
128103
5
4
3
2
1
D2
 
Obtendo a Matriz R
4 
 
54321
 






















4444
5322
4441
4441
4232
5
4
3
2
1
R 2
 
Etapa 5: 
Não há melhorias a serem feitas, agora basta 
interpretar a matriz resultante na 4ª iteração (etapa 4). 
 
v 
v 
v v v 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
DESAFIO!
 
Etapa 0 
Obtendo a Matriz D
0
 
 
TEDCBAO
 






























71
5
41
34
72
452
T
E
D
C
B
A
O
D0
 
Obtendo a Matriz R
0 
 
TEDCBAO
 























7654321
7654321
7654321
7654321
7654321
7654321
7654321
T
E
D
C
B
A
O
R 0
 
 
1.4. O PROBLEMA DO FLUXO MÁXIMO 
 
Contextualizando ... 
 
Considere uma rede de tubulações que transporte 
petróleo cru de poços de petróleo e refinarias. 
Estações intermediárias de impulsores auxiliares e de 
bombeamento são instalados a distâncias adequadas 
para transportar o petróleo cru pela rede. Cada 
segmento de tubulação tem uma taxa de descarga 
máxima finita (ou capacidade) de fluxo de petróleo cru. 
Um seguimento de tubulação pode ser unidirecional 
ou bidirecional, dependendo de seu projeto. Como 
podemos determinar a capacidade máxima da rede 
entre poços e refinarias? 
 
 
 
Formulação Matemática 
 
Aj)i, (,ux
d,ok,xx
Fx
Fx
:a sujeito
FMax 
ijij
m
A)j,k(
kj
A)k,i(
ik
A)d,i(
id
A)j,o(
oj










 
 

 Capacidade do arco (i,j) = uij 
 Fluxo Máximo = F 
 Quantidade Transportada no Arco (i,j) = xij 
Observação: quantidade transportada não pode 
ultrapassar a capacidade. 
 
1.4.1. Algoritmo de Ford-Fulkerson Simplificado 
 
Etapas do Algoritmo 
 
Em cada arco coloque o rótulo (a, b) 
 a – fluxo disponível no arco 
 b – fluxo enviado pelo arco 
 
1. Encontre um caminho da origem ao destino 
que ainda possua um fluxo disponível 
2. Atualize os valores do par ordenado 
3. Caso não encontre um caminho com fluxo 
disponível, pare, caso contrário volte a etapa 
2. 
Exemplo: 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
1.4.2. Algoritmo de Ford-Fulkerson 
O Algoritmo de Fluxo Máximo é baseado em achar 
rotas de passagem com fluxo positivo entre os nós de 
origem e o sorvedouro. Cada rota compromete parte 
ou toda a capacidade de seus arcos ao fluxo de rede. 
Considere o arco (i,j) inicialmente com capacidade (Cij, 
Cji). À medida que porções dessas capacidades são 
comprometidas ao fluxo do arco, as capacidades 
residuais (ou capacidades restantes) do arco são 
atualizadas. Usamos a notação (cij, cji) para 
representar essas capacidades residuais. 
Para um nó j que recebe fluxo do nó i, anexamos um 
rótulo [aj, i], no qual aj é o fluxo do nó i ao nó j. 
 
Etapas do Algoritmo 
 
Deve-se considerar um fluxo residual nos dois 
sentidos. 
 
Constrói-se um caminho aumentado: caminho da 
origem para o destino com fluxo residual estritamente 
positivo. 
 
1. Encontre um caminho da origem ao destino 
que ainda possui fluxo residual positivo, caso 
não encontre, a solução é ótima 
2. Determine a capacidade residual máxima 
desse caminho, subtraia da capacidade 
residual de cada arco e adicione a capacidade 
residual na direção oposta. Retorne ao passo 
1. 
 
Exemplo: 
 
 
 
1.5. BIBLIOGRAFIA E REFERÊNCIAS 
 
[1] TAHA, Hamdy. Pesquisa Operacional. 8ª Edição. 
São Paulo: Pearson Prentice Hall, 2008. 
[2] HILLIER, Frederick S. & LIEBERMAN, Gerald J. 
Introduction to Operations Research. 7th Edition. 
McGraw Hill. 2001. 
[3] MEZA, Lidia Angulo. Teoria dos Grafos com 
Algoritmo Ótimo de Fluxo Máximo. Universidade 
Federal Fluminense. Disciplina: Pesquisa Operacional 
II. 32 slides. 2010. 
[4] LACHTERMACHER, Gerson. Pesquisa 
Operacional na Tomada de Decisões. Modelagem 
em Excel. Rio de Janeiro: Elsevier, 2007.

Outros materiais