Matemática

CAPÍTULO 6

Problemas de Transportes e de Afectação

1. Problema de Transporte
Este problema, que é um dos particulares de PL, consiste em determinar a forma mais económica de enviar um bem disponível, em quantidades limitadas, em determinados locais para outros locais onde é necessário. Como qualquer problemas de PL, também este pode ser resolvido pelo método Simplex. Porém, a sua estrutura própria permitiu a utilização de métodos que, embora derivados do Simplex, são mais eficientes. Existem muitos problemas de PL, que podem ser formulados como de transporte, apesar de, aparentemente, não existir qualquer relação com este tipo de problemas. O problema clássico de transporte surge com a necessidade de programar a distribuição óptima de um produto homogéneo que : a) encontra-se disponível em m origens nas quantidades fixas ai > 0 (oferta), com i = 1, …, m; b) é necessário em n destinos nas quantidades fixas bj > 0 (procura), com j = 1, 2, …, n; c) deve ser enviado directamente para os destinos, esgotando as disponibilidades em cada origem e satisfazendo as necessidades em cada destino (a procura total iguala a oferta total); e tendo por objectivo a minimização do custo total envolvido no programa de distribuição desse produto, em que se supõe que os custos unitários de transporte da cada origem i para cada destino j, cij, são proporcionais às quantidades transportadas, xij.

70

Problema de Transporte

Figura 1. Rede do Problema de Transporte. A Figura 1 ilustra o problema de transporte sob a forma de uma rede com m origens e n destinos representados por nós; os arcos que ligam as origens aos destinos representam os percursos através dos quais o produto pode ser transportado. Uma outra forma de representar este problema, consiste na utilização de um quadro (ver Quadro 1), em que,
• cada linha corresponde a uma origem, • cada coluna corresponde a um destino, • a última coluna contém a informação relativa às quantidades disponíveis nas origens, • a