Prova de POII

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia – Primeira Verificação – POII 1 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO – VEP 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
Prova Nº 1 
Nome _______________________________________________________Data 04/05/2009 
Leia atentamente as seguintes instruções antes de realizar a prova: 
a. Para os problemas de caminho mínimo que utilizam o algoritmo de Floyd realize três 
iterações. 
b. Para os problemas de árvore geradora mínima, resolva com qualquer algoritmo e apresente a 
árvore o grafo e a extensão total resultantes. 
c. Para os problemas de Fluxo Máximo faça três iterações utilizando o algoritmo de Ford-
Fulkerson e formule o PPL. 
d. Para os problemas de decisão multicritério resolva utilizando três métodos de solução. 
e. Para os problemas de decisão com incerteza em que não seja especificado o método de 
solução resolva por quatro métodos incluindo o de Savage. 
f. Para os problemas de decisão com risco faça também uma análise de sensibilidade das 
probabilidades a priori. 
 
1. 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. 
(2,5 p) 
 Refinaria Centro de Distribuição 
Campo R1 R2 Refinaria D1 D2 
C1 6 7 R1 15 8 
C2 5 4 R2 6 6 
C3 7 3 
 
 
2. Um novo depilador elétrico está para ser lançado no mercado pela Companhia A. A alta 
direção está desejosa de saber de quanto deverá ser a produção diária do depilador. Essa 
produção é classificada como pequena, média e grande. Se for programada uma quantidade 
pequena e a demanda também for pequena, haverá um lucro líquido de R$ 15.000 semanais. 
Se a demanda for média ou alta, ainda assim haverá um lucro líquido de R$ 15.000 já que a 
baixa produção não permitirá que se tire vantagem da situação. 
Por outro lado, se for programada uma produção média e a demanda for baixa, o lucro será 
de apenas R$ 5.000, pois muitos depiladores não serão vendidos. Se a demanda for média, o 
lucro será de R$ 25.000; o lucro também será esse se a demanda for alta. 
Finalmente, se a produção for alta e a demanda for baixa, o lucro líquido será nulo. Se 
demanda for média, o lucro será de R$ 15.000, mas se for alta, o lucro será de R$ 30.000. 
Há muita preocupação na Companhia com a quantidade a produzir. Perdas vêm sendo 
contabilizadas em outros negócios, e decisões erradas podem se tornar catastróficas. 
Determine a melhor alternativa para este caso. (1,5 p) 
 
3. O presidente de uma firma num setor muito competitivo tem razões para suspeitar que um 
empregado da firma está fornecendo informações confidenciais a uma empresa rival. Ele tem 
90% de certeza de que o informador é o tesoureiro da firma, cujos contatos tem sido 
 Universidade Federal Fluminense 
Profª. Lídia – Primeira Verificação – POII 2 
extremamente importantes na obtenção de financiamentos para a firma. Se o presidente o 
despede e ele não for o informador, a companhia perde esse funcionário tecnicamente 
competente e continua com o informador entre os seus colaboradores, o que representa uma 
perda estimada de 500.000 u.m. para a firma. Se o presidente não despedir o tesoureiro, a 
companhia perderá 300.000 u.m., independentemente de ele ser, ou não, o informador, já 
que em qualquer caso o informador permanecerá na firma. (3 p) 
a. Antes de decidir o destino do tesoureiro, o presidente pode sujeitá-lo a testes no 
detector de mentiras. Para evitar possíveis processos judiciais, estes testes terão de 
ser usados com todos os empregados da firma, com um custo total de 30.000 u.m. 
Um outro problema é que os testes com o detector de mentiras não são 
absolutamente infalíveis. Se uma pessoa estiver mentindo, os testes detectarão tal 
situação em 90% das vezes; mas se uma pessoa não estiver mentindo, os testes 
assim o indicarão apenas em 70% das vezes. O que recomendaria ao presidente da 
firma? 
b. Vale a pena pagar pelo teste no detector de mentiras? 
 
 
4. A rede ao lado representa cidades e as 
rodovias entre elas. Formule o Problema 
de Programação Linear (PPL) para 
determinar a rota mais curta da cidade 3 à 
cidade 7. (1,5 p) 
 
 
 
 
 
 
 
 
 
 
 
5. Um banco em breve estará conectando 
terminais de computador de cada uma de 
suas agencias ao computador localizado 
em sua sede principal usando linhas 
telefônicas especiais com dispositivos de 
telecomunicações. A linha telefônica de 
uma filial não precisa estar conectada 
diretamente à matriz. Ela pode estar 
conectada indiretamente, sendo conectada 
a outra filial que, por sua vez, está 
conectada (direta ou indiretamente) à 
matriz. A tarifa para estas linhas é da US$ 
100 vezes o número de milhas envolvidas, 
em que a distância (em milhas) entre cada 
par de vértices encontra-se na tabela a 
seguir. A gerência deseja determinar quais 
pares de agências devem estar conectados 
diretamente através destas linhas de modo 
a conectar todas as filiais à matriz a um 
custo total mínimo. (1,5 p) 
 
 Distância entre pares de agências 
 Matriz F. 1 F. 2 F. 3 F. 4 F. 5 
Matriz - 190 70 115 270 160 
Filial 1 190 - 100 110 215 50 
Filial 2 70 100 - 140 120 220 
Filial 3 115 110 140 - 175 80 
Filial 4 270 215 120 175 - 310 
Filial 5 160 50 220 80 310 - 
 
 
Fórmula: 
( ) ( ) ( )( ) ( )
k j j
j k n
k j j
j 1
P t S P S
P S t
P t S P S
=
=
�
 a probabilidade de ocorrer o estado Sj dada a informação tk.