Pesquisa operacional

5. Problema de Transporte
O Problema de Transporte é talvez o mais representativo dos Problemas de Programação Linear. É um problema de grande aplicação prática, tendo sido estudado por vários investigadores, embora tenha sido Dantzig o primeiro a estabelecer a sua formulação em PL e a propor um método sistemático de resolução. O problema geral de transporte consiste em determinar a forma mais eficiente, isto é, mais económica de enviar um bem disponível em quantidades limitadas em determinados locais para outros locais onde é necessário. Como qualquer problema de PL, este pode ser resolvido pelo método do simplex.. Porém a sua estrutura particular, permitiu a utilização de métodos que embora derivados do simplex, são bastante mais eficientes. A resolução de um problema de transporte, envolve basicamente três etapas: a 1ª consiste em encontrar uma solução básica inicial; na 2ª procede-se ao teste para verificar se essa solução é óptima ou não; finalmente esta fase consiste na passagem desta solução a outra melhor, caso exista evidentemente. 5.1. Formulação O problema clássico de transporte surge como necessidade de programar a distribuição óptima de um produto que: 1. se encontra disponível em m origens nas quantidades fixas ai>0 (oferta), com i=1,2,...,m. 2. é necessário em n destinos nas quantidades fixas bj>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 é, 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 de cada origem para cada destino, cij, são independentes das quantidades transportadas, xij. ORIGENS a1 1 …. Oferta ai ... am
Cristina Canavarro

DESTINOS c11 x11 1 ... cij xij cmn xmn
2005

b1

i

j ... n

bj

Procura

m

bn
56

Esta figura ilustra o problema de