Cap tulo IV

5. O problema de Transportes

5.1 Problemas particulares de programação linear
Uma grande variedade de problemas de Programação Linear, aparentemente não relacionados, tais como, programação sequencial da produção, afectação de pessoal, gestão de tesouraria, entre outros, pode ser formulado como problemas de transporte. É no entanto o problema de transporte clássico, que atribui esta designação a estes problemas. 5.2 O Problema de transporte

O problema clássico de transporte surge com a necessidade de programar a distribuição óptima de um produto homogéneo, que:
1. Se encontra disponível em m origens nas quantidades fixas, a i  0 (oferta), com i=1,2,...,m; 2. É necessário em n destinos nas quantidades fixas b j  0 (procura), com j=1,2,...,n; 3. Deve ser enviado directamente para os destinos, esgotando as disponibilidades em cada origem e satisfazendo as necessidades em cada destino, isto é, procura total igual a oferta total e tendo como objectivo a minimização do custo total envolvido no programa de distribuição desse produto. Considera-se que os custos unitários de transporte de cada origem i para cada destino j, Cij, são independentes das quantidades transportadas xij.
Existem vários tipos de representação para um problema de transporte:

38

 Rede
 Quadro
 Formulação matemática.

Representação em forma de rede de transporte
Quer uma SBA quer a solução óptima de um problema de transporte podem ser representadas sob a forma de rede. A representação genérica desta forma apresenta-se de seguida:
Origens
a1 ai am

Destinos

1

1

... i … m ... j … n b1 bj bn

Rede do problema de transporte
Os arcos que ligam as origens aos destinos representam os percursos através dos quais o produto pode ser transportado.
Representação em forma de quadro
Facilita a formulação do problema de transporte. Cada linha do quadro corresponde a uma origem e cada coluna a um destino. A última coluna contém a informação relativa às quantidades disponíveis nas origens e a última