Capítulo_4_-_Problema_de_Trans

Prévia do material em texto

Capítulo 4 Problema de Transbordo 
Pesquisa Operacional II Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 4 
Problema de Transbordo 
 
 
 
 
 
 
4.1 Introdução 
 
 
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. 
 
4.2 Problema de Transbordo 
 
Neste capítulo mostra como um problema de transbordo pode ser convertido em (e 
resolvido como) um problema de transporte normal usando a noção de tampão. 
 
Exemplo 1. 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 
Capítulo 4 Problema de Transbordo 
Pesquisa Operacional II Jhoab Negreiros 
2
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	��
��																																														 
Capítulo 4 Problema de Transbordo 
Pesquisa Operacional II Jhoab Negreiros 
3
 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. 
 
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 
 
 
 
 
 
 
4.3 Atividades 
 
Exercício 1. 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 4 Problema de Transbordo 
Pesquisa Operacional II Jhoab Negreiros 
4
Exercício 2. No exercício 1, suponha que o nó de origem 1 possa ser ligado ao nó de origem 2 com 
um custo unitário de expedição de R$ 1,00 custo unitário de expedição do nó 1 ao nó 3 sofre um 
aumento de R$ 5,00. Formule a questão como um problema de transbordo e ache a programação 
de expedição ótima. 
 
Exercício 3. A rede a seguir mostra as rotas de expedição de carros de três fábricas (nós 1, 2 e 3) 
para as três revendedoras (nós 6 a 8), passando por duas centrais de distribuição (nós 4 e 5). Os 
custos de expedição por carro (em $ 100) são mostrados nos arcos. 
(a) Resolva a questão como um problema de transbordo. 
(b) Ache a nova solução ótima considerando que a Central de Distribuição 4 possa vender 240 
carros diretamente a clientes.