AULA 001 - INTRODUÇÃO MODELOS OTIMIZAÇÃO DE REDES

Prévia do material em texto

PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
Fernando Tadeu Pongelupe Nogueira 
fernando.nogueira@prof.una.br 
PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
I – MODELOS DE OTIMIZAÇÃO DE REDES 
I - Introdução 
• O modelo de redes é utilizado em diversos 
ambientes: 
 
– Exemplos: 
• Redes de transporte; 
• Redes elétricas; 
• Redes de comunicações; 
• Etc... 
I - Introdução 
• As redes são utilizadas, também, em diversas 
áreas: 
 
– Exemplos: 
• Produção; 
• Distribuição; 
• Planejamento de projetos; 
• Administração de recursos; 
• Planejamento financeiro; 
• Etc... 
I - Introdução 
 
• Apesar das tendências em considerar o estudo 
de fluxo em rede, muitos outros problemas 
podem ser resolvidos através da teoria dos 
grafos. 
I - Introdução 
• Uma representação em rede fornece uma 
ferramenta conceitual e visual para descrever as 
relações entre os componentes de sistemas, que 
é utilizada praticamente em todos os campos de 
empreendimentos cientifico, social e econômico. 
 
• Muitos modelos de otimização de redes, na 
verdade, são tipos especiais de problemas de 
programação linear. 
I - Introdução 
• Neste capítulo, a ideia é apresentar 5 (cinco) 
tipos importantes de problemas de rede: 
– Problema do caminho mais curto; 
– Problema da árvore de expansão mínima; 
– Problema do fluxo máximo; 
– Problema do fluxo de custo mínimo; 
– Problema de determinar a forma mais econômica 
de se conduzir um projeto de modo que de possa 
ser cumprido no prazo (método CPM de relações 
tempo-custo). 
1.1. Exemplo do protótipo 
 
• Ver arquivo WORD 
(AULA_001_TXT_001.DOC). 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
Grafo: 
• É uma noção simples, abstrata e intuitiva, usada 
para representar a ideia de alguma espécie de 
relação entre “objetos”. 
 
• Graficamente, aparece representado por uma 
figura com nós ou vértices, significando os 
objetos, unidos por um traço denominado aresta 
ou arco configurando a relação imaginada. 
 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
• Representação Matemática: 
 
G=(V,A) 
V - conjunto de vértices ou nós. 
A - conjuntos de arestas ou arcos 
entre os vértices. 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
Grafo Direcionado (Dígrafo): 
• Um Grafo é dito direcionado ou Dígrafo quando o sentido 
das ligações entre os vértices é considerado. 
 
 
 
 
 
 
• Neste exemplo, 
• V={1,2,3,4,5,6} e A={(3,1),(2,3),(4,3),(3,5),(6,6)}. 
 
• {V}= 6 , {A}= 5. 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
Grafo Valorado (Rede): 
 
• Uma rede é um grafo cujos vértices e/ou arestas têm 
associado valores numéricos (custos, capacidades, 
distâncias, e/ou suprimentos e demandas). 
 
• Este número é, frequentemente, referido como o peso da 
ligação. 
 
• A rede pode ser direcionada ou não direcionada - depende 
da necessidade, ou não, da indicação do fluxo entre os nós. 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
Grafo Valorado (Rede): 
 
G=(V,A, c) 
V - conjunto de vértices ou nós. 
A - conjuntos de arestas ou arcos 
entre os vértices. 
c - peso associado aos vértices e/ou 
arcos. 
1.2.1. Motivação 
Pontes de Königsberg: 
• Marco inicial da Teoria dos Grafos. 
• A cidade de Königsberg, na Prússia (agora 
Kalingrado, na Rússia), foi fundada em 1254 
às margens do rio Pergel e tem 7 pontes que 
conectam suas 4 seções (A,B,C e D). 
• Problema: os habitantes queriam verificar se 
seria possível percorrer as quatro seções e 
voltar ao local de partida cruzando cada 
ponte exatamente uma vez. 
 
1.2.1. Motivação 
1.2.1. Motivação 
Pontes de Königsberg: 
•Resolvido em 1736 por 
Leonhard Euler. 
•Necessário um modelo 
para representar o 
problema. 
•Abstração de detalhes 
irrelevantes: 
 Área de cada ilha; 
 Formato de cada 
ilha; 
 Tipo da ponte, etc. 
