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

Origem: Wikilivros, livros abertos por um mundo aberto.

O objectivo é localizar uma nova instalação num ponto ,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, . 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 for o máximo das distâncias ponderadas entre e os nós da árvore, tem-se:


O centro absoluto é um ponto na árvore que minimiza . 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,

2. Encontrar uma ponta da árvore, , que esteja mais afastada de

3. Encontrar uma ponta da árvore , que esteja mais afastada de . O ponto a meio do caminho que liga a é o único centro absoluto.


Figura 9.12.1.2.1 Rede em árvore


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 . é a ponta da árvore mais afastada de . é a ponta da árvore mais afastada de . Então o centro absoluto ,localiza-se o no arco .

O valor óptimo da função objectivo é:

Procedimento para Determinar o Centro Absoluto Ponderado

Primeiro calcule-se . Então é o ponto único no caminho que liga os nós e que satisfaz as seguintes equações:




com



e



Portanto, é o menor valor de , que, por sua vez, é o menor valor da função objectivo do problema do centro absoluto.


Com



Para calcular , o maior valor da matriz , o procedimento é o seguinte:


1. Calcular os valores de uma linha qualquer de , por exemplo e encontrar o maior valor na linha , por exemplo na coluna .


2. Calcular os valores da coluna e encontrar o maior valor na coluna , que ocorre, por exemplo, na linha .


3. Calcular os valores da linha e encontrar o maior valor na linha 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 .

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.

Figura 9.12.1.2.2. Exemplo de rede em árvore onde os nós representam as localizações 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 é . Portanto, o tempo máximo para fazer uma entrega, , é 27,4. Para determinar a localização da nova instalação, , utilizam-se as equações acima e, uma vez que e , conclui-se que a nova instalação, , 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 a



Interpretando como o tempo de transporte de para o nó , pode-se designar por adenda, , o tempo de preparar o transporte mais o tempo de carga ou descarga do nó, mais o tempo de viagem do nó 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 que se pretende minimizar é


Procedimento para Determinar o Centro Absoluto Ponderado com Adendas


1.Para cada e tais que Calcular definido por:



Seguidamente encontrar , valor máximo de .


2.Calcular , máximo dos .


3. Calcular , máximo de e .


4. Se , então é a solução do problema.


5. Caso o ponto 4 não se verifique, , então é o ponto que liga os vértices e que satizafaz as seguintes equações:




Quando se pretende determinar o centro absoluto ponderado num nó, deve-se avaliar nos nós do arco que contém e escolher como centro absoluto ponderado num nó aquele que tenha menor valor de .