aula04

Prévia do material em texto

4ºAula
Problema do transporte e suas 
variantes
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de:
•  entender o que é o problema do transbordo;
•  aprender sobre as principais variantes do problema do transbordo;
•  usar o Excel Solver para resolver problemas de do transporte;
•  entender o problema da designação (método húngaro);
•  aprender sobre o problema do transbordo.
Prezados(as) alunos(as),
Nesta quarta aula, estudaremos os conceitos do problema 
do transporte, e suas variantes, como o balanceamento 
do transporte o problema da designação e o problema do 
transbordo. Também inclui em nosso material da aula 4 uma 
seção de resolução dos problemas utilizando o Solver do Excel, 
para ajudar no dia a dia dos profissionais que tratem desses 
temas em suas rotinas, como em logística, programação da 
produção, etc. 
Bons estudos!
34Pesquisa Operacional
Seções de estudo
1 - Defi nição do problema de transporte
2 - O problema de designação (método húngaro)
3 - O problema de transbordo 
1 -Defi nição do problema de transporte
De acordo com Thaha (2008), o problema geral pode ser 
representado pela rede na Figura 1. Há m origens e n destinos, 
cada um representado por um nó. Os arcos representam as 
rotas que ligam as origens aos destinos. O arco (i, j), que liga 
a origem i ao destino j, nos dá duas informações: 1) o custo 
de transporte por unidade, cij; e 2) a quantidade enviada, xij. 
.A quantidade de suprimento na origem i é a e a quantidade 
de demanda no destino a e b.. O objetivo do problema e 
determinar as incógnitas x que minimizarão o custo total de 
transporte e, ao mesmo tempo, satisfarão todas as restrições 
de suprimento e demanda.
Figura 1: Representação do problema do transporte com 
nós e arcos
Fonte: Taha (2008).
1.1 - Exemplo de um problema do 
transporte
Para exemplifi car, veremos um exemplo resolvido 
adaptado de Taha (2008). A American Auto tem três fábricas: 
uma em Los Angeles, uma em Detroit e outra em Nova 
Orleans, e duas grandes centrais de distribuição: uma em 
Denver e outra em Miami. As capacidades das três fábricas 
para o próximo trimestre são 1.000, 1.500 e 1.200 carros. As 
demandas trimestrais nas duas centrais de distribuição são 
2.300 e 1.400 carros. O mapa de distâncias entre as fábricas e 
as centrais de distribuição é dado na Tabela 1.
Tabela 1: mapa das distâncias entre as fábricas e depósitos
Mapa das distâncias 
Denver Miami
Los Angeles 1.000 2.690
Detroit 1.250 1.350
Nova Orleans 1.275 850
Fonte: Taha (2008).
A empresa transportadora encarregada do transporte 
dos carros cobra 8 centavos por milha por carro. Os custos de 
transporte por carro nas diferentes rotas, arredondados para o 
valor mais próximo, são dados na Tabela 2.
Tabela 2: custos de transporte por carro
Custos de transporte por carro  
Denver (1) Miami (2)
Los Angeles (1) 80 215
Detroit (2) 100 108
Nova Orleans (3) 102 68
Fonte: Taha (2008).
A formulação do problema de PL da questão é dada por:
Minimizar z: = 80x11 + 215x12 + 100x21 + 108x22 + 
102x31 + 68x32
sujeito a:
x11 + x12 = 1.000 (Los Angeles)
x21 + x22 = 1.500 (Detroit)
x31 + x32 = 1.200 (Nova Orleans)
x11 + x21 + x31 = 2.300 (Denver)
x12 + x22 + x32 = 1.400 (Miami)
xíj ≥ 0; i =1,2,3; j = 1,2
Todas essas restrições são equações porque o suprimento 
total das três origens (= 1.000 + 1.500 + 1.200 = 3.700 carros) 
é igual a demanda total dos dois destinos (= 2.300 + 1.400 = 
3 700 carros).
Tabela 3: representação da solução pelo algoritmo 
simplex 
Denver Miami Suprimento
Los Angeles
  80   215 
1.000 
 x11   x12  
Detroit
  100   108 
1.500 
 x21   x22  
Nova Orleans
  102   68 
1.200 
 x31   x32  
