O problema do transporte

Suponhamos que estamos na presença de uma série de fontes, cada qual com um determinado número de provisões. As provisões de cada uma das fontes terão de ser transportadas para um conjunto de clientes, os quais requerem, cada um, uma determinada quantidade de provisões. As provisões têm de ser transportadas das fontes para os clientes estando associado um custo de transporte por provisão entre cada fonte e cliente. Pretende-se determinar as quantidades de provisões que são transportadas de cada uma das fontes e os clientes de modo a minimizar o custo respectivo.

Não pretendo expor aqui uma descrição deste famigerado problema de optimização. No entanto, como iniciei o meu doutoramento na área, tenho ensaiado a implementação de alguns algoritmos dos quais conto precisamente com o que permite resolver este problema. Trata-se de uma variação do algoritmo do simplex e podemos encontrá-lo no livro Introduction to Operations Research de Hillier e Liberman.

Disponibilizo o código da minha implementação em C# aqui.

Para o utilizar, segue um pequeno exemplo de código:

int[] supplyVector = new int[4] { 50, 60, 50, 50 };
int[] demandVector = new int[5] { 30, 20, 70, 30, 60 };
double[,] costs = new double[4, 5] {
{ 16, 16, 13, 22, 17 },
{ 14, 14, 13, 19, 15 },
{ 19, 19, 20, 23, double.MaxValue },
{ double.MaxValue,0, double.MaxValue, 0, 0 } };
TransportationProblemDouble transportationProblem = new TransportationProblemDouble(
supplyVector,
demandVector,
costs);
transportationProblem.Run();
Console.WriteLine("z={0}", transportationProblem.ObjectiveFunctionValue);
for (int i = 0; i < transportationProblem.Results.GetLength(0); ++i)
{
for (int j = 0; j < transportationProblem.Results.GetLength(1); ++j)
{
Console.WriteLine("[{0},{1}]->{2}", i, j, transportationProblem.Results[i, j]);
}
}

A matriz que segue como exemplo provém do livro supracitado. Aproveito para referir que não testei o algoritmo em instâncias muito grandes.

No que concerne à implementação, recorri ao método de Russel para obter uma boa solução inicial. Contudo, considero pertinente referir que o de Vogel e o Norte-Oeste se encontram implementados apesar de não estarem a ser utilizados.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet, Matemática com as etiquetas , , , , . ligação permanente.

Uma resposta a O problema do transporte

  1. Pingback: O algoritmo do simplex revisto | Sérgio's space

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s