Pesquisa operacional

Disponível somente no TrabalhosFeitos
  • Páginas : 13 (3148 palavras )
  • Download(s) : 0
  • Publicado : 11 de junho de 2011
Ler documento completo
Amostra do texto
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 maiseficiente, 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 encontradisponí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 custototal 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 detransporte 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. No quadro seguinte pode ver-se que em cada linha está a informação relativa a uma origem, e cada coluna a um destino. A última coluna contém informação relativa às quantidades disponíveis nasorigens e a última linha contém informação referente às quantidades necessárias nos destinos. Em cada quadrícula (i,j), encontra-se a quantidade a transportar da origem i para o destino j, xij, e o correspondente custo unitário de transporte, cij. Para qualquer plano de transporte admissível a soma em linha dos xij iguala a quantidade ai, ∑ xij = ai e a soma dos xij iguala a quantidade b j , ∑ xij = bj . O custo
j
i

do percurso (i,j) é dado por cij × xij , pelo que o custo total do plano de transporte é dado por

∑∑ c
i j

ij

xij .

Destino 1 Origem 1 2 ... n OFERTA

c11 x11 x12 c21 x21 x22
... ...

c12 c22

... x1n ... x2n
... ...

c1n
a1

2

c2n
a2
...

...

m

cm1 xm1 xm2
b1 b2

cm2

... xmn
...

cm3

am bn

PROCURA

∑a = ∑b
i

i

Aformalização matemática do problema de transporte como problema de programação linear vem então: Minimizar z = ∑∑ cij xij Sujeito a

∑x ∑x
i j

i

j

ij

= ai = bj

(i = 1,2,..., m) ( j = 1,2,..., m)

restrições de oferta restrições de procura

ij

xij ≥ 0
Cristina Canavarro

(i = 1,2,..., m; j = 1,2,..., n)
2005 57

Exemplo
Certa empresa possui dois armazéns, A1 e A2,onde dispõe de 100 e 50 unidades de determinado produto, respectivamente, com o que abastece três mercados, M1, M2 e M3, que consomem 80, 30 e 40 unidades. Sabendo que os custos de transporte são dados no quadro

A1 A2

M1 5 4

M2 3 2

M3 2 1

A formalização do problema – minimização do custo total de transporte – vem: Minimizar z = 5 x11 + 3x12 + 2 x13 + 4 x 21 + 2 x 22 + x 23 sujeito a...
tracking img