Problemas de Transporte: Conceitos e Resolução

Prévia do material em texto

Problemas de Transporte 
 
Um problema de transporte consiste basicamente em determinar as 
quantidades a serem transportadas de uma ou mais origens para um ou mais 
destinos de modo que o custo total referente a esse problema seja o menor 
possível. Para podermos resolver um problema de transporte, inicialmente 
precisamos conhecer as capacidades de cada origem, as demandas de cada 
destino e os custos unitários de transporte de cada origem para cada destino. 
Se o problema a ser resolvido possuir apenas uma origem, não há 
dificuldades em obtermos a solução ótima do problema. Basta iniciarmos a 
resolução do problema enviando a quantidade necessária da origem para o 
destino cujo custo unitário de transporte é o menor. Em seguida, enviaremos o 
que for necessário para o segundo destino de menor custo e assim por diante. 
Ao final do processo, se a demanda total for igual à capacidade da origem, não 
haverá falta e nem sobra do material transportado. Se a capacidade da origem 
for maior do que a demanda, teremos uma quantidade excedente em estoque. 
Se a demanda for maior do que a capacidade de fornecimento da origem, 
teremos falta do material transportado. É importante ressaltar que um ou mais 
destinos de maior custo unitário de transporte deixarão de receber esses itens. 
A figura a seguir exemplifica essa situação. 
 
Observe que a capacidade do depósito é de 1.200 unidades e que a 
demanda total referente às três lojas corresponde a 1.100 unidades. Nesse 
caso, como a oferta é maior do que a demanda, teremos um estoque de 100 
unidades no depósito. 
Fazendo a distribuição dos produtos, a solução do problema é dada por: 
De Para Quantidade Custo unitário Custo total 
Depósito Loja 1 300 21,00 6.300,00 
Depósito Loja 2 600 17,00 4.200,00 
Depósito Loja 3 200 15,00 3.000,00 
Estoque 100 0,00 0,00 
Total geral 13.500,00 
 
No caso de duas ou mais origens ou dois ou mais destinos, a solução do 
problema nem sempre é tão óbvia e nesses casos devemos recorres à pesquisa 
operacional para obtermos a solução ótima do problema. 
 Um problema de transporte é um caso particular de um problema de 
programação linear que pode ser resolvido pelo método simplex ou por 
métodos específicos desenvolvidos para esses tipos de problemas, tais como o 
método de Vogel, método do canto noroeste ou o método do custo mínimo. 
 Para que possamos aprender a resolver problemas de transporte, vamos 
considerar como exemplo, uma indústria fictícia de automóveis com duas 
unidades localizadas em Curitiba e São Paulo. A unidade de Curitiba possui 
20.000 automóveis e a unidade de São Paulo 25.000 automóveis a serem 
transportados para os portos de Santos, Paranaguá e Itajaí cujas demandas 
são, respectivamente, de 12.000, 16.000 e 8.000 veículos. 
 
 
 
 
 
 
 
Os custos unitários de transporte são apresentados na figura a seguir. 
 
 
Observe que o nosso objetivo é, sempre que possível, atender às demandas 
dos destinos, dentro das capacidades de cada origem, com o menor custo total 
de transporte. Nesse caso, a formulação do problema é dada por: 
 
min z = 400x11 + 150x12 + 280x13 + 110x21 + 380x22 + 410x23 
s.a. 
x11 + x12 + x13 <= 20000 
x21 + x22 + x23 <= 25000 
x11 + x21 >= 12000 
x12 + x22 >= 16000 
x13 + x23 >= 8000 
xij ≥ 0 onde xij é a quantidade de automóveis a serem transportados da fábrica 
i para o depósito j. 
 
Observe que a função objetivo apresenta como coeficientes os custos 
unitários de transporte de cada origem para cada destino. As restrições 
garantem que as quantidades transportadas não ultrapassem as capacidades 
de cada origem e também respeitam as demandas de cada destino. O sinal de 
menor ou igual (<=) é usado, pois a capacidade de cada destino é igual ou 
inferior a 20.000 e 25.000, respectivamente, ou seja, as quantidades ofertadas 
não podem ser maiores do que 20.000 e 25.000. As restrições que se referem 
às demandas são de maior ou igual (>=) por que a demanda mínima de cada 
destino deve ser suprida. 
 É claro que esse problema só terá solução se o sistema for equilibrado, 
ou seja, se a capacidade total for igual à demanda total. Caso a capacidade 
seja maior do que a demanda, haverá sobra em estoque. Para esse tipo de 
problema, devemos criar então um destino fictício. Mas o que é um destino 
fictício? É uma forma de representarmos matematicamente que haverá sobra 
em uma ou mais origens. Como essa quantidade excedente não será 
transportada, pois permanecerá em estoque, o custo de transporte de cada 
origem para o destino fictício é igual a zero. Podemos ter também uma 
demanda total maior do que a capacidade total das origens. Nesse caso haverá 
falta em um ou mais destinos. Matematicamente, a solução de um problema 
assim requer a criação de uma origem fictícia, também com custos de 
transporte nulos. A origem fictícia, além de possibilitar a resolução do 
problema, servirá também para indicar qual ou quais destinos não terão a 
demanda atendida. 
 Após a criação de uma origem ou de um destino fictício, a formulação do 
problema de transporte pode ser feita novamente. Nesse caso, podemos, além 
de adicionar a origem ou destino fictício, substituir as desigualdades por 
igualdades, já que o sistema passa a estar em equilíbrio. 
 No nosso exemplo, como a oferta 20.000+25.000=45.000 é maior do 
que a demanda que corresponde a 12.000+16.000+8.000=36.000, iremos criar 
um destino fictício cuja demanda corresponde a 45.000-36.000=9.000. Fazendo 
isso, a formulação fica assim: 
min z = 400x11 + 150x12 + 280x13 + 0x14 + 110x21 + 380x22 + 410x23 + 0x24 
s.a. 
x11 + x12 + x13 + x14 = 20000 
x21 + x22 + x23 + x24 = 25000 
x11 + x21 = 12000 
x12 + x22 = 16000 
x13 + x23 = 8000 
x14 + x24 = 9000 
xij ≥ 0 onde xij é a quantidade de automóveis a serem transportados da fábrica 
i para o depósito j. 
 Na prática, a quantidade a ser transportada para o destino fictício 
corresponde à quantidade que ficará no estoque. 
 A solução de um problema de transporte pode ser obtida pelo método 
Simplex. No entanto, devido às particularidades dos problemas de transporte, 
temos métodos exclusivos destinados à solução desses problemas. O uso 
desses métodos minimiza os esforços necessários para a obtenção da solução 
ótima.