Saltar para o conteúdo

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

Origem: Wikilivros, livros abertos por um mundo aberto.

Quando se fala em localização mediana o objectivo é encontrar um ponto que minimiza a soma das distâncias ponderadas entre a nova instalação e os clientes localizados nos nós de uma rede em árvore, . Ao ponto dá-se o nome de mediana absoluta (Francis, 1992, p. 400-403).

O número de deslocações, o custo de transporte ou o tempo de deslocação por unidade de distância, durante um periodo de tempo, entre o ponto e o vértice representa-se por , logo, o objectivo é minimizar:



Neste problema, apenas os vértices são considerados como localizações potenciais, em que pelo menos um deles é uma localização óptima ou mediana absoluta e a localização mediana depende dos pesos, , assim como da estrutura da árvore, mas é independente das distâncias entre os nós. Estas distâncias só influenciam o valor de .

Algoritmo da Maioria

Este algoritimo é utilizado para determinar o valor da mediana, seguindo os dois passos indicados abaixo:

1. Escolher um nó com peso em qualquer um dos extremos da árvore. Se for maior que , onde é a soma dos pesos dos nós, esse nó é a mediana, caso contrário executar o passo 2.

2. Designar por o nó adjacente a . Somar a , de forma a encontrar o novo peso do nó e apagar da árvore o arco , excepto , e voltar ao passo 1.


Na Figura 9.12.1.1.1 o peso dos nós está representado nos quadrados, sendo .


Figura 9.12.1.1.1 Exemplo de rede em árvore com o peso dos nós dentro dos quadrados


Para encontrar a mediana da árvore representada na Figura 9.12.1.1.1 escolhe-se, por exemplo, .

O peso de é 2, como , não é mediana, segue-se, portanto, para o passo 2, ou seja, adiciona-se o peso de ao vértice adjacente , eliminando o caminho que ligava a , dando origem à seguinte rede em árvore (Figura 9.12.1.1.2):


Figura 9.12.1.1.2


Seguidamente escolhe-se . Como o peso de é inferior a , adiciona-se o peso de ao vértice adjacente , eliminando o caminho que ligava a . A rede resultante é apresentada na Figura 9.12.1.1.3.


Figura 9.12.1.1.3


De seguida escolhe-se o vértice . Como é menor que , volta-se a repetir o passo 2, dando origem a outra árvore, representada na Figura 9.12.1.1.4.


Figura 9.12.1.1.4


Como , é a localização mediana, sendo o valor óptimo da função objectivo dado por: