Pesquisa operacional

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2588 palavras )
  • Download(s) : 0
  • Publicado : 2 de setembro de 2011
Ler documento completo
Amostra do texto
Problemas de Transportes
V 1.2, V.Lobo, EN / ISEGI, 2008

Problemas de transportes

Problema 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

1

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

Aplicações de problemas detransporte
Fornecimento de água Distribuição de energia eléctrica Dimensionamento de redes de telecomunicaçõ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

m

2

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

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

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

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

P&T – Ervilhas enlatadas
1 2 2 3

3

1

4

3

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

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

1 $ 464 $ 352 $ 995 80

2 $ 513 $ 216 $ 682 65

3 $ 654 $ 690 $388 70

4 $ 867 $ 791 $ 685 85

oferta
(camiões)

75 125 100 300

Formulação como rede
Produtores Origens
464
(Be llingham) 75 S1

Consumidores Destinos
D1 80 (Sa cr amento)

513 867 654
D2 65 (Sa lt La ke City)

352
(E ugene) 125 S2

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

995
100 (A lber t Le a) S3

4

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

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

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

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

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

x21+x22+x23+x24

x31+x32+x33+x34

x11

x12

x13

x14

+ x21 + x31 +x22 +x32 +x23 +x33 +x24 +x34

5

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

Caracterí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


i =1

i


j =1

j

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, mas que são em menor número que as tradicionais

Vamosconstruir um novo tipo de tabela
Tabela do Problema de transportes

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

6

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ç inicial

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

Sim FIM !!! a solução é soluç óptimaNão Escolher a variável de entrada variá e saída, e ajustar a tabela saí

Tabela do método dos transportes
Destinos Origens 1 2 … m Procura vj cm1 d1 c11 c21 … cm2 d2 1 c12 c22 … 2 … … … … … … cmn dn c1n c2n … n Oferta s1 s2 … sm Z= ui

7

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

Cada quadrícula da tabela
Se xij for variável básica (≠0) Se xij for não-básica (=0)...
tracking img