Transportes

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2384 palavras )
  • Download(s) : 0
  • Publicado : 13 de março de 2012
Ler documento completo
Amostra do texto
Problemas de Transportes


Problema de transportes

Problemas de transportes

Caso particular de programação linear Permite uma solução particular mais simples que o caso geral de PL Embora se chame “problema de transportes”, aplica-se em muitos outros casos

Aplicações de problemas de transporte
Fornecimento de água Distribuição de energia eléctrica Dimensionamento de redes detelecomunicações Aconselhar/prever escoamento de tráfego

Formulação geral (em rede)
Min custo
Origens Produtor (supplier) s1 Produtor s2 Destinos Consumidor (demand) d1 Consumidor d2

1 2

1 2



Xij Produtor sm


n
Custos cij Consumidor dn 3 3 4

m

Exemplo: P&T – Ervilhas enlatadas
Produz ervilhas enlatadas em três fábricas
Bellingham, WA, Eugene, OR, and Albert Lea, MN

P&T –Ervilhas enlatadas
1 2 2

Envia em camiões a produção para quatro armazéns
Sacramento, CA, Salt Lake City, UT, Rapid City, SD, and Albuquerque, NM
1

Pode-se estimar as capacidades de produção, as necessidades para os armazéns, e os custos dos transportes Quere-se minimizar os custos em transportar as latas !

1

Problemas de Transportes
V 1.2, V.Lobo, EN / ISEGI, 2008

Dados doproblema
Quantidades produzidas nas fábricas Quantidades necessárias nos armazéns Matriz de custo dos transportes
Armazem fabrica 1 2 3
Procura
(camiões)

Formulação como rede
Produtores Origens Consumidores Destinos
D1 80 (Sa cr amento)

1 $ 464 $ 352 $ 995 80

2 $ 513 $ 216 $ 682 65

3 $ 654 $ 690 $ 388 70

4 $ 867 $ 791 $ 685 85

oferta
(camiões)

464
(Be llingham) 75 S1513 867 654
D2 65 (Sa lt La ke City)

75 125 100 300

352
(E ugene) 125 S2

416 791 690 682 388 685
D4 85 (Albuquerque ) D3 70 (Rapid Cit y)

995
(A lber t Le a) 100 S3

Formulação como PL
Variáveis de controlo: quantidade xij transportada entre a fábrica i e o armazém j Em cada fábrica i :
xi1 + xi2 + xi3 +…. = si capacidade de i procura de j

Formulação como PL
Minimizar =$464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22 + $690x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34 Sugeito a x11+x12+x13+x14 = 75 = 125 = 100 = 80 = 65 = 70 = 85

Em cada armazém j :
x1j + x2j + x3j +…. = di

x21+x22+x23+x24

x31+x32+x33+x34

Custo a minimizar
Z = c11x11+ c12x12+ c21x21+ …+cijxij

x11

x12

x13

x14

+ x21 + x31 +x22 +x32 +x23 +x33 +x24 +x34Características do PT
Forma da matriz simplex
Temos muitos 0, e alguns 1 (matriz binária) Cij só aparecem na função a minimizar Todas as restrições são IGUALDADES Muitas variáveis de decisão (n x m) “forma característica” m n Forma balanceada: s = d

Ideia geral do método dos transportes
Não vamos ter necessidade de usar “M” e variáveis artificiais
Vamos usar outras variáveis auxiliares, masque são em menor número que as tradicionais

Vamos construir um novo tipo de tabela
Tabela do Problema de transportes


i =1

i


j =1

2 passos:
Obter solução inicial Iterar o passo de optimização até ter a solução óptima

j

2

Problemas de Transportes
V 1.2, V.Lobo, EN / ISEGI, 2008

Ideia geral do método dos transportes
Obtenção de solução Obtenç soluç inicialTabela do método dos transportes
Destinos Origens 1 c11 c21 … cm1 d1 cm2 d2 1 c12 c22 … 2 … … … … … … cmn dn c1n c2n … n Oferta s1 s2 … sm Z= ui

Verifica o critério de crité optimalidade? optimalidade?

Sim FIM !!! a solução é soluç óptima

2 … m Procura vj

Não Escolher a variável de entrada variá e saída, e ajustar a tabela saí

Cada quadrícula da tabela
Se xij for variável básica(≠0) Se xij for não-básica (=0) Variáveis auxiliares Ui e Vj
Cij
Cij-ui-vj

Determinação de uma solução inicial
Método do “canto noroeste” xij
Mais simples e fácil de entender A solução inicial pode ser longe de óptima

Cij

Método dos “mínimos custos”
Mais complexo, mas melhor solução inicial

Correspondem às variáveis duais Calculadas a partir dos coeficientes das variáveis básicas:...
tracking img