Calculadora do Problema de Transporte (Custo Mínimo + MODI)

O que o problema de transporte resolve

O problema de transporte é um dos modelos mais antigos e úteis da pesquisa operacional, e a sua pergunta é intensamente prática: dados vários lugares que podem ofertar um bem e vários que precisam dele, cada rota com o seu próprio custo unitário de envio, quanto deve mover por cada rota para atender toda a demanda a partir da oferta disponível ao menor custo total? É a matemática por trás de distribuir produto de fábricas a armazéns, de armazéns a lojas, de usinas de energia a regiões, ou qualquer situação onde um bem homogêneo flui de origens a destinos e o custo depende da rota. Como a estrutura se repete em toda a logística, o modelo é um pilar tanto da sala de aula quanto da caixa de ferramentas do planejador de distribuição.

O que torna o problema tratável e elegante é a sua estrutura. As únicas restrições são que cada origem envie exatamente a sua oferta e cada destino receba exatamente a sua demanda, e o objetivo é uma simples soma de custo de rota vezes unidades enviadas.

Essa forma especial significa que o problema sempre tem uma solução ótima inteira quando as ofertas e demandas são inteiras, e pode ser resolvido por métodos dedicados rápidos em vez de otimização de propósito geral.

Também significa que um problema balanceado, onde a oferta total iguala a demanda total, sempre tem solução viável, e qualquer desbalanceamento pode ser reparado adicionando uma origem ou destino fictício que absorva a diferença.

Esta calculadora encontra o plano de envios comprovadamente ótimo para qualquer problema de transporte que você informar. Digite a matriz de custos com uma origem por linha, liste as ofertas e as demandas, e ela devolve a alocação ótima, quantas unidades enviar por cada rota, junto com o custo total mínimo e o número de rotas usadas. Balanceia automaticamente os problemas não balanceados adicionando um fictício a custo zero e diz qual adicionou, e lida com a degeneração que faz as soluções à mão tropeçarem. Tudo roda no seu navegador e nada do que você informa é armazenado.

Como esta calculadora funciona, passo a passo

Comece com a matriz de custos. Informe uma origem por linha, e em cada linha coloque o custo unitário de envio a cada destino, separados por espaços ou vírgulas, mantendo os destinos na mesma ordem em cada linha. Depois liste as ofertas, um número por origem na mesma ordem das linhas, e as demandas, um número por destino na mesma ordem das colunas. A calculadora abre com um exemplo resolvido de três origens e quatro destinos já preenchido, para que você veja um plano ótimo completo e o seu custo antes de mudar qualquer coisa.

Assim que a entrada é válida a ferramenta resolve. Primeiro verifica se o problema está balanceado; se a oferta total e a demanda total diferem, adiciona uma origem ou destino fictício a custo zero para balanceá-las e anota isso abaixo do resultado. Depois constrói um plano viável inicial pelo método do custo mínimo e o melhora até o ótimo com o método MODI, lidando com qualquer degeneração pelo caminho. Todo o processo é instantâneo e roda de novo ao vivo enquanto você edita, então você pode explorar como mudar um custo ou uma oferta desloca o plano ótimo.

O painel de resultados encabeça com o custo total mínimo, depois mostra a alocação ótima como uma matriz: as linhas são as origens, as colunas são os destinos, e cada célula é quantas unidades enviar por aquela rota, com um ponto onde uma rota não é usada. Os totais de oferta e demanda emolduram a matriz para que você verifique que cada origem se esvazia e cada destino se enche. Abaixo, uma nota indica se o problema estava balanceado ou qual fictício foi adicionado, e um gráfico desdobra o custo total por origem. Baixe um PDF ou CSV do plano ou compartilhe; tudo acontece localmente.

Como o solucionador chega ao ótimo