Demanda 2.300 1.400  
Fonte: Taha (2008).
A solução ótima na Figura 2 recomenda o embarque de 
1.000 carros de Los Angeles para Denver, 1.300 de Detroit 
para Denver, 200 de Detroit para Miami e 1,200 de Nova 
Orleans para Miami. O custo mínimo de transporte associado 
é calculado como 1.000 x $ 80 + 1.300 x $ 100 + 200 x $ 108 
+ 1.200 x $ 68 = $ 313.200.
Figura 2: representação gráfi ca da solução ótima.
Fonte: Taha (2008). 
35
1.2 - Balanceamento do problema 
de transporte. 
O algoritmo de transporte é baseado na premissa de 
que o problema é balanceado, o que significa que a demanda 
total é igual ao fornecimento total. Se o problema não for 
balanceado, sempre podemos adicionar uma origem fictícia 
ou um destino fictício para restaurar o equilíbrio (também 
chamada de “dummy”).
No modelo da American Auto, suponha que a capacidade 
da fábrica de Detroit seja 1.300 carros (em vez de 1.500). O 
suprimento total (= 3.500 carros) é menor do que a demanda 
total (= 3.700 carros), o que significa que parte da demanda 
em Denver e Miami não será satisfeita.
Como a demanda ultrapassa o fornecimento, uma origem 
(fábrica) fictícia com uma capacidade de 200 carros (= 3.700 - 
3.500) é adicionada para equilibrar o problema de transporte. 
O custo unitário de transporte da fábrica fictícia para os dois 
destinos é zero porque a fábrica não existe.
A Tabela 4 dá o problema balanceado acompanhado 
de sua solução ótima. A solução mostra que a fábrica fictícia 
despacha 200 carros para Miami. O que significa que Miami 
terá 200 carros a menos do que sua demanda de 1.40%) carros. 
Tabela 4: problema balanceado acompanhado de sua 
solução ótima
Denver Miami Suprimento
Los Angeles
  80   215 
 
1.000 
 1.000   
Detroit
  100   108 
1.300 
 1.300    
Nova Orleans
  102   68 
1.200 
   1.200  
Fictícia
  0   0
200 
   200  
Demanda 2.300 1.400  
Fonte: Taha (2008). 
Podemos garantir que um destino específico não sofra 
escassez designando um custo unitário de transporte muito 
alto da origem fictícia até aquele destino. Por exemplo, uma 
multa de $ 1.000 na célula fictícia de Miami evitará escassez 
em Miami. Claro que não podemos usar esse “truque” em 
todos os destinos, porque com certeza ocorrerá escassez em 
alguma parte do sistema. 
Tabela 5: garantia de um fornecimento para um destino 
específico
Denver Miami Fictício Suprimento
Los Angeles
  80   215   0
1.000 
1.000      
Detroit
  100   108   0
1.500 
 900   300  
 
400  
Nova Orleans
  102   68   0
