Prova 1 de POII

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia 1 
DEPARTAMENTO DE CIÊNCIA DOS MATERIAIS 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
Prova Nº 1 
 
Nome ___________________________________________________________________ 
Data 28/04/2008 
 
Observações: Leia atentamente estas instruções antes de fazer 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 mostre o 
grafo e a extensão final. 
c. Para os problemas de Fluxo Máximo formule o PPL e resolva utilizando o algoritmo de Ford-
Fulkerson. 
d. Para os problemas de decisão multicritério utilize três métodos incluindo o da soma 
ponderada. 
e. Para os problemas de decisão com incerteza resolva por quatro métodos incluindo o de 
Savage. Além disso, diga se você é pessimista, levemente pessimista, indiferente, levemente 
otimista ou otimista, defina seu α, e diga qual seria a sua escolha. 
f. Para os problemas de decisão com risco desenhe a árvore de decisão e mostre a solução 
final. 
 
 
1. Uma companhia possui três campos de petróleo, três refinarias e três 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 R3 Refinaria D1 D2 
C1 11 7 2 R1 5 9 
C2 5 4 8 R2 8 7 
C3 7 3 12 R3 4 6 
 
 
2. 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 
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 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. (2,5 p) 
a. Qual seria a decisão neste caso? 
 Universidade Federal Fluminense 
Profª. Lídia 2 
b. 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 o 
indicarão apenas em 70% das vezes. O que recomendaria ao presidente da firma? 
c. Vale a pena pagar pelo teste? 
 
3. 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 - 
 
 
4. Mencione e explique três métodos para seleção nos Métodos Multicritério de Decisão. (1,5 p) 
 
5. Explique quando se aplica e descreva o método de Savage. (1 p)