Журнал обчислювальної та прикладної математики / Київ. нац. ун-т ім. Тараса Шевченка. № 3 (123). - Київ: ТВіМС, 2016
Анотація:
Рассматривается задача оптимальной упаковки произвольных эллипсов в контейнере минимальной площади. Допускаются непрерывные трансляции и вращения эллипсов. Предлагаются новые, свободные от радикалов phi-функции для эллипсов, аппроксимированных дугами окружностей, которые используются для аналитического описания основных ограничений размещения (непересечение эллипсов и включение эллипсов в контейнер). Строится математическая модель задачи в виде задачи нелинейного программирования (NLP-model). Предлагается эффективный алгоритм, позволяющий получать "хорошие" допустимые упаковки эллипсов за значительно меньшее время, чем известные аналоги. Предложенный подход позволяет упаковывать большое число эллипсов (до 1000). Приводятся результаты численных экспериментов упаковки эллипсов в прямоугольном и круговом контейнерах.
We consider a packing problem of arbitrary ellipses in a container of minimal area. Сontinuous translations and rotations of ellipses are allowed. New radical free phi-functions for approximated by circular arcs ellipses are employed, which allow us to describe placement (nonoverlapping and containment) constraints analitically. We present an exact mathematical model of our problem in the form of continuous nonliner programming problem& (NLPmodel). We develop the efficient algorithm to search for "good" feasible arrangments of ellipses for considerably smaller computational time than the known analogs. The proposed approach allows us to pack the large number of ellipses (up to 1000&). Computational results are given for packing ellipses in rectangular and circular containers.