1.200 
 
 
1.100    
Demanda 1.900 1.400 400  
Fonte: Taha (2008).
O caso em que o fornecimento ultrapassa a demanda pode 
ser demonstrado ao se considerar que a demanda em Denver 
é apenas 1.900 carros. Nesse caso, precisamos adicionar uma 
central de distribuição fictícia para “receber”, o suprimento 
excedente. Novamente, o custo unitário de transporte para a 
central de distribuição fictícia é zero, a menos que exijamos 
que a fábrica esgote seu suprimento, completamente. Nesse 
caso, devemos designar um alto custo unitário de transporte 
da fábrica designada ao destino fictício.
1.3 - Utilizando o método 
computacional – solver
A Figura 3 mostra um exemplo de como montar o 
problema apresentado anteriormente em uma planilha do 
Excel para ser resolvido com o Solver. Lembrando que esse é 
apenas um exemplo de montagem.
Figura 3: Solução do problema do transporte modelado 
em Excel.
Fonte: o autor. 
Como vimos anteriormente, o problema pode ser 
balanceado para achar outras soluções. As figuras 4 e 5 
mostram como pode ser modelado em planilha do Excel os 
cenários apresentados nesta aula. 
Figura 4: problema balanceado
Fonte: o autor. 
36Pesquisa Operacional
Figura 5: problema resolvido com garantia de um 
fornecimento para um destino específi co
Fonte: o autor. 
2 -O problema de designação (método 
húngaro)
De acordo com Taha (2008), a melhor pessoa para a 
tarefa é uma descrição adequada do problema de designação. 
A situação pode ser ilustrada pela designação de trabalhadores 
com graus variáveis de habilidade a determinadas tarefas. 
Uma tarefa que combine com a habilidade de um trabalhador 
custa menos do que uma tarefa para a qual o trabalhador não 
seja tão habilidoso. O objetivo do problema é determinar a 
designação de menor custo de trabalhadores a tarefas.O problema geral de designação com n trabalhadores e n 
tarefas é representado na Tabela 6. O elemento c ij representa 
o custo de designar o trabalhador i à tarefa j (i, j = 1, 2,…, 
n). Não há nenhum prejuízo em termos de generalidade se 
considerarmos que o número de trabalhadores é sempre igual 
ao número de tarefas, uma vez que sempre podemos adicionar 
trabalhadores fi ctícios ou tarefas fi ctícias para satisfazer essa 
premissa. 
Tabela 6 – Problema da designação
Fonte: Taha (2008). 
Para Taha (2008), o problema de designação é, na 
realidade, um caso especial do problema de transporte no 
qual os trabalhadores representam as origens e as tarefas 
representam os destinos. A quantidade fornecida (demandada) 
em cada origem (destino) é exatamente igual a 1. O custo de 
‘transportar’ o trabalhador i para a tarefa j é cij. Na verdade, o 
problema de designação pode ser resolvido diretamente como 
um problema de transporte comum. De qualquer maneira, o 
fato de todas as quantidades fornecidas e demandadas serem 
iguais a 1 levou ao desenvolvimento de um algoritmo de 
solução simples denominado método húngaro. Embora o 
novo método de solução pareça não ter relação alguma com 
o problema de transporte, na realidade a raiz do algoritmo 
é o método simplex, exatamente como a do problema de 
transporte (TAHA, 2008). 
Ainda de acordo com Taha (2008), usaremos o seguinte 
exemplo para apresentar a mecânica do novo algoritmo. Os 
três fi lhos de Joe Klyne (John, Karen e Terri) querem ganhar 
algum dinheiro para gastar durante uma excursão da escola até 
o zoológico local. O Sr. Klyne escolheu três tarefas para seus 
fi lhos: 1) cortar a grama; 2) pintar a porta da garagem; e 3) 
lavar os carros da família. Para evitar a concorrência prevista 
entre os irmãos, ele pediu que seus fi lhos apresentassem 
propostas (fechadas) do que eles consideravam que fosse 
um pagamento justo para cada uma das três tarefas. Ficou 
combinado que os três concordariam com a decisão do pai 
sobre quem executaria qual tarefa. A Tabela 7 resume as 
propostas recebidas. Com base nessas informações, como o 
Sr. Klyne deve designar as tarefas? O problema de designação 
será resolvido pelo método húngaro. 
Tabela 7 – Problema da designação do Sr. Klyne
Fonte: Taha (2008).
Etapa 1. Na matriz de custo original, identifi que o 
mínimo de cada linha e o subtraia de todas as entradas da 
linha. 
Tabela 8 – Etapa 1 do método húngaro
Fonte: Taha (2008).
Etapa 2. Na matriz resultante da etapa 1, identifi que o 
mínimo de cada coluna e o subtraia de todas as entradas da 
coluna. 
Tabela 9 – Etapa 2 do método húngaro
Fonte: Taha (2008).
37
Etapa 3. Identifique a solução ótima como a designação 
viável associada com os elementos zero da matriz obtida na 
etapa 2. 
Sejam pi e qj os custos mínimos associados com a linha i 
e a coluna j, como definido nas etapas 1 e 2, respectivamente. 
Os mínimos de linha da etapa 1 são calculados de acordo com 
a matriz de custo original, como mostra a Tabela 8. 
Em seguida, subtraia o mínimo da linha de cada linha 
respectiva para obter a matriz reduzida da Tabela 9. 
A aplicação da etapa 2 resulta nos mínimos de coluna 
da Tabela 9. Subtraindo esses valores das respectivas colunas, 
obtemos a matriz reduzida da Tabela 10. 
Tabela 10 – Etapa 3 do método húngaro
Fonte: Taha (2008).
As células com entradas zero sublinhadas dão a solução 
ótima, o que significa que John pintará a porta da garagem, 
Karen cortará a grama e Terri lavará os carros da família. O 
custo total para o Sr. Klyne é 9 + 10 + 8 = $ 27. Essa quantia 
também será sempre igual a (p1 + p2 + p3 ) + (q1 + q2 + q3 ) = 
(9 + 9 + 8) + (0 + 1 + 0) = $ 27 (TAHA, 2008). 
As etapas do método húngaro apresentadas funcionam 
bem no exemplo precedente porque as entradas zero na 
matriz final produzem uma designação viável (no sentido de 
que uma tarefa distinta é designada a cada filho). Em alguns 
casos, os zeros criados pelas etapas 1 e 2 podem não resultar 
em uma solução viável diretamente e serão necessárias mais 
etapas para achar a designação ótima (viável). O exemplo 
seguinte demonstra essa situação (TAHA, 2008). 
Suponha que a situação discutida no exemplo anterior 
seja estendida para quatro filhos e quatro tarefas. A Tabela 11 
resume os elementos de custo do problema. A aplicação das 
etapas 1 e 2 à matriz da Tabela 11 (usando p1 = 1, p2 = 7, p3 
= 4, p4 = 5, q1 = 0, q2 = 0, q3 = 3 e q4 = 0) dá como resultado 
a matriz reduzida da Tabela 12. As localizações das entradas 
zero não permitem designar tarefas únicas a todos os filhos. 
Por exemplo, se designarmos a Tarefa 1 ao Filho 1, então a 
coluna 1 será eliminada e o Filho 3 não terá uma entrada zero 
nas três colunas restantes. Esse obstáculo pode ser superado 
com a adição das seguintes etapas ao procedimento delineado 
no exemplo anterior (TAHA, 2008). 
Etapa 2a. Ainda de acordo com Taha (2008), se não for 
possível garantir nenhuma designação viável (com todas as 
entradas zero) pelas etapas 1 e 2, 
1. Trace o número mínimo de linhas horizontais e 
verticais na última matriz reduzida que abrangerá 
todas as entradas zero; 
2. Selecione a menor entrada não abrangida, subtraia 
essa entrada de todas as entradas não abrangidas e 
então a adicione a todas as entradas na interseção de 
duas linhas; 
3. Se não for possível encontrar nenhuma designação 
viável entre as entradas zero resultantes, repita a 
etapa 2a. Caso contrário, passe para a etapa 3 a fim 
de determinar a designação ótima. 
Tabela 11 – modelo de designação
Fonte: Taha (2008).
Tabela 12 – matriz de designação reduzida
Fonte: Taha (2008).
Tabela 13 – aplicação da etapa 2a
Fonte: Taha (2008).
Tabela 14 – Designação ótima
Fonte: Taha (2008). 
A aplicação da etapa 2a à última matriz produz as células 
sombreadas da Tabela 13. A menor entrada não sombreada 
(mostrada em caracteres itálicos) é igual a 1. Essa entrada é 
adicionada à interseção de células em negrito e subtraída das 
38Pesquisa Operacional
células sombreadas restantes para produzir a matriz da Tabela 
14. A solução ótima (mostrada pelos zeros não sublinhados) 
recomenda a designação do Filho 1 à Tarefa 1, do Filho 2 à 
Tarefa 3, do Filho 3 à Tarefa 2 e do Filho 4 à Tarefa 4. O custo 
ótimo associado é 1 + 10 + 5 + 5 = $ 21. O mesmo custo 
também é determinado pela soma dos pi e qj e pela entrada 
que foi subtraída depois que as células sombreadas foram 
determinadas, isto é, (1 + 7 + 4 + 5) + (0 + 0 + 3 + 0) + (1) 
= $ 21. 
3 - O problema de transbordo
De acordo com Taha (2008), 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 fi nal. 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. 
Esta seção 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. 
Por 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, de acordo com a rede mostrada 
na Figura 6. As quantidades fornecidas pelas fábricas P1 e 
P2 são 1.000 e 1.200 carros, e as quantidades demandadas 
nas revendedoras D1, D2 e D3 são 800, 900 e 500 carros. 
Os custos de expedição por carro (em centenas de dólares) 
entre pares de nós são mostrados nas ligações (ou arcos) que 
conectam os nós da rede. 
Figura 6 - Rede de transbordo entre as fábricas e as 
revendedoras 
 Fonte: Taha (2008). 
