Transporte em Tempo Mínimo
Prof. Fernando Augusto Silva Marins
Departamento de Produção
Faculdade de Engenharia – Campus de Guaratinguetá
UNESP
www.feg.unesp.br/~fmarins
[email protected]
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
1
Introdução
• Modelo do transporte a tempo mínimo se propõe a atender as
demandas de diferentes mercados no menor tempo possível.
• Exemplos: produtos perecíveis devem ser transportados, ou
quando suprimentos militares devem ser enviados às frentes de
combate durante uma emergência.
• Admite-se a existência de m fábricas com capacidade de produção
, , a 2 , , a m ,que devem abastecer n depósitos com demandas
a1
m
n
b1 , b 2 ,, b n tais que: . a i   b j
i 1
j1
t ij
• Seja
o tempo gasto com o transporte do produto da fábrica i
para o depósito j, independentemente da quantidade transportada.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
2
Introdução
• Transportes das fábricas para os depósitos podem ser feitos
simultaneamente, e todas as fábricas produzem um único
produto.
• Para um plano de transporte: a entrega que for a mais demorada
determinará o tempo requerido para se completar este plano de
transporte.
• Deseja-se completar todas as entregas no menor tempo possível.
• T= tempo requerido para completar todas as entregas de um determinado
plano de transporte  T  M axt ij 
para todo par (i, j), x ij > 0,
Sendo x ij = quantidade a ser transportada da fábrica i ao depósito j.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
3
Transporte em Tempo Mínimo
• Objetivo: encontrar x ij que satisfaçam as restrições de oferta e
demanda e minimizem o tempo de entrega t.
• Algoritmo usa o mesmo tipo de quadro de resolução aplicado no
“Stepping stone method”.
• Observações sobre as etapas de aplicação do algoritmo:
• Para achar uma solução básica viável inicial: usar um método
análogo ao da regra do menor custo, aplicado aos tempos de
entrega.
• Com um procedimento análogo ao do “Stepping Stone Method”
podem ser encontradas soluções básicas viáveis melhores, se
existirem.
• A regra para selecionar a variável não-básica, que se tornará
variável básica na próxima solução básica viável, sofre
modificações.
4
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
Algoritmo
• Passo i: achar solução básica viável inicial com m+n-1 variáveis básicas
pela “regra do menor tempo de entrega”. ir ao Passo ii.
• Passo ii: calcular o tempo de entrega , T  M axt ij  , xij  0
associado a
solução básica viável atual. ir ao Passo iii.
• Passo iii: eliminar todas as variáveis não-básicas onde tij > T. (basta
bloquear estes trajetos). ir ao Passo iv.
• Passo iv:
Colocar o valor -  para a variável básica com tij = T.
Construir um ciclo de compensação com as variáveis básicas e uma das
variáveis não-básicas que não tenha sido eliminada no Passo iii:
Colocar +  ou -  nas células que compõem o ciclo.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
5
Algoritmo
•
Colocar +  na célula não-básica escolhida pois ela deverá receber
unidades do produto das variáveis básicas “doadoras” associadas ao
valor do ciclo.
• Se nenhum ciclo puder ser encontrado  solução básica viável atual é
ótima (FIM). Caso contrário ir para o Passo v.
• Passo v: aumentar  mantendo as variáveis básicas do ciclo  0. Sairá
da solução básica atual a variável básica que se anular primeiro e temse uma nova solução básica viável. Voltar ao Passo ii.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
6
Exemplo
• Achar o plano de entrega do problema de transporte a tempo mínimo,
com a1 = 3, a2 = 7, a3 = 5, b1 = 4, b2 = 3, b3 = 4 e b4 = 4. Os tempos de
transporte são:
D
D
D
D
1
2
3
4
O1
2
2
2
1
O2
10
8
5
4
O3
7
6
6
8
• Resolução:
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
7
Exemplo
T  Maxt14 ,t 21,t 23 ,t 24 ,t 31, t 32   t 21  10
• As células não básicas têm
t ij  10
assim nenhuma será eliminada.
• A variável básica x21 tem o maior tempo de entrega colocar -  nesta
célula e achar um ciclo: O2D1 O2 D2 (não básica), O3 D1 e O3 D2
• No ciclo: maior  = 2, a variável não-básica O2D2 entra, saindo a
variável básica x21. A nova solução básica viável está no quadro 2:
Quadro 2
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
8
Exemplo
• O tempo de entrega T=8 da variável x22. As variáveis não básicas x21 e
x34 serão eliminadas pois tem t ij  8
• Novo ciclo x 22 , x 24 , x14 e x12(Não básica). O maior valor para  é 2 e a
nova solução básica está no quadro 3.
Quadro 3
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
9
Exemplo
• Tempo de entrega T=7, da variável básica x31.
• Novo ciclo
x 31 , x 32 , x12 e x11
(não básica) .O maior valor para  é 2, o
que implica que x12 sai para a entrada de x11 na nova solução básica. A
variável básica com o maior tempo de entrega x31 permaneceu
• Nesta solução atual (quadro 4)  T = 7.
• Quadro 4
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
10
Exemplo
• Tempo de entrega T=7, da variável básica x31.
• Novo ciclo: x31 , x11 , x14 , x24 , x23 e x33 (Não básica)
• Maior valor para  é 1  x14 será substituída por x 33 (quadro 5).
Quadro 5
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
11
Exemplo
• Tempo de entrega T=7, correspondente a variável básica x31.
• Não há ciclo a partir de x31.
• O quadro 5 representa, portanto uma solução ótima.
Quadro 5
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
12
Exemplo
•
•
•
•
•
•
•
•
Plano de entrega ótimo:
Enviar 3 unidades de o1 para d1,
Enviar 3 unidades de o2 para d3,
Enviar 4 unidades de o2 para d4,
Enviar 1 unidades de o3 para d1,
Enviar 3 unidades de o3 para d2,
Enviar 1 unidades de o3 para d3,
Menor tempo possível: 7.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
13