Metodos Quantitativos 2016 2 Secao (11)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Métodos Quantitativos
Prof. Gerson Lachtermacher
Prof. Paulo Sérgio Coelho
2016/2
Seção 11
‹nº›
1
Modelos de Rede
Regra do Fluxo Balanceado
Modelos de Transporte
Caso LCL Motocicletas S.A. 
Modelos de Escala de Produção
Caso LCL Fórmula Turismo Ltda.
Caso LCL Fogões Ltda.
Modelos de Rede de Distribuição
Caso Automóveis Brasil
Modelos de Menor Caminho
Modelos de Fluxo Máximo
Conteúdos do Capítulo
2016/2
Seção 11
‹nº›
2
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.
Modelos em Rede
Nós
arcos
[-oferta]
[+demanda]
2016/2
Seção 11
‹nº›
3
Num modelo de rede cada nó terá uma denominação ou numeração especifica.
As variáveis de decisão estarão ligadas aos arcos existentes entre os nós.
X12 – pode indicar o nº de veículos que passa na estrada que liga a cidade 1 à cidade 2.
X34 – pode indicar o nº de geladeiras que é entregue pela fábrica 3 no revendedor 4.
Modelos em Rede
2016/2
Seção 11
‹nº›
4
A função-objetivo do problema de rede de distribuição é dada por:
Onde 
cij é o custo unitário de transporte de uma unidade do produto de i para j
xij é o número de produto transportados na rota de i para j
Modelos em Rede
2016/2
Seção 11
‹nº›
5
Uma maneira de modelar as restrições de um problema de rede é seguir a Regra Fluxo Balanceado para cada nó.
Nesta regra para cada nó da rede devemos estabelecer a diferença entre as variáveis que estão chegando (entradas) ao nó menos e as variáveis que estão deixando o nó (saídas).
	xij – é uma entrada para o nó j e é uma saída do nó i
O sinal da restrição varia com ofertas e demandas totais
O lado direito das restrições serão as ofertas ou demandas de cada nó
Regra de Fluxo Balanceado
2016/2
Seção 11
‹nº›
6
Caso de Oferta Total = Demanda Total
Caso a Oferta Total > Demanda Total
Caso a Oferta Total < Demanda Total
Regra de Fluxo Balanceado
2016/2
Seção 11
‹nº›
7
Caso LCL Motocicletas S.A.
A LCL Motocicletas S.A. possui 3 fábricas localizadas em Cuiabá, Santo André e Florianópolis. A produção deve ser entregue em Recife, Salvador e Fortaleza. 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
Recife
Salvador
Fortaleza
Capacidade
Cuiabá
25
18
30
2000
Santo André
32
24
25
2000
Florianópolis
23
16
23
1500
Demanda
2000
3000
1000
2016/2
Seção 11
‹nº›
8
Caso LCL Motocicletas S.A.
Variáveis de Decisão
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.
Centro Consumidor
Fábrica
Recife (4)
Salvador (5)
Fortaleza (6)
Cuiabá (1)
x14
x15
x16
Santo André (2)
x24
x25
x26
Florianópolis (3)
x34
x35
x36
ï
î
ï
í
ì
-
-
-
=
 
Florianópolis
 
3
 
Santo André
 
2
Cuiabá
 
1
 
i
ï
î
ï
í
ì
-
-
-
=
Fortaleza
 
6
Salvador
 
5
Recife
 
4
 
j
2016/2
Seção 11
‹nº›
9
Caso LCL Motocicletas S.A.
Modelo Gráfico
25
Cuiabá
1
Sto.André
2
Florianópolis
3
Recife
4
Salvador
5
Fortaleza
6
18
30
32
24
25
23
16
23
[-2000]
[-2000]
[-1500]
[+2000]
[+3000]
[+1000]
2016/2
Seção 11
‹nº›
10
Caso LCL Motocicletas S.A.
Modelo
2016/2
Seção 11
‹nº›
11
Caso LCL Motocicletas S.A. Parâmetros
2016/2
Seção 11
‹nº›
12
Caso LCL Motocicletas S.A.
Solução
2016/2
Seção 11
‹nº›
13
O problema de rede 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;
Problema de Rede
Aplicações
2016/2
Seção 11
‹nº›
14
A GLP Fórmula Turismo Ltda. fornece motores para equipes de fórmula turismo. A companhia detém contratos de entregas futuras programadas para o próximo ano. As entregas deverão ocorrer a cada quadrimestre. A tabela resume as entregas programadas, a capacidade máxima de produção e o custo de produção por quadrimestre incluindo o custo de armazenamento. Formule o problema para achar o número de motores que devem ser fabricados em cada quadrimestre de maneira a atender os pedidos contratados.
Caso LCL Fórmula Turismo Ltda.
Quadrimestre Produção
Quadrimestre de Entrega
milhões de Reais
1º (nó 4)
2º (nó 5)
3º (nó 6)
Capacidade
1º (nó 1)
1,08
1,09
1,10
45
2º (nó 2)
1,08
1,09
35
3º (nó 3)
1,07
25
Demanda
30
40
30
2016/2
Seção 11
‹nº›
15
Caso LCL Fórmula Turismo Ltda.
Representação Gráfica do Modelo
1,08
Prod. Q1
1
Prod. Q2
2
Prod. Q3
3
Ent.Q1
4
Ent.Q2
5
Ent.Q3
6
1,09
1,10
[-45]
[-35]
[-25]
[+30]
[+40]
[+30]
1,08
1,09
1,07
2016/2
Seção 11
‹nº›
16
Caso LCL Fórmula Turismo Ltda.
2016/2
Seção 11
‹nº›
17
Caso LCL Fórmula Turismo Ltda.
2016/2
Seção 11
‹nº›
18
Caso LCL Fórmula Turismo Ltda.
Solução
2016/2
Seção 11
‹nº›
19
A LCL Fogões Ltda. deseja realizar o escalonamento de sua produção para os próximos 3 meses. Sua fábrica pode produzir mensalmente, em horário normal, 250 fogões a um custo de R$35,00, e em horário extra, 50 unidades a um custo de R$40,00. Considere que é possível armazenar durante um mês a um custo unitário de R$5,00 sem restrições de espaço. Suponha que as demandas para os próximos quatro meses são de 140, 200 e 130. Qual o escala de produção a ser seguida?
Caso LCL Fogões Ltda.
2016/2
Seção 11
‹nº›
20
Para resolver este problema, criaremos uma rede onde:
Cada nó representará uma unidade produtora ou unidade receptora. 
São 6 unidades produtoras (2 por mês) 
São 3 unidades receptoras (3 meses)
Cada arco está relacionado ao custo de produção e/ou armazenagem.
Caso LCL Fogões Ltda.
2016/2
Seção 11
‹nº›
21
Caso LCL Fogões Ltda.
[-250]
1
3
5
2
4
6
C
B
 [+200]
