Apostila 5 - Pesquisa Operacional

Prévia do material em texto

Capítulo 5 Problema da designação e do transbordo 
Pesquisa Operacional I Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 5 
Problema da designação e do transbordo 
 
 
 
 
 
1 Problema da designação 
 
Um caso especial do modelo de transporte é aquele em que cada origem tem uma unidade disponível e 
cada destino necessita também de uma única unidade, por exemplo, 
 
• Várias fábricas e vários destinos sendo que uma fábrica abastecerá apenas um destino; 
• Vários funcionários e várias tarefas, designar um funcionário para cada tarefa; 
• Várias obras e várias firmas, uma obra para cada firma. 
 
 
Exemplo 1. O quadro representa as eficiências (capacidade de atingir o potencial da cada região) de quatro 
vendedores testados em quatro regiões. Os potenciais de vendas nas regiões são conhecidos. Designar um 
vendedor para cada região para maximizar o valor total das vendas. 
 
R1 R2 R3 R4 
V1 70% 60% 80% 90% 
V2 70% 80% 70% 90% 
V3 60% 90% 60% 70% 
V4 70% 80% 70% 80% 
 
Potencial de vendas: R1 - R$ 100.000,00, R2 - R$ 80.000,00, R3 – R$ 60.000,00 e R4 – R$ 90.000,00. 
 
 
Exemplo 2. Resolva este exemplo 2 supondo que não seja possível enviar o vendedor 3 para a região 2. 
 
Capítulo 5 Problema da designação e do transbordo 
Pesquisa Operacional I Jhoab Negreiros 
2
2 O Problema do Transbordo 
 
O problema de transbordo reconhece que pode ser mais barato despachar mercadorias com a utilização 
de nós intermediários ou transientes antes de chegar ao destino final. Esse conceito é mais geral do que o do 
problema de transporte normal, no qual são permitidas apenas expedições diretas entre uma origem e um 
destino. 
 
Exemplo 3. Ocorre transbordo na rede da figura a seguir porque seria concebível que a quantidade total de 
carros fornecida, de 2.200 pelas montadoras M1 (1.000) e M2 (1.200) passasse por qualquer um dos nós da 
rede antes de chegar a seus destinos nos nós C1 (800), C2 (900) e C3 (500) que representam três 
concessionárias. Quanto a isso, cada nó da rede que tenha arcos de entrada, bem como de saída (T1, T2, 
C1 e C2), agem como uma origem e também como um destino, e é denominado nó de transbordo. Os nós 
restantes são nós de fornecimento puros (M1 e M2) ou nós de demanda puros (C3). 
 
M1 – T1 � 3 
M1 – T2 � 4 
M2 – T1 � 2 
M2 – T2 � 5 
T1 – T2 � 7 
T1 – C1 � 8 
T1 – C2 � 6 
T2 – C2 � 4 
T2 – C3 � 9 
C1 – C2 � 5 
C2 – C3 � 3 
 
 O problema de transbordo pode ser convertido em um problema de transporte simples com seis 
origens (M1, M2, T1, T2, C1 e C2) e cinco destinos (T1, T2, C1, C2 e C3). As quantidades fornecidas e 
demandadas nos diferentes nós são calculadas por 
 
• Fornecimento em nó de suprimento puro igual fornecimento original; 
• Demanda em um nó de demanda puro igual demanda original; 
• Fornecimento em um nó de transbordo igual fornecimento original mais quantidade tampão; 
• Demanda em um nó de transbordo igual demanda original mais quantidade tampão; 
 
A quantidade tampão deve ser suficientemente grande para permitir que todas as unidades de 
fornecimento (ou de demanda) originais passem por qualquer um dos nós de transbordo. Seja 
 a 
quantidade tampão desejada; então 
 
 � ��
��������	���	��������	�����										 
� 1.000 � 1.200	���	800 � 900 � 500� 
� 2.200	��
��																																														 
 
Usando o tampão 
 e os custos unitários de expedição dados na rede, construímos o problema de 
transporte simples equivalente como mostra a tabela a seguir. 
 
 
Capítulo 5 Problema da designação e do transbordo 
Pesquisa Operacional I Jhoab Negreiros 
3
 
T1 T2 C1 C2 C3 
M1 3 4 Infinito Infinito Infinito 
M2 2 5 Infinito Infinito Infinito 
T1 0 7 8 6 Infinito 
T2 Infinito 0 Infinito 4 9 
C1 Infinito Infinito 0 5 Infinito 
C2 Infinito Infinito Infinito 0 3 
 
 Solução final do problema de transbordo obtida via Solver do Excel. 
 
 
T1 T2 C1 C2 C3 
M1 
M2 
T1 
T2 
C1 
C2 
 
 
3 Atividades 
 
Exercício 1. A empresa de ar condicionado Top Clima tem seis instalações programadas para o próximo 
mês. Ela poderá realizar no máximo duas instalações com pessoal próprio, e solicitou a quatro empreiteiras 
cadastradas o orçamento para cada um das obras e a disponibilidade para o serviço. O quadro a seguir 
resume os dados coletados. 
 
Empreiteiras 
Obras - Orçamentos em 1.000 unidades monetárias Disponibilidade: 
Número de obras 1 2 3 4 5 6 
A 12 20 25 30 22 20 2 
B 15 20 22 26 18 20 2 
C 16 24 26 22 21 21 2 
D 14 25 24 28 24 20 2 
Top Clima 13 25 30 27 20 15 2 
 
(a) Qual o plano de instalação de menor custo? 
(b) Resolva o problema supondo que cada empreiteira deve realizar pelo menos uma obra. 
(c) Resolva o problema supondo que a empreiteira Top Clima realize duas obras. 
(d) Resolva o problema supondo que a empreiteira Top Clima realize duas obras e as demais realize cada 
uma única obra. 
 
 
Exercício 2. A rede mostrada na figura a seguir dá as rotas de expedição dos nós 1 e 2 para os nós 5 e 6, 
passando pelo nós 3 e 4. Os custos unitários d expedição são mostrados nos respectivos arcos. Resolva o 
problema de transbordo correspondente. (Observação: R$ 1,00 de (3) – (4) e R$ 3,00 (4) – (3)) 
 
Capítulo 5 Problema da designação e do transbordo 
Pesquisa Operacional I Jhoab Negreiros 
4