# Logística/Localização/Localização em redes/Localização em redes em árvore/Localização central

O objectivo é localizar uma nova instalação num ponto $\ y^{*}$,de uma rede em árvore, que minimize o máximo das distâncias ponderadas entre a nova instalação e as instalações existentes localizadas nos nós da árvore, $\ v_{i}$. Este ponto designa-se por centro absoluto (Francis, 1992, p. 405-411).
A nova instalação deve ser localizada de modo a minimizar um tempo, custo ou perda: a preocupação é com o pior caso que se quer tornar no menor mal possível.
Se $\ g(y)$ for o máximo das distâncias ponderadas entre $\ y$ e os nós da árvore, tem-se:
$\ g(y)=\max {\big \w_{i}d(y,v_{1}),...,w_{m}d(y,v_{m}){\big \}}$
O centro absoluto $\ y^{*}$ é um ponto na árvore que minimiza $\ g(y)$. O centro absoluto não ponderado localiza-se a meio do caminho mais longo da árvore, de onde se poder usar o algoritmo particularmente simples, seguinte, para resolver o problema.
Algoritmo para Determinar o Centro Absoluto Não-Ponderado
1. Escolher um nó qualquer, $\ v$
2. Encontrar uma ponta da árvore, $\ v'$, que esteja mais afastada de $\ v$
3. Encontrar uma ponta da árvore $\ v''$, que esteja mais afastada de $\ v'$. O ponto a meio do caminho que liga $\ v'$ a $\ v''$ é o único centro absoluto.
Para determinar a localização central de um centro de distribuição, na árvore da Figura 9.12.1.2.1, escolhe-se por exemplo $\ v_{1}$. $\ v_{3}$ é a ponta da árvore mais afastada de $\ v_{1}$. $\ v_{1}$ é a ponta da árvore mais afastada de $\ v_{3}$. Então o centro absoluto $\ y^{*}$,localiza-se o no arco $\ (v_{2},v_{3})$.
O valor óptimo da função objectivo é:
$\ g(y^{*})=6$
Procedimento para Determinar o Centro Absoluto Ponderado
Primeiro calcule-se $\ b_{st}$. Então $\ y*$ é o ponto único no caminho que liga os nós $\ s$ e $\ t$ que satisfaz as seguintes equações:
$\ d(y^{*},v_{s})=w_{t}d(v_{s},v_{t})/(w_{s}+w_{t})$
$\ d(y^{*},v_{t})=w_{s}d(v_{s},v_{t})/(w_{s}+w_{t})$
com
$b_{st}=\max {\big \b_{ij}:1\leq j\leq m{\big \}}\leq z$
e
$w_{i}d(y,v_{i})\leq z,i=1,...,m$
Portanto, $\ b_{st}$ é o menor valor de $\ z$, que, por sua vez, é o menor valor da função objectivo do problema do centro absoluto.
Com
$\ b_{ij}=w_{i}w_{j}d(v_{i},v_{j})/(w_{i}+w_{j})$
Para calcular $\ b_{st}$, o maior valor da matriz $\ B=(b_{ij})$, o procedimento é o seguinte:
1. Calcular os valores de uma linha qualquer de $\ B=(b_{ij})$, por exemplo $\ l(1)$ e encontrar o maior valor na linha $\ l(1)$, por exemplo na coluna $\ c(1)$.
2. Calcular os valores da coluna $\ c(1)$ e encontrar o maior valor na coluna $\ c(1)$, que ocorre, por exemplo, na linha $\ l(2)$.
3. Calcular os valores da linha $\ l(2)$ e encontrar o maior valor na linha $\ l(2)$ e assim sucessivamente, continuando até se encontrar, pela primeira vez, a mesma entrada da matriz duas vezes seguidas; este número será o maior elemento da matriz $\ B$.
Considere-se, por exemplo, a rede em árvore da Figura 9.12.1.2.2, onde os nós representam localizações de instalações existentes e os pesos, tempo por unidade de distância.
Para determinar a localização de uma nova instalação que minimize o tempo máximo das viagens de entregas as instalações existentes, o centro absoluto da rede em árvore da Figura 9.12.1.2.2, pode-se ver que o maior valor da matriz $\ B$ é $\ (b_{35}=27,4$. Portanto, o tempo máximo para fazer uma entrega, $\ g(y^{*})$, é 27,4. Para determinar a localização da nova instalação, $\ y^{*}$, utilizam-se as equações acima e, uma vez que $\ d(y^{*},v_{s})=9,15$ e $\ d(y^{*},v_{t})=6,85$, conclui-se que a nova instalação,$\ y^{*}$ , deve ficar a uma distância de 9,15 do nó 3 e a uma distância de 6,85 do nó 5, ou seja, essa localização será no arco que liga $\ v_{4}$ a $\ v_{5}$
${\begin{bmatrix}0&5&8,4&13,3&25,3&18\\5&0&2,4&8&18,6&13\\8,4&2,4&0&13,7&27,4&18\\13,3&8&13,7&0&20&9,3\\24,3&18,6&27,4&20&0&20\\18&13&18&9,3&10&0\end{bmatrix}}$
Interpretando $\ w_{1}d(y,v_{i})$ como o tempo de transporte de $\ y$ para o nó $\ i$, pode-se designar por adenda, $\ h_{i}$, o tempo de preparar o transporte mais o tempo de carga ou descarga do nó, mais o tempo de viagem do nó $\ i$ para qualquer outro ponto conhecido na rede, tal como um centro de recolha de veículos. Naturalmente, dependendo das circunstâncias, alguns destes tempos podem ser nulos.
Neste caso, a função $\ g(y)$ que se pretende minimizar é
$\ g(y)=\max {\big \w_{1}d(y,v_{1})+h_{1},...,w_{m}d(y,v_{m})+h_{m}{\big \}}$
Procedimento para Determinar o Centro Absoluto Ponderado com Adendas
1.Para cada $\ i$ e $\ j$ tais que $\ 1\leq i\leq j\leq m$ Calcular $\ b_{ij}$ definido por:
$\ b_{ij}=(w_{i}w_{j}d(v_{i},v_{j})+w_{j}h_{i}+w_{i}h_{j})/(w_{i}+w_{j})$
Seguidamente encontrar $\ b_{st}$, valor máximo de $\ b_{ij}$.
2.Calcular $\ h_{p}$, máximo dos $\ h_{i}$.
3. Calcular $\ b$, máximo de $\ b_{st}$ e $\ h_{p}$.
4. Se $\ b=h_{p}$, então $\ y^{*}=v_{p}$ é a solução do problema.
5. Caso o ponto 4 não se verifique, $b=b_{st}$, então $\ y^{*}$ é o ponto que liga os vértices $\ s$ e $\ t$ que satizafaz as seguintes equações:
$\ d(y^{*},v_{s})=(w_{t}d(v_{s},v_{t})+h_{t}-h_{s})/(w_{s}+w_{t})$
$\ d(y^{*},v_{t})=(w_{s}d(v_{s},v_{t})+h_{s}-h_{t})/(w_{s}+w_{t})$
Quando se pretende determinar o centro absoluto ponderado num nó, deve-se avaliar $\ g$ nos nós do arco que contém $\ y^{*}$ e escolher como centro absoluto ponderado num nó aquele que tenha menor valor de $\ g$.