Pesquisa Operacional
na Tomada de Decisões
Problemas de Rede
2ª Edição
Capítulo 5
Conteúdos do Capítulo
 Problema de Transporte

Caso LCL Bicicletas
 Sem/Com Dummy
 Como Modelos de Rede
Capítulo 5
Problema de Transporte
Caso LCL Bicicletas
 A LCL Bicicletas possui 3 fábricas localizadas no Rio, São Paulo e
Belo Horizonte. A produção deve ser entregue em Recife, Salvador e
Manaus. Considerando os custos de transporte unitários, as
capacidades de produção das fábricas e as demandas dos centros
consumidores que estão especificados na tabela a seguir, determine
quanto deve ser produzido e entregue por cada fábrica em cada centro
consumidor de forma a minimizar os custos de transporte.
Centro Consumidor
Fábrica
Rio
São Paulo
B.Horizonte
Demanda
Capítulo 5
Recife
25
30
20
2000
Salvador
20
25
15
2000
Manaus
30
25
23
1000
Capacidade
2000
1500
1500
Problema de Transporte:
Modelo Tradicional
 Existem 9 variáveis para expressar a quantidade
transportada em cada uma das possíveis vias.

xij = Quantidade transportada da fábrica i para o centro
consumidor j.
1 - Rio

i = 2 - São Paulo
3 - Belo Horizonte

Capítulo 5
1 - Recife

j = 2 - Salvador
3 - Manaus

Problema de Transporte:
Variáveis de Decisão
x11
RIO
x21
SP
x12
x13
Fábrica REC
x22
x23
SSA
x31
x32
BHZ
Centro
Consumidor
REC
x33
Capítulo 5
MAN
SSA
MAN
Rio
x11
x12
x13
SP
x21
x22
x23
BH
x31
x32
x33
Problema de Transporte:
Modelo Tradicional
Min 25 x11  20 x12  30 x13  30 x21  25 x22  25 x23
 20 x31  15 x32  23x33
s.t.
x11  x12  x13 = 2000
x11  x21  x31 = 2000
x21  x22  x23 = 1500 x12  x22  x32 = 2000
x31  x32  x33 = 1500
xij  0
Capítulo 5
x13  x23  x33 = 1000
Problemas de Transporte:
Propriedades
 Soluções Inteiras:

Para problemas de transporte onde os valores das ofertas, oi e
demandas dj , sejam números inteiros, todos os valores das
variáveis das soluções básicas viáveis, incluindo a solução
ótima, também serão inteiros.
Capítulo 5
Problemas de Transporte:
Propriedades
 A condição necessária e suficiente para um problema
de transporte com n fábricas e m centros consumidores
tenha solução é dada por:
Total da Capacidade = Total da demanda
n

i =1
Capítulo 5
m
fi =  d
j =1
j
Problema de Transporte
Oferta Diferente da Demanda
 A regra das variáveis fantasma (Dummy):
 No caso de Oferta Demanda devemos introduzir
um destino fantasma;
 No caso de Demanda  Oferta devemos introduzir
uma oferta fantasma;
 Todos os custos relacionados às variáveis fantasma
serão nulos;
 A oferta ou a demanda fantasma será dada pela
diferença entre o total ofertado e total demandado.
Capítulo 5
Problema de Transporte
Caso LCL Bicicletas
 Modificando a oferta de São Paulo de 1500 para 3000
Centro Consumidor
Fábrica
Capacidade
Recife
Salvador
Manaus
(oferta)
Rio
25
20
30
2000
São Paulo
30
25
25
3000
B.Horizonte
20
15
23
1500
2000
2000
1000
Demanda
 Demanda total menor que a Oferta total!
Capítulo 5
Problema de Transporte
Caso LCL Bicicletas
 Cria-se um consumidor Dummy:
Centro Consumidor
Fábrica
Recife Salvador
Manaus
Dummy
Capacidade
Rio
25
20
30
0
2000
São Paulo
30
25
25
0
3000
B.Horizonte
20
15
23
0
1500
2000
2000
1000
1500
Demanda
Capítulo 5
Caso LCL Bicicletas
Resolvendo no Excel
Capítulo 5
Caso LCL Bicicletas
Parâmetros e Opções do Solver
Capítulo 5
Caso LCL Bicicletas
Resolvendo no Excel
Capítulo 5
Problemas de Transporte
Solução Alternativa
 As Variáveis Dummy não são obrigatórias, apenas
facilitam a interpretação do resultado da otimização.
 Capacidade > Demanda:
 Criação de consumidor
dummy
 Interpretação: capacidade
ociosa
 Alternativa: restrições
de oferta com sinal 
Capítulo 5
 Demanda > Capacidade:
 Criação de fábrica dummy
 Interpretação: demanda
não atendida;
 Alternativa: restrições
de demanda com sinal 
Caso LCL Bicicletas
Modelo sem Fantasma no Excel
 Todas as fórmulas são idênticas...
Capítulo 5
Caso LCL Bicicletas
Modelo sem Fantasma no Excel
As restrições de oferta
estão com sinal 
Capítulo 5
Caso LCL Bicicletas
Modelo sem Fantasma no Excel
Capítulo 5
Modelos em Rede
 Modelos de rede podem ser utilizados em diversas áreas tais
como transportes, energia e comunicações para modelagem de
diversos tipos de problemas.
 Uma rede é um conjunto de vértices ou nós ligados entre si por
um conjunto de arcos.
arcos
Nós
Capítulo 5
Caso LCL Bicicletas
Representação Como Problema de Rede
 Sem Utilização de Variáveis Dummy
Capítulo 5
Caso LCL Bicicletas
Representação Como Problema de Rede
 Com Utilização de Variáveis Dummy
Capítulo 5
Regra de Fluxo Balanceado
 Uma maneira de modelar um problema de rede é seguir
a Regra Fluxo Balanceado para cada nó.
 No Caso de Oferta Total = Demanda Total
 total de entradas   total de saídas  Oferta/Dem anda 
-
=




no
nó
no
nó
do
nó

 
 

Capítulo 5
Regra de Fluxo Balanceado
 Caso a Oferta Total > Demanda Total
 total de entradas   total de saídas
-


no nó
no nó

 
 Oferta/Dem anda 


do
nó
 

 Caso a Oferta Total < Demanda Total
 total de entradas   total de saídas
-


no nó
no nó

 
Capítulo 5
 Oferta/Dem anda 


do
nó
 

Caso LCL Bicicletas
Representação Como Problema de Rede
=SOMASE($C$4:$C$15;H4;$F$4:$F$15)
-SOMASE($A$4:$A$15;H4;$F$4:$F$15)
Capítulo 5
Caso LCL Bicicletas
Representação Como Problema de Rede
Capítulo 5
Caso LCL Bicicletas
Representação Como Problema de Rede
Capítulo 5