Cobertura de pontos por elipses usando programação não linear

Resumo

Problemas de cobertura maximal de pontos (MCLP - Maximal Covering Location Problems) surgem quando há recursos insuficientes para cobrir todos os pontos de demanda. Também surgem quando uma empresa busca maximizar o lucro para a cobertura selecionada. Qualquer ponto dentro da distância de cobertura é coberto e os demais pontos não são. O problema envolve implementar diferentes categorias de cobertura que possuem um custo específico associado a elas. O objetivo é cobrir os pontos que maximizam o lucro.Estamos interessados no problema de cobertura de pontos no plano por elipses: temos um conjunto de n pontos no plano (cada um com um peso associado), dispomos de um número m de elipses (cada uma com um custo associado à sua alocação) e desejamos alocar até k destas elipses de forma a cobrir os pontos no plano que tragam o maior lucro. O lucro é medido como a soma do peso dos pontos cobertos, subtraindo-se a soma dos custos das elipses alocadas.Há alguns métodos que podem ser usados para a resolução deste problema, vários dos quais empregam heurísticas e aproximações da solução. Estamos interessados em algoritmos exatos para solução do problema. Neste caso, faremos uma enumeração de subconjuntos das m elipses, com até k elementos. Para cada um destes subconjuntos, analisaremos quais pontos podem ser cobertos por estas elipses e encontraremos a melhor solução. Para descobrir onde posicionar uma elipse no plano de forma a cobrir um dado subconjunto de pontos (e se este posicionamento é possível), usaremos ALGENCAN, um método para resolver problemas de programação não linear.Estamos interessados também em desenvolver um método que considere o caso em que as elipses possuem tamanhos variáveis. Desta forma, o custo de sua alocação seria uma função de sua área. Um método para resolução deste problema mais genérico deve ser essencialmente diferente do método de enumeração mencionado acima. (AU)