|
O [[w:Objectivo|objectivo]] é encontrarlocalizar uma nova instalação num ponto <math>\ y^*</math> situado em umanuma rede em árvore, que minimize o máximo das distâncias ponderadas entre a nova instalação e os [[w:Consumidor|clientes]] localizados nos nós de umaduma árvore, <math>\ v_i</math>. Este ponto designa-se por centro absoluto ([[Logística/Referências#refbFrancisb|Francis, 1992, p. 405-411]]).
O ponto <math>\ y^*</math> é designado por centro absoluto.
Quando se fala em [[w:Localização|localização]] central aA nova instalação deve estarser situada num ponto <math>\ y^*</math>localizada de formamodo a minimizar um tempo, custo ou perda.: ([[Logística/Referências#refbFrancisb|Francis,a 1992,preocupação é com o p.pior caso que se quer tornar 405-411]])no menor mal possível.
<math>\ g(y) = \max \big\{w_i d (y, v_1), ..., w_m d (y, v_m)\big\}</math>
O centro absoluto <math>\ y^*</math> é um ponto na árvore que minimiza <math>\ g(y)</math>. O centro absoluto não ponderado localiza-se a meio do caminho mais longo da árvore. Para resolver o [[w:Problema matemático|problema]] utiliza-se o seguinte [[w:Algoritmo|algoritmo]]:
O [[w:Algoritmo|algoritmo]] para determinar o centro absoluto não-ponderado é utilizado para encontrar <math>\ y^*</math> que minimiza <math>\ g(y)</math>, sendo que este está situado a meio do caminho mais longo da árvore.
Para resolver o problema basta seguir os seguintes passos:
1. Escolher um nó qualquer <math>\ v</math>
Para determinar oa centrolocalização absolutocentral não-ponderadoduma dainstalação rede emna árvore representada nada Figura 9.12.1.2.1, escolhe-se por exemplo <math>\ v_1</math>, como <math>\ v_3</math> é a ponta da árvore mais afastada de <math>\ v_1</math> e <math>\ v_1</math> é a ponta da árvore mais afastada de <math>\ v_3</math> o centro absoluto está situado no arco <math>\ (v_2, v_3) </math>, sendo que o valor óptimo da função objectivo é:
<math>\ g(y^*) = 6 </math>
Quando o que se pretende é determinar o centro absoluto ponderado deve-se determinar <math>\ b_{st}</math>.
Neste caso <math>\ y*</math> é o ponto único pontono caminho naque ligaçãoliga dosos nós <math>\ s</math> e <math>\ t</math> que satisfaz as seguintes equações:
Portanto, <math>\ b_{st}</math> é o menor valor de <math>\ z</math>., Sendoque, <math>\por z</math>sua vez, é o menor valor da função objectivo do problema do centro absoluto.
Para determinar o valor de <math>\ b_{st}</math>, o maior valor da matriz <math>\ B = (b_{ij})</math> utiliza-se o seguinte procedimento:
1. Calcular os valores de uma linha qualquer da [[w:Matriz (matemática)|matriz]] <math>\ B = (b_{ij})</math> e determinar o maior valor na linha <math>\ l</math>, por [[w:Exemplo|exemplo]] na coluna <math>\ c(1)</math>.
21. Calcular os valores de uma linha qualquer da coluna[[w:Matriz (matemática)|matriz]] <math>\ cB = (b_{ij})</math>, por [[w:Exemplo|exemplo]] <math>\ l(1)</math> e encontrar o maior valor quena ocorrelinha <math>\ l(1)</math>, por exemplo na linhacoluna <math>\ lc(21)</math>.
32. Calcular os valores deda coluna <math>\ lc(21)</math> e encontrar o seu maior valor na coluna <math>\ c(1)</math>, que ocorre por exemplo, na linha <math>\ l(2)</math>.
Estes3. passosCalcular devemos servalores feitosda linha <math>\ l(2)</math> e encontrar o maior valor na linha <math>\ l(2)</math> e assim sucessivamente, continuando até se conseguir encontrar, pela primeira vez, a mesma entrada da matriz duas vezes seguidas; este número será o maior elemento da matriz <math>\ B </math>.
| 