• Euler generalizou o 
problema através de 
um modelo de grafos. 
• Para haver solução é 
necessário que cada 
região tenha um número 
par de pontes associadas. 
1.2.2. Aplicações 
Problema das 3 casas: 
•É possível conectar os 3 serviços em cada uma das casas 
sem haver cruzamento de tubulação? 
1.2.2. Aplicações 
• Problemas que podem ser modelados e resolvidos 
como grafos e/ou redes: 
 
 Projeto de uma rede de tubulações marítimas para ligar 
as bocas de poço de uma plataforma offshore de gás 
natural no golfo do México a um ponto de entrega na 
terra  Árvore Geradora Mínima 
 
 Determinação do caminho mais curto entre duas 
cidades em uma rede de rodovias existentes  
Problema de caminho mais curto 
1.2.2. Aplicações 
• Problemas que podem ser modelados e resolvidos como 
grafos e/ou redes: 
 
 Determinação de um esquema de fluxo de custo mínimo entre 
as bacias de petróleo e as refinarias por meio de uma rede de 
tubulações  Problema de fluxo de custo mínimo 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
Exemplos de Redes e suas Terminologias: 
 
• Redes ferroviárias; 
• Redes de telecomunicações; 
• Redes de estradas; 
• Redes elétricas; 
• Redes de esgotos; 
• Redes de transportes; 
• Redes de atividades → programação de atividades em 
grandes projetos. 
1.2. Conceitos Básicos em 
Teoria dos Grafos 
1.3. Terminologia das redes 
• É uma terminologia extensa, pois existem 
vários tipos de redes e de componentes. 
 
• Uma rede é formada por um conjunto de 
pontos e de traços que conectam certos pares 
de pontos. 
1.3. Terminologia das redes 
 
• Os pontos são chamados nós (ou vértices). 
 
– Conforme se pode verificar na figura do próximo 
slide, esta possui 7 (sete) nós designados por 7 
(sete) círculos (O, A, B, C, D, E, T). 
1.3. Terminologia das redes 
Figura 1: Sistema de pequenas estradas par o Seervada Park. 
1.3. Terminologia das redes 
• Os traços são chamados arcos (ou ligaçoes ou 
bordas ou ramificações). 
– Conforme se pode verificar na figura do slide 
anterior, esta possui 12 (doze) arcos 
correspondentes a 12 (doze) estradas no sistema 
viário do Parque. 
– Os traços são identificados nomeando-se os nós 
em cada extremidade. 
• Exemplo: AB é o arco entre os nós A e B. 
1.3. Terminologia das redes 
• Os arcos podem ser: 
 
– (a) Direcionados: quando o fluxo através de um 
arco é permitido apenas em uma direção. 
• Nó de partida: A; 
• Nó de chegada: B; 
• Notação: A  B ou simplesmente AB. 
1.3. Terminologia das redes 
• Os arcos podem ser: 
 
– (b) Não direcionados: quando o fluxo através de 
um arco é permitido em ambas as direções. 
• Geralmente são chamados de ligações; 
• O fluxo real será o fluxo líquido (a diferença entre os 
fluxos designados nas duas direções). 
– Exemplo: fluxo AB igual a 10 e fluxo BA igual a 4  então o 
fluxo real será 6, ou seja, será o fluxo líquido: 10 – 4 = 6. 
1.3. Terminologia das redes 
• Os redes podem ser: 
 
– (a) Direcionadas: aquelas que possuem apenas 
arcos direcionados; 
– (b) Não direcionadas: aquelas que só possuem 
arcos não direcionados; e 
– (c) “Mista”: aquelas que possuem os dois tipos de 
arcos, ou seja, possuem arcos direcionados e 
arcos não direcionados. 
1.3. Terminologia das redes 
• Um caminho entre dois nós é uma sequência 
de arcos distintos conectando esses nós. 
 
– Exemplo: 
 
• Na rede de estradas do Seervada Park (Figura 1), o 
caminho OT é a sequência de arcos OB-BD-DT 
(OBDT), ou vice-versa (lembre-se que os arcos 
nesta rede (Figura1) não são direcionados). 
1.3. Terminologia das redes 
• Um caminho pode ser: 
 