Ocorre transbordo na rede da Figura 6 porque seria 
concebível que a quantidade total de carros fornecida, de 2.200 
(= 1.000 + 1.200), pelos nós P1 e P2 passasse por qualquer um 
dos nós da rede antes de chegar a seus destinos nos nós D1, 
D2 e D3. Quanto a isso, cada nó da rede que tenha arcos de 
entrada, bem como de saída (T1, T2, D1 e D2), age como uma 
origem e tambémcomo um destino, e é denominado nó de 
transbordo. Os nós restantes são nós de fornecimento puros 
(P1 e P2) ou nós de demanda puros (D3). 
O problema de transbordo pode ser convertido em um 
problema de transporte normal com seis origens (P1, P2, T1, 
T2, D1 e D2) e cinco destinos (T1, T2, D1, D2 e D3). As 
quantidades fornecidas e demandadas nos diferentes nós são 
calculadas por:
Fornecimento em um nó de suprimento puro = 
Fornecimento original
Demanda em um nó de demanda puro = Demanda 
original
Fornecimento em um nó de transbordo = Fornecimento 
original + Quantidade tampão
Demanda em um nó de transbordo = Demanda original 
+ Quantidade tampão
A quantidade tampão deve ser sufi cientemente grande 
para permitir que todas as unidades de fornecimento (ou 
de demanda) originais passem por qualquer um dos nós de 
transbordo. Seja B a quantidade tampão desejada; então 
B = Fornecimento (ou demanda) total 
= 1.000 + 1.200 (ou 800 + 900 + 500) = 2.200 carros
Usando o tampão B e os custos unitários de expedição 
dados na rede, construímos o problema de transporte normal 
equivalente, como mostra a Tabela 15. A solução do problema 
de transporte resultante é mostrada na Figura 7. Observe o 
efeito do transbordo: a revendedora D2 recebe 1.400 carros, 
conserva 900 carros para satisfazer sua demanda e envia os 
500 carros restantes para a revendedora D3. 
Tabela 15 - Dados do problema de transbordo
Fonte: Taha (2008). 
Figura 7 - Solução de um problema de transbordo 
Fonte: Taha (2008).
Ao chegar ao fi nal da quarta aula, vamos recordar o 
que aprendemos:
Retomando a aula
 01 - Defi nição do problema de transporte
