terça-feira, junho 06, 2006

 

Afectação quadrática (I)


Quando há trocas de mercadorias ou materiais entre as novas instalações, o problema é de afectação quadrática.

Suponha-se que queremos localizar quatro postos de trabalho, no talho de um hipermercado. Os valores dos fluxos e distâncias são dadas nas matrizes simétricas V e D,

V=0283
2049
8405
3950


D=08102
8047
10409
2790

Ordenando os valores de vj h e os valores dk l obtêm-se os vectores v e d.

v = (9, 8, 5, 4, 3, 2)

e

d = (2, 4, 7, 8, 9, 10)

O limite inferior LB é dado por

LB = v d’ = 9 (2) + 8 (4) + 5 (7) + 4 (8) + 3 (9) + 2 (10) = 164


Procedimento de construção

O maior valor de fluxo (v2 4 = 9) é entre os postos de trabalho 2 e 4; a menor distância (d1 4 = 2) é entre os locais 1 e 4. Então, o posto de trabalho 1 é afectado ou ao local 1 ou local 4 e o posto de trabalho 4 é afectado ao local restante. O valor seguinte de fluxo em v é v13 = 8 e o valor seguinte da distância em d é d2 3 = 4; portanto, é desejável afectar os postos de trabalho 1 e 3 aos locais 2 e 3. O valor seguinte de fluxo em v é v3 4= 5 e o valor seguinte da distância em d é d2 4 = 7; portanto, é desejável afectar os postos de trabalho 3 e 4 aos locais 2 e 4. Dado que o posto de trabalho 4 pode ser afectado ao local 1 ou local 4 e o posto de trabalho pode ser afectado ao local 2 ou local 4 ela, decorre que o posto de trabalho 4 é afectado ao local 4. Então, o posto de trabalho 2 é afectado ao local 1, o posto de trabalho 3 é afectado ao local 2 e o posto de trabalho 1 é afectado ao local 3.

O custo desta afectação é

z = v1 2 d3 1 + v1 3 d3 2 + v1 4 d3 4 + v2 3 d1 2 + v2 4 d1 4 + v3 4 d2 4

= 2 (10) + 8 (4) + 3 (9) + 4 (8) + 9 (2) + 5 (7)

= 164

Uma vez que o valor da função objectivo da afectação é igual ao limite inferior, foi obtida uma solução óptima. Isto nem sempre acontece. Para problemas maiores, os detalhes deste método tornam-se um pouco mais complicados; no entanto, o princípio mantém-se o mesmo: Localizar as instalações que têm a maior interacção (fluxo) o mais próximas possível.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

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