Otimização Combinatória
O Problema da
K-Dispersão Discreta
Fabrício Lacerda Biajoli
Natacha Silva e Clemente
Importância
1. A solução de problemas de dispersão está hoje crescendo
em importância.
• Necessidade de providenciar um destino adequado a
uma série de materiais (rejeitos industriais e nucleares,
armamentos etc);
2. Conceito:
• “Dado um conjunto de n facilidades alocadas sobre os
nós de um grafo, o problema consiste em selecionar
k facilidades dentre as n possíveis, de modo que a
distância mínima entre qualquer par das k facilidades
selecionadas seja máxima.”
Aplicações
1.
2.
3.
4.
5.
6.
7.
Localização de reservatórios de combustível;
Alocação de agentes competitivos como franquias etc;
Distribuição de depósitos de lixo;
Localização de silos de mísseis e instalações nucleares;
Prisões e instalações militares;
Tratamento de águas residuais;
Distribuição de freqüências em sistemas de
comunicações;
8. Experimentos estatísticos;
9. Exploração de madeira etc.
Heurística de Erkut - Fase de Construção
de uma solução míope
INÍCIO
Ler grafo G=(N, A) e k;
B:= 0; Gargalo:= 0;
Ordenar arestas (u,v) e duv de G em uma lista C;
Enquanto |B| < (n – k) fazer
Encontrar a menor distância d(u,v) em C;
Se ( u ou v)  B então fazer
Eliminar aleatoriamente (u ou v)  B;
C  C – [(u,v), (duv)];
B  B  {elemento u ou v eliminado};
Se |B| = (n - k) então fazer
Gargalo  Min { duv , u e v  A – B};
Fim_enquanto
FIM
Exemplo:
Consideremos o problema de localizar 3
facilidades no grafo abaixo.
6
3
5
4
4
8
5
9
2
10
5
9
1
9
5
8
6
C = { [(3,6), (4)], [(1,6),(5)], [(2,3),(5)], [(1,4),(5)], [(3,4),(6)],
[(4,6), (9)], [(4,5),(8)], [(5,6),(8)], [(2,5),(9)], [(1,3),(9)],
[(2,6),(9)], [(1,2),(10)], [(2,4),(11)], [(3,5),(12)] , [(1,5),(13)]}
Encontrar a menor distância duv em C e
escolher aleatoriamente u ou v
6
3
5
4
4
8
5
9
2
10
5
9
1
9
5
8
6
C = { [(3,6), (4)], [(1,6),(5)], [(2,3),(5)], [(1,4),(5)], [(3,4),(6)],
[(4,6), (9)], [(4,5),(8)], [(5,6),(8)], [(2,5),(9)], [(1,3),(9)],
[(2,6),(9)], [(1,2),(10)], [(2,4),(11)], [(3,5),(12)], [(1,5),(13)]}
B = { (3) };
Gargalo = 0;
|B| = 1;
Encontrar a menor distância duv em C e
escolher aleatoriamente u ou v
6
3
5
4
4
8
5
9
2
10
5
9
1
9
5
8
6
C = { [(1,6),(5)], [(2,3),(5)], [(1,4),(5)], [(3,4),(6)], [(4,6), (9)],
[(4,5),(8)], [(5,6),(8)], [(2,5),(9)], [(1,3),(9)], [(2,6),(9)],
[(1,2),(10)], [(2,4),(11)], [(3,5),(12)] , [(1,5),(13)]}
B = { (3) , (1)}
Gargalo = 0;
|B| = 2;
Encontrar a menor distância duv em C e
escolher aleatoriamente u ou v
6
3
5
4
4
8
5
9
2
10
5
9
1
9
5
8
6
C = { [(2, 3),(5)], [(1,4),(5)], [(3,4),(6)], [(4,6), (9)], [(4,5),(8)],
[(5,6),(8)], [(2,5),(9)], [(1,3),(9)], [(2,6),(9)], [(1,2),(10)],
[(2,4),(11)], [(3,5),(12)] , [(1,5),(13)]}
B = { (3) , (1), (2)}
Gargalo = 8;
|B| = (n – k) = 3;
Solução Míope Encontrada pelo
algoritmo de Erkut
6
3
5
4
4
8
5
9
2
10
9
9
1
5
5
6
Gargalo = 8;
Solução Míope = {4, 5, 6};
8
Fase de Melhoria da Solução Corrente
INÍCIO
Ler grafo G=(N, A), B, k e o Gargalo;
V := A – B; temp:= Ø;
Para  i  B fazer
Se ((diu > div ) & (diu > Gargalo)) então w:= v ;
Se ((div > diu ) & (div > Gargalo)) então w:= u ;
temp:= {i}  V – {w};
Novo_Gargalo:= Min (duv , u e v  temp);
Se Novo_Gargalo > Gargalo então fazer
V  { i }  V – { w };
temp  V;
B  B – { i };
Fim_para
FIM
Fase de Melhoria da Solução Corrente
Nó i
escolhido
(u, v) d(u, v)
Maior
d(u, v)
Possível Gargalo
Solução
d24=11 d24 > d25
9>8
(4 , 5)
(2, 4, 6)
Melhoria
d25=9 d24 > Garg.
2
d24=11 d24 > d26
(4 , 6)
(2, 4, 6)
d26=9 d24 > Garg.
d25=9
(5 , 6)
d26=9
d25 = d26
-
Mesma
anterior
-
Solução Melhorada se o nó escolhido
fosse o nó 2
5
4
9
2
6
3
4
5
9
8
5
9
10
1
11
6
5
4
2
9
9
6
8
Gargalo = 9;
Solução = {2, 4, 6};