Nessa seção, estudamos a defi nição do problema do 
transporte a também um exemplo resolvido. Vimos que esse 
39
é uma classe específi ca de problemas, que busca, por exemplo, 
o menor custo de transporte entre várias rotas disponíveis 
para serem usadas. Na sequência, aprendemos a balancear 
problemas de transporte, e, fi nalmente, aprendemos a resolver 
esse tipo de problema usando o Excel Solver.
02 - O problema de designação (método húngaro)
Nessa seção, vimos que o problema de designação, ou 
método húngaro, consiste em um problema do transporte 
onde nós podemos indicar um recurso preferencial a 
ser utilizado, adicionando alguns passos na metodologia 
apresentada na seção 01, para que nosso problema seja 
resolvido com a indicação desejada.
03 - O problema de transbordo 
Finalmente, nessa última seção, vimos o último caso 
especial do problema do transporte, que é o problema do 
transbordo, que consiste em um problema do transporte, em 
que nós acrescentamos um caminho intermediário entre o 
fornecedor e o destino fi nal, e testamos qual é a rota mais 
econômica.
Hillier, F.S. e Lieberman G.J., Introdução à Pesquisa 
Operacional, 8ª. edição. São Paulo: McGraw-Hill, 2006.
Lachtermacher, G. Pesquisa operacional na tomada de 
decisões, 5ª. edição. São Paulo: Prentice Hall, 2016.
Taha, H. A. Pesquisa Operacional. 8ª edição. São Paulo: 
Pearson, 2008.
Vale a pena ler
Vale a pena
Minhas anotações