Avaliação de Engenharia de Produção

Prévia do material em texto

P
á g
in
á1
 
 
Centro Federal de Educação Tecnológica Celso Suckow da Fonseca 
Curso Superior de Engenharia de Produção 
 
EAD 16030 - PESQUISA OPERACIONAL II 
 
Prof. Coordenador(a): Ormeu Coelho Data: 
Tutoria a Distância: Breno Assis Polo: 
Aluno (a): Período: 2024/01 Mat.: 
 
AVALIAÇÃO PRESENCIAL 2 
INSTRUÇÕES GERAIS: 
- A memória de cálculo de todas as questões deve ser apresentada. 
- Não é permitida a consulta a qualquer material durante a prova. 
- O uso de calculadora está permitido. 
 
Questão 1 (3pts) Em uma certa região de uma grande cidade há uma estação do corpo de bombeiros a partir da qual 
sete locais devem ser rapidamente atendidos. Estes locais caracterizam, juntamente à base do corpo de bombeiros, os 
vértices de uma rede, sendo a base numerada com o índice 1 e os locais a serem atendidos com os índices 2 a 8. As 
ligações nesta rede representam as ruas que conectam os locais, sendo que algumas possuem mão dupla e outras não. 
Além disso, nas ruas de mão dupla, o tráfego nos sentidos contrários não ocorre na mesma velocidade. A tabela abaixo 
apresenta as ligações possíveis e os tempos de viagem em cada uma delas. 
 
Ilustre a rede correspondente aos dados apresentados e calcule o caminho mínimo entre a base e cada um dos locais. 
Questão 2 (4pts) Como parte de um desvio temporário, planejado para lidar com uma dada contingência, o tráfego 
em uma rodovia deve ser roteado através uma cidade. A rodovia suporta até 2.000 carros por hora nos horários de 
pico. Um conjunto de rotas através da cidade foi então proposto. As ruas da malha rodoviária da cidade e suas 
correspondentes capacidades (em centenas de carros por hora) são dadas na tabela abaixo, onde 𝐸 é o ponto onde 
os carros entram na cidade, 𝐽1, 𝐽2, … , 𝐽5 são os pontos de interseção da malha, e 𝐿 é o ponto onde os carros deixam 
a cidade. A maior parte das vias são de mão-única. É possível acomodar 2.000 carros por hora através desta malha? 
 
 
 
 
P
á g
in
á2
 
 
OBS: Antes de resolver o problema, ilustre a rede correspondente. 
Questão 3 (3pts) Uma oficina de reparos recebe pedidos, em média, a cada 5 dias, com uma distribuição exponencial 
para o tempo entre pedidos. Os tempos de reparo também seguem uma distribuição exponencial com média de quatro 
dias. 
(a) Qual a probabilidade de a oficina ficar sem serviço? 
(b) Se a oficina cobra R$50 por reparo, qual é sua renda mensal média (assuma um mês com 22 dias 
trabalhados)? 
(c) Qual o tempo médio que uma peça permanece na oficina até estar pronta para entrega? 
(d) Qual o número médio de peças aguardando reparo? 
 
RESOLUÇÃO: 
Questão 1) 
 
REDE 
 
 
OBS: A disposição dos vértices não é relevante nesta representação, mas sim as relações expressas por suas conexões 
por meio dos arcos. 
1 
6 
2 
8 5 
2 
5 
2 
9 
10 
3 
7 
10 
1 7 
4 
4 
3 
7 10 
9 
7 
7 
 
 
 
P
á g
in
á3
 
SOLUÇÃO PELO ALGORITMO DE DIJKSTRA 
Memória de cálculo em tabela única: 
 1 2 3 4 5 6 7 8 
k=0 0 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 
k=1 - 5;1 +∞ 2;1 +∞ +∞ +∞ +∞ 
k=2 - 4;4 +∞ - +∞ 5;4 +∞ +∞ 
k=3 - - 13;2 - +∞ 11;2 14;2 +∞ 
k=4 - - 13;2 - +∞ - 7;6 14;6 
k=5 - - 13;2 - 14;7 - - 13;7 
k=6 - - - - 23;3 - - 13;7 
k=7 - - - - 14,8 - - - 
k=8 - - - - - - - - 
 