A calculadora usa a abordagem de duas etapas que é padrão para o problema de transporte, porque a estrutura recompensa um método especializado muito mais eficiente que jogar o simplex geral nele. A primeira etapa produz um plano de início viável: o método do custo mínimo procura a rota disponível mais barata, envia o que a oferta e a demanda daquela rota permitem, risca o que se esgota e repete até alocar tudo. Isso dá um plano que já respeita cada oferta e demanda, e ao favorecer rotas baratas costuma começar perto do ótimo, embora raramente seja ótimo por si só.

A segunda etapa é o método MODI, que converte um plano viável no ótimo. Atribui a cada origem e cada destino um potencial, escolhido de modo que, para cada rota realmente usada, o potencial da origem mais o do destino seja igual ao custo daquela rota. Com esses potenciais, avalia cada rota não usada: se o custo da rota é menor que a soma dos seus dois potenciais, enviar unidades por ela baixaria o custo total, então o plano ainda não é ótimo.

O método então traça um ciclo fechado que alterna entre rotas usadas, desloca o máximo de unidades possível por esse ciclo para a rota que melhora e recalcula. Quando nenhuma rota não usada supera os seus potenciais, o plano é ótimo e o método para. A degeneração, quando há poucas rotas em uso para calcular os potenciais, é tratada inserindo uma rota de zero unidades, o que esta calculadora faz automaticamente para que o processo nunca trave.

Cinco exemplos resolvidos que você pode seguir

Exemplo 1: o problema balanceado padrão

A calculadora abre com três origens de oferta 35, 50 e 40 e quatro destinos de demanda 45, 20, 30 e 30, um problema balanceado já que ambos totalizam 125, com a matriz de custos mostrada. O plano ótimo envia a um custo total mínimo de 1.020. Ao ler a alocação, você pode ver quais rotas levam unidades e quais ficam vazias, e que cada origem é totalmente enviada e cada destino totalmente abastecido. Este é o problema canônico de livro-texto, e é bom para mudar um único custo e observar como o roteamento ótimo e o custo total se deslocam em resposta.

Exemplo 2: a oferta supera a demanda

Suponha que as origens podem ofertar mais do que os destinos precisam. Informe ofertas que totalizem mais que as demandas, e a calculadora balanceia o problema adicionando um destino fictício cuja demanda iguala o excedente e cujo custo de envio é zero de cada origem. O plano ótimo então roteia as unidades genuinamente necessárias ao menor custo e envia a oferta sobrante ao fictício. Ao ler o resultado, as unidades atribuídas a esse destino fictício são exatamente a oferta que convém deixar sem enviar, o que diz não só como enviar mas quanta capacidade é excedente e onde está.

Exemplo 3: a demanda supera a oferta

Agora o contrário: os destinos precisam de mais do que as origens podem prover. A calculadora adiciona uma origem fictícia cuja oferta iguala a falta, de novo a custo zero, e resolve. As unidades que o plano ótimo tira dessa origem fictícia são a demanda que não pode ser atendida, e a sua localização diz quais destinos ficam curtos no plano de mínimo custo. Isso é valioso na prática, porque quando você não pode atender todos o modelo mostra a forma mais barata de alocar o que você tem e torna explícita a falta inevitável em vez de escondê-la.

Exemplo 4: um caso pequeno verificável à mão

Experimente um problema de duas origens e dois destinos com custos 4 e 6 na primeira linha e 5 e 3 na segunda, ofertas 20 e 30, e demandas 10 e 40. O método do custo mínimo preenche primeiro a rota mais barata, a segunda origem ao segundo destino a custo 3, e o ótimo resulta em um custo total de 190. Um caso tão pequeno pode ser verificado à mão em um minuto, o que o torna uma boa forma de confirmar que você lê a matriz de alocação corretamente antes de confiar na ferramenta em um problema maior onde verificar à mão é impraticável.

Exemplo 5: ler o desdobramento de custos

Para qualquer problema resolvido, o gráfico mostra como o custo total se divide entre as origens, a soma de unidades enviadas vezes custo para as rotas de cada origem. Esta costuma ser a visão gerencial mais útil: diz qual ponto de oferta representa a maior parte da conta de envio, o que pode apontar onde uma redução de custo, um fornecedor mais próximo ou uma mudança de capacidade economizaria mais. A matriz de alocação diz como enviar; o desdobramento de custos diz para onde o dinheiro vai, e lê-los juntos converte o ótimo de um único número em um plano de distribuição acionável.

