Упаковка эллипсов в прямоугольник минимальных размеров
Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективн...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Назва видання: | Управляющие системы и машины |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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| id |
irk-123456789-113394 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1133942017-02-08T03:02:53Z Упаковка эллипсов в прямоугольник минимальных размеров Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. Фундаментальные и прикладные проблемы информатики и информационных технологий Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы 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. 2016 Article Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/113394 616.12-07 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Фундаментальные и прикладные проблемы информатики и информационных технологий Фундаментальные и прикладные проблемы информатики и информационных технологий |
| spellingShingle |
Фундаментальные и прикладные проблемы информатики и информационных технологий Фундаментальные и прикладные проблемы информатики и информационных технологий Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. Упаковка эллипсов в прямоугольник минимальных размеров Управляющие системы и машины |
| description |
Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективный алгоритм поиска локально-оптимальных решений. |
| format |
Article |
| author |
Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. |
| author_facet |
Данилин, А.Н. Комяк, В.В. Комяк, В.М. Панкратов, А.В. |
| author_sort |
Данилин, А.Н. |
| title |
Упаковка эллипсов в прямоугольник минимальных размеров |
| title_short |
Упаковка эллипсов в прямоугольник минимальных размеров |
| title_full |
Упаковка эллипсов в прямоугольник минимальных размеров |
| title_fullStr |
Упаковка эллипсов в прямоугольник минимальных размеров |
| title_full_unstemmed |
Упаковка эллипсов в прямоугольник минимальных размеров |
| title_sort |
упаковка эллипсов в прямоугольник минимальных размеров |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2016 |
| topic_facet |
Фундаментальные и прикладные проблемы информатики и информационных технологий |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/113394 |
| citation_txt |
Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос. |
| series |
Управляющие системы и машины |
| 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 |
| first_indexed |
2024-03-30T09:26:57Z |
| last_indexed |
2024-03-30T09:26:57Z |
| _version_ |
1796149984167460864 |