Uma vez que não há caminhos que ligam o vértice 1 aos demais, o algoritmo para, retornando os seguintes caminhos 
ótimos: 
1→ 2 ={(1,4), (4,2)}, de custo igual a 4. 
1→ 3 ={(1,4), (4,2), (2,3)}, de custo igual a 13. 
1→ 4 ={(1,4)}, de custo igual a 2. 
1→ 5 ={(1,4), (4,6), (6,7), (7,8), (8,5)}, de custo igual a 14. Ou {(1,4), (4,6), (6,7), (7,5)}, de custo igual a 14. 
1→ 6 ={(1,4), (4,6)}, de custo igual a 5. 
1→ 7 ={(1,4), (4,6), (6,7)}, de custo igual a 7. 
1→ 8 ={(1,4), (4,6), (6,7), (7,8)}, de custo igual a 13. 
 
 
Questão 2) 
 
REDE 
 
 
E 
𝐽
5
 
𝐽
3
 
L 
𝐽
4
 7 
7 𝐽
1
 
5 
12 
5 
𝐽
2
 
3 
7 
5 
4 4 
 
 
 
P
á g
in
á4
 
SOLUÇÃO PELO ALGORITMO DE FORD-FULKERSON 
Cadeias de aumento de fluxo empregadas na solução: 
𝐶1 = {𝐸, 𝐽1, 𝐽4, 𝐿}, ∆𝑓 = min{7,7,10} = 7 ⇒ 𝑓 = 0 + 7 = 7, 
𝑢+(𝐸, 𝐽1) = 0, 𝑢−(𝐸, 𝐽1) = 7, 
𝑢+(𝐽1, 𝐽4) = 0, 𝑢−(𝐽1, 𝐽4) = 7, 
𝑢+(𝐽4, 𝐿) = 3, 𝑢−(𝐽4, 𝐿) = 7. 
 
𝐶2 = {𝐸, 𝐽2, 𝐽4, 𝐿}, ∆𝑓 = min{9,3,3} = 3 ⇒ 𝑓 = 7 + 3 = 10, 
𝑢+(𝐸, 𝐽2) = 6, 𝑢−(𝐸, 𝐽2) = 3, 
𝑢+(𝐽2, 𝐽4) = 0, 𝑢−(𝐽2, 𝐽4) = 3, 
𝑢+(𝐽4, 𝐿) = 0, 𝑢−(𝐽4, 𝐿) = 10. 
 
𝐶3 = {𝐸, 𝐽2, 𝐽5, 𝐿}, ∆𝑓 = min{6,7,12} = 6 ⇒ 𝑓 = 10 + 6 = 16, 
𝑢+(𝐸, 𝐽2) = 0, 𝑢−(𝐸, 𝐽2) = 9, 
𝑢+(𝐽2, 𝐽5) = 1, 𝑢−(𝐽2, 𝐽5) = 6, 
𝑢+(𝐽5, 𝐿) = 6, 𝑢−(𝐽5, 𝐿) = 6. 
 
𝐶4 = {𝐸, 𝐽3, 𝐽5, 𝐿}, ∆𝑓 = min{8,8,6} = 6 ⇒ 𝑓 = 16 + 6 = 22, 
𝑢+(𝐸, 𝐽3) = 2, 𝑢−(𝐸, 𝐽3) = 6, 
𝑢+(𝐽3, 𝐽5) = 2, 𝑢−(𝐽3, 𝐽5) = 6, 
𝑢+(𝐽5, 𝐿) = 0, 𝑢−(𝐽5, 𝐿) = 12. 
 
Como o fluxo máximo (𝑓∗ = 22) na rede é superior a 20, é possível acomodar o tráfego da rodovia através do 
desvio por esta cidade. 
 
 
Questão 3) 
Letra a) 𝑃0 = 1 − 𝜌 =
1
5
. 
Letra b) 𝐸{Renda mensal} = 50 ∙ 𝜇22𝑑 = 50 ∙
22
4
= $275. 
Letra c) 𝑊 =
1
(𝜇−𝜆)
= 20 dias. 
Letra d) 𝐿𝑞 =
𝜆2
𝜇(𝜇−𝜆)
=
16
5
= 3,2 peças.