Revisao Area 2

Prévia do material em texto

PROVA 2 DE PESQUISA OPERACIONAL PARA ENGENHARIA I – 2008/I 
As questões podem ser resolvidas a lápis. Organize suas respostas e coloque seu nome na folha de rosto. A prova é 
individual e sem consulta. 
 
1. 25 pts – Resolva o seguinte problema utilizando o algoritmo Branch-and-Bound e resolvendo cada 
subproblema graficamente. Identifique no gráfico o espaço de soluções formado por cada subproblema (ou 
seja, faça um gráfico grande!). Organize a solução do problema em uma árvore hierárquica. 
��� � � 4�	 
 5�� 
. �: 
�	 
 4�� � 5 
3�	 
 2�� � 7 
�	, �� � 0 � �������
 
 
2. 25 pts – Uma empresa fornece produtos a três clientes, os quais demandam 30 unidades cada. A empresa 
tem dois depósitos. O depósito 1 possui 40 unidades disponíveis em estoque e o depósito 2 possui 30 
unidades disponíveis. Os custos unitários de envio dos depósitos para os clientes vêm dados na tabela 
abaixo. Existe uma multa para cada unidade não fornecida aos clientes: no caso do cliente 1, a multa é de 
R$90; no caso do cliente 2, a multa é de R$80; no caso do cliente 3, a multa é de R$110. Resolva o problema 
abaixo utilizando o algoritmo simplex dos transportes. O objetivo é minimizar os custos de transporte e 
multa. Determine a base inicial pelo método do extremo noroeste e não se esqueça de balancear o 
problema (Dica: no total, o problema é resolvido em 4 tableaus). 
 
 Para 
De Cliente 1 Cliente 2 Cliente 3 
Depósito 1 R$15 R$35 R$25 
Depósito 2 R$10 R$50 R$40 
 
3. 25 pts – Utilize o algoritmo de Dijkstra para encontrar o caminho mais curto entre os nós 1 e 5 da rede 
abaixo. Explicite todas as etapas do algoritmo na solução do problema. 
 
 
 
4. 25 pts – Cinco funcionários estão disponíveis para realizar quatro trabalhos. O tempo demandado por cada 
funcionário para realizar cada trabalho é dado na tabela abaixo (um traço indica que o funcionário não 
realiza o trabalho). Utilize o algoritmo húngaro para determinar a alocação de funcionários a trabalhos de 
forma a minimizar o tempo total de sua realização. Explicite os passos do algoritmo húngaro e não esqueça 
de balancear o problema. 
 
 Tempo (horas) 
Funcionário Trabalho 1 Trabalho 2 Trabalho 3 Trabalho 4 
F1 22 18 30 18 
F2 18 ― 27 22 
F3 26 20 28 28 
F4 16 22 ― 14 
F5 21 ― 25 28