Método do Custo Mínimo

Prévia do material em texto

Método do Custo Mínimo 
 
 Vamos aprender a resolver um problema de transporte utilizando o 
método do custo mínimo. Como exemplo, vamos considerar a indústria fictícia 
de automóveis com duas unidades localizadas em Curitiba e São Paulo. 
Sabemos que 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 e que os custos unitários de transporte são apresentados na 
figura a seguir. 
 
 
 
 O primeiro passo é construir uma tabela com as ofertas, demandas, 
custos unitários de transporte e também com um espaço para que possamos 
anotar as quantidades que serão transportadas. 
 
 
 
 Para iniciarmos a solução do problema de transporte pelo método do 
custo mínimo, teremos que anotar o máximo que pode ser transportado na 
célula de menor custo. Havendo empate, a escolha é feita de forma aleatória. 
Nesse caso, iremos colocar 9.000 na célula (1,4) que corresponde à quantidade 
a ser transportada de Curitiba para o destino fictício. 
 
 
 
 É importante reduzir o valor adicionado da coluna da capacidade e da 
linha da demanda para que as capacidades e as demandas estejam sempre de 
acordo com o que já está sendo transportado. 
 Iremos escolher agora a próxima célula de menor custo. Fazendo isso, 
deveremos adicionar 12.000 na célula (2,1). 
 
 
 
 Em seguida, colocaremos 11.000 na célula (1,2). 
 
 
 
 
 Observe que sempre iremos escolher a célula de menor custo. Agora 
devemos colocar 5.000 na célula (2,2). 
 
 
 
 Finalmente basta adicionar 8.000 na célula (2,3). 
 
 
 Observe que nessa solução inicial todas as demandas estão sendo 
atendidas e todas as capacidades foram utilizadas. A quantidade referente ao 
destino fictício corresponde ao estoque que na realidade não será enviado. 
 
 Os dados da solução inicial são os seguintes: 
 
 
 
 A solução inicial é viável, mas por enquanto não sabemos se essa 
solução, de fato, possui o menor custo total para o envio dos automóveis das 
fábricas para os devidos portos. 
 
 Para sabermos se a solução obtida é ótima, precisamos calcular os 
custos reduzidos denotados por dij. Para as variáveis básicas, isto é, as variáveis 
que fazem parte da solução, os custos reduzidos são iguais a zero. Para as 
variáveis não básicas, esses custos reduzidos são diferentes de zero. Caso 
algum custo reduzido referente a uma variável não básica seja negativo, temos 
que a solução atual não é ótima e que o custo total de transporte pode ser 
menor do que o atual. 
 
 
 
 As variáveis ui e vj são conhecidas como variáveis duais. Essas variáveis 
serão utilizadas para o cálculo dos custos reduzidos. 
 Vamos calcular os valores das variáveis duais. Como ainda não temos o 
valor dessas variáveis, inicialmente iremos atribuir o valor zero para a variável 
u1. Com isso é possível encontrar o valor de v2. 
 
 
 
 Tendo o valor de u1, é possível também encontrarmos o valor de v4. 
 
 
 Com o valor de v2, podemos calcular o valor de u2. 
 
 
 
 Seguindo essa idéia, é possível agora encontrarmos o valor de v1. 
 
 
 Finalmente, com o valor de u2, podemos encontrar o valor de v3. 
 
 
 
 Para sabermos, então, se a solução é ótima, iremos agora calcular os 
valores dos custos reduzidos referentes às variáveis não básicas. 
 
 
 
 O que fazer então? 
 O valor negativo referente à variável não básica x24 indica que se essa 
variável entrar na base, ou seja, se transportarmos tantos veículos quanto 
forem possíveis de São Paulo para o depósito fictício, teremos uma redução no 
custo total de transporte. Apenas ressaltando, transportar veículos para o 
depósito fictício, na prática, significa que esses veículos ficarão no estoque. 
 Uma maneira bem simples de alterarmos as quantidades a serem 
transportadas, sempre respeitando a capacidade de cada depósito e a demanda 
de cada destino, é traçarmos um caminho onde os vértices são formados por 
variáveis básicas. 
 
 
 
 Como o nosso objetivo é colocar a variável x24 na base, isto é, 
transportar o máximo possível de São Paulo para o destino fictício, precisamos, 
primeiramente, saber qual é o valor máximo a ser transportado. Para isso, 
vamos verificar quais são os valores pertencentes aos vértices do caminho e, 
depois disso, vamos escolher o menor deles. 
 Os valores que pertencem aos vértices do caminho são: 5.000, 11.000 e 
9.000. Como o menor deles é igual a 5.000, vamos colocar 5.000 na célula 
(2,4). Para continuarmos atendendo às demandas e as capacidades, termos 
que somar e subtrair 5.000 dos vértices, alternadamente. 
 Vamos ver como isso pode ser feito. 
 
 Note que adicionamos 5.000 na célula (2,4) e subtraímos 5.000 da célula 
(2,2). Em seguida, somamos 5.000 na célula (1,2) e, finalmente, subtraímos 
5.000 da célula (1,4). Fazendo isso, as capacidades e demandas continuam 
sendo atendidas e a variável x24 entrou na base, fazendo com que a variável x22 
saísse da base. 
 Com essas alterações, a nossa tabela ficou assim: 
 
 
 
 É importante ressaltar que a mudança implicou em uma redução no 
custo total de transporte. 
 
 
 
 No entanto, ainda não sabemos se essa nova solução é a solução ótima 
ou se ainda podemos obter uma solução de menor custo. 
 Para verificarmos se a solução ainda pode ser melhorada, vamos calcular 
os custos reduzidos. Para isso precisamos, primeiro, dos valores das variáveis 
duais u e v. 
 
 
 
 
 
 
 
 
 
 
 Agora que já calculamos os valores das variáveis duais, vamos calcular 
os custos reduzidos para cada variável não básica. 
 
 
 
 Nesse caso, a variável x13 deverá entrar na base. Vamos fazer o caminho 
para determinarmos qual variável deixará de ser básica. 
 
 Observe que o menor valor das células que forma o caminho é 4.000. 
Logo, iremos somar e subtrair, alternadamente, esse valor, no caminho 
escolhido. 
 
 
 
 As novas quantidade a serem transportadas de cada origem para cada 
destino são: 
 
 
 
 É possível perceber que houve, mais uma vez, uma redução do custo 
total de transporte conforme o esperado. 
 
 
 
 Mas ainda não sabemos se essa solução é a solução ótima ou ainda não. 
Novamente teremos que obter os valores dos custos reduzidos referentes às 
variáveis não básicas e, para isso, teremos que calcular os valores das variáveis 
duais como já fizemos anteriormente. 
 
 
 
 
 
 
 
 
 
 
 Agora que já temos os valores das variáveis duais, vamos calcular os 
custos reduzidos.