Modelagem de Transportes

Prévia do material em texto

Marco Caldas - Ph.D.
Núcleo de Logística Integrada e Sistemas - Logis
Universidade Federal Fluminense
Curso de Engenharia de Produção
Roteirização/Sequenciamento
Introdução
Inúmeros problemas de decisão práticos caem em uma 
categoria conhecida como problemas de fluxo de rede.
Neste trabalho serão apresentados os seguintes problemas de 
fluxo de rede:
• Problemas de baldeação
• Problema do caminho mínimo
• Problemas de fluxo de rede generalizados
Embora existam procedimentos de solução especializados 
para resolver problemas de fluxo de rede, aqui será 
considerado como formular e resolver estes problemas como 
problemas de PL.
O problema de baldeação
�Muitos dos outros tipos de problemas de fluxo de rede podem ser vistos
como uma simples variação de problemas de baldeação;
�A Bavarian Motor Company BMC fabrica carros luxuosos em Hamburg e
exporta carros para serem vendidos nos Estados Unidos. Os carros
exportados são despachados de Hamburg para portos em Newark e
Jacksonville. Desses portos, os carros são transportados por trem ou
caminhão para distribuidoras localizadas em Boston, Columbs, Atlanta,
Richmond e Móbile.
O problema de baldeação
�A Figura abaixo mostra as possíveis rotas disponíveis pela companhia
juntamente com o custo do transporte para enviar cada carro ao longo do
trajeto indicado.
O problema da baldeação
�Atualmente, 200 carros estão disponíveis no porto de Newark e 300 estão
disponíveis em Jacksonville;
�Os números de carros demandados pelos distribuidores em Boston,
Columbus, Atlanta, Richmond, e Móbile são 100, 60, 170, 80, e 70,
respectivamente;
A BMC quer determinar a maneira menos cara de transportar carros dos 
portos em Newark e Jocksonville para as cidades onde eles são 
demandados.
O problema da baldeação
2.1 Características do Problema de fluxo de rede
• nós de oferta e nós de demanda;
• Nós de baldeação podem ambos emitir para ou receber de outros nós na 
rede;
• Números positivos representam a demanda de um dado nó, e números 
negativos representam a oferta disponível no nó; 
• Um nó de baldeação pode ter uma oferta ou demanda, mas não ambos; 
2.2 Variáveis de decisão para problemas de fluxo de rede
• Cada arco no modelo de fluxo de rede representa uma variável de decisão;
• Para cada arco, definimos uma variável de decisão como:
• Xij = o número de itens transportados (ou fluxo) do nó i para o 
nó j
• A rede na Figura 1 para nosso problema de exemplo contém 11 arcos.
O problema da baldeação
2.3 A Função objetivo para problemas de fluxo de rede
�Como a BMC está interessada em minimizar o custo total de transporte, a
função objetivo para este problema é expressa como:
MIM: 30X12 + 40X14 + 50X23 + 35X35 + 40X53 + 30X54 + 
35X56 + 25X65 + 50X74 + 45X75 + 50X76
Problema de custo mínimo de fluxo de rede.
O problema da baldeação
2.4 As restrições para o problema de fluxo de rede
• O número de nós determina o número de restrições;
• As Regras de Balanceamento de Fluxo, aplicam-se para construir as 
restrições para os problemas de custo mínimo de fluxo de rede. Estas regras 
são resumidas como seguem:
Para Problema de custo mínimo
de fluxo de rede, onde:
Aplicar esta regra de Balanceamento de
fluxo em cada nó
Total ofertado > Total demandado Fluxo entrando – Fluxo saindo >= Oferta ou demanda
Total ofertado < Total demandado Fluxo entrando – Fluxo saindo <= Oferta ou demanda
Total ofertado = Total demandado Fluxo entrando – Fluxo saindo = Oferta ou demanda
O problema da baldeação
• Primeiramente devemos comparar o total ofertado na rede com o total 
Demandado; 
• Em nosso problema de exemplo, existe uma oferta de 500 carros e um total 
demandado de 480 carros. Neste caso podemos usar a primeira regra de 
balanceamento de fluxo para formular nosso problema de exemplo;
• Restrições
-X12 – X14 ≥ -200
+X12 – X23 ≥ +100
+X23 + X53 – X35 ≥ +60
+X14 + X54 + X74 ≥ +80
+X35 + X65 + X75 –X53 – X54 – X56 ≥ +170
+X56 + X76 – X65 ≥ +70
-X74 – X75 - X76 ≥ -300
Xij ≥ 0 para todo i e j
O problema do caminho mínimo
� A América Car Association (ACA) fornece uma variedade de serviços de
viagem para seus membros, e o planejamento da rota de viagem, é um
de muitos serviços populares. A ACA determina uma rota ótima para
viajar entre estas cidades. A ACA possui um banco de dados
computadorizado das principais estradas e tempos de viagem em vários
segmentos de estradas;
�Para ver quanto a ACA poderia ter de benefício para resolver os
problemas de caminho mínimo, considere a rede simplificada
mostrada na figura para um membro que quer viajar dirigindo de
Birmingham para Virgínia Beach;
� Para cada arco, a figura lista o tempo dirigindo estimado para viajar a
estrada e o número de pontos que a rota recebeu no sistema ACA’s para
avaliar a qualidade scenic das várias rotas.
O problema do caminho mínimo
� Para cada arco, a 
figura lista o tempo 
dirigindo estimado 
para viajar a estrada 
e o número de 
pontos que a rota 
recebeu no sistema 
ACA’s para avaliar a 
qualidade scenic das 
várias rotas.
O problema do caminho mínimo
• Resolver este problema como um modelo de fluxo de 
rede requer que os vários nós tenham alguma oferta ou 
demanda. Na figura anterior (Birmingham) tem uma 
oferta de 1, o nó 11 (Virgínia Beach) tem uma demanda 
de 1, e todos os outros nós tem uma demanda (ou oferta) 
de 0;
• Se nós enxergarmos este modelo como um problema de 
baldeação, nós queremos encontrar a maneira mais 
rápida ou a maneira mais scenic de transportar 1 
unidade de fluxo do nó 1 para o nó 11;
O problema do caminho mínimo
3.1 Um Modelo de PL para o problema do exemplo
�Usando a regra de balanceamento de fluxo, o modelo de PL para 
minimizar o tempo dirigindo neste problema é representado como:
MIN: +2,5X12 + 3X13 + 1,7X23 + 2,5X24 + 1,7X35 + 2,8X36 + 2X46 
+ 1,5X47 + 2X56 + 5X59 +3X68 + 4,7X69 + 1,5X78 + 2,3X7,10 + 
2X89 + 1,1X8,10 + 3,3X9,11 + 2,7X10,11
O problema do caminho mínimo
Sujeita a:
-X12 – X13 =1 restrição de fluxo para o nó 1
+X12 – X23 – X24 =0 restrição de fluxo para o nó 2
+X13 + X23 – X35 – X36 =0 restrição de fluxo para o nó 3
+X24 – X46 – X47 =0 restrição de fluxo para o nó 4
+X35 – X56 – X59 =0 restrição de fluxo para o nó 5
+X36 + X46 + X56 – X68 – X69 =0 restrição de fluxo para o nó 6
+X47 + X78 – X7,10 =0 restrição de fluxo para o nó 7
+X68 + X78 – X89 – X8,10 =0 restrição de fluxo para o nó 8
+X59 + X69 + X89 – X8,11 =0 restrição de fluxo para o nó 9
+X7,10 + X8,10 – X10,11 =0 restrição de fluxo para o nó 10
+X9,11 – X10,11 =1 restrição de fluxo para o nó 11
Xij ≥ 0 para todo i e j
A solução mostrada na figura a seguir minimiza o tempo dirigindo esperado.
Problemas de fluxo de rede 
generalizado
� Em todos os problemas de rede nós temos considerado que a quantidade 
de fluxo que entra no arco sempre é a mesma que sai do arco. Porém, 
existem numerosos exemplos de problemas de fluxo de rede os quais um 
ganho ou perda acontece em fluxos por arcos; 
� Por exemplo, se é transportado gás ou óleo por um oleoduto mal vedado, a 
quantia de óleo ou gás chegando ao destino planejado pode ser menor que a 
quantia originalmente colocada no oleoduto;
� Exemplo: Nancy Grant é o dono de Coal Bank Hollow Recycling, uma 
companhia especializada em reciclagem de produtos de papel. A companhia 
usa dois diferentes processos de reciclagem para converter jornal, papel 
misturado, papel de escritório branco e papelão em polpa de papel; 
� A quantidade de polpa de papel extraída dos materiais recicláveis e o custo 
de extrair as diferentes polpas dependem de qual processo de reciclagem é 
usado. A tabela seguinte resume os processos de reciclagem:
Processo 1 Processo 2
Material Custo por ton Rendimento Custo por tonRendimento
Jornal $13 90% $12 85%
Papel 
Misturado
$11 80% $13 85%
Papel de 
Escritório 
Branco
$9 95% $10 90%
Papelão $13 75% $14 85%
Problemas de fluxo de rede 
generalizado
• Os rendimentos associados com transformar a polpa 
reciclada em polpa para os produtos finais são 
resumidos na tabela seguinte:
Problemas de fluxo de rede 
generalizado
Polpa de jornal
Polpa de papel 
de pacote
Print stock pulp
Fonte de polpa
Custo
por ton
Rendim
ento
Custo
por ton
Rendim
ento
Custo
por ton
Rendim
ento
Processo de reciclagem 1 $5 95% $6 90% $8 90%
Processo de reciclagem 2 $6 90% $8 95% $7 95%
• Nancy atualmente tem 70 toneladas de jornal, 50 
toneladas de papel misturado , 30 toneladas de papel de 
escritório branco, e 40 toneladas de papelão. 
• Ela quer determinar a maneira mais eficiente de 
converter estes materiais em 60 toneladas de 
polpa de papel de jornal, 40 toneladas de polpa 
de papel de pacote, e 50 toneladas de polpa de 
papel stock.
Problemas de fluxo de rede 
generalizado
• Os arcos neste grafo indicam possíveis fluxos de material reciclado 
entre os processos de produção. Para cada arco, nós temos listados 
os custos do fluxo ao longo do arco e o fator de redução aplicado 
para o fluxo ao longo do arco.
Problemas de fluxo de rede 
generalizado
• Para formular o Modelo de PL para este problema algebricamente, nós 
definimos as variáveis de decisão Xij para representar as toneladas de 
produtos fluindo do nó i para o nó j. O objetivo é então declarado na 
maneira usual como segue:
• MIN: 13X15 + 12X16 + 11X25 + 13X26 + 9X35 + 10X36 + 13X45 + 
14X46 + 5X57 + 6X58 +8X59 + 6X67 + 8X68 + 7X69
• As restrições para os quatro primeiros nós (representando a oferta de 
jornal, papel misturado, papel de escritório branco e papelão, 
respectivamente), são dados por:
-X15 - X16 ≥ -70 restrição de fluxo para o nó 1
-X25 – X26 ≥ -50 restrição de fluxo para o nó 2
-X35 – X36 ≥ -30 restrição de fluxo para o nó 3
-X45 – X46 ≥ -40 restrição de fluxo para o nó 4
Problemas de fluxo de rede 
generalizado
• Aplicando a regra de balanceamento de fluxo nos nós 5 e 
6 (representando os dois processos de reciclagem) nós 
obtemos:
+0,9X15 +0,8 X25 +0,95X35 + 0,75X45 -X57 – X58 –X59 ≥ 0 restrição de fluxo para o nó 5
+0,85X16 +0,85 X26 +0,9X36 + 0,85X46 - X67 - X68 - X69 ≥ 0 restrição de fluxo para o nó 6
• Finalmente, aplicando a regra de balanceamento de 
fluxo para os nós 7, 8 e 9 nós obtemos as restrições:
+0,95X57 + 0,90X67 ≥ 60 restrição de fluxo para o nó 7
+0,90X58 + 0,95X68 ≥ 40 restrição de fluxo para o nó 8
+0,90X59 + 0,95X69 ≥ 50 restrição de fluxo para o nó 9
Problemas de fluxo de rede 
generalizado