Três dicas de especialista para o planejamento de distribuição

Balancear a oferta e a demanda

Um problema de transporte só pode ser resolvido depois que a oferta total iguala a demanda total, porque a solução deve enviar cada unidade de oferta e preencher cada unidade de demanda, o que é impossível se os dois totais diferem.

Os problemas reais frequentemente estão não balanceados, uma rede de fábricas com mais capacidade que pedidos, ou um conjunto de lojas cujas necessidades excedem o que os armazéns contêm, então balancear é um primeiro passo rotineiro e não uma exceção.

A técnica padrão é adicionar um fictício, uma origem ou destino artificial que existe só para absorver o desajuste, com um custo de envio de zero em cada uma das suas rotas de modo que mude a viabilidade do problema sem mudar o seu custo real.

Qual fictício adicionar depende da direção do desbalanceamento, e a interpretação dos seus envios é onde está o valor prático. Quando a oferta supera a demanda, adiciona-se um destino fictício com uma demanda igual ao excedente; as unidades que o plano ótimo lhe envia são a oferta mais barata de deixar sem enviar, e a sua origem diz qual localização tem a capacidade em excesso.

Quando a demanda supera a oferta, adiciona-se uma origem fictícia com uma oferta igual à falta; as unidades tiradas dela são a demanda que não pode ser atendida, e o seu destino diz quem fica curto. Esta calculadora detecta o desbalanceamento, adiciona o fictício correto automaticamente, resolve a versão balanceada e indica na nota qual fictício usou, então você obtém tanto o plano ótimo para as rotas reais quanto uma leitura clara do excedente ou da falta.

Tratar o fictício como informativo e não como um mero conserto técnico é o que converte um problema não balanceado em uma percepção de capacidade ou serviço.

Um programa linear especial e bem comportado

O problema de transporte é formalmente um programa linear: minimizar o total de custo por unidades sobre todas as rotas, sujeito a que cada origem envie a sua oferta e cada destino receba a sua demanda, com todos os envios não negativos.

Em princípio você poderia dá-lo ao método simplex geral, o motor por trás da calculadora de programação linear, e obter a mesma resposta. Mas a sua estrutura é tão especial que merece e recompensa o seu próprio método, por isso tem um.

A matriz de restrições tem uma forma de rede particular na qual cada variável aparece em exatamente duas restrições, uma de oferta e uma de demanda, e essa forma é o que o simplex de transporte e o MODI exploram para resolver o problema com muito menos trabalho que o algoritmo geral.

Essa estrutura também entrega uma propriedade que os programas lineares gerais não garantem: a integralidade. Sempre que as ofertas e demandas são inteiras, o plano de envios ótimo sai inteiro automaticamente, sem necessidade da maquinaria mais dura da programação inteira. Isto não é sorte; segue de uma característica profunda da estrutura de rede, e é por isso que você pode confiar que as alocações da calculadora sejam quantidades enviáveis e não frações que teriam que ser arredondadas.

O problema de transporte também é o pai de dois parentes próximos: o problema de designação, que é um problema de transporte onde cada oferta e demanda é um, e o problema de transbordo, que permite nós intermediários que recebem e enviam.

Reconhecer o problema de transporte como um programa linear especialmente estruturado é o que o conecta à caixa de ferramentas de otimização mais ampla enquanto explica por que ele recebe um solucionador dedicado, e os seus potenciais tipo preço-sombra são a mesma informação dual que o programa linear geral produziria.

Erros comuns nos modelos de transporte

Um punhado de erros se repete e produz resultados errados ou confusos. Fique atento a eles.