A
1
3
5
2
[-50]
4
6
9
 [+130]
8
7
 [ +140]
35
40
35
40
35
40
5
5
[-250]
[-50]
[-250]
[-50]
2016/2
Seção 11
‹nº›
22
Caso LCL Fogões Ltda.
2016/2
Seção 11
‹nº›
23
Caso LCL Fogões Ltda.
2016/2
Seção 11
‹nº›
24
Observação: Propor atividade de fixação e indicar leitura básica e complementar. 
Caso LCL Fogões Ltda.
2016/2
Seção 11
‹nº›
25
Observação: Propor atividade de fixação e indicar leitura básica e complementar. 
A Automóveis Brasil terá duas fábricas no Brasil, uma em Salvador (1) e outra em Santo.André (2), e está estudando a forma de distribuição de seus carros para as diversas revendas de Minas Gerais, nas cidades de Juiz de Fora (3), B.Horizonte (4), Barbacena (5) e Tiradentes (6).
	A seguir é apresentada a rede de revendas da Automóveis Brasil, seus custos de transporte unitários, demandas das revenda e as capacidades das fábricas.
	Determine a forma como a entrega de veiculas deve ser realizada pelas fabricas às revendas.
Caso Automóveis Brasil
2016/2
Seção 11
‹nº›
26
Caso Automóveis Brasil
1
2
3
4
5
6
[-800]
[-600]
[+200]
[+300]
[+350]
40
20
20
25
25
35
40
10
10
10
15
[+450]
2016/2
Seção 11
‹nº›
27
Variáveis de Decisão
xij – Quantidade de carros remetidos de i para j
Exemplo:
x14 – Quantidade de carros remetidos de 1 para 4
Função-Objetivo = Minimizar o Custo de Distribuição
Caso Automóveis Brasil
2016/2
Seção 11
‹nº›
28
Como a oferta total é maior que a demanda total devemos utilizar a seguinte restrição em todos os nós:
	
Caso Automóveis Brasil
2016/2
Seção 11
‹nº›
29
Caso Automóveis Brasil
Modelo
2016/2
Seção 11
‹nº›
30
Caso Automóveis Brasil
2016/2
Seção 11
‹nº›
31
Caso Automóveis Brasil
2016/2
Seção 11
‹nº›
32
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.
Problemas de Menor Caminho
2016/2
Seção 11
‹nº›
33
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.
Problemas de Menor Caminho 
Exemplo
A
B
4
3
2
1
40
30
30
30
20
20
20
2016/2
Seção 11
‹nº›
34
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 oferta (=0)
Problemas de Menor Caminho 
Exemplo
[-1]
[+1]
A
B
4
3
2
1
40
30
30
30
20
20
20
2016/2
Seção 11
‹nº›
35
Problemas de Menor Caminho 
Exemplo
2016/2
Seção 11
‹nº›
36
Problemas de Menor Caminho 
Exemplo
2016/2
Seção 11
‹nº›
37
Problemas de Menor Caminho
Solução
2016/2
Seção 11
‹nº›
38
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. 
Problema do Fluxo Máximo
2016/2
Seção 11
‹nº›
39
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.
Problemas de Rede
Problema do Fluxo Máximo
2016/2
Seção 11
‹nº›
40
Problemas de Rede
Problema do Fluxo Máximo
A
B
4
3
2
1
40
30
30
30
20
20
20
2016/2
Seção 11
‹nº›
41
Problemas de Rede
Problema do Fluxo Máximo
2016/2
Seção 11
‹nº›
42
Problemas de Rede
Problema do Fluxo Máximo
2016/2
Seção 11
‹nº›
43
Problemas de Rede
Problema do Fluxo Máximo
2016/2
Seção 11
‹nº›
44
Observação: Propor atividade de fixação e indicar leitura básica e complementar. 
Livro Básico 1
Exercícios 5.1, 1 – 10, pp. 134 – 136
Exercícios 5.2, 1 – 10, pp. 152 – 153 
Livro Básico 2
Problemas 5.1 – 5.31, pp. 263 - 269
Exercícios Propostos
2016/2
Seção 11
‹nº›
45
Lachtermacher, Gerson. Pesquisa Operacional na Tomada de Decisões. 4ª ed. São Paulo: Pearson Prentice Hall, 2009.
Bibliografia
2016/2
Seção 11
‹nº›
46