文章基本信息

标题：A study of ellipse packing in the high-dimensionality problems
本地全文：下载
作者：Valentina Komyak ; Vladimir Komyak ; Alexander Danilin 等
期刊名称：Eastern-European Journal of Enterprise Technologies
印刷版ISSN：1729-3774
电子版ISSN：1729-4061
出版年度：2017
卷号：1
期号：4
页码：17-23
DOI：10.15587/1729-4061.2017.91902
语种：English
出版社：PC Technology Center
摘要：The problems of optimum ellipse packing belong to the class of NP-hard problems. The issues of development of efficient algorithms based on application of local and global optimization methods, construction of adequate mathematical models based on the analytical description of the ellipse interrelations taking into account their continuous translations and rotations are of vital importance. In this article, the problem of packing of sets of ellipses in a given region taking into account conditions of nonintersection and technological restraints which are concretized in the conditions of the applied problem is formulated. The model of packing of a set of ellipses in a rectangle of minimum dimensions is constructed. Continuous ellipse rotations and translations are allowed, the possibility of availability of minimum admissible distances between them is assumed. New quasi-phi-functions are constructed for modeling of the relations of ellipse nonintersection and to define belonging of an ellipse to the container. The algorithm of search for locally optimal solutions is modified. It consists of two stages: generation of the regions of feasibility which contain the starting point and local optimization in the constructed region of feasibility. Only the algorithm step concerning construction of quasi-phi-functions is subjected to modification. It is necessary to notice that the algorithm have shown its efficiency when the quantity of ellipses does not exceed the value of 400.The model of the individual-and-flow movement of individuals approximated by ellipses with specification of technological restraints is constructed. The method of local optimization is given. Examples of computer modeling of the problems assigned in the work are given.
关键词：packing;continuous rotations;quasi-phi-functions;mathematical model;nonlinear optimization;individual-and-flow movement