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
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
5 +250
40
SP +200
-500 20
1 3 15 10
25
10
35 6 +350 demanda
oferta
10 4 +300
20 10 10
BA 25
-600
2
40 7 +350
Problemas de Rede de Distribuição
Caso Frod Brasil
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
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
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ó
Regra de Fluxo Balanceado
Caso a Oferta Total > Demanda Total
total de entradas total de saídas Oferta/Dem anda
no nó no nó do nó
Caso a Oferta Total < Demanda Total
total de entradas total de saídas Oferta/Dem anda
no nó no nó do nó
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).
30
1 3
20
40
20
A B
30 20
2 4
30
Problemas de Menor Caminho
Exemplo
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) 30
1 3
20
40
20
[-1] A B [+1]
30 20
2 4
30
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.
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.
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
Problema do Fluxo Máximo
Exemplo - Lindo
30
1 3
40 20
20
A 30 B
40
30
2 4
Problema do Fluxo Máximo
Exemplo - Lindo
Problema do Fluxo Máximo
Exemplo - Excel
Fórmulas de Balanceamento do nó usam SUMIF
Problema do Fluxo Máximo
Exemplo - Excel
Problema do Fluxo Máximo
Solução - Excel