Упаковка эллипсов в прямоугольник минимальных размеров
Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективн...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2016 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113394 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862622871785832448 |
|---|---|
| author | Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. |
| author_facet | Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. |
| citation_txt | Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективный алгоритм поиска локально-оптимальных решений.
Розглянуто задачу упаковки набору еліпсів у прямокутник мінімальних розмірів. Для моделювання відносин неперетинання еліпсів і його належності контейнеру використано phi-функції і квазі-phi-функції. Побудовано математичну модель у вигляді задачі нелінійної оптимізації. Запропоновано ефективний алгоритм пошуку локально-оптимальних рішень.
Introduction. In this paper, we deal with the optimal ellipse packing problem, which is a part of operational research and computational geometry. Ellipse packing problems have a variety of real world applications. However, the problem has received relatively little attention in the literature so far. Finding high quality ellipse packings is a difficult computational problem. Меthods and results. The problem is formulated as follows: the set of ellipses is to be placed without overlapping, free of any orientation restrictions, on a rectangular plate such that the area of the rectangle is minimized. The ellipses are described by the coordinates of their center and an orientation angle to allow their rotation. Two types of constraints are necessary to be modeled: the non-overlapping ellipses and the bounds placing the ellipses inside the rectangle. A new quasi-phi-function is developed for an analytical description of non-overlapping ellipses. An additional variable is introduced for each quasi-phi-function. Already known phi-function is applied to hold the containment constraint. A new mathematical programming formulations for this problem in the form of a nonlinear programming problem are presented. The constrained optimization problem is NP-hard nonlinear programming problem. The solution space Q has a complicated structure. A matrix of the inequality system which specifies Q is strongly sparse and has a block structure. Our LOFRT procedure allows us to reduce the problem with O(n2) inequalities and O(n2)-dimensional solution space to a sequence of sub-problems, each with O(n)inequalities and a O(n)-dimensional solution subspace. This reduction is of a paramount importance, since it deals with non-linear optimization problems. Conclusion. The ellipse packing problem in the form of a nonlinear programming problem is formulated and an efficient solution algorithm is developed. The presented algorithm allows to reduce the computational cost of the researched problem.
|
| first_indexed | 2025-12-07T13:28:11Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113394 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-07T13:28:11Z |
| publishDate | 2016 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. 2017-02-07T20:39:02Z 2017-02-07T20:39:02Z 2016 Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113394 616.12-07 Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективный алгоритм поиска локально-оптимальных решений. Розглянуто задачу упаковки набору еліпсів у прямокутник мінімальних розмірів. Для моделювання відносин неперетинання еліпсів і його належності контейнеру використано phi-функції і квазі-phi-функції. Побудовано математичну модель у вигляді задачі нелінійної оптимізації. Запропоновано ефективний алгоритм пошуку локально-оптимальних рішень. Introduction. In this paper, we deal with the optimal ellipse packing problem, which is a part of operational research and computational geometry. Ellipse packing problems have a variety of real world applications. However, the problem has received relatively little attention in the literature so far. Finding high quality ellipse packings is a difficult computational problem. Меthods and results. The problem is formulated as follows: the set of ellipses is to be placed without overlapping, free of any orientation restrictions, on a rectangular plate such that the area of the rectangle is minimized. The ellipses are described by the coordinates of their center and an orientation angle to allow their rotation. Two types of constraints are necessary to be modeled: the non-overlapping ellipses and the bounds placing the ellipses inside the rectangle. A new quasi-phi-function is developed for an analytical description of non-overlapping ellipses. An additional variable is introduced for each quasi-phi-function. Already known phi-function is applied to hold the containment constraint. A new mathematical programming formulations for this problem in the form of a nonlinear programming problem are presented. The constrained optimization problem is NP-hard nonlinear programming problem. The solution space Q has a complicated structure. A matrix of the inequality system which specifies Q is strongly sparse and has a block structure. Our LOFRT procedure allows us to reduce the problem with O(n2) inequalities and O(n2)-dimensional solution space to a sequence of sub-problems, each with O(n)inequalities and a O(n)-dimensional solution subspace. This reduction is of a paramount importance, since it deals with non-linear optimization problems. Conclusion. The ellipse packing problem in the form of a nonlinear programming problem is formulated and an efficient solution algorithm is developed. The presented algorithm allows to reduce the computational cost of the researched problem. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы информатики и информационных технологий Упаковка эллипсов в прямоугольник минимальных размеров Упаковка еліпсів в прямокутник мінімальних розмірів The Ellipses Packing in a Rectangle of the Minimal Size Article published earlier |
| spellingShingle | Упаковка эллипсов в прямоугольник минимальных размеров Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. Фундаментальные и прикладные проблемы информатики и информационных технологий |
| title | Упаковка эллипсов в прямоугольник минимальных размеров |
| title_alt | Упаковка еліпсів в прямокутник мінімальних розмірів The Ellipses Packing in a Rectangle of the Minimal Size |
| title_full | Упаковка эллипсов в прямоугольник минимальных размеров |
| title_fullStr | Упаковка эллипсов в прямоугольник минимальных размеров |
| title_full_unstemmed | Упаковка эллипсов в прямоугольник минимальных размеров |
| title_short | Упаковка эллипсов в прямоугольник минимальных размеров |
| title_sort | упаковка эллипсов в прямоугольник минимальных размеров |
| topic | Фундаментальные и прикладные проблемы информатики и информационных технологий |
| topic_facet | Фундаментальные и прикладные проблемы информатики и информационных технологий |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113394 |
| work_keys_str_mv | AT danilinan upakovkaéllipsovvprâmougolʹnikminimalʹnyhrazmerov AT komâkvv upakovkaéllipsovvprâmougolʹnikminimalʹnyhrazmerov AT komâkvm upakovkaéllipsovvprâmougolʹnikminimalʹnyhrazmerov AT pankratovav upakovkaéllipsovvprâmougolʹnikminimalʹnyhrazmerov AT danilinan upakovkaelípsívvprâmokutnikmínímalʹnihrozmírív AT komâkvv upakovkaelípsívvprâmokutnikmínímalʹnihrozmírív AT komâkvm upakovkaelípsívvprâmokutnikmínímalʹnihrozmírív AT pankratovav upakovkaelípsívvprâmokutnikmínímalʹnihrozmírív AT danilinan theellipsespackinginarectangleoftheminimalsize AT komâkvv theellipsespackinginarectangleoftheminimalsize AT komâkvm theellipsespackinginarectangleoftheminimalsize AT pankratovav theellipsespackinginarectangleoftheminimalsize |