Pesquisa Operacional
na Tomada de Decisões
Problemas de Rede
2ª Edição
Capítulo 5
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Problema de Transporte



Caso LCL Bicicletas
 Sem/Com Dummy
 Como Modelos de Rede
Caso LCL Fórmula 1 Ltda.
Caso LCL Construções S.A.
 Problemas de Rede de Distribuição;


Caso Frod Brasil
Caso LCL Eletrodomésticos
 Problemas do Menor Caminho;
 Problemas de Fluxo Máximo;
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
Problema de Transporte
Aplicações
 O problema de transporte não é aplicado apenas a
problemas de distribuição de mercadorias das fábricas
para centros distribuidores;
 O mesmo tipo de formulação pode ser aplicado a outros
tipos de problema, tais como:

Problemas de Escalas de Produção;

Problemas de Lay-out de fábricas;
Capítulo 5
Caso LCL Fórmula 1 Ltda.
A LCL Fórmula 1 Ltda. fornece motores para um grande nº de equipes de
fórmula 1. A companhia detém uma série de contratos de entregas futuras
programadas para o próximo ano. As entregas deverão ocorrer
trimestralmente de acordo com as necessidades das equipes. A tabela
resume as entregas programadas, a capacidade máxima de produção, o
custo de produção por trimestre e o custo de armazenamento. Formule o
problema para achar o número de motores que devem ser fabricados em
cada trimestre de maneira a atender os pedidos contratados.
* em milhões de reais
Capítulo 5
Caso LCL Fórmula 1 Ltda.
 Fonte i = Produção de motores
no trimestre i (i=1,..,4)
 Destino j= entrega dos
motores às equipes no
trimestre j (j=1,..,4)
 xij = nº de motores produzidos
no trimestre i para entrega no
trimestre j
 cij = custo associado ao motor
xi
 Dj = nº de pedidos contratados
 Fi = capacidade de produção
no mês i
Entrega dos Motores (trimestre)
Produção
no
Trimestre
Demanda
Capítulo 5
1
2
3
4
1
2
3
4
1,080 1,095 1,110 1,125
1,110 1,125 1,140
1,10 1,115
1,130
10
15
25
20
5(D)
0
0
0
0
30
Oferta
25
35
30
10
Caso LCL Fórmula 1 Ltda.
Capítulo 5
Caso LCL Fórmula 1 Ltda.
Capítulo 5
Caso LCL Fórmula 1 Ltda.
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
 A Frod Brasil terá duas fábricas no Brasil, uma na Bahia e outra
em São Paulo, e está estudando a forma de distribuição de seus
carros para as diversas revendas de Minas Gerais.
A seguir é apresentada a possível rede de distribuição dos
veículos, seus custos de transporte unitários, demandas por
revenda e as capacidades das fábricas.
Formule o Problema de LP que resolva as rotas que devem ser
seguidas a partir das fábricas para atender as diversas revendas.
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
5
40
-500
SP
1
+250
+200
20
3
15
25
10
10
oferta
10
-600
6
35
BA
2
4
20
10
10
25
40
Capítulo 5
+300
+350
7
+350
demanda
Problemas de Rede de Distribuição
Caso Frod Brasil
 Variáveis de Decisão


xij – Nº de Carro remetidos de i para j
Exemplo:
x14 – Nº de Carro remetidos de 1 para 4
 Função-Objetivo = Minimizar o Custo de Distribuição
Min 10 X 14  20 X 13  40 X 15  10 X 23  20 X 24  40 X 27
 25 X 36  35 X 45  25 X 47  15 X 56  10 X 67  10 X 65
 10 X 76
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
 Como a oferta total é menor que a demanda total
devemos utilizar a seguinte restrição em todos os nós:
Entradas – Saídas < Oferta / Demanda no nó
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
Capítulo 5
Problemas de Rede de Distribuição
Caso Frod Brasil
Capítulo 5
Caso LCL Eletrodomésticos Ltda.
 A LCL Eletrodomésticos Ltda. deseja realizar o