• Esquecer de balancear. Resolver sem totais iguais não faz sentido. A calculadora balanceia automaticamente, mas se você balancear à mão, adicione o fictício do lado correto.
• Ignorar os envios do fictício. As unidades em uma linha ou coluna fictícia são informação real, o seu excedente ou falta, não apenas enchimento a descartar.
• Matriz desalinhada. Cada linha de custos deve listar um custo por destino na mesma ordem, e as ofertas e demandas devem coincidir com linhas e colunas. Uma entrada deslocada resolve um problema diferente em silêncio.
• Parar no plano inicial. Um início de canto noroeste ou custo mínimo é viável mas em geral não ótimo. Deve ser melhorado até a otimalidade, o que esta ferramenta faz; um plano por si só não é a resposta.
• Confundir custo com quantidade. A matriz contém custos unitários, enquanto o resultado contém unidades enviadas. Informar quantidades onde vão custos inverte todo o problema.
• Supor uma solução única. Alguns problemas têm vários planos ótimos com o mesmo custo total. Uma alocação diferente mas igualmente ótima não é um erro.
• Ler um envio fracionário como válido. Com ofertas e demandas inteiras o ótimo é inteiro; uma fração sinaliza um erro de digitação na entrada, não um plano real.

Onde este modelo se encaixa nas ferramentas

O problema de transporte está no grupo de otimização da pesquisa operacional, e o hub de Pesquisa Operacional o agrupa com os modelos que compartilham o seu DNA.

É um programa linear especialmente estruturado, então quando o seu problema é genuinamente sobre enviar de origens a destinos ao mínimo custo, esta ferramenta dedicada o resolve mais diretamente que o simplex geral dando o mesmo ótimo; quando o seu problema tem outra estrutura, a calculadora geral de programação linear é a escolha certa.

O problema de designação, emparelhar agentes com tarefas um a um, é o caso especial do problema de transporte onde cada oferta e demanda é um, e recebe a sua própria calculadora porque um método ainda mais rápido se encaixa nesse caso.

Além do grupo de otimização, o modelo de transporte se conecta com as ferramentas de cadeia de suprimentos pelas decisões que informa e consome. As ofertas que você informa costumam vir de posições de capacidade ou estoque calculadas em outra parte, e as demandas de previsões; o roteamento ótimo que produz alimenta as decisões de distribuição e logística que o silo de cadeia de suprimentos aborda.

Onde o problema de transporte encontra o plano de envios estático mais barato, a teoria das filas e os modelos estocásticos lidam com o tempo e a variabilidade dos fluxos pela rede, e a estrutura de custos que otimiza é justo o tipo de cifra que retroalimenta as decisões de projeto de rede e localização de instalações. Visto assim, é o núcleo quantitativo da distribuição a mínimo custo, um elo na cadeia da previsão à capacidade ao roteamento.

Volte ao hub de Pesquisa Operacional para o conjunto completo de modelos.

A origem do modelo

O problema de transporte tem uma linhagem distinta que espelha o nascimento da otimização em si.

Foi formulado pela primeira vez por Frank Hitchcock em 1941, por isso às vezes é chamado de problema de Hitchcock, e um trabalho estreitamente relacionado foi feito de forma independente pelo matemático soviético Leonid Kantorovich, cujo estudo da alocação ótima de recursos, incluindo o transporte de bens, foi parte do corpo de trabalho pelo qual dividiu o Nobel de economia de 1975.

Tjalling Koopmans, que dividiu esse prêmio, também trabalhou no transporte de carga durante a Segunda Guerra Mundial, e a relevância bélica do problema para mover materiais de forma eficiente ajudou a impulsionar o interesse inicial nele.

Os métodos de solução dedicados vieram logo após a teoria geral da programação linear. Uma vez que George Dantzig desenvolveu o método simplex no fim da década de 1940, a sua especialização para a estrutura de rede do problema de transporte seguiu logo, e os métodos MODI e do degrau se tornaram ferramentas de ensino padrão porque tornam visível a lógica da otimização sobre uma simples grade.

O problema perdura nos currículos e na prática pelas mesmas razões que no início: captura uma pergunta logística universal em uma forma simples de resolver à mão mas rica para ensinar as ideias centrais de viabilidade, otimalidade e dualidade.

