AATD#10 Otimizacao em Redes Arvore Geradora Minima Algoritmo

Prévia do material em texto

11/06/2015
1
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
yyyy
AVALIAÇÃO E APOIO À 
TOMADA DE DECISÃO
Prof. Ely Sena, MSc.
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
ÁRVORE GERADORA MÍNIMA
• O algoritmo da árvore geradora mínima trata 
de conectar os nós de uma rede, direta ou 
indiretamente, usando o comprimento total 
mais curso de ramos conectores.
11/06/2015
2
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo
11/06/2015
3
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co}
NC = { E1, E2, E3, E4, E5, }
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co, E4}
NC = { E1, E2, E3, E5, }
11/06/2015
4
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co, E4 ,E3}
NC = { E1, E2, E5, }
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co, E4 ,E3 ,E5}
NC = { E1, E2}
11/06/2015
5
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co, E4 ,E3 ,E5 ,E2}
NC = { E1}
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo C = {Co, E4 ,E3 ,E5 ,E2 ,E1}
NC = { ∅ }
11/06/2015
6
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exemplo
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exercício
• A Net está em vias de fornecer serviços de TV a cabo a cinco 
novas áreas onde estão em desenvolvimento projetos 
residenciais. 
• A figura abaixo mostra as possíveis conexões de TV entre as 
cinco áreas. As extensões (em milhas) dos cabos são mostradas 
em cada arco. Determine a rede mais econômica.
11/06/2015
7
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Resposta
• A extensão mínima de cabos resultantes necessárias para 
oferecer o serviço por cabo desejado são:
1-2, 2-4, 2-5, 3-4, 4-6.
1+3+4+3+5 = 16 milhas.
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
Exercícios
• Determine a árvore geradora mínina 
da rede do exemplo anterior sob cada 
uma das seguintes condições 
específicas.
a) Os nós 5 e 6 são conectados por um cabo de 
2 milhas; 14
b) Os nós 2 e 5 não podem ser conectados; 21
c) Os nós 2 e 6 são conectados por um cabo de 
4 milhas; 16
d) O cabo entre os nós 1 e 2 tem 8 milhas de 
comprimento; 20
e) Os nós 3 e 5 são conectados por um cabo de 
4 milhas; 15
f) O nó 2 não pode ser conectado diretamente 
aos nós 3 e 5; 21
11/06/2015
8
FACULDADE DE TECNOLOGIA ENGENHARIA DE PRODUÇÃO
REFERÊNCIAS
CUKIERMAN, Z.S. O Modelo PET/CPM Aplicado a Projetos. Rio de Janeiro: 
Qualitymark Editora Ltda., 1993.
HIRSCHFELD, H. Planejamento com pert-cpm e análise do desempenho. São 
Paulo: Atlas, 1985.
KERZNER, Harold, Project Management: A Systerns Aplroach to Planning, 
Scheduling, and Controlling, 7th edition, ISBN: 0471393428, John Wiley & Sons, 
Inc., 2001.
MEREDITH, J.; MANTEL Jr. Project Management: A Managerial Approach. 3rd 
ed. New York: John Wiley & Sons, Inc., 1995.
MODER, J.J.; PHILIPS, C.R. Project Management with CPM and PERT. New
York: Van Nostrand Reinhold Company, 1970.
PRADO, D. Administração de Projetos com PERT/CPM. Rio de Janeiro: Livros 
Técnicos e Científicos Editora S.A., 1984.
PROJECT MANAGEMENT INSTITUTE. A guide to the project management 
body of Knowlwdge: PMBOK GUIDE. Pensylvania USA: PMI Inc., 2000.
VALERIANO, D.I. Gerenciamento estratégico e administração por projetos: 
pesquisa, desenvolvimento e engenharia. São Paulo: Makron Books, 2001.