Introdução

O problema de Transporte é uma categoria de Programação Linear que trata do envio de mercadorias de uma origem até um determinado destino. O objetivo é determinar a expedição da mercadoria com custo e tempo ótimos e que atenda os limites de fornecimento e demanda. A analogia feita sobre mercadorias pode ser estendida a controle de estoque, programação de empregos, entre outros. As etapas do algoritmo de Transporte são as mesmas do Simplex.

O problema geral descrito na imagem abaixo, consiste em m origens e n destinos, cada um representado por um nó. Os arcos representam o trajeto entre origem e destino. Em um trajeto, são determinadas duas características:

• 1) O custo de transporte por unidade em um trajeto;
• 2) A quantidade enviada.

O objetivo do problema é determinar essa quantidade enviada ótima, de forma a satisfazer as restrições de demanda e suprimento.

O algoritmo para o problema de Transporte

O algoritmo para o problema de Transporte seguem as mesmas etapas do Simplex. Abaixo vemos essas etapas em paralelo com as etapas do Simplex.

Podemos escolher três métodos para garantir uma solução básica inicial não artificial:

• 1) Método do canto noroeste;
• 2) Método do menor custo;
• 3) Método de aproximação de Vogel (MAV).

Método do canto noroeste

O método começa na célula do canto noroeste da tabela Simplex. Abaixo veremos as etapas do método.

Método do menor custo

O método acha uma solução inicial melhor baseando-se nas rotas mais baratas. A rota designa o máximo a célula que tiver o menor custo unitário (empates são resolvidos arbritariamente). Logo após, a linha ou coluna que foi satisfeita é cancelada e as quantidades de fornecimento ou demanda são ajustadas.

Se tanto linha como coluna forem satisfeitas, apenas uma delas será cancelada. Logo após, procure a célula não cancelada de menor custo e repita todo o processo até que reste apenas uma linha ou coluna não cancelada.

Método de aproximação de Vogel (MAV)

O MAV é uma versão melhorada do método de menor custo, que em geral, produz soluções iniciais melhores. As etapas do método são descritas abaixo.