Modelos em Rede: Problemas de LP

Prévia do material em texto

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. 
Nós 
arcos 
Programação Linear 
Problemas de Rede 
 Um grande número de problemas de tomadas de 
decisão no mundo real estão categorizados como 
Problemas de Fluxo de Rede: 
 Rede de Distribuição; 
 Problemas do Menor Caminho; 
 Problemas de Fluxo Máximo; 
 Problemas de Transporte/Designaçã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 é apresentado a possível rede de distribuição dos 
veículos, seus custos de transporte unitários, demandas por 
revenda e capacidade 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. 
Problemas de Rede de Distribuição 
 Caso Frod Brasil 
SP 
1 
BA 
2 
3 
4 
5 
6 
7 
-500 
-600 
+200 
+300 
+250 
+350 
+350 
40 
20 
20 
25 
25 
35 
40 
10 
10 
10 10 
10 15 
oferta 
demanda 
 Variáveis de Decisão 
 Xii – Nº de Carro remetidos de i para j 
 Exemplo: 
 X14 – Nº de Carro remetidos de 1 para 4 
 
 Função-Objetiva = Minimizar o Custo de Distribuição 
 
76
656756474536
272423151314
10 
101015253525 
402010402010 
X
XXXXXX
XXXXXXMin



Problemas de Rede de Distribuição 
 Caso Frod Brasil 
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 
 


















nó do
andaOferta/Dem
nó no 
 saídas de total
 
nó no
entradas de total
Regra de Fluxo Balanceado 


















nó do
andaOferta/Dem
nó no 
 saídas de total
 
nó no
entradas de total


















nó do
andaOferta/Dem
nó no 
 saídas de total
 
nó no
entradas de total
 Caso a Oferta Total > Demanda Total 
 
 
 Caso a Oferta Total < Demanda Total 
 
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 do nó 
Caso Frod Brasil 
Usando Excel 
Caso Frod Brasil 
Usando Excel 
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 energia, renovação de frota de veículos 
entre outros. 
Problemas de Menor Caminho 
Exemplo 
 Considere a rede abaixo que representa a ligação 
rodoviária entre duas cidades. O tamanho dos arcos 
representa a distância entre as Cidades (nós). 
A B 
4 
3 
2 
1 
40 
30 
30 
30 
20 
20 
20 
 Este problema pode ser visto como um problema de 
rede de distribuição com uma fonte(A)= -1 e um 
demanda (B)=+1 e os demais sem demanda ou fonte 
(=0) 
 
A B 
4 
3 
2 
1 
40 
30 
30 
30 
20 
20 
20 
Problemas de Menor Caminho 
Exemplo 
[-1] [+1] 
Problemas de Menor Caminho Exemplo 
Problemas de Menor Caminho 
Solução 
Solução proposta: 
•de A para 1; 
•de 1 para 4; 
•de 4 para B. 
Problemas de Rede 
Problema do Fluxo Máximo 
 Neste tipo de problema temos uma rede de nos e arcos e 
desejamos que o maior fluxo de uma grandeza possa 
fluir de um determinado nó para outro. 
 Neste 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. 
 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. 
 Utilizar a regra de balanceamento de redes 
 As grandezas associadas aos arcos são o fluxo máximos em 
cada trecho da rede, portanto restrições no modelo 
 O Valor de Oferta/Demanda em cada nó é igual a zero 
Problemas de Rede 
Problema do Fluxo Máximo 
Problema do Fluxo Máximo 
Exemplo - Lindo 
30 
30 
A B 
4 
3 
2 
1 
40 
30 
20 
20 
40 
Problema do Fluxo Máximo 
Exemplo - Lindo 
Fórmulas de Balanceamento do nó usam SUMIF 
Problema do Fluxo Máximo 
Exemplo - Excel 
Problema do Fluxo Máximo 
Exemplo - Excel 
Problema do Fluxo Máximo 
Solução - Excel