– (a) Direcionado: quando o caminho vai do nó “i” 
para o nó “j” e é uma sequência de arcos 
conectados cuja direção (se houver alguma) será 
no sentido do nó “j”, de modo que o fluxo do nó 
“i” para o nó “j” ao longo desse caminho 
desejável. 
1.3. Terminologia das redes 
• Um caminho pode ser: 
 
– (b) Não direcionado: quando o caminho vai do nó 
“i” para o nó “j” e é uma sequência de arcos 
conectados cuja direção (se houver alguma) pode 
ser tanto no sentido do nó “i” para o nó “j” 
quanto do nó “j” para o nó “i”. 
1.3. Terminologia das redes 
• Exemplo de caminho direcionado e não direcionado: 
Exs: 
- Caminho Direcionado: 
 AB-BC-CE 
- Caminho Não Direcionado: 
 BC-AC-AD 
1.3. Terminologia das redes 
• Observação: 
 
– Um caminho direcionado também satisfaz a 
definição de um caminho não direcionado, mas o 
inverso não é verdadeiro. 
1.3. Terminologia das redes 
• Exemplos: 
Figura 2: Exemplo de rede. 
1.3. Terminologia das redes 
• Exemplos: 
 
– A e B  Fábricas 
– D e E  Depósitos 
– C  Centro de Distribuição 
– Arcos  rotas marítmas. 
1.3. Terminologia das redes 
• Exemplos: 
 
– AB-BC-CE (ABCE)  caminho direcionado do 
nó “A” para o nó “E”  é um caminho viável; 
 
– BC-AC-AD (BCAD) ´ não é um caminho 
direcionado do nó “B” para o nó “D”  não é um 
caminho viável (AC não é um fluxo direcionado de “C” 
para “A”). 
• No entanto, BC-AC-AD é um caminho não direcionado do nó 
“B” para o nó “D”, pois a sequência acima conecta esses dois 
pontos. 
1.3. Terminologia das redes 
• Chama-se de ciclo o caminho que começa e 
termina no mesmo nó. 
 
– Numa rede direcionada, um ciclo será direcionado 
ou não direcionado, dependendo se o caminho 
em questão for direcionado ou não. 
 
• Ex: DE-ED é um ciclo direcionado. 
• Ex: AB-BC-AC é um ciclo não direcionado. 
1.3. Terminologia das redes 
Figura 3: Exemplo de rede. 
1.3. Terminologia das redes 
• Observação: 
 
– OB-BO não pode ser qualificado como ciclo, visto 
que OB e BO são dois nomes para o mesmo arco 
(um único arco). 
 
– ED-DE é um ciclo direcionado, pois DE e ED são 
arcos distintos (DE é um arco e ED é outro arco). 
1.3. Terminologia das redes 
• Dois nós são ditos conectados caso a rede 
contenha pelo menos um caminho não 
direcionado entre eles (OBS: o caminho não 
precisa ser direcionado mesmo se a rede for 
direcionada). 
 
• Uma rede conectada é uma rede no qual todo 
par de nós é conectado. 
1.3. Terminologia das redes 
Teoria dos Grafos e Aplicações 16 
2.10 - Conexidade 
Um Grafo G = (V, E) é conexo se para todo par de vértices existe pelo menos uma 
cadeia entre eles, por outro lado, se existir pelo menos um par de vértices que não é unido 
por nenhuma cadeia diz-se que o grafo é não-conexo, ou desconexo. Veja os exemplos da 
Figura 2.12. 
 
 
Figura 2.12 - Grafos Conexo ( G1 ) e Desconexo ( G2 ) 
Observe que o conceito de conexidade em grafos orientados não exige que haja um 
caminho ligando qualquer par de vértices, se isto acontecer diz-se que o grafo é 
fortemente conexo o que significa dizer que dados dois vértices “v” e “w” quaisquer, 
cada um pode ser atingido a partir do outro, ou seja partindo de “v” pode-se chegar a “w” 
ou vice-versa. A Figura 2.13 mostra um exemplo. 
 
 
 
Figura 2.13 - Grafo Dirigido Fortemente Conexo 
Como aplicação deste conceito podemos dizer que uma das características mais 
importante de uma rede de comunicação (telefonia, por exemplo) é sua conexidade. 
 