escalonamento de sua produção para os próximos 4
meses. Sua fábrica pode produzir mensalmente em
horário normal 150 ferros de passar a um custo de R$5,
e em horário extra, 50 unidades a um custo de R$ 7.
Considere que é possível armazenar durante um mês a
um custo unitário de R$1. Suponha que as demandas
para os próximos quatro meses são de 120, 200,120 e
180.
Capítulo 5
Caso LCL Eletrodomésticos Ltda.
 Para resolver este problema, criaremos uma rede onde:

Cada nó representará uma unidade produtora ou unidade
receptora. São 8 unidades produtoras (2 por mês), e 5
unidades receptoras (4 meses mais o Dummy – visto que a
capacidade produtiva é maior que a demanda);

Cada arco está relacionado ao custo de produção ou
armazenagem.
Capítulo 5
Caso LCL Eletrodomésticos Ltda.
-150
1
0
-50
2
E
Dummy
-150
0
3
0
4
0
0
0
0
-50
+120
7
-150
5
6
-50
7
+200
B
5
+120
C
7
1
-150
8
5
1
7
Capítulo 5
A
1
0
+800-620=
+180
5
-50
5
7
D
+180
Caso LCL Eletrodomésticos Ltda.
=somarproduto(D3:D21;E3:E21)
=SOMASE($C$3:$C$21;F15;$E$3:$E$21)
-SOMASE($B$3:$B$21;F15;$E$3:$E$21)
Capítulo 5
Caso LCL Eletrodomésticos Ltda.
Capítulo 5
Problemas de Menor Caminho
 Se considerarmos uma rede na qual o arco signifique a
distância entre dois pontos (nós) e desejarmos achar a
rota que une estes pontos com distância mínima,
teremos um problema do tipo do Menor caminho.
 Este tipo de problema pode ser generalizado e aplicado
a distribuição de produtos, entre outros.
Capítulo 5
Problemas de Menor Caminho
Exemplo
 Considere a rede abaixo que representa a ligação
rodoviária entre duas cidades (A e B). O tamanho dos
arcos representa a distância entre pontos da malha
rodoviária entre as cidades.
30
1
3
40
20
20
B
A
30
Capítulo 5
2
30
4
20
Problemas de Menor Caminho
Exemplo
 Este problema pode ser visto como um problema de
rede de distribuição com um ponto de oferta de um
caminhão (A=-1) e ponto de demanda de um caminhão
(B=+1) e os demais pontos da malha sem demanda ou
30
oferta (=0)
3
1
40
20
20
[-1]
B
A
30
Capítulo 5
2
30
4
20
[+1]
Problemas de Menor Caminho
Exemplo
Capítulo 5
Problemas de Menor Caminho
Exemplo
Capítulo 5
Problemas de Menor Caminho
Solução
Capítulo 5
Problema do Fluxo Máximo
 Nesse tipo de problema temos uma rede de nós e arcos,
e desejamos que o maior fluxo de uma grandeza possa
fluir de um determinado nó para outro.
 Nesse tipo de problema mais de um caminho pode ser
utilizado simultaneamente.
 Aplicações

Rede de distribuição de água, luz, gás e tráfego na internet.
Capítulo 5
Problemas de Rede
Problema do Fluxo Máximo
 Como resolver o problema?

Adicionar um arco artificial ligando o ponto de saída (A) ao
ponto de chegada (B).

Maximizar o fluxo no arco artificial criado (fluxo grande).

Utilizar a regra de balanceamento de redes.

As grandezas associadas aos arcos são o fluxo máximo em
cada trecho da rede, portanto restrições no modelo.

O Valor de Oferta/Demanda em cada nó é igual a zero.
Capítulo 5
Problemas de Rede
Problema do Fluxo Máximo
30
40
3
1
20
20
A
30
40
30
2
Capítulo 5
4
B
Problemas de Rede
Problema do Fluxo Máximo
Capítulo 5
Problemas de Rede
Problema do Fluxo Máximo
Capítulo 5
Problemas de Rede
Problema do Fluxo Máximo
Capítulo 5
Problemas de Rede
Problema do Fluxo Máximo
Capítulo 5