ATIVIDADE 2 PESQUISA OPERACIONAL II trabalho entregue

Prévia do material em texto

Exercício PO II 2020.1: 
PO II 
Profa Ana Lúcia / Turma: CCE1014 
Aluno: Anderson Luiz de Oliveira Rios / Matrícula: 
201708043845 
ATIVIDADE 2 - PESQUISA OPERACIONAL II 
Problema 1. Use o algoritmo de PRIM. 
Em transporte intermodal. caminhões-reboque carregados são despachados entre 
terminais ferroviários sobre vagões-plataformas especiais. A Figura 6.8 mostra a localização dos 
principais terminais ferroviários nos Estados Unidos e as ferrovias existentes. O objetivo é decidir 
quais ferrovias devem ser “revitalizadas ' para enfrentar o tráfego intermodal. Em particular o 
terminal de Los Angeles (LA) deve ser conectado diretamente ao de Chicago (CH) para dar conta 
do esperado tráfego pesado. Fora estes todos os terminai s restantes podem 
ser conectados direta ou indiretamente de modo que o comprimento total (em milhas) das 
ferrovias selecionadas seja minimizado. Determine os trechos das ferrovias que devem 
ser incluídos no programa de revitalização. 
 
figura 6.8 
 
 
 
 
 
 
 
 
 
 
 
 
 
SE 
DE 
LA 
1000 
2000 
800 
900 
DA 
CH 
NY 
DC 
1100 
200 
LA;CH/CH;BY/NY;DC/CH;DA/SE;LA/DE;CH 
Total AGM: 2000+800+200+900+1100+1000= 6000 
Problema 2. Use o algoritmo de PRIM. 
A Figura 6.9 apresenta as extensões das conexões viáveis para ligar nove bocas de poços 
localizadas em plataformas marítimas offshore de gás natural com um ponto de entrega em 
terra. Como a boca de poço 1 é a mais próxima do litoral, está equipada com capacidades de 
bombeamento e armazenagem suficientes para bombear a produção dos oito poços restantes 
até o ponto de entrega. Determine a rede mínima de tubulações para ligar as bocas de poço ao 
ponto de entrega. 
figura 6.9 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2 
6 
5 
1 
3 
5 
8 
4 
9 
4 
6 
7 
(1;5);(5;6);(1;2);(5;7);(2;3);(5;9);(9;8);(6;4) 
Total AGM: 4+3+5+5+5+16+6+7= 41 
6 
7 
3 5 
5 
 Ponto de Entrega 
Problema 3. Use o algoritmo de PRIM. 
Na Figura 6.9 do Problema2, suponha que as bocas de poço possam ser divididas em dois grupos 
dependendo da pressão do gás: um grupo de alta pressão, que inclui os poços 2,3,4 e 6, e um 
grupo de baixa pressão, não é possível conectar as bocas de poço de um grupo com as do outro. 
Ao mesmo tempo, os dois grupos devem ser conectados ao ponto de entrega passando pela 
boca de poço1. Determine a rede mínima de tubulações para esta situação. 
 
 
 
 
 
 
 
 
 
 
Problema 4. Use o algoritmo de Kruskal. 
A empresa de telefonia celular Tell-All atende seis áreas geográficas. As distâncias de de 
satélite (em milhas) entre as seis áreas são dadas na figura 6.23. A tell-All precisa determinar 
as rotas de mensagens mais eficientes que devem ser estabelecidas entre cada duas áreas da 
rede. 
 
figura 6.23 
 
 
 
 
 
 
 
 
 
 Alta Pressão 
2 1 
5 
6 
3 
(1;2);(2;3);(3;4);(4;6) 
Total AGM: 5+15+6+7= 33 
15 
4 
7 
1 
9 
4 
6 
5 
8 
 Baixa Pressão 
 (1;5); (5;7);(5;9);(9;8) 
Total AGM: 4+5+5+6= 20 
5 
5 
7 
DE 
NY 
CH 
DA 
DC 
{{1},{2},{3},{4},{5},{6}} 
(4,6) 100; (1,3) 200; (2,4) 200; (2,3) 300; (4,5) 300; (2,6) 400; (5,6) 500; (3,5) 600; (1,2) 700; (3,4) 700. 
Total AGM: 100+200+200+300+300= 6000 
100 
300 
4 
6 
5 
1 
200 
3 
2 
300 
200 
6