Gestão de projetos e Caixeiro viajante

Prévia do material em texto

- Investigação Operacional II
Trabalho
Regras para elaboração e entrega do trabalho
1. O Trabalho é individual e vale cinco valores.
2. Deve haver uma página de capa com a identificação completa do aluno(a)-
nome completo, número, curso e deve incluir
• Enunciado
• Procedimentos utilizados e método.
• Resultados
Data de entrega: 16 de Agosto de 2020,
1. Uma companhia está pronta para começar a desenvolver um projeto. O prazo para entregue do projeto
é de 100 semanas. O projeto envolve 10 atividades com as seguintes relações de precedências e previsões
de duração (em semanas)
Atividades Precedências
Duração
Otimista Provável Pessimista
A – 28 32 36
B – 22 28 32
C A 26 36 46
D B 14 16 18
E B 32 32 32
F B 40 52 74
G D 12 16 24
H E,G 16 20 26
I G,E 26 34 42
J C,F 12 16 30
(a) Encontre a estimativa de média e variância da duração de cada atividade.
(b) Represente a sua rede AOA do Projeto.
(c) Encontre o caminho Cŕıtico Médio.
(d) Encontre a probabilidade aproximada de que o projeto irá terminar em até 100 semanas.
(e) d. Calcule o tempo inicial mais cedo, tempo inicial mais tarde, tempo final mais cedo e tempo final
mais tarde considerando a estimativa de média da duração de cada atividade.
(f) Temos caminhos sub-cŕıtico? Justifique.
2. Considere o seguinte problema do caixeiro viajante
A B C D E
A - 26 22 28 26
B 20 - 28 30 30
C 28 30 - 38 26
D 24 28 20 - 18
E 18 22 22 22 -
(a) Determine um ciclo de Hamilton, usando a heuŕıstica:
• Do vizinho mais próximo.
• Da inserção com menor encargo.
• Da inserção com maior afastamento.
• De Clarke e Wright.
(b) Parte da solução do vizinho mais próximo, aplica o algoritmo de melhoramento 2-otp, para melhorar
a tua solução.
(c) Resolve o problema aplicando o Algoritmo de Little.
Page 2