aula 9 - 2011-02 - Metricas-01

Prévia do material em texto

M
ÉT
R
IC
A
S 
 
ES
PA
CI
A
IS
Pr
o
f 
M
a
ri
o
 
A
n
to
n
io
 
P.
 
Bi
te
n
co
u
rt
Definição dos pontos que formam uma cadeia de 
suprimentos:
•Fornecedores
•Produtores
•Armazéns
•Depósitos
•Clientes
Demarcar a posição geográfica
P.
 
A
le
gr
e
B
el
ém
N
at
al
?
2
1
3
4
5
6
Região A
Fabricante
Fornecedor A
Fornecedor B
Fornecedor C
Armazém A
Armazém B
Cliente 3
Cliente 1
Cliente 2
Cliente 4 Cliente 5
•Reduzir Custos
•Minimizar Tempos
•Maximizar Satisfação do 
Cliente etc
ANÁLISE ESPACIAL
8
5
2
9
6 10
1 3
4 7
-Análise de Redes
- Análise Agregada
(Conj infinito de caminhos entre dois pontos)
1 2 4 5
3
6 7
8 9 11
10
Estimativa de distância entre dois pontos
- Análise Agregada
•Distância Euclidiana
•Distância Retangular
Y
(XB,YB)
(XA,YA)
X
Métrica Euclidiana
2122 ])()[( ABABAB yyxxDE −+−=
Y
M B
L N
A
X
O
Métrica Retangular
|||| ABABAB YyxxDR −+−=
ABAB DED ≥Distância Real:
Estimativa por regressão: D a bDEAB AB= +
•Distância Euclidiana
São Paulo
Estimativa por regressão: D a bDEAB AB= +
Distância Real Distância
Euclidiana
45,4 Km 30 Km
88,5 Km 76 Km
189 Km 135 km
… …
D a bDEAB AB= +
Estado de São Paulo
Ferrovias: DED 25.18.9 +=
Vias Urbanas: DED .366,181,0 +=
Restrições de sentido, retorno, restrições de vias a 
transportes de carga
Rodovias: 
D DE DE Km= + ≥239 111 60. . ( )
D DE DE Km= <148 60. ( )
Novaes (1989)
DED .366,181,0 +=
DRD 048,113,1 +=
ABAB DRDE ≤
ABE DEbD .≅
ABR DRbD .≅
ER bb <
Vias Urbanas:
\Para estudos preliminares: D=1,30. DE
ρρρ
ρ
1
)( 



−+−= BABAAB YYXXD
Love (1988):
Brimley & Love (1992):
[ ] ( ) ( )[ ] 2122210 BABABABAAB YYXXbYYXXbbD −+−+−+−+=
Outras Fórmulas:
Ballou (2001):
( ) ( ) ( ) }coscoscos{arccos3959 



−••+•




= ABbAbAAB LONGLONGLATLATLATsenLATsenD
Fatores de correção:
1,17 (rodovias)
1,20 (ferrovias)
P.
 
A
le
gr
e
B
el
ém
N
at
al
CD
Po
n
to
 
Ce
n
tr
al
2
1
3
4
5
6
CD
Po
n
to
 
Ce
n
tr
al
Ponto Central
Métrica Euclidiana
Y
Y
Yi Pi
Xi X X
∑ −+−=
=
N
1i
2
12
i
2
i )])yy()xx[(pi)xy(fMin
0
x
)y,x(f
=
∂
∂ 0
y
)y,x(f
=
∂
∂
( ) ( )[ ] 0).(),( 2/122
1
=−+−−∑=
∂
∂ −
=
iiii
N
i
yyxxxxP
x
yxf
( ) ( )[ ] 0).(),( 2/122
1
=−+−−∑=
∂
∂ −
=
iiii
N
i
yyxxyyP
y
yxf
∑
∑
−+−
−+−
=
2/122
2/122
])()[(
])()[(
ii
i
ii
ii
yyxx
P
yyxx
xP
x
∑
∑
=




















=




















−+−
−+−
=
n
i
i
n
i
ii
yiyxix
P
yiyxix
yP
y
1
2/122
1
2/122
X
p x D E
p D E
i i i
i
N
i i
i
N=
=
=
∑
∑
/
/
1
1
∑
∑
=
=
= N
i
ii
N
i
iii
DEp
DEyp
Y
1
1
/
/
Solução:
DE x x y yi i i= − + −[( ) ( ) ]2 2
1
2
Solução: método iterativo (Weisfeld)
DE DE1 2= ... DE DEM =
X
p x
p
i i
i
0
=
∑
∑
Y
p y
p
i i
i
0
=
∑
∑
( ) ( ) 2/12020
2/12020
1
1
1






−+−
=
∑
−+−
=
∑
=




















ii
ii
ii
yyxx
Pi
N
i
yyxx
xP
N
i
x
( ) ( ) 2/12020
2/12020
1
1
1






−+−
=
∑
−+−
=
∑
=




















ii
i
ii
ii
yyxx
P
N
i
yyxx
yP
N
i
y
Em geral na k-ésima iteração.
X
p x DE
p DE
k
i i i
k
i
N
i i
K
i
N
+ =
=
=
∑
∑
1 1
1
/
/
( )
( )
Y
p y DE
p DE
k
i i i
k
i
N
i i
k
i
N
+ =
=
=
∑
∑
1 1
1
/
/
( )
( )
Parar:
( ) ( ) ( ) ε≤−+ kkk xxx /1 ( ) ( ) ( ) ε≤−+ kkk yyy /1e
P.
 
A
le
gr
e
B
el
ém
N
at
al
CD
Po
n
to
 
Ce
n
tr
al
DE x x y y Di i i= − + − +[( ) ( ) ]2 2
1
2 ∆
Truque:
∆ D ≈ 0.05 x unidade
Não vale se ponto central cai sobre um ponto i
X
p x D E
p D E
i i i
i
N
i i
i
N=
=
=
∑
∑
/
/
1
1
∑
∑
=
=
= N
i
ii
N
i
iii
DEp
DEyp
Y
1
1
/
/
Quanto ao método de Weisfeld, 
BALLOU [2001] conclui que 
para uma solução bem próxima da 
ótima, as fórmulas para x0 e y0
são suficientes. Demonstra-se que 
o erro de se usar essas fórmulas é
significantemente pequeno para 
os casos de: 
�O peso de um ou alguns pontos não 
for expressivamente maior do que os 
pontos restantes;
�Haver um grande número de pontos 
dados;
�Considerar o peso, quando 
representado por custos ou receitas 
de transportes, linearmente 
proporcionais à distância.
Ponto x y p
P1 0 0 1
P2 0 10 1
P3 5 0 1
P4 12 6 1
25,4
4
170
===
∑
∑
i
ii
p
xp
X 00,4
4
160
===
∑
∑
i
ii
p
yp
Y
BALLOU [2001] estima um erro médio de 1,6% do valor 
ótimo, para 50 pontos e taxas lineares de transporte. No 
nosso exemplo, para somente 4 pontos, caso fosse 
considerada a 1ª aproximação 
)000,4;250,4(* =X
F(X) teria o valor de 25,263. 
Este valor é 2,07% maior que o valor de F(X) no ponto 
ótimo (4,2).
1
2
3
4
5
6
7
8
9
10
2 3 4 5 6 7 8 9 1010
P2
P1 M3
M1
M2
Fonte: Ballou
Ponto Prod Vol.Tot
m3
Taxa
Transp($/
m3/km
xi yi
P1 A 2.000 0,050 3 8
P2 B 3.000 0,050 8 2
M1 A&B 2.500 0,075 2 5
M2 A&B 1.000 0,075 6 4
M3 A&B 1.500 0,075 8 8
1. Procurando minimizar o custo total de 
transporte. Determine a localização do 
armazém.
1) Pergunta
M
ÉT
R
IC
A
 
R
ET
A
N
G
U
LA
R
PONTO CENTRAL
∑
=
−+−=
N
i
iii yyxxpyxf
1
|]|||[),(
Separando: f x y p x x p y yi i i i
i
N
i
N
( , ) | | | |= − + −
==
∑∑
11
f x y f x f y( , ) ( ) ( )= +1 2
(MIN)
Minimizar é min. e f x y( , ) f x1( ) f y2 ( )
MÉTRICA RETANGULAR
Ip
a
n
em
a
i 1 2 3
Pi 1 1 1
X(x,y) (10,10) (15,20) (18,9)
181151101)(1 −+−+−= xxxxf
0
5
10
15
20
25
30
35
40
45
50
1 3 5 7 9 1 1 1 3 1 5 1 7 1 9 2 1 2 3 2 5 2 7 2 9
181151101)(1 −+−+−= xxxxf
Como a função-soma dos módulos é uma 
poligonal convexa, pode-se afirmar que ela só
tem um único ponto mínimo
Solução:Método de Fibonacci
Solução para x (igual para y)
Processo Iterativo
Iteração k ; No máximo de iterações: I
Passos
1. Determina XI = min xi
XS = max xi
K = 0
2. K = k+1 Se k > I, pare.
F(x)
S1 S2 X
3. Faz S1 = XI e S2 = XS
Segmento S1 - S2 Dividido em 3 partes pelos pontos R1
e R2
618.0
51
2
=
+
=F
F(x)
G1 G2
S1 R1 R2 S2 X(inverso da seção Áurea)
F(x)
S1 R1 R2 S2 X
G2G1
R1 = (1-F) . (S2 - S1) + S1
R2 = F . (S2 - S1) + S1
4. Calcula G1 = f1 (R1) e G2 = f1 (R2)
Se G1 ≤≤≤≤ G2 →→→→ S1 ≤≤≤≤ xMin ≤≤≤≤ R2
Então (abandona-se segmento R2 - S2)
Faz S2 = R2 e volta para o passo 2
F(x)
G1 G2
S1 R1 R2 S2 X
S2
Se G1 > G2 →→→→ R2 ≤≤≤≤ xMin ≤≤≤≤ S2
Então (abandona-se S1 - R1)
Faz S1 = R1 e volta para o passo 2
F(x)
G1 G2
S1 R1 R2 S2 X
S1
S1 + S2
No final xMin = ___________
2
Precisão: ∈ =
+






2
1 5
k
F(x)
G1 G2
S1 R1 R2 S2 X
F(x)
G1 G2
S1 R1 R2 S2 X
0102030405060
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
9
1
20
1
10
1
)
(
2
−
+
−
+
−
=
y
y
y
y
f
No exemplo anterior considerando o intervalo 
inicial Xs-Xi igual a (18-10) e Ys-Yi igual a (20-9), 
ambos medidos em quilômetros, tem-se, para um 
número de iterações igual a 20, as precisões em 
relação as coordenadas X e Y: (lembrar problema)
cmXiXsx 53)1018.(51
2).(
20
≈−





+
=−= εε
cmYiYsy 73)920.(51
2).(
20
≈−





+
=−= εε
Pergunta
Supondo o mesmo exemplo e desejando
uma precisão de 20 cm para ambas as 
coordenadas, determine o número de 
iterações necessárias.
181151101)(1 −+−+−= xxxxf 91201101)(2 −+−+−= yyyyf
∈ =
+






2
1 5
k
Cidade Xi Yi Pi (população)
1 82 125 85000
2 173 61 120000
3 298 87 180000
4 255 131 250000
5 270 202 57000
6 278 230 88000
7 221 259 110000
8 182 203 330000
9 118 240 42000
10 120 32063000
EXEMPLO:
Cidade Xi Yi Pi (população)
1 82 125 85000
2 173 61 120000
3 298 87 180000
4 255 131 250000
5 270 202 57000
6 278 230 88000
7 221 259 110000
8 182 203 330000
9 118 240 42000
10 120 320 63000
EXEMPLO:
Solução: Método da Derivada.
0
5
10
15
20
25
30
35
40
45
50
1 3 5 7 9 1 1 1 3 1 5 1 7 1 9 2 1 2 3 2 5 2 7 2 9
181151101)(1 −+−+−= xxxxf
100 ≤≤ x ;343)18()15()10()(1 xxxxxf −=−+−+−=⇒
;23)18()15()10()(1510 1 xxxxxfx −=−+−+−=⇒≤<
;7)18()15()10()(1815 1 −=−+−+−=⇒≤< xxxxxfx
.433)18()15()10()(18 1 −=−+−+−=⇒> xxxxxfx
181151101)(1 −+−+−= xxxxf
100 ≤≤ x ;343)18()15()10()(1 xxxxxf −=−+−+−=⇒
;23)18()15()10()(1510 1 xxxxxfx −=−+−+−=⇒≤<
;7)18()15()10()(1815 1 −=−+−+−=⇒≤< xxxxxfx
.433)18()15()10()(18 1 −=−+−+−=⇒> xxxxxfx
0
5
10
15
20
25
30
35
40
45
50
1 3 5 7 9 1 1 1 3 1 5 1 7 1 9 2 1 2 3 2 5 2 7 2 9
181151101)(1 −+−+−= xxxxf
xxf 343)(1 −=
xxf −= 23)(1
1º Função: 0 -3= -3
2º Função: 1 -2= -1
3º Função: 2 -1= 1 7)(1 −= xxf
4º Função: 3-0 = 3 433)(1 −= xxf
100 ≤≤ x
0
5
10
15
20
25
30
35
40
45
50
1 3 5 7 9 1 1 1 3 1 5 1 7 1 9 2 1 2 3 2 5 2 7 2 9
181151101)(1 −+−+−= xxxxf
xxf 343)(1 −=
xxf −= 23)(1
7)(1 −= xxf
433)(1 −= xxf
∑−= ipa1
1510 ≤< x 11*231 −=+−=a
1815 ≤< x 11*211 =+−=a
18>x 31*211 =+=a
Ordene os pesos por ordem crescente das abscissas
Min:= ∑
=
−
n
i
ip
1
;
i:=0;
Enquanto 0<Min faça
i:=i+1;
ipMinMin 2: +=
fim enquanto
ixX =:min
Fim
Inicio
Pergunta
Dado os 5 pontos abaixo, calcule a 
abcissa do ponto central pelo método da
derivada .
Pto X Y Peso
1 157 94 1500
2 230 153 2000
3 328 166 3000
4 198 245 1000
5 313 277 2000
Outra solução ( Método da Mediana):
Inicio
Ordene os pesos por ordem crescente das abscissas;
2
: 1
∑
=
=
n
i
ip
Compara
soma:=0;
i:=0;
enquanto (soma<compara) faça
i:=i+1;
soma:=soma+ ip
;
fim enquanto
Xmin:=xi
Fim
Pergunta
Dado os 5 pontos abaixo, calcule a 
ordenada ponto central pelo método da
mediana .
Pto X Y Peso
1 157 94 1500
2 230 153 2000
3 328 166 3000
4 198 245 1000
5 313 277 2000
D
ist
ri
bu
iç
ão
Es
pa
ci
a
l
A
le
a
tó
ri
a
Distribuição Espacial Aleatória
Processo de Poisson
[ ]
!
)()(
K
etKtXP
tk λλ −
== para t 0≥
[ ]KtXP =)(
Onde:
→ Probabilidade de ocorrer K eventos no 
intervalo [0,t];
ttk λ=)(
ttKVar λ=)((
λ → Constante positiva que representa a taxa 
média de ocorrência de eventos por unidade 
de tempo
Ex: min/2pass=λ
[ ] 0058,0
!10
)20(10)(
2010
===
−e
tXP
Depois de 10 min. Probabilidade de chegar 10 pass?
[ ]
!
)()(
K
etKtXP
tk λλ −
==
P1
P4
P2
P3
Região A
Área Aλ
!
)())((
N
eANAXP
AN λλ −
==
N A A( ) = λ
AλVar =
Se N > 15 Pede-se aproximar a distribuição por 
uma dist. Normal.
NNN σ96,1±=
NNN σ96.11 +=
NNN σ96.12 −=
No Intervalo de Confiança de 95%:
N A A( ) = λ ( ) 21Aλσ =
Exemplo:
Uma região urbana com dens média de 2000hab/km2, o consumo
médio de gás engarrafado é ~ 0,24 botijões/hab e por mês. Cada
caminhão de entrega percorre por semana/ uma zona com área média
de 3 km2. Qual a variação esperada do num de botijões vendidos por
caminhão e por viagem (1 viagem por semana), supondo uma dist. 
Poisson para os pontos de venda?
( ) botAt 3,18336 5,021 === λσ
viag
bot
kmdiashab
diashabkmbotAtAN .336
.30.
7.2000.3.24,0)( 2
2
=== λ
NNN σ96,1±= botNN N 3003,18.96,133696.12 =−=−= σ
botNN N 3723,18.96,133696.11 =+=+= σ
B
o
m
F
im
d
e
 
S
e
m
a
n
a
!!
!