lista de exercIcios 1

Prévia do material em texto

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
LISTA DE EXERCÍCIOS 1 – TEORIA DOS GRAFOS E OTIMIZAÇÃO EM REDES 
 
QUESTÕES PARA DISCUSSÃO 
 
 
Q1 Defina matematicamente um grafo. 
 
Q2 Quais são os problemas possíveis, no que se 
refere aos objetivos (maximização ou minimização), 
quando se otimiza uma rede? 
 
Q3 Como é o problema do Caixeiro Viajante? Como 
este pode ser aplicado em problemas atuais? 
 
Q4 Como é o problema do Carteiro Chinês? Como 
este pode ser aplicado em problemas atuais? 
 
Q5 Como pode ser obtida uma Árvore Geradora 
Mínima? Quais aplicações esta pode ter? Cite 
exemplos. 
 
Q6 Quais as diferenças entre o algoritmo de Prim e o 
algoritmo de Kruskal? 
 
Q7 Quando se deve obter um caminho mínimo? Quais 
variáveis podem ser analisadas em problemas desta 
característica? 
 
Q8 Explique os passos do algoritmo de Dijkstra. 
 
Q9 Explique os passos do algoritmo de Floyd. 
 
Q10 Quais são as diferenças entre os objetivos nos 
algoritmos de Dijkstra e Floyd? 
 
Q11 Em quais tipos de problemas deve-se analisar o 
Fluxo Máximo de uma rede? Cite exemplos. 
 
Q12 Explique os passos do Algoritmo de Ford-
Fulkerson. 
 
Q13 Qual a função do Algoritmo PERT/CPM? 
 
Q14 Quais são as informações obtidas por meio do 
algoritmo PERT e do algoritmo CPM, separadamente? 
 
Q15 Explique os passos do Algoritmo PERT/CPM.
 
 
EXERCÍCIOS DE FIXAÇÃO 
 
E1 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. 
 
E2 Desenhe os grafos que representem as situações 
a seguir. 
a. Planta Baixa 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
b. Labirinto 
 
 
c. Pontes de Acesso em uma Ilha 
 
 
E3 Para os exercícios E1 e E2, classifique os grafos 
em orientados e não-orientados. 
 
E4 Considere o seguinte grafo orientado. 
 
a. Encontre um caminho direto entre o nó A e o 
nó F, e em seguida, encontre três outros caminhos 
entre os nós A e F, desconsiderando a orientação dos 
arcos. 
b. Encontre três ciclos orientados, e em seguida, 
identifique um ciclo não-orientado que inclua todos os 
nós 
c. Identifique um conjunto de arcos (arestas) que 
formem uma árvore 
 
E4 Obtenha a matriz de adjacências para os grafos a 
seguir: 
a. 
 
b. 
 
c. 
 
d. 
 
 
E5 Para as redes do exercício E4, calcule utilizando o 
Algoritmo de Dijkstra, o caminho mais curto entre os 
vértices mais extremos (esquerda e direita). 
 
E6 Para as mesmas redes do exercício E4, calcule o 
caminho mínimo entre todos os vértices utilizando o 
Algoritmo de Floyd. 
 
E7 Continuando nas redes do E4, obtenha utilizando o 
algoritmo PERT/CPM: 
a. A duração total de cada projeto 
b. O caminho crítico 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
c. As atividades que apresentam folga 
 
E8 Seja a matriz de distâncias a seguir, determine a 
árvore geradora mínima. 
 
 
PROBLEMAS E APLICAÇÕES 
 
P1 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 de 
Ocaso 
19,1 16,2 18,1 0 17,2 
O Prado 
 
25,7 13,2 5,2 17,2 0 
 
P2 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. 
 
 
P3 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. 
 
P4 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. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
 
P5 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 1,3 - 0,9 1,8 1,2 2,6 2,3 1,1 
3 2,1 0,9 - 2,6 1,7 2,5 1,9 1,0 
4 0,9 1,8 2,6 - 0,7 1,6 1,5 0,9 
5 0,7 1,2 1,7 0,7 - 0,9 1,1 0,8 
6 1,8 2,6 2,5 1,6 0,9 - 0,6 1,0 
7 2,0 2,3 1,9 1,5 1,1 0,6 - 0,5 
8 1,5 1,1 1,0 0,9 0,8 1,0 0,5 - 
 
P6 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. 
 
 1 2 3 4 5 
1 - 12 19 33 49 
2 - - 14 23 38 
3 - - - 16 26 
4 - - - - 13 
 
Onde i é linha e j coluna. 
 
P7 No problema anterior, formule um problema de 
programação linear que otimize a política de 
substituição desejada. 
 
P8 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. 
 
54321
 
















01432
40543
23054
32105
12210
5
4
3
2
1
D5
 
 
54321
 

















54111
14111
55355
34324
55221
5
4
3
2
1
R 5
 
 
P9 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. 
 
P10 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 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
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? 
Granja 
S
il
o
 
 1 2 3 4 
1 30 5 0 40 20 
2 0 0 5 90 20 
3 100 40 60 40 200 
 200 10 60 20 
 
P11 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? 
 
P12 Determinar o fluxo máximo F da fonte s ao 
destino t na rede a seguir, onde os números ao lado 
dos arcos representam suas capacidades. 
 
 
P13 Uma companhia possui três campos de 
petróleo, duas refinarias e dois centros de 
distribuição. Uma greve de empresas de 
transporte tem reduzido a capacidade da empresa 
de enviar petróleo para suas refinarias e para 
enviar seus produtos derivados. As capacidades 
atuais de distribuição se encontram nas tabelas a 
seguir (em milhares de barris de petróleo e 
refinados). A empresa deseja determinar quantas 
unidades enviar de cada campo de petróleo a 
cada refinaria e de cada refinaria para cada centro 
de distribuição de tal forma de maximize o número 
total de unidades que chegam aos centros de 
distribuição. 
 Refinaria 
Campo R1 R2 
C1 6 7 
C2 5 4 
C3 7 3 
 
 Centro de 
Distribuição 
Refinaria D1 D2 
R1 15 8 
R2 6 6 
 
P14 Para um projeto de fábrica, foi feita uma relação 
com as atividades, tempo de duração e suas 
respectivas dependências: 
Atividades Duração 
(semanas) 
Antecessoras 
Imediatas 
A Estudo inicial do projeto 
do produto 
12 - 
B Estudo preliminar de 
tecnologia de processo 
10 - 
C Pesquisa de 
capacitação dos 
fornecedores 
8 - 
D Projeto de modificação 
do layout 
14 B 
E Redesenho preliminar 
de layout 
6 C 
F Redesenho preliminar 
do produto 
18 A, B 
G Projeto de máquinas 
especiais 
11 D, E 
H Integração dos 
fornecedores 
21 E 
I Projeto final de produto, 
processo e layout 
7 F, G 
 
De acordo com o quadro apresentado e fazendo uso 
de PERT/CPM, obtenha: 
a. A rede associada do projeto 
b. A duração do projeto 
c. O caminho crítico (atividades gargalo) 
 
P15 Para um processo de publicação de um livro, foi 
feita uma relação com as atividades, tempo de 
duração e suas respectivas dependências: 
Atividades Duração 
(semanas) 
Antecessoras 
Imediatas 
A Revisão do 
manuscrito pela 
editora 
3 - 
B Preparação de 
páginas de amostra 
2 - 
C Projeto gráfico da 
capa do livro 
4 - 
D Preparação da arte-
final 
3 - 
E Aprovação do autor 
para o manuscrito 
editado e para as 
páginas amostra 
2 A, B 
F Diagramação do livro 4 E 
G Revisão das provas 
diagramadas pelo 
autor 
2 F 
H Revisão da arte-final 
pelo autor 
1 D 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
I Produção dos clichês 2 G, H 
J Produção e 
encadernação do 
livro 
4 C, I 
 
