| Processo: | 10/18980-3 |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Data de Início da vigência: | 01 de fevereiro de 2011 |
| Data de Término da vigência: | 31 de janeiro de 2013 |
| Área do conhecimento: | Ciências Exatas e da Terra - Matemática - Matemática Aplicada |
| Pesquisador responsável: | Marina Andretta |
| Beneficiário: | Marina Andretta |
| Instituição Sede: | Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil |
| Município da Instituição Sede: | São Carlos |
| Assunto(s): | Elipse Programação não linear |
| Palavra(s)-Chave do Pesquisador: | Cobertura planar | Cobertura por elipses | programação não linear | 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)
| Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio: |
| Mais itensMenos itens |
| TITULO |
| Matéria(s) publicada(s) em Outras Mídias ( ): |
| Mais itensMenos itens |
| VEICULO: TITULO (DATA) |
| VEICULO: TITULO (DATA) |