Essa combinação, um problema real, uma estrutura limpa e um método transparente, é a razão de o problema de transporte continuar sendo uma primeira parada na pesquisa operacional décadas depois de Hitchcock tê-lo escrito, e de uma calculadora que o resolve até a otimalidade ser uma ferramenta de planejamento genuinamente útil e não apenas um exercício acadêmico.

As três formas de construir um plano inicial

Todo método para o problema de transporte começa construindo um plano viável inicial, um que satisfaça todas as ofertas e demandas sem se preocupar ainda com o custo, e três métodos clássicos o fazem com sofisticação crescente. O método do canto noroeste é o mais simples: comece na célula superior esquerda, envie o que a sua oferta e demanda permitirem, mova-se para a direita ou para baixo conforme cada uma se esgota, e continue até a célula inferior direita. Ele ignora o custo por completo, então é o mais rápido de aplicar à mão mas costuma produzir o plano inicial mais caro, deixando o maior trabalho para a etapa de otimização.

O método do custo mínimo, que esta calculadora usa, olha o custo enquanto constrói o plano: repetidamente encontra a célula mais barata que ainda tenha oferta e demanda disponíveis, envia o máximo possível ali e risca o que se esgote. Como preenche rotas baratas primeiro, costuma começar muito mais perto do ótimo que o canto noroeste.

A aproximação de Vogel (VAM) vai ainda mais longe, e muitas vezes é a melhor das três: para cada linha e coluna calcula uma penalidade, a diferença entre os dois custos mais baixos, que mede quanto a mais você paga se perder a rota mais barata, depois aloca à célula mais barata da linha ou coluna com a maior penalidade.

A VAM frequentemente chega ao plano ótimo de uma vez ou a uma iteração dele.

O ponto importante é que a escolha do método de início não muda a resposta final. Os três produzem um plano viável, e a etapa de otimização MODI leva qualquer plano viável ao mesmo custo ótimo; os métodos diferem apenas em quantos passos de otimização restam.

Esta calculadora otimiza até a otimalidade verdadeira independentemente do início, então você obtém o plano de mínimo custo garantido independentemente de o plano inicial de custo mínimo ter sido ótimo. Conhecer os três métodos ainda importa para os exercícios, onde muitas vezes se pede que você aplique um específico, e para a intuição de por que um bom início economiza trabalho.

A ideia de penalidade por trás do método de Vogel vale mesmo quando um computador faz a aritmética: as rotas a vigiar não são simplesmente as baratas mas aquelas onde ser forçado à segunda melhor opção custa mais.

Montar um problema de distribuição real

Traduzir uma situação logística real em um modelo de transporte é sobretudo questão de decidir o que são realmente as origens, os destinos e os custos, e fazê-lo de forma consistente.

As origens são onde o bem se origina e tem uma quantidade fixa disponível, fábricas, armazéns, portos ou fornecedores, e a oferta de cada uma é quanto pode enviar no período de planejamento.

Os destinos são onde é consumido e tem uma quantidade requerida, lojas, regiões, clientes ou fábricas a jusante, e a demanda de cada um é quanto precisa no mesmo período. Manter o período consistente, uma semana, um mês, uma estação, importa, porque a oferta, a demanda e o custo devem se referir ao mesmo horizonte ou o plano não faz sentido.

As entradas de custo são a parte mais sutil, porque devem ser por unidade e comparáveis entre todas as rotas. A escolha natural é o custo de mover uma unidade de uma dada origem a um dado destino, mas pode ser qualquer custo unitário linear que você queira minimizar, custo total posto no destino, distância, tempo de trânsito ou carbono, desde que use a mesma medida em tudo e realmente escale com o número de unidades.

Se uma rota é impossível, uma origem que não pode servir a um destino de forma alguma, dê a ela um custo muito grande para que o otimizador a evite em vez de deixá-la em branco.