De acordo com o quadro apresentado e fazendo uso 
de PERT/CPM, obtenha: 
a. A rede associada do projeto 
b. A duração do projeto 
c. O caminho crítico (atividades gargalo) 
 
 
 
DESAFIOS 
 
D1 Apresente o modelo matemático (Programação Linear) e aplique a um exemplo, para os problemas: 
Observação: Para pesquisar. 
a. Caixeiro Viajante 
b. Carteiro Chinês 
c. Caminho Mínimo 
d. Fluxo Máximo 
 
D2 A rede representa cidades e as rodovias entre elas. Utilizando os Algoritmos de Dijkstra, Floyd e Kruskal 
obtenha: 
 
 
 
a. O menor caminho entre os nós 1 e 11 
b. O caminho mínimo entre qualquer par de vértices 
c. A árvore geradora mínima 
 
D3 A LCL Bicicletas Ltda. é uma empresa fabricante de bicicletas que possui três fábricas localizadas no Rio de 
Janeiro, em São Paulo e em Belo Horizonte. A Produção da empresa deve ser entregue em Recife, Salvador e 
Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos 
centros consumidores ilustrados na tabela, determine quanto deve ser produzido e entregue por fábrica em cada 
centro consumidor, de forma a minimizar os custos de transporte. 
Fábrica/Centro 
Consumidor 
Recife Salvador Manaus Capacidade 
Rio de Janeiro 25 20 30 2000 
São Paulo 30 25 25 3000 
Belo Horizonte 20 15 23 1500 
Demanda 2000 2000 1000 
 
D4 As atividades necessárias para a construção de uma nova casa estão descritas na tabela a seguir: 
Atividade Predecessoras Duração 
(dias) 
A: Limpar o local _ 1 
B: Trazer utilidades até o local _ 2 
C: Escavar A 1 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
D: Verter Fundação C 2 
E: Encanamento Externo B,C 6 
F: Arcabouço da casa em madeira D 10 
G: Fiação elétrica F 3 
H: Assentar assoalho G 1 
I: Assentar telhado F 1 
J: Encanamento interno E,H 5 
K: Paredes externas I 2 
L: Revestimento isolante externo F,J 2 
M: Instalar janelas e portas externas F 2 
N: Alvenaria L,M 4 
O: Isolamento térmico de paredes e tetos G,J 2 
P: Revestir paredes e tetos O 2 
Q: Isolamento térmico do telhado I,P 1 
R: Acabamento interno P 7 
S: Acabamento externo I,N 7 
T: Paisagismo S 3 
 
Com estes dados responder às seguintes perguntas: 
a. Construa o cronograma do projeto (gráfico de Gantt). 
b. Construa a rede associada para o projeto. 
c. Determine o prazo do projeto. 
d. Determine o caminho crítico do projeto. 
e. Determine a taxa de ocupação e as atividades com folga em cada gargalo da rede. 
 
D5 Utilizando dos softwares Google Maps e TORA System, faça: 
1. Pesquise 10 locais que tenham interesses em comum e relações entre si, como por exemplo: 
i. Universidades/Centros Universitários em uma determinada região 
ii. Empresas/Indústrias de um mesmo seguimento 
iii. Fornecedores de uma determinada empresa/indústria 
iv. Pontos de entrega de mercadorias(Centros de Distribuição) 
v. Outros 
2. Utilizando-se do Google Maps e outros meios de pesquisa, obtenha a Matriz de Adjacências entre cada uma 
das 10 localizações de acordo com: 
i. Distância percorrida 
ii. Tempo 
iii. Custo 
3. Insira a matriz no Software Tora e aplique o Algoritmo de Floyd, a fim de se obter o menor caminho (rotas) 
entre cada uma das localizações. 
4. Escolha uma localização ótima para um centro de operações logísticas e elabore três rotas que otimizem o 
sistema logístico.