terça-feira, maio 23, 2006

 

Localização central de centro de distribuição / hipermercado numa rede


Um centro é qualquer nó x com o menor valor possível de MVV (x); isto é, um centro é qualquer nó x tal que o nó mais distante de x está tão perto quanto possível,

MVV (x) = min {MVV (i)}

onde

MVV (i) = max { d (i, j)}

O algoritmo de Floyd ou o algoritmo de Dantzig podem ser usados para calcular a matriz das distâncias nó - nó, D, cujo elemento i, j é d (i, j), a distância mais curta do nó i ao nó j. A distância máxima MVV (i) do nó i a qualquer nó é o maior elemento da linha i da matriz D. Um centro é qualquer nó x com o menor valor possível de MVV (x); isto é, um centro é qualquer nó cuja a linha na matriz D tem o menor valor máximo.


Para encontrar o centro da rede da Figura 1 (Localização mediana), a matriz das distâncias mais curtas entre todos os pares de nós, D, usando o algoritmo de Floyd ou o de Dantzig, é



Então,

MVV (1) = max {0, 2, 3, 3} = 3

MVV (2) = max {4, 0, 2, 1} = 4

MVV (3) = max {6, 2, 0, 3} = 6

MVV (4) = max {3, 5, 4, 0} = 5

Então, min MVV (i) = min {3, 4, 6, 5} = 3 = MVV (1). Consequentemente, o nó 1 é um centro desta rede. O nó mais distante do nó 1 está a 3 unidades de distância. Nenhum outro nó está a menos de 3 unidades.

EVANS, James R.; MINIEKA, Edward - Optimization Algorithms For Networks and Graphs. 2.ª ed., Nova Iorque, Marcel Dekker, 1992.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?