aula10 problema transporte

Problema de Transporte

Prof. M.Sc. Fábio Francisco da Costa
Fontes



O problema de transporte é uma classe especial de problema de programação linear que trata do envio de uma mercadoria de origens (por exemplo, fábricas) para destinos (por exemplo, depósitos). O objetivo é determinar a programação de expedição que minimize o custo total de expedição e, ao mesmo tempo, satisfaça os limites de fornecimento e demanda.

A aplicação do problema de transporte pode ser estendida a outras áreas de operações, entre elas controle de estoque, programação de empregos e designação de pessoal.

Definição do problema


O problema geral é representado pela rede na figura a seguir:
Origens
a1 1 a2 am

:

2

m

c11:x11

Destinos
1 b

1

:

2

n

b2

bn

Há m origens e n destinos, cada um representado por um nó. Os arcos representam as rotas que ligam as origens aos destinos. O arco (i, j), que liga a origem i ao destino j, nos dá duas informações:



O custo de transporte por unidade cij



A quantidade enviada, xij
A quantidade de suprimento na origem i é ai e a quantidade de demanda no destino j é bj. O objetivo do problema é determinar as incógnitas xij que minimizarão o custo total de transporte e, ao mesmo tempo, satisfarão todas as restrições de suprimento e demanda.

Esta classe de problemas recebeu este nome porque seu método de resolução, denominado Método de Transporte, foi inicialmente utilizado para determinar o menor custo de transporte entre diversas fábricas de um produto e diversos centros consumidores.

O Método de Transporte resolve esta classe de problemas de programação linear de uma maneira mais eficiente que o Simplex tradicional.
Porém o Método de Transporte foi especialmente utilizado antes da era da microcomputação, ou seja, nos primórdios da Pesquisa Operacional, para aperfeiçoar cálculos feitos a mão.

Com o advento dos computadores pessoais, cada vez mais rápidos e com maior capacidade de processamento, diversos sistemas automatizados de