Buscar

04 Métricas Espaciais

Prévia do material em texto

ENG1545
Distribuição Física
Métricas Espaciais
Prof. Rafael Martinelli
Introdução
ENG1545 - Distribuição Física 2
▪ Planejamento de um 
sistema logístico
• Definição da localização 
dos pontos que formam 
uma cadeia de 
suprimentos.
• Fornecedores, produtores, 
armazéns, depósitos e 
clientes, ou quaisquer 
outros elementos de uma 
rede logística para os 
quais é possível demarcar 
sua posição geográfica.
▪ Problemas de 
Localização
• Redução de custos, 
minimização de tempos 
de distribuição e/ou 
coleta e maximização do 
nível de serviço prestado.
– Número/tamanho de 
facilidades.
– Programação matemática, 
heurísticas e estudos de 
cenários.
Métricas Espaciais
Introdução
ENG1545 - Distribuição Física 3
▪ Rede: quando há condicionantes de caminho (arcos)
entre dois pontos de uma cadeia de suprimentos
(nós).
▪ A análise de rede representa, de forma geral, os
problemas de localização sob um sistema de
transporte em uma malha já definida, onde se tem
determinadas as possibilidades de percursos.
▪ A otimização de percursos em uma rede é tratada
através de grafos.
Introdução
ENG1545 - Distribuição Física 4
modelagemMapa Rede
Introdução
ENG1545 - Distribuição Física 5
▪ Há casos, entretanto, que não há necessidade de trabalhar com restrições
de caminhos (não há necessidade de uma solução exata):
• Fases iniciais de planejamento;
• Estudos gerais de políticas abrangentes;
• Respostas rápidas sobre diversas alternativas;
• Áreas geográficas amplas, onde os pontos, a serem determinados, podem ser
cidades.
▪ Nestas situações é comum simplificar a representação das redes. Em lugar
de representar todos os nós e arcos, imagina-se que a distância
correspondente a uma ligação qualquer entre dois pontos possa ser
estimada através da distância geométrica entre esses pontos.
Multiplicando a distância geométrica por um coeficiente de correção apropriado 
estima-se o valor da distância “verdadeira” entre dois pontos.
Distância Euclidiana
ENG1545 - Distribuição Física 6
• Há vários caminhos 
para ligar os pontos A e 
B, quase sempre com 
distâncias diferentes. A 
menor distância 
possível é a Distância 
Euclidiana. É a distância 
mais usada nas 
aplicações reais de 
transportes.
• Este tipo de distância 
apresenta unicidade de 
percurso.
𝐴
𝐵
𝑋𝐴 𝑋𝐵
𝑌𝐴
𝑌𝐵
Distância Euclidiana:
𝐷𝐸𝐴𝐵 = 𝑥𝐵 − 𝑥𝐴
2 + 𝑦𝐵 − 𝑦𝐴
2
Distância Efetiva – Coeficiente de Correção
ENG1545 - Distribuição Física 7
▪ Através de coeficientes corretivos médios pode-se
relacionar matematicamente as distâncias efetivas
com as distâncias euclidianas, possibilitando assim o
tratamento mais realista das aplicações.
𝐷𝐴𝐵 ≥ 𝐷𝐸𝐴𝐵
𝐷𝐴𝐵 = 𝑎 + 𝑏 × 𝐷𝐸𝐴𝐵
Multiplicando a distância geométrica por um coeficiente de correção apropriado 
estima-se o valor da distância “verdadeira” entre dois pontos.
Distância Efetiva – Coeficiente de Correção
ENG1545 - Distribuição Física 8
Limite inferior da distância 
efetiva, caso em que ela é igual 
a euclidiana
Exemplo:
Dist. em linha reta (teórica) = 
100 km
Dist. marcada no odômetro do 
caminhão = 125 km
0 100 200 300 400 500 600 700 800
Distância em linha reta (km)
D
is
tâ
n
ci
a 
ef
et
iv
a 
(k
m
)
800
700
600
500
400
300
200
100
a
𝑦 = 𝑎 + 𝑏 × 𝑥
𝑦 = 𝑥
Distância Efetiva – Coeficiente de Correção
ENG1545 - Distribuição Física 9
▪ Os coeficiente de correção são específicos de cada região e de cada tipo de
via. O cálculo desses coeficientes é feito com base em amostragens.
𝑑 (𝑒𝑓. ) = 23,9 + 1,11 × 𝑑 (𝑒𝑢. ) Válido para 𝑑 (𝑒𝑢. ) ≥ 60 𝑘𝑚
𝑑 (𝑒𝑓. ) = 1,48 × 𝑑 (𝑒𝑢. ) Válido para 𝑑 (𝑒𝑢. ) < 60 𝑘𝑚
▪ Para ligações muito curtas os efeitos da sinuosidade das ligações, e
principalmente dos vazios da rede de transporte, são bastante mais graves,
impedindo que se extrapolem os resultados para outras situações.
𝑑 (𝑒𝑓. ) = 9,8 + 1,25 × 𝑑 (𝑒𝑢. )
𝑑 (𝑒𝑓. ) = 0,81 + 1,366 × 𝑑 (𝑒𝑢. )
EXEMPLO: Um estudo sobre 110 ligações rodoviárias sobre a rede pavimentada de 
estradas do Estado de São Paulo nos anos 60 revelou as seguintes correções.
EXEMPLO: Em 33 ligações ferroviárias no Estado de São Paulo, correspondentes a 
percursos entre cidades servidas por vias de bitola larga (1,60 m).
EXEMPLO: Uma análise sobre 57 pares de pontos localizados na malha urbana da 
cidade de São Paulo, através de regressão.
Distância Retangular – Manhattan
ENG1545 - Distribuição Física 10
▪ É bastante utilizada em análises 
sobre a malha urbana, quando 
essa apresenta estrutura do tipo 
retangular (ex.: São Paulo e 
Zona Sul do Rio de Janeiro).
▪ Nos casos em que a rede de 
transportes é retangular (arcos 
se cortam perpendicularmente), 
a distância entre os pontos A e 
B corresponde a qualquer uma 
das possíveis soluções (sem 
retorno) ao longo da rede. Esta 
distância é a denominada 
Distância Retangular. 
𝐴
𝐵
𝑋𝐴 𝑋𝐵
𝑌𝐴
𝑌𝐵
Distância Retangular:
𝐷𝑅𝐴𝐵 = 𝑋𝐴 − 𝑋𝐵 + 𝑌𝐴 − 𝑌𝐵
Distância Efetiva – Coeficiente de Correção
ENG1545 - Distribuição Física 11
▪ Raciocínio análogo ao feito com a distância euclidiana
pode ser feito para relacionar a distância efetiva com a
distância retangular, nos casos em que esse tipo de
representação seja utilizada.
𝑑 (𝑒𝑓. ) = 1,13 + 1,048 × 𝑑 (𝑟𝑒𝑡. )
EXEMPLO: Uma análise sobre 30 pares de pontos localizados na malha urbana da 
cidade de São Paulo, através de regressão.
Distância Real – Tendência Atual
ENG1545 - Distribuição Física 12
Outras Distâncias – Distância Geodésica
ENG1545 - Distribuição Física 13
Problemas de Localização
ENG1545 - Distribuição Física 14
▪ Admite-se que o 
precursor da Teoria de 
Localização Moderna 
tenha sido Alfred Weber 
em 1909.
▪ A hipótese mais 
importante postulada 
por Weber era de que as 
empresas escolhiam a 
localização que lhes 
permitia minimizar os 
custos operacionais.
Problemas de Localização
ENG1545 - Distribuição Física 15
▪ Decisão de onde localizar uma ou mais instalações (infraestruturas, veículos
estacionários, etc.) num determinado espaço com vista a atingir um ou
vários objetivos e satisfazendo um conjunto de restrições.
▪ A localização ótima depende do tipo de infraestrutura em análise.
▪ A localização ótima varia também de acordo com o setor do projeto:
• Setor público: maximizar o benefício para a sociedade ou minimizar os custos
dos serviços oferecidos.
• Setor privado: procura minimizar os custos e maximizar os lucros. Os efeitos
exteriores como o meio ambiente, bem estar, economia são negligenciáveis.
EXEMPLO: o centro da cidade será a localização ótima para uma estação de 
correios mas uma solução péssima para uma central de incineração. Funções 
objetivo razoáveis: 
• Correios: minimizar a distância média percorrida pelos clientes. 
• Central de incineração: maximizar a distância mínima da central ao edifício mais 
próximo.
A localização ótima depende da medida de eficiência do sistema, isto é, da função 
objetivo.
Problemas de Localização
ENG1545 - Distribuição Física 16
Localização no Plano
▪ Considera-se um sistema de 
coordenadas, em que as 
instalações podem ser 
localizados em qualquer ponto 
definido por esse sistema de 
coordenadas. Não tem 
restrições de percurso (pode 
usar-se a distância mais curta). 
Tem que ser definida uma 
métrica que permita calcular 
distâncias (ex.: Euclidiana ou 
Manhattan).
▪ Põe-se o problema no caso de 
localização de instalações em 
locais que não oferecem 
barreiras. Ex.: Instalações 
petrolíferas no mar.
Localização na Rede
▪ A rede é composta por arcos e 
nós, sendo que só é possível 
localizar instalações nesses 
arcos ou nós. Transpondo para a 
realidade corresponde no 
transporte rodoviário à rede de 
estradas, no ferroviário à rede 
de ferrovias, no fluvial à rede 
hídrica, etc.
▪ Num problema de localização 
discreto as potenciais 
localizações para as instalações 
são conhecidas e em número 
finito.Determinação do Ponto Central
ENG1545 - Distribuição Física 17
▪ Os modelos de localização apresentados nesta seção correspondem àqueles em que
o número de localizações possíveis não está limitado a um conjunto finito.
▪ O problema da determinação de ponto central ocorre quando se deseja localizar
uma facilidade para atender a um conjunto de pontos.
▪ Esta facilidade pode ser uma fábrica, ou loja, um depósito, ou centro de prestação
de serviço, etc.
▪ Dependendo do tipo de facilidade, o critério para a localização pode mudar:
• Para a localização de fábricas ou depósitos, o critério dominante pode ser o custo total de
investimento, transporte e estoque.
• Já para a localização de uma loja, o critério receita, proveniente da acessibilidade dos clientes
potenciais pode ser o determinante (Ballou, 1995).
▪ O Problema do Ponto Central também se designa de Problema do Centro de
Gravidade.
▪ O ponto central pode ser relativo ao centro do peso, centro da distância ou ao
centro combinado do peso-distância ou ainda do centro peso-tempo-distância,
sempre tentando encontrar uma localização de menor custo.
Determinação do Ponto Central
ENG1545 - Distribuição Física 18
EXEMPLO:
Considere o problema em que se pretende localizar uma única instalação 
que deverá servir múltiplos pontos. A distribuição consiste em transportar 
determinadas quantidades de produto desde um conjunto de pontos até 
uma instalação (ou desde essa instalação para um conjunto de pontos).
Partimos dos seguintes pressupostos:
• As quantidades a transportar encontram-se concentradas num número 
limitado de pontos.
• Apenas os custos variáveis de transporte são relevantes (ausência de 
custos fixos).
• Os custos de transporte aumentam proporcionalmente com a 
quantidade transportada e com a distância.
• O transporte é feito em linha reta.
• A instalação pode ser localizada em qualquer par de coordenadas do 
plano.
Determinação do Ponto Central
ENG1545 - Distribuição Física 19
Quais as coordenadas do 
Ponto Central, p?
30, 120
60, 40
90, 110
130, 130
0
30
60
90
120
150
0 30 60 90 120 150
São Paulo
Rio de Janeiro
Belo Horizonte
Vitória
p
?x y Carga/mês
Belo Horizonte 30 120 2000
São Paulo 60 40 2000
Rio de Janeiro 90 110 1000
Vitória 130 130 1000
Ponto Central – Centro Peso
ENG1545 - Distribuição Física 20
▪ A localização final é aquela em que há um equilíbrio de peso entre os
destinos (pessoas, cargas, etc.) ou as origens.
• Destinos se o ponto a ser localizado distribui mercadorias ou pessoas para os demais
pontos.
• Origens se o ponto a ser localizado recebe mercadorias ou pessoas dos demais
pontos.
▪ 𝑥𝑝 = coordenada 𝑥 do centro de gravidade, 𝑝, a ser determinada
▪ 𝑦𝑝 = coordenada 𝑦 do centro de gravidade, 𝑝, a ser determinada
▪ 𝑥𝑖 = coordenada 𝑥 da instalação 𝑖
▪ 𝑦𝑖 = coordenada 𝑦 da instalação 𝑖
▪ 𝑉𝑖 = volume de material deslocado de/ou para 𝑖
𝑥𝑝 =
σ𝑖 𝑥𝑖𝑉𝑖
σ𝑖 𝑉𝑖
𝑦𝑝 =
σ𝑖 𝑦𝑖𝑉𝑖
σ𝑖 𝑉𝑖
Ponto Central – Centro Peso
ENG1545 - Distribuição Física 21
Exemplo:
30, 120
60, 40
90, 110
130, 130
0
30
60
90
120
150
0 30 60 90 120 150
São Paulo
Rio de Janeiro
Belo Horizonte
Vitória
p
?
x y Carga/mês
Belo Horizonte 30 120 2000
São Paulo 60 40 2000
Rio de Janeiro 90 110 1000
Vitória 130 130 1000
𝑥𝑝 =
σ𝑖 𝑥𝑖𝑉𝑖
σ𝑖 𝑉𝑖
𝑦𝑝 =
σ𝑖 𝑦𝑖𝑉𝑖
σ𝑖 𝑉𝑖
𝑥𝑝 =
30 × 2000 + 90 × 1000 + 130 × 1000 + 60 × 2000
2000 + 1000 + 1000 + 2000
= 66,7
𝑦𝑝 =
120 × 2000 + 110 × 1000 + 130 × 1000 + 40 × 2000
2000 + 1000 + 1000 + 2000
= 93,3
Ponto Central – Centro de Gravidade da Distância
ENG1545 - Distribuição Física 22
▪ O ponto central baseado na distância é determinado
pelo ponto geográfico que representa a menor
distância combinada para todas as origens ou
destinos. Considera-se que os custos de entrega são
apenas função da distância. Se a distância é a menor,
fica identificada a localização de menor custo.
▪ Nota: A deficiência da solução baseada na distância é
a omissão de considerações de peso e de custo de
transporte.
Ao contrário da solução baseada no peso, a solução baseada na distância 
não pode ser obtida simplesmente tendo em conta a média ponderada 
da coordenada × peso. A solução baseada na distância exige um 
processo iterativo.
Ponto Central – Centro de Gravidade da Distância
ENG1545 - Distribuição Física 23
(𝑥𝑖 , 𝑦𝑖) = coordenadas 
do ponto 𝑖
(𝑥𝑝, 𝑦𝑝) = coordenadas 
desconhecidas do centro 
de gravidade a 
determinar.
𝑑𝑖𝑝 = distância 
euclidiana do ponto 𝑖 ao 
centro de gravidade 
𝑁 = número de pontos 
servidos ou atendidos
𝑃𝑖
𝑃1
𝑃2
𝑃3
𝑃
𝑋𝑖 𝑋𝑝 𝑥
𝑦
𝑌𝑝
𝑌𝑖
Ponto Central – Centro de Gravidade da Distância
ENG1545 - Distribuição Física 24
▪ Distância Euclidiana:
𝑑2 = 𝑥𝑖 − 𝑥𝑗
2
+ 𝑦𝑖 − 𝑦𝑗
2
▪ Pretende-se minimizar a soma das distâncias entre a instalação a localizar e
os demais pontos da rede.
𝑀𝑖𝑛 𝑧 =෍
𝑖∈𝐼
𝑑𝑖𝑝 =෍
𝑖∈𝐼
𝑥𝑖 − 𝑥𝑝
2
+ 𝑦𝑖 − 𝑦𝑝
2
𝜕𝑧
𝜕𝑥𝑝
=෍
𝑖∈𝐼
𝑥𝑖 − 𝑥𝑝
𝑑𝑖𝑝
= 0 ⇒ 𝑥𝑝 =
σ𝑖∈𝐼
𝑥𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
1
𝑑𝑖𝑝
𝜕𝑧
𝜕𝑦𝑝
=෍
𝑖∈𝐼
𝑦𝑖 − 𝑦𝑝
𝑑𝑖𝑝
= 0 ⇒ 𝑦𝑝 =
σ𝑖∈𝐼
𝑦𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
1
𝑑𝑖𝑝
Ponto Central – Centro de Gravidade da Distância
ENG1545 - Distribuição Física 25
▪ Distância Euclidiana (Processo iterativo de Weisfeld)
1. Arbitrar a posição do ponto 𝑃 e calcular todas as distâncias 𝑑𝑖𝑝.
– NOTA: Para aproximação inicial pode usar-se o centro de gravidade do
peso!
2. Calcular 𝑥𝑝 e 𝑦𝑝 usando as expressões:
𝑥𝑝 =
σ𝑖∈𝐼
𝑥𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
1
𝑑𝑖𝑝
e 𝑦𝑝 =
σ𝑖∈𝐼
𝑦𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
1
𝑑𝑖𝑝
– o que significa achar um novo ponto 𝑃.
3. Com o novo ponto 𝑃, recalcular as distâncias 𝑑𝑖𝑝, ou seja, repetir os
passos anteriores até que o ponto 𝑃 permaneça estacionário.
A experiência mostra que, após poucas iterações, o método converge para o 
ponto 𝑝 desejado. 
Ponto Central – Centro de Gravidade da Distância
ENG1545 - Distribuição Física 26
▪ Exemplo: Localize o ponto central dos pontos abaixo:
▪ Utilize o ponto (1,5; 0,0) como ponto inicial.
▪ Compare a solução encontrada com a do Ponto
Central – Peso.
𝑥 𝑦
𝑃1 0,0 0,0
𝑃2 1,5 3,0
𝑃3 3,0 0,0
Ponto Central – Centro Peso-Distância
ENG1545 - Distribuição Física 27
▪ Distância Euclidiana (Processo iterativo de Weisfeld)
1. Arbitrar a posição do ponto 𝑃 e calcular todas as distâncias 𝑑𝑖𝑝.
– NOTA: Para aproximação inicial pode usar-se o centro de gravidade do
peso!
2. Calcular 𝑥𝑝 e 𝑦𝑝 usando as expressões:
𝑥𝑝 =
σ𝑖∈𝐼
𝑉𝑖𝑥𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
𝑉𝑖
𝑑𝑖𝑝
e 𝑦𝑝 =
σ𝑖∈𝐼
𝑉𝑖𝑦𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
𝑉𝑖
𝑑𝑖𝑝
– o que significa achar um novo ponto 𝑃.
3. Com o novo ponto 𝑃, recalcular as distâncias 𝑑𝑖𝑝, ou seja, repetir os
passos anteriores até que o ponto 𝑃 permaneça estacionário.
O objetivo é minimizar a distância e o peso, ou seja:
𝑀𝐼𝑁 ෍
𝑖∈𝐼
𝑉𝑖𝑑𝑖
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 28
▪ Distância Euclidiana (Processo iterativo de Weisfeld)
1. Arbitrar a posição do ponto 𝑃 e calcular todas as distâncias 𝑑𝑖𝑝.
– NOTA: Para aproximação inicial pode usar-se o centro de gravidade do
peso!
2. Calcular 𝑥𝑝 e 𝑦𝑝 usando as expressões:
𝑥𝑝 =
σ𝑖∈𝐼
𝑉𝑖𝑅𝑖𝑥𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
𝑉𝑖𝑅𝑖
𝑑𝑖𝑝
e 𝑦𝑝 =
σ𝑖∈𝐼
𝑉𝑖𝑅𝑖𝑦𝑖
𝑑𝑖𝑝
σ𝑖∈𝐼
𝑉𝑖𝑅𝑖
𝑑𝑖𝑝
– o que significa achar um novo ponto 𝑃.
3. Com o novo ponto 𝑃, recalcular as distâncias 𝑑𝑖𝑝, ou seja, repetir os
passos anteriores até que o ponto 𝑃 permaneça estacionário.
O objetivo é minimizar os custos totais de transporte, 𝑇𝐶, ou seja:
𝑇𝐶 =෍
𝑖∈𝐼
𝑉𝑖𝑅𝑖𝑑𝑖
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 29
▪ Exemplo: Uma empresa pretende construir um centro de tratamento de resíduos,
para tratar resíduos produzidos pelas suas três fábricas. Considere que o único fator
relevante na localização do centro é o custo de transporte dos resíduos de cada
fábrica para o centro que a serve.
▪As quantidades a transportar anualmente,
respectivos custos de transporte e
localização das fábricas são mostrados na
tabela seguinte. Utilizando o método do
Centro de Gravidade Peso / Distância /
Custo, calcular a localização ótima de um
único centro de tratamento (3 iterações).
Calcular o custo total de transporte para a
solução obtida.
10, 20
40, 40
20, 10
0
5
10
15
20
25
30
35
40
45
0 5 10 15 20 25 30 35 40 45
𝑥 𝑦
Carga 
Anual (t)
Custo
(R$/t.km)
Fábrica 1 10 20 30 5
Fábrica 2 40 40 70 10
Fábrica 3 20 10 30 5
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 30
▪ Este método iterativo é de convergência rápida, mas
não é válido quando o ponto central coincide com um
dos pontos dados. Nessa condição a distância entre
ponto central e o ponto dado é nula, impedindo que
sejam definidas as derivadas parciais.
▪ Uma forma simples de contornar a indeterminação
mencionada é a de acrescentar uma constante
positiva pequena à expressão da distância euclidiana,
impedindo desta forma que se torne nula:
𝑑𝑖
′ = 𝑑𝑖 + 𝛿
▪ O Solver do Excel e um processo devido a Kuhn-
Kuenne contornam essa situação.
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 31
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 32
▪ Distância Retangular (Manhattan)
𝑑 = |𝑥𝑖 − 𝑥𝑗| + |𝑦𝑖 − 𝑦𝑗|
▪ Pretende-se minimizar a soma das distâncias entre a instalação a localizar e os
demais pontos da rede.
𝑀𝑖𝑛 𝑧 =෍
𝑖∈𝐼
𝑝𝑖𝑑𝑖𝑝 =෍
𝑖∈𝐼
𝑝𝑖 𝑥𝑝 − 𝑥𝑖 + 𝑦𝑝 − 𝑦𝑖
▪ Podemos dividir a função original em duas funções:
𝑧 =෍
𝑖∈𝐼
𝑝𝑖 𝑥𝑝 − 𝑥𝑖 +෍
𝑖∈𝐼
𝑝𝑖 𝑦𝑝 − 𝑦𝑖 ⇒ 𝑧 = 𝑧𝑥 + 𝑧𝑦
▪ Minimizar a função original é o mesmo que minimizar as duas funções
separadamente.
▪ Podemos resolver o problema do ponto central com distância retangular de três
formas:
• Método de Fibonacci
• Método da Derivada
• Método da Mediana
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 33
▪ Trata-se um método semelhante ao da mediana para
localizar pontos centrais. O método busca o ponto
onde a derivada da função muda de sinal.
▪ Definição do Problema:
• Tem-se um conjunto de pontos, com coordenadas (𝑥𝑖 , 𝑦𝑖).
• Para cada ponto, existe um peso/custo (𝑝𝑖) associado.
▪ Deseja-se minimizar a função:
𝑧 =෍
𝑖∈𝐼
𝑝𝑖 𝑥𝑝 − 𝑥𝑖 +෍
𝑖∈𝐼
𝑝𝑖 𝑦𝑝 − 𝑦𝑖
O método da derivada (ao contrário do método de Fibonacci) não busca um 
ponto central no plano mas sim o ponto central que usa as coordenadas dos 
que estão sendo analisados.
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 34
▪ Método de cálculo:
• Calcula-se a derivada da função em cada intervalo e descobre-se o ponto limite
entre dois intervalos, onde a derivada passa de valor negativo em um intervalo a não
negativo no intervalo seguinte.
• Como a função é separável, pode-se encontrar o mínimo de cada parcela da função,
ou seja, encontrar o valor de 𝑥 e depois o valor de 𝑦 que minimizam cada parcela da
função objetivo. A modelagem a seguir para a variável 𝑥 também serve para a
variável 𝑦. A função é contínua e por partes com descontinuidade em cada ponto
entre dois intervalos.
▪ Considerando um exemplo, seja uma função de quatro pontos, ordena-se
em ordem crescente da coordenada em questão, ou seja, 𝑥 ou 𝑦.
𝑥1 ≤ 𝑥2 ≤ 𝑥3 ≤ 𝑥4
𝑧𝑥
0 = 𝑝1 𝑥1 − 𝑥 + 𝑝2 𝑥2 − 𝑥 + 𝑝3 𝑥3 − 𝑥 + 𝑃4 𝑥4 − 𝑥
▪ A derivada em relação a 𝑥, neste intervalo, é:
𝜕𝑧𝑥
0
𝜕𝑥
= −𝑝1 − 𝑝2 − 𝑝3 − 𝑝4 = −෍
𝑖∈𝐼
𝑝𝑖
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 35
▪ No intervalo seguinte entre 𝑥1 e 𝑥2, a função assume o valor:
𝑧𝑥
1 = 𝑝1 𝑥 − 𝑥1 + 𝑝2 𝑥2 − 𝑥 + 𝑝3 𝑥3 − 𝑥 + 𝑃4 𝑥4 − 𝑥
▪ A derivada com relação a x, neste intervalo, é:
𝜕𝑧𝑥
1
𝜕𝑥
= 𝑝1 − 𝑝2 − 𝑝3 − 𝑝4 = −෍
𝑖∈𝐼
𝑝𝑖 + 2𝑝1
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 36
▪ Para a coordenada 𝑥:
1. Ordenam-se os pontos por ordem crescente de valor da coordenada
2. Calcula-se:
𝜕𝑧𝑥
0
𝜕𝑥
= −෍
𝑖∈𝐼
𝑝𝑖
3. Iniciar com 𝑖 = 0
Enquanto Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 < 0 fazer
𝑖 = 𝑖 + 1
Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 = Τ𝜕𝑧𝑥
𝑖−1 𝜕𝑥 + 2𝑝𝑖
4. Se Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 = 0 ou Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 > 0 parar
𝑥𝑚𝑖𝑛 = 𝑥𝑖
– Se Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 > 0: o ponto de mínimo da função é único, e o valor da variável correspondente a este
mínimo, coincide com o valor da coordenada neste ponto.
– Se Τ𝜕𝑧𝑥
𝑖 𝜕𝑥 = 0: o mínimo da função terá o mesmo valor em todo o intervalo entre o ponto que
torna a variável zero e o ponto seguinte, onde a derivada se torna positiva.
5. Repetir o processo para 𝑦.
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 37
▪ Exemplo: Considere os dados abaixo:
▪ Resolução pelo método da derivada:
𝑧𝑥 = 1 × 𝑥 − 10 + 1 × 𝑥 − 15 + 1 × 𝑥 − 18
𝑥 ≤ 10 → 𝑧𝑥
0 = 10 − 𝑥 + 15 − 𝑥 + 18 − 𝑥 = 43 − 3𝑥
10 ≤ 𝑥 ≤ 15 → 𝑧𝑥
1 = 𝑥 − 10 + 15 − 𝑥 + 18 − 𝑥 = 23 − 1𝑥
15 ≤ 𝑥 ≤ 18 → 𝑧𝑥
2 = 𝑥 − 10 + 𝑥 − 15 + 18 − 𝑥 = 1𝑥 − 7
𝑥 > 18 → 𝑧𝑥
3 = 𝑥 − 10 + 𝑥 − 15 + 𝑥 − 18 = 3𝑥 − 43
𝑥 𝑦
𝑃1 10 10
𝑃2 15 20
𝑃3 18 9
Ponto Central – Método da Derivada
ENG1545 - Distribuição Física 38
▪ Resolução pelo método da derivada:
𝑥 𝑝𝑖 𝜕𝑧𝑥
𝑖 /𝜕𝑥
– – – −3
𝑃1 10 1 −3 + 2 × 1 = −1
𝑃2 15 1 −1 + 2 × 1 = 1
𝑃3 18 1 1 + 2 × 1 = 3
𝑦 𝑝𝑖 𝜕𝑧𝑦
𝑖 /𝜕𝑦
– – – −3
𝑃2 9 1 −3 + 2 × 1 = −1
𝑃3 10 1 −1 + 2 × 1 = 1
𝑃1 20 1 1 + 2 × 1 = 3
Localização: (15; 10)
Ponto Central – Método da Mediana
ENG1545 - Distribuição Física 39
▪ Para a coordenada 𝑥:
1. Ordenam-se os pontos por ordem crescente de valor da
coordenada
2. Calcula-se:
𝑚 =
σ𝑖∈𝐼 𝑝𝑖
2
3. Iniciar com 𝑖 = 0 e 𝑠𝑜𝑚𝑎 = 0
Enquanto 𝑠𝑜𝑚𝑎 < 𝑚 fazer
𝑖 = 𝑖 + 1
𝑠𝑜𝑚𝑎 = 𝑠𝑜𝑚𝑎 + 𝑝𝑖
4. Se 𝑠𝑜𝑚𝑎 ≥ 𝑚 parar
𝑥𝑚𝑖𝑛 = 𝑥𝑖
5. Repetir o processo para 𝑦.
▪ Resolução pelo método da mediana:
𝑚𝑥 = σ𝑖∈𝐼 𝑝𝑖 =
3
2
𝑚𝑦 = σ𝑖∈𝐼 𝑝𝑖 =
3
2
Ponto Central – Método da Mediana
ENG1545 - Distribuição Física 40
𝑥 𝑝𝑖 𝑠𝑜𝑚𝑎
𝑃1 10 1 0 + 1 = 1
𝑃2 15 1 1 + 1 = 2
𝑃3 18 1 2 + 1 = 3
𝑦 𝑝𝑖 𝑠𝑜𝑚𝑎
𝑃2 9 1 0 + 1 = 1
𝑃3 10 1 1 + 1 = 2
𝑃1 20 1 2 + 1 = 3
Localização: (15; 10)
Ponto Central – Centro Peso-Distância-Custo
ENG1545 - Distribuição Física 41
▪ Considere os seguintes dados:
▪ Calcule o ponto central para a métrica retangular,
usando os métodos da derivada e da mediana.
Ponto 𝑥 𝑦 Peso
1 230 153 2000
2 328 166 3000
3 198 245 1000
4 313 277 2000
ACESSE O NOSSO SITE!
@deipucrio
Departamento de 
Engenharia Industrial -
PUC-Rio
Departamento de 
Engenharia Industrial -
PUC-Rio
Um boa semana!
Até a próxima aula!

Continue navegando