Упаковка эллипсов в прямоугольник минимальных размеров

Упаковка эллипсов в прямоугольник минимальных размеров

Рассмотрена задача упаковки набора эллипсов в прямоугольник минимальных размеров. Для моделирования отношений непересечения эллипсов и его принадлежности контейнеру использованы phi-функции и квази-phi-функции. Построена математическая модель в виде задачи нелинейной оптимизации. Предложен эффективн...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Управляющие системы и машины
Datum:2016
Hauptverfasser: Данилин, А.Н., Комяк, В.В., Комяк, В.М., Панкратов, А.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Schlagworte:
Фундаментальные и прикладные проблемы информатики и информационных технологий
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/113394
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-113394
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
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Упаковка эллипсов в прямоугольник минимальных размеров
spellingShingle Упаковка эллипсов в прямоугольник минимальных размеров
Данилин, А.Н.
Комяк, В.В.
Комяк, В.М.
Панкратов, А.В.
Фундаментальные и прикладные проблемы информатики и информационных технологий
title_short Упаковка эллипсов в прямоугольник минимальных размеров
title_full Упаковка эллипсов в прямоугольник минимальных размеров
title_fullStr Упаковка эллипсов в прямоугольник минимальных размеров
title_full_unstemmed Упаковка эллипсов в прямоугольник минимальных размеров
title_sort упаковка эллипсов в прямоугольник минимальных размеров
author Данилин, А.Н.
Комяк, В.В.
Комяк, В.М.
Панкратов, А.В.
author_facet Данилин, А.Н.
Комяк, В.В.
Комяк, В.М.
Панкратов, А.В.
topic Фундаментальные и прикладные проблемы информатики и информационных технологий
topic_facet Фундаментальные и прикладные проблемы информатики и информационных технологий
publishDate 2016
language Russian
container_title Управляющие системы и машины
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
format Article
title_alt Упаковка еліпсів в прямокутник мінімальних розмірів
The Ellipses Packing in a Rectangle of the Minimal Size
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.
issn 0130-5395
url https://nasplib.isofts.kiev.ua/handle/123456789/113394
citation_txt Упаковка эллипсов в прямоугольник минимальных размеров / А.Н. Данилин, В.В. Комяк, В.М. Комяк, А.В. Панкратов // Управляющие системы и машины. — 2016. — № 5. — С. 3-9. — Бібліогр.: 18 назв. — рос.
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
first_indexed 2025-12-07T13:28:11Z
last_indexed 2025-12-07T13:28:11Z
_version_ 1850856273991434240

Ähnliche Einträge