Modelo de
Transporte com Baldeação
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
1. Neste modelo de transporte mais geral há a possibilidade de um
nó da rede não ser nem origem nem destino, ou seja, a demanda
(ou produção) nele é nula (bi = 0). Esse tipo de nó recebe o nome
de nó de transbordo.
2. Apresenta-se a seguir um algoritmo proposto por Alex Orden
que estende a abordagem feita para o modelo de transporte simples
(“Stepping Stone Method”) de forma que seja permitida a
ocorrência de baldeação do produto por qualquer nó da rede.
3. A idéia do método consiste em admitir que em cada nó haja um
“estoque fictício” do produto que seja capaz de viabilizar qualquer
plano de entregas do produto na rede.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
2
Introdução
• Assim todo nó será subdividido em dois: um nó tipo origem e
outro nó tipo destino, com um fluxo interno de produto entre eles.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
3
Modelo de Transporte com Baldeação
• Modelagem: transportar um produto a partir de m origens (com
produções ai) para n destinos (com demandas bj).
• Todo nó será considerado tanto como origem como por destino.
• Numerar de 1 até m as origens reais e de m + 1 até m + n os
destinos reais.
• Nas origens reais têm-se:
(produto enviado) – (produto recebido) = produção local.
• Nos destinos reais têm-se:
(produto recebido) – (produto enviado) = demanda local.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
4
Modelo de Transporte com Baldeação
• Admite-se que:  a i   b j
i
j
Variáveis de decisão:
Xij = Quantidade do produto enviada da origem i para o destino j.
Função objetivo:
Min Z=  C ijX ij
i j
Sujeito a:
  X ij -  X ji  a i para i  1 até m e j  1 até m  n.
(1)
j i
j i

  X ij -  X ji  b j para i  1 até m  n e j  m  1 até m  n . (2)
i  j
i j
X  0 para todo i  j.
 ij
Esse modelo não pode ser resolvido pelo “Stepping Stone Method”, pois
há coeficientes negativos nas restrições.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
5
Modelo de Transporte com Baldeação
• Desenvolvimento do algoritmo:
• Seja ti a quantidade do produto baldeada no nó i. Assim:
• Nas origens reais  t i   X ji
j i
Nos destinos reais: t j   X ji
j i
Tem-se portanto, as seguintes equivalências:
(1)  (1’):  X ij  a i  t i
j i
X ij  b j  t j
(2)  (2’): j
i
Seja Ci o custo da baldeação do produto no nó i.
C X  Ct
Função objetivo: Min Z=  ij ij  i i
i j
i
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
6
Modelo de Transporte com Baldeação
Para cada nó: T = ti + Xii, onde Xii é o valor da baldeação interna nos nós.
Substituindo T = ti + Xii em (1’) e (2’): para i = 1 até m+n e j = 1 até m+n.
(1’’):  X ij  X ii  a i  T
j i
X ij  X jj  b j  T
(2’’): i
j
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
7
Modelo de Transporte com Baldeação
Ou ainda, se Ci=Cii=0 tem-se:
Min Z=  C ijX ij
i j
Sujeito a:
 X ij  a i  T para i  1 até m  n e j  1 até m  n.
j

 X ij  b j  T para i  1 até m  n e j  1 até m  n .
i
X  0 para todo i e j.
 ij
Observe que ai=bj= 0 para i=m+1 até m+n e j até m.
Este modelo pode ser resolvido pelo “Stepping Stone Method”.
Seja T = Limitante superior sobre todas as quantidades baldeadas nos nós
= estoque fictício em cada nó suficientemente grande para assegurar a
realização de qualquer plano de entregas do produto. Normalmente utilizase o valor de T =
. ai   b j
i
j
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
8
Modelo de Transporte com Baldeação
Comentário: número de variáveis básicas = m’ + n’ – 1, onde m’ = nº total
de origens = m + n, n’ = nº total de destinos = m + n.
Tabela típica para a aplicação do “Stepping Stone Method” ao problema de
transporte com baldeação com m origens e n destinos.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
9
Modelo de Transporte com Baldeação
Exemplo: admitindo a possibilidade de baldeação, determinar o programa
de entregas de custo mínimo para os dados a seguir.
D1
D2
D3
Produção
O1
6
4
6
5
O2
6
6
5
6
Demanda
2
5
4
11
•Considere os seguintes custos de baldeação: O1O2= 1, O2O1 = 2, D1D2 =
2, D1D3 = 1 = D3D1, D2D3 = 2, D2D1 = 4, D1O1 = 3, D1O2 = 1, D3D2 = 5,
D2O1 = 2, D2O2 = 3, D3O1 = 3, D3O2 = 2.
Observação: se não fosse admitida a possibilidade de baldeação a solução
ótima Z* = 56, com X*11 = X*13=X*21=0, X*12=5, X*21=2 e X*23=4.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
10
Modelo de Transporte com Baldeação
Tabela inicial.
O1
O1
D1
D2
D3
Produção
0
5
1
6
4
6
16
O2
2
6
0 11 8
6
5
17
D1
3
1
1
11
D2
2
2
11
D3
3
5 11 0
11
Demanda
11
O2
11
11
2
0
9
2
3
4
7
0
2
1
13
4
16
15
Custo da solução inicial= 119.
Número de variáveis básicas= M’+N’-1=5+5-1=9.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
11
Modelo de Transporte com Baldeação
• Tabela ótima obtida após a aplicação do “Stepping Stone Method”:
O1
O1
11
O2
0
D3
6
5
4
0
8
0
6
2
D1
3
1
D2
2
3
D3
3
2
11
D2
1
O2
Demanda
11
D1
11
11
0
4
2
11
1
13
Produção
6
16
5
17
2
1
11
0
2
11
0
11
5
16
6
9
15
Custo da solução ótima= 52
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
12
Modelo de transporte com baldeação
• Quantidade de produto na rota O1D2 = 5  levar 5 unidades do
produto da origem 1 ao destino 2;
• Quantidade de produto na rota O2D3 = 6  levar 6 unidades do
produto da origem 2 ao destino 3, havendo uma baldeação de 2
unidades que irão ao destino 1;
• Quantidade de produto na rota D3D1 = 2  levar 2 unidades do
produto do destino 3 (que vieram da origem 2) ao destino 1;
• Observe-se as quantidades de produto nas rotas fictícias O1O1,
O2O2, D1D1, D2D2, D3D3, geradas pelo artifício de dividir cada nó
em dois – uma origem e um destino, devem ser desconsideradas
da solução ótima.
Custo da solução ótima= 52.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá
13