No quadro de transporte a seguir, estão expostos os custos de transporte e as capacidades das origens e dos destinos. Determine o plano de transporte que minimiza o custo total.
d1 | d2 | d3 | oferta | |
o1 |
10 |
15 | 20 | 40 |
o2 | 12 | 25 | 18 | 100 |
o2 | 16 | 14 | 24 | 10 |
demanda | 50 | 40 | 60 |
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.
Bom dia Debora,
Parece-me que estão faltando critérios/restrições complementares de oferta e/ou de demanda para que o modelo convirja.
Qq dúvida entre em contato: 21 99151-8393 ou gfoborges@gmail.com.
Abraços,
Gustavo Borges
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.
Oi Débora, tudo bom?
Para resolver o problema, começaremos aplicando o método aproximado de Vogel. Primeiro temos que calcular as diferenças entre os 2 menores custos de cada linha e coluna.
d1 | d2 | d3 | dif | |
o1 | 10 | 15 | 20 | 5 |
o2 | 12 | 25 | 18 | 6 |
o3 | 16 | 14 | 24 | 2 |
dif | 2 | 1 | 2 |
A linha 02 possui a maior diferença, então começaremos por ela. Escolhemos nessa linha a posição com o menor custo e alocamos a maior quantidade possível(menor valor entre a demanda e custo disponíveis para este ponto). Desta forma, a tabela de distribuição ficará assim:
d1 | d2 | d3 | Oferta | ||||
o1 | _ | 10 | _ | 15 | _ | 20 | 40 |
o2 | 50 | 12 | _ | 25 | _ | 18 | 50 |
o3 | _ | 16 | _ | 14 | _ | 28 | 10 |
Demanda | 0 | 40 | 60 |
A seguir, repetimos os passos anteriores removendo as demandas e ofertas zeradas, até completar a tabela de distribuição, que ficará assim:
d1 | d2 | d3 | ||||
o1 | _ | 10 | 30 | 15 | 10 | 20 |
o2 | 50 | 12 | _ | 25 | 50 | 18 |
o3 | _ | 16 | 10 | 14 | _ | 28 |
O custo dessa distribuição é 50*12 + 30*15 + 10*14 +10*20 + 50*18 = 2290
O próximo passo é aplicar a técnica de Stepping Stone para verificar se a distribuição já está otimizada.
Para cada posição zerada, faremos o caminho fechado para ver se é possível encontrar uma solução com menor custo utilizando esse caminho.
o1d1 = 10 - 12 + 18 - 20 = -4
o3d1 = 16 - 14 + 15 - 20 + 18 - 12 = 3
o2d2 = 25 - 18 + 20 - 15 = 13
o3d3 = 28 - 14 + 15 - 20
A partir deste passo, percebemos que é possível reduzir o custo utilizando o vértice o1d1. Pegamos o menor valor entre os vértices que estão sendo subtraídos neste caminho (o2d1 e o1d3) e reajustamos a distribuição, que ficará assim:
d1 | d2 | d3 | ||||
o1 | 10 | 10 | 30 | 15 | _ | 20 |
o2 | 40 | 12 | _ | 25 | 60 | 18 |
o3 | _ | 16 | 10 | 14 | _ | 28 |
O custo dessa distribuição é 10*10 + 40*12 + 30*15 + 10*14 + 60*18 = 2250
Vimos que essa solução diminuiu o custo. Vamos aplicar novamente o método Stepping Stone para verificar se ainda há otimização a ser feita:
o3d1 = 16 - 14 + 15 - 10 = 7
o2d2 = 25 - 12 + 10 - 15 = 8
o3d1 = 20 - 10 + 12 - 18 = 4
o3d3 = 28 - 14 + 15 - 10 + 12 - 18 = 13
Como não achamos nenhum caminho com resultado negativo, comprovamos então que essa solução possui o menor custo.
Qualquer dúvida que tiver, estou à disposição. Um abraço!
Envie sua primeira dúvida gratuitamente aqui no Tira-dúvidas Profes. Nossos professores particulares estão aqui para te ajudar.