Modelos Matemáticos para o Problema da Poligonização de Área Máxima

Raí Caetano de Jesus, Fábio L. Usberti

Resumo


O problema do caixeiro viajante, do ponto de vista geométrico, tem por objetivo encontrar um polı́gono simples sobre um dado conjunto de vértices cujo perı́metro é mı́nimo. É possı́vel derivar o problema de modo que o objetivo seja encontrar um polı́gono simples cuja área interna seja máxima: trata-se do problema de poligonização de área máxima. Este é um problema de otimização combinatória NP-difı́cil com aplicações práticas em segmentos como reconhecimento de padrões, reconstrução de imagens, clusterização e robótica. Este trabalho apresenta dois modelos matemáticos de programação linear inteira. Experimentos computacionais foram executados para comparar as metodologias propostas com um algoritmo 12 -aproximado da literatura. Os modelos matemáticos propostos mostram a dificuldade de resolver de maneira exata o problema de poligonização de área máxima, encontrando soluções ótimas em uma hora somente para as instâncias de 10 pontos, em um conjunto de instâncias de até 50 pontos.


Palavras-chave


Poligonização, Área Máxima, Programação Linear Inteira, Matheuristic

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2018.006.02.0303

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato