AULA 003 - O PROBLEMA DA ARVORE DE EXPANSÃO MINIMA

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 
• Á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. 
 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
• Á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 
• O Seervada Park foi reservado recentemente para 
visitação e excursões limitadas. Não se permite a 
entrada de carros no parque, porém há um 
sistema de estradinhas onde podem trafegar 
pequenos carros elétricos e jipes dirigidos pelos 
guardas florestais (e outras instalações limitadas). 
O Problema da Árvore de Expansão 
Mínima 
• As linhas telefônicas do parque têm de ser instaladas sob as vias 
para estabelecer comunicação telefônica entre os postos (inclusive 
entrada do parque). Pelo fato da instalação ser cara e também 
prejudicial ao meio ambiente, as linhas serão instaladas somente 
debaixo de um numero de estradas suficientes para fornecer 
alguma conexão entre cada par de postos. A questão é, onde as 
linhas devem ser colocadas para que atenda a um numero total 
minimo de milhas de linha instalada??? 
O Problema da Árvore de Expansão 
Mínima 
Algoritmo para o problema da árvore de expansão 
mínima 
 
1. Selecione qualquer nó arbitrariamente e depois o 
conecte ao nó destino mais próximo. 
2. Identifique o nó sem conexão que esteja mais 
próximo a um nó conectado e, em seguida, 
conecte esses dois nós. Repita esta etapa até que 
todos eles tenham sido conectados. 
3. Em caso de empate permite-se fazer uma escolha 
arbitrária. 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
O Problema da Árvore de Expansão 
Mínima 
• Exercício: 
 
– Imagine que a rede a seguir, é um Estado com 
várias cidades e que a Companhia de Gás do 
Estado vai implantar uma rede de distribuição de 
Gás nestas Cidades. A Companhia de Gás busca 
minimizar o custo de implantação e, para tanto, 
decidiu que a resolução desta questão está em 
buscar a árvore de expansão mínima. 
O Problema da Árvore de Expansão 
Mínima 
• Exercício: 
 
– Considerando que os números ao lado das 
ligações na rede são as distâncias (em 
quilômetros) e que o custo é de R$ 30.000,00 por 
quilômetro instalado, ache a árvore de expansão 
mínima e calcule o custo para implantação deste 
gasoduto entre as cidades no referido Estado. 
 
– Veja a rede no próximo slide. 
O Problema da Árvore de Expansão 
Mínima 
Agradecimento 
 
 
• Agradeço à Profa. Alaine Cardoso Silva (Msc) 
pelas orientações e materiais que serviram de 
base para elaboração deste power point. 
Bibliografia 
 
 
HILLIER, 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.