8 
5 
3 
4 
8 
Teoria dos Grafos e Aplicações 16 
2.10 - Conexidade 
Um Grafo G = (V, E) é conexo se para todo par de vértices existe pelo menos uma 
cadeia entre eles, por outro lado, se existir pelo menos um par de vértices que não é unido 
por nenhuma cadeia diz-se que o grafo é não-conexo, ou desconexo. Veja os exemplos da 
Figura 2.12. 
 
 
Figura 2.12 - Grafos Conexo ( G1 ) e Desconexo ( G2 ) 
Observe que o conceito de conexidade em grafos orientados não exige que haja um 
caminho ligando qualquer par de vértices, se isto acontecer diz-se que o grafo é 
fortemente conexo o que significa dizer que dados dois vértices “v” e “w” quaisquer, 
cada um pode ser atingido a partir do outro, ou seja partindo de “v” pode-se chegar a “w” 
ou vice-versa. A Figura 2.13 mostra um exemplo. 
 
 
 
Figura 2.13 - Grafo Dirigido Fortemente Conexo 
Como aplicação deste conceito podemos dizer que uma das características mais 
importante de uma rede de comunicação (telefonia, por exemplo) é sua conexidade. 
 
8 
7 
5 
3 
Figura 4: Rede conectada. Figura 5: Rede não conectada. 
• Exemplo de rede conectada e não conectada: 
1.3. Terminologia das redes 
• ÁRVORE 
 
– Árvore é uma rede conectada sem ciclos não 
direcionados formado por um subconjunto de todos 
os nós. 
 
– Árvore de expansão (geradora) é uma rede conectada 
de todos os “n” nós sem ciclos direcionados. 
 
• Cada árvore de expansão tem exatamente “n-1” arcos. 
1.3. Terminologia das redes 
• ÁRVORE – Exemplo de crescimento de uma 
árvore através de um arco: 
(a) Os nós 
sem arcos 
(b) uma árvore 
com 1 arco 
(c) uma árvore 
com 2 arcos 
(d) uma árvore 
com 3 arcos 
(e) uma árvore 
de expansão 
1.3. Terminologia das redes 
 
• Capacidade do arco é a quantidade máxima 
de fluxo (possivelmente finita) que pode ser 
transportada em um arco direcionado. 
1.3. Terminologia das redes 
• Para nós, é feita uma distinção entre aqueles 
que são geradores de fluxo líquido, que 
absorvem fluxo ou nenhum dos dois: 
 
– Um nó de suprimento (ou nó de origem ou 
origem) tem a propriedade de que o fluxo que sai 
do nó excede o fluxo que entra no nó. 
1.3. Terminologia das redes 
• Para nós, é feita uma distinção entre aqueles 
que são geradores de fluxo líquido, que 
absorvem fluxo ou nenhum dos dois: 
 
– Um nó de demanda (ou nó escoador ou 
escoadouro) tem a propriedade de que o fluxo 
que entra do nó excede o fluxo que sai no nó. 
1.3. Terminologia das redes 
• Para nós, é feita uma distinção entre aqueles 
que são geradores de fluxo líquido, que 
absorvem fluxo ou nenhum dos dois: 
 
– Um nó de transbordo (ou nó intermediário) 
satisfaz a conversão do fluxo, de modo que o fluxo 
que entra seja igual ao fluxo que sai. 
1.3. Terminologia das redes 
• Representação de Grafos: Matriz de 
Incidência 
 
• Seja um grafo G=(V,A) em que |V|=n e |A|=m. Uma 
matriz de incidência An x m nó-arco é representada por: 
 
– Uma linha para cada nó; 
 
– Uma coluna para cada arco. 
1.3. Terminologia das redes 
• Representação de Grafos: Matriz de 
Incidência 
– Cada elemento (i,j) assume os seguintes valores: 






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
1.3. Terminologia das redes 
• Exercício: Monte o grafo a partir da matriz de 
incidência abaixo: 
1.3. Terminologia das redes 
• Solução: 
a1 
a2 a3 
a4 
a5 
a6 
a7 
a8 
a9 a10 
a11 
Agradecimento 
 
 
• Agradeço à Profa. Alaine Cardoso Silva (Msc) 
pelas orientações e materiais que serviram de 
base para elaboração deste power point. 
BibliografiaHILLIER, Frederick S. e LIEBERMAN, Gerald J. 
Introdução à Pesquisa Operacional. 9ª 
edição. Porto Alegre: AMGH Editora Ltda 
(McGraw Hill), 2013. Capitulo 9 – pg. 341-
403.