O modelo pressupõe que o custo é estritamente proporcional à quantidade sem encargos fixos, sem descontos por volume e sem limites de capacidade em rotas individuais; quando esses recursos estão presentes, o modelo de transporte simples é uma aproximação, e a resposta honesta é aceitá-lo como uma estimativa de primeira instância ou passar a um modelo de rede mais rico.

Por fim, agregue com bom senso. Uma rede de distribuição nacional poderia ter centenas de lojas, mas agrupá-las em regiões com demanda combinada mantém o modelo pequeno o bastante para raciocinar sobre ele enquanto ainda captura a decisão de roteamento que importa. A arte de aplicar bem o modelo é escolher um nível de agregação fino o bastante para ser útil e grosso o bastante para ser tratável, e depois verificar que o plano resultante faça sentido físico antes de agir sobre ele. Um modelo é uma simplificação, e o valor de resolvê-lo está tanto na estrutura que ele obriga você a tornar explícita, quem pode servir a quem e a que custo, quanto nos números específicos que devolve.

Quando o modelo precisa de mais que isto

O problema de transporte simples é deliberadamente estreito, e conhecer os seus limites é parte de usá-lo bem.

Ele pressupõe um único bem homogêneo, um produto intercambiável entre todas as origens e destinos; quando vários produtos distintos compartilham uma rede e competem pela mesma capacidade, isso é um problema de fluxo multiproduto, que precisa de um modelo de rede mais geral.

Pressupõe que os bens se movem direto de uma origem a um destino; quando os envios podem passar por concentradores intermediários que recebem e reencaminham, o problema de transbordo estende o modelo tratando esses concentradores como nós que são ao mesmo tempo destinos e origens, e também pode ser reduzido a um programa linear tipo transporte mas com mais estrutura.

O modelo também pressupõe capacidade ilimitada em cada rota individual e custos puramente lineares. Quando uma rota específica só pode levar certa quantidade, um problema de transporte capacitado adiciona um limite superior a cada rota; quando os custos incluem encargos fixos por usar uma rota, ou quebram em limiares de volume, o problema se torna de encargo fixo ou por partes que precisa de métodos inteiros ou mistos.

Nenhum destes é razão para desconfiar do modelo simples nas muitas situações que de fato se encaixam, mas marcam o ponto onde você deveria buscar uma ferramenta mais capaz.

Esta calculadora resolve o problema de transporte clássico sem capacidade, de um único bem e com custo linear até a otimalidade, o que cobre a grande maioria dos problemas de ensino e boa parte das decisões reais de distribuição a mínimo custo; quando a sua situação tem capacidades, concentradores ou múltiplos produtos, trate a resposta dela como um limite e uma linha de base úteis e não como o plano final.

Formato de entrada e referência rápida

Informe a matriz de custos com uma origem por linha e um custo unitário para cada destino nessa linha, separados por espaços ou vírgulas, mantendo os destinos na mesma ordem entre linhas. Informe as ofertas como um número por origem em ordem de linha, e as demandas como um número por destino em ordem de coluna. Os totais não precisam coincidir; a calculadora balanceia automaticamente. A referência abaixo explica cada parte do resultado.

Perguntas frequentes

Fontes, aviso legal e transparência editorial

Esta calculadora resolve o problema de transporte com uma solução inicial de custo mínimo e o método de otimização MODI (u-v), a técnica padrão de pesquisa operacional (formulação de Hitchcock; simplex de transporte). Esta calculadora e este guia são criados e revisados pela equipe da OpsCalculators; consulte a nossa Política Editorial para saber como cada ferramenta é pesquisada, construída e testada.

Os resultados são estimativas precisas para planejamento e educação, não consultoria de engenharia certificada, e pressupõem um único bem homogêneo com custos lineares independentes da rota; os problemas de transbordo e multiproduto precisam de um modelo mais rico. Valide contra os seus próprios dados antes de comprometer envios. Consulte o nosso Aviso Legal completo. OpsCalculators.com é operado pela MAFHH INTERNATIONAL LTD. Os seus dados são processados no seu navegador e nunca são guardados; consulte a nossa Política de Privacidade.