Problema de Transbordo

Prévia do material em texto

Problema de Transbordo 
(caso especial do problema de 
transporte) 
POII – FeMASS 
Prof. Irineu 
Problema de Transbordo 
• Reconhece que pode ser mais barato despachar mercadorias 
com a utilização de nós intermediários (transientes) antes de 
chegar ao destino final; 
– Conceito é mais geral do que o problema de transporte 
normal, que permite apenas expedições diretas entre 
origem de destino. 
• Problema de transbordo -> convertido e resolvido como um 
problema de transporte normal usando a noção de tampão. 
Logo, consideram-se: 
– Variáveis de decisão representam a quantidade de produtos 
enviados de uma origem para um destino; 
– A função-objetivo é de minimizar o custo total de transporte; 
– Problemas com o balanceamento (ou não) das restrições 
(verificar balanceamento previamente). 
• Vejamos o exemplo: 
Duas fábricas de automóveis (P1 e P2) estão ligadas a três 
revendedoras (D1, D2 e D3) por meio de duas centrais de 
trânsito (T1 e T2), conforme a rede: 
Problema de Transbordo 
• As quantidades 
fornecidas pelas fábricas 
são 1000 + 1200 carros; 
• As quantidades 
demandadas pelas 
revendedoras são 800 + 
900 + 500; 
• Os custos de expedição 
por carro nos arcos estão 
em centenas de dólares. 
 
• Considerações sobre cada nó: 
– Cada nó que tenha arcos de entrada e de saída (T1, T2, D1, 
D2) é denominado nó de transbordo; 
– Cada nó que tenha arcos somente de saída (P1, P2) são 
denominados nós de suprimento/fornecimento puros; 
– Cada nó que tenha arcos somente de entrada (D3) são 
denominados nós de demanda puros. 
Problema de Transbordo 
É fundamental saber identificar os tipos de nós citados!!! 
• Convertendo o problema de transbordo em um problema de 
transporte convencional: 
– Há 6 origens: 
(P1, P2, T1, T2, D1, D2) 
– Há 5 destinos: 
(T1, T2, D1, D2, D3) 
Problema de Transbordo 
Observe que nós de 
transbordo são origens 
e destinos. 
Cálculo de quantidades fornecidas e demandas: 
• Nó suprimento/fornecimento puro: fornecimento original; 
• Nó demanda puro: demanda original; 
• Nó de transbordo: 
 1) Fornecimento (origem): fornecimento original + quantidade tampão; 
 2) Demanda (destino): demanda original + quantidade tampão. 
TABELA DO MODELO 
 
> Lançar custos previstos. E: 
- Se origem = destino, então o custo 
é zero; 
- Se origem e destino não possuem 
correspondência, então se descarta 
do quadro (células com letra M); 
> Lançar fornecimentos e 
demandas. E, para nós de 
transbordo, considerar B: 
- A quantidade tampão (B) deve ser 
suficientemente grande para 
permitir que todas as unidades de 
fornecimento (ou de demanda) 
originais passem por qualquer nó de 
transbordo. 
B = fornecimento (ou demanda) 
total; 
B = 1000 + 1200 (ou 800+900+500); 
B = 2200 carros. 
(Obs.: considerando problema equilibrado, 
é claro!) 
• Modelando o problema (tradicional), considerando: 
• Xij, onde i é a origem e j o destino. Reescrevendo DE MODO 
MAIS CLARO: 
– P1T1 – quantidade de itens enviados da origem P1 para 
destino T1. 
– P2T2 – quantidade de itens enviados da origem P2 para 
destino T2. 
• O objetivo é minimizar o custo (z) de transporte, logo: 
 MIN z = 3 P1T1 + 4 P1T2 + 2 P2T1 + 5 P2T2 + 0 T1T1 
 + 7 T1T2 + 8 T1D1 + 6 T1D2 + 0 T2T2 + 4 T2D2 + 9 T2D3 
 + 0 D1D1 + 5 D1D2 + 0 D2D2 + 3 D2D3 
(Vide Tabela no slide anterior. Vars de transbordo 
origem=destino possuem custo nulo, podem ser removidos ou 
mantidos na função objetivo, a critério, de qualquer modo, não 
impactarão o resultado.) 
Problema de Transbordo 
• Modelando o problema (tradicional)... Continuação... 
• Restrições: 
S.R.: 
Rest1) P1T1 + P1T2 = 1000 !FORNECEDOR P1 
Rest2) P2T1 + P2T2 = 1200 !FORNECEDOR P2 
Rest3) T1T1 + T1T2 + T1D1 + T1D2 = 2200 !FORNECEDOR T1 
Rest4) T2T2 + T2D2 + T2D3 = 2200 !FORNECEDOR T2 
Rest5) D1D1 + D1D2 = 2200 !FORNECEDOR D1 
Rest6) D2D2 + D2D3 = 2200 !FORNECEDOR D2 
Rest7) P1T1 + P2T1 + T1T1 = 2200 !DEMANDA T1 
Rest8) P1T2 + P2T2 + T1T2 + T2T2 = 2200 !DEMANDA T2 
Rest9) T1D1 + D1D1 = 3000 !DEMANDA D1 
Rest10) T1D2 + T2D2 + D1D2 + D2D2 = 3100 !DEMANDA D2 
Rest11) T2D3 + D2D3 = 500 !DEMANDA D3 
(Vars de transbordo origem=destino devem ser incluídos para aplicação do 
Simplex. Vide tabela do modelo. No entanto, veremos uma outra forma preferida 
de restrições simplificadas mais a frente...) 
 
Xij ≥ 0, i = {1, 2, ..., 6}, j = {1, 2, ..., 5} (em coordenadas originais da tabela 
do modelo). 
Problema de Transbordo 
Problema de Transbordo 
Aplicando o LINGO (linguagem LINDO – “Lindo Model”): 
Resultado do Solver no próximo slide... “Solution report”. 
Custo ótimo: 
$20.700 
Quantidades Xij 
utilizadas 
(vars básicas em 
vermelho) 
Quantidades Xij 
transbordo, 
origem=destino, 
custo nulo, 
desconsideradas, 
mas são vars 
básicas úteis 
para o Simplex. 
 
Solução ótima em rede: 
• Montando o problema de transbordo, conforme a 
representação algébrica (forma preferida): 
}..1{},..1{,0
}..1{},..1{,**
*min
1
1 1
njmixij
njmicapixjiajixijaij
xijcij
n
j
m
i
n
j




 
Problema de Transbordo 
Para as restrições (simplificadas...): 
• Identifique o total de restrições para cada nó origem e 
destino (evitando-se repetições); 
• O número de itens que o referido nó se relaciona chegam 
ao nó menos o montante que sai deve ser igual ao 
suprimento (negativa); e, ao montante positivo que sai 
deve ser igual a demanda (positiva). 
Vejamos o exemplo... 
Linha (suprimento) - negativo 
C
o
lu
n
a 
(d
em
an
d
a)
 -
 p
o
si
ti
vo
 
P1 e P2 (apenas Linha [-}) 
T1, T2, D1, D2 - (Linha [-} e 
Coluna[+}) 
D3 (apenas Coluna [+}) 
Nota: 
Na equivalência, 
B é reduzido a 
zero. 
Custo ótimo: 
$20.700 
Quantidades Xij 
utilizadas 
(vars básicas em 
vermelho). 
Relatório de Solução Simplex para as restrições simplificadas 
Exercícios 
• A seguir, resolva os dois exercícios propostos para o problema 
de transbordo; 
• Ao desenvolver o problema de transbordo correspondente, 
modele a Função Objetivo + restrições e tabela de distribuição 
– utilizando a abordagem de restrições simplificadas; 
• Aplique LINGO/LINDO para solução ótima e mostre 
roteamentos desde as origens até os destinos; 
• Documente tudo e gere PDF de resposta para submissão no 
AVA. 
 
Exercícios 
1) A rede da figura abaixo dá as rotas de expedição dos nós 1 e 2 
para os nós 5 e 6, passando pelos nós 3 e 4. Os custos unitários 
de expedição são mostrados nos respectivos arcos. 
a) Desenvolva o problema de transbordo correspondente, 
modelando-o em Função Objetivo + restrições e tabela de 
distribuição. 
b) Aplique LINGO/LINDO para solução ótima e mostre como os 
embarques são roteados desde as origens até os destinos. 
Exercícios 
2) Considere a rede de 
tubulações de petróleo (figura 
ao lado). Os diferentes nós 
representam estações de 
bombeamento e recepção. As 
distâncias em milhas entre as 
estações são mostradas na rede. 
O custo de transporte por galão 
entre dois nós é diretamente 
proporcional ao comprimento 
da tubulação. Desenvolva o 
modelo de transbordo associado 
e ache a solução ótima (aplique 
LINGO/LINDO).