Aprimoramentos na Resolução de Problemas de Empacotamento Utilizando Suavização Hiperbólica
Autores
|
4391 |
47,1968
|
|
|
4392 |
47,1968
|
Informações:
Publicações do PESC
No presente trabalho, considera-se a resolução do problema de empacotamento de círculos congruentes sem sobreposição no interior de um quadrado unitário. Trata-se de encontrar a posição dos centros dos círculos que enseje a possibilidade de produzir o máximo diâmetro de q círculos idênticos, não sobrepostos, contidos no interior de um quadrado unitário. Equivalentemente, esse problema corresponde a maximizar a mínima distância entre pares de q pontos dentro de um quadrado unitário.
O problema considerado apresenta as características de ser não linear, não convexo e não diferenciável e de possuir um número expressivamente grande de mínimos locais. A metodologia desenvolvida basicamente está fundamentada no uso da técnica da suavização hiperbólica articulada ao método da penalização hiperbólica, destinado à resolução do problema de programação não linear com restrições. Nesse enfoque, a solução do problema original é produzida pela resolução de uma seqüência de problemas irrestritos da classe C".
Um conjunto de experimentos numéricos é apresentado comparando os resultados obtidos com os da literatura internacional, mostrando cabalmente a eficiência e robustez da metodologia proposta.
In this work, it is considered the solution of packing of non overlapping equal circles inside an unit square problem. It deals with finding the circle centers which offers the possibility of obtaining the maximum diameter. Equivalently, this problem corresponds to maximize the minimum distance between q points inside an unit square.
This packing problem presents non-linear, non-convex and non-differentiable characteristics and has a myriad of local minima. The proposed methodology basically makes use of the hyperbolic smoothing approach in connection with the hyperbolic penalty method, intended for the constrained non-linear programming problem solution. In this approach, the original problem solution is obtained for solving a sequence of unconstrained C.
A set of computational results obtained by using the proposed methodology together results from the literature is presented. It shows both the efficiency and the robustness of the proposal.