Lista 1 POII

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia 1 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO – VEP 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
Lista de Exercícios Nº 1 – Teoria de Grafos 
 
1. A seguir encontra-se a tabela de idades dos alunos de uma turma. 
19 anos 21 anos 23 anos 25 anos 
Alberto 
Bernardo 
Carlos 
Davi 
Eduardo 
Fábio 
Gabriel 
Heitor 
Desenhe a representação gráfica dos seguintes grafos: 
a. G1 = (X1, U1), no qual X1 é o conjunto dos alunos e U1 = {(x,y) / x é mais jovem 
que y} 
b. G2 = (X2, U2), no qual X2 é o conjunto dos alunos e U2 = {(x,y) / x tem a mesma 
idade que y} 
c. Imagine que uma pessoa tem 3 calças e 4 blusas. Desenhe a representação do 
grafo G3 que mostre as combinações de roupas possíveis. 
 
2. Desenhe os grafos que representem as situações a seguir. 
 
(a) (b) 
 
(c) (d) 
 
3. Usando os grafos das questões 1 e 2, indique se são: orientados, conexos, bipartidos, 
árvores, e se contém ciclos. 
 Universidade Federal Fluminense 
Profª. Lídia 2 
 
4. O serviço de Parques Nacionais planeja fomentar o turismo em uma área inexplorada. 
Foram designados quatros acesso automobilísticos para a área. Estes lugares e as 
distâncias entre eles (em milhas) estão listados na tabela a seguir. A fim de infligir o 
mínimo de danos ao meio ambiente, o Serviço de Parques deseja minimizar a extensão 
das rodovias necessárias a propiciar o acesso desejado. Resolva o problema. 
 
 Entrada do 
Parque 
Cataratas 
Selvagens 
Rocha 
Majestosa 
Ponto de 
Ocaso 
O Prado 
Entrada do Parque 0 7,1 19,5 19,1 25,7 
Cataratas Selvagens 7,1 0 8,3 16,2 13,2 
Rocha Majestosa 19,5 8,3 0 18,1 5,2 
Ponto do Ocaso 19,1 16,2 18,1 0 17,2 
O Prado 25,7 13,2 5,2 17,2 0 
 
 
5. Quatro fábricas se dedicam à produção de quatro tipos de brinquedos. A tabela a seguir 
mostra os brinquedos que cada fábrica pode produzir. 
 
Fábrica Brinquedos 
1 1, 2, 3 
2 2, 3 
3 1, 4 
4 3, 4 
 
Todos os brinquedos precisam da mesma quantidade de mão de obra e o mesmo 
material por unidade. As capacidades diárias das quatro fábricas são 250, 180, 300 e 
100 brinquedos, respectivamente. As demandas diárias para os quatro brinquedos são 
200, 150, 350 e 100, respectivamente. Determine os programas de produção das 
fábricas que podem satisfazer melhor as demandas dos quatro brinquedos. 
 
 
6. Uma empresa de telefonia móvel dá serviço a seis áreas geográficas. As distâncias por 
satélite (em quilômetros) entre as seis áreas encontram-se na figura a seguir. A 
empresa precisa determinar as rotas de mensagem mais eficientes entre cada par de 
áreas da rede. 
 
 
 
 
7. Diga se as matrizes de distâncias e de rotas, a seguir, representam as distâncias 
mínimas e as rotas entre cada par de vértices. Caso afirmativo, determine as distâncias 
mínimas e rota entre os vértices 3 e 5, 4 e 2, e 2 e 4. Caso contrário, continue com o 
algoritmo até a última iteração. 
 
 Universidade Federal Fluminense 
Profª. Lídia 3 
 
 
 
 
8. A figura a seguir mostra dutos que ligam poços de gás natural no mar com um ponto de 
entrega perto da praia. O poço 1 encontra-se mais perto da praia e ele está equipado 
com capacidade suficiente para armazenar a produção dos oito poços. Determine a 
rede mínima de dutos que vinculem os poços com o ponto de entrega. 
 
 
 
 
 
9. Usando a figura anterior, considere agora que os poços podem ser divididos em dois 
grupos: um grupo de pressão elevada, poços 2, 3, 4 e 6, e outro grupo de pressão 
baixa, poços 5, 7, 8 e 9; e que, devido a diferença de pressão, não é possível fazer uma 
conexão. Determine a rede mínima de dutos que ligam esses poços com o ponto de 
entrega, se os dois grupos devem estar conectados com o ponto de entrega através do 
poço 1. 
 
 
 
10. Um alimento para galinhas deve ser transportado em caminhões de três depósitos a 
quatro granjas avícolas. Alguns dos depósitos não podem fazer envios diretamente a 
algumas granjas. As capacidades das outras rotas estão limitadas pelo número de 
caminhões disponíveis e o número de viagens que fazem diariamente. A tabela a seguir 
mostra as quantidades diárias da oferta nos depósitos e da demanda nas granjas (em 
milhares de libras). As quantidades nas células da tabela especificam as capacidades 
diárias das rotas associadas. Determine o programa que satisfaz a maior demanda. O 
programa proposto satisfaz toda a demanda nas granjas? 
 
 
Ponto de entrega 
 Universidade Federal Fluminense 
Profª. Lídia 4 
 Granja 
 1 2 3 4 
Silo 
1 30 5 0 40 20 
2 0 0 5 90 20 
3 100 40 30 40 200 
 200 10 60 20 
 
 
11. No problema das galinhas, suponha que está permitido os transbordos entre os 
depósitos 1 e 2 e os depósitos 2 e 3. Suponha também que o transbordo está permitido 
entre as granjas 1 e 2, 2 e 3, e 3 e 4. A capacidade máxima diária nas rotas de 
transbordo é de 50 (mil). Qual será o efeito do transbordo nas demandas não satisfeitas 
nas granjas? 
 
 
12. Seja a matriz de distâncias a seguir, determine a árvore geradora mínima. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13. Uma fábrica ganhou um contrato para produzir embalagens. O contrato é de 4 anos e 
não se espera que seja renovado. O processo de produção requer uma máquina 
especial que a fábrica ainda não tem. Pode-se comprar a máquina, fazer sua 
manutenção durante os 4 anos do contrato e depois vendê-la a um preço residual, ou 
substituí-la no final de cada ano por um modelo novo. Os novos modelos requerem 
menos manutenção do que os antigos. O custo líquido de operação estimado (preço de 
compra da máquina, adicionando ao custo de manutenção e subtraído ao valor da 
retoma) para se comprar uma máquina no início do ano i e dá-la como retoma no início 
do ano j é dado na tabela a seguir (valores expressos em unidades monetárias). 
Determine uma política de substituição que minimize o custo total de operação da 
máquina durante a vigência do contrato. 
 
 j 
i 1 2 3 4 5 
1 - 12 19 33 49 
2 - - 14 23 38 
3 - - - 16 26 
4 - - - - 13 
 
 
 
 
 
0 
 
0 
 0 
 0 
 
0 
 0 
 0 
 0 
 0 
 
5 
 Universidade Federal Fluminense 
Profª. Lídia 5 
14. A madeireira Wirehouse realizara uma tala de árvores em oito zonas da mesma área. 
Para isso deve desenvolver um sistema de caminhos de terra para ter acesso a 
qualquer zona desde qualquer outra. A distância (em milhas) entre cada par de zonas 
se encontra na tabela a seguir. Resolva o problema de tal forma a efetuar o mínimo 
dano à natureza. 
 
 1 2 3 4 5 6 7 8 
1 - 1,3 2,1 0,9 0,7 1,8 2,0 1,5 
2 - 0,9 1,8 1,2 2,6 2,3 1,1 
3 - 2,6 1,7 2,5 1,9 1,0 
4 - 0,7 1,6 1,5 0,9 
5 - 0,9 1,1 0,8 
6 - 0,6 1,0 
7 - 0,5 
8 -