Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов

В статье рассматриваются конструктивные средства математического и компьютерного моделирования отношений (включения, пересечения, касания, непересечения) эллиптических объектов. Определяется полный класс свободных от радикалов аппроксимаций phi-функций для эллипсов и их дополнений. Строится математи...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Панкратов, А.В., Романова, Т.Е., Суббота, И.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2012
Schriftenreihe:	Штучний інтелект
Schlagworte:	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/57700
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:	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов / А.В. Панкратов, Т.Е. Романова, И.А. Суббота // Штучний інтелект. — 2012. — № 4. — С. 89-96. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-57700
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-577002025-02-09T14:11:19Z Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов Математичне моделювання відносин еліпсів у задачах оптимальної кластеризації об’єктів Mathеmatical Modeling of Relations of Ellipses in Optimal Object Clustering Панкратов, А.В. Романова, Т.Е. Суббота, И.А. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем В статье рассматриваются конструктивные средства математического и компьютерного моделирования отношений (включения, пересечения, касания, непересечения) эллиптических объектов. Определяется полный класс свободных от радикалов аппроксимаций phi-функций для эллипсов и их дополнений. Строится математическая модель задачи оптимальной кластеризации эллиптических объектов в виде последовательности задач нелинейной оптимизации. Приводятся результаты тестовых примеров. У статті розглянуті конструктивні засоби математичного та комп’ютерного моделювання відносин (включення, перетину, дотику, неперетину) еліптичних об’єктів. Визначено повний клас апроксимацій phi-функцій (що вільні від радикалів) для еліпсів та їх доповнень. Побудовано математичну модель задачі оптимальної кластеризації еліптичних об’єктів у вигляді послідовності задач нелінійної оптимізації. Наведено результати тестових прикладів. The article considers constructive tools of mathematical modeling and computer simulation technique of relations (inclusion, non-intersecting, touching, intersecting) between elliptic objects. A complete class of free radical approximations of phi-functions for ellipses and their complements are defined. We provide a mathematical model of the optimal clustering of elliptic objects in the form of constrained optimisation problem. A number of computational results are given. 2012 Article Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов / А.В. Панкратов, Т.Е. Романова, И.А. Суббота // Штучний інтелект. — 2012. — № 4. — С. 89-96. — Бібліогр.: 10 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57700 004:519.6;519.859 ru Штучний інтелект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
spellingShingle	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Панкратов, А.В. Романова, Т.Е. Суббота, И.А. Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов Штучний інтелект
description	В статье рассматриваются конструктивные средства математического и компьютерного моделирования отношений (включения, пересечения, касания, непересечения) эллиптических объектов. Определяется полный класс свободных от радикалов аппроксимаций phi-функций для эллипсов и их дополнений. Строится математическая модель задачи оптимальной кластеризации эллиптических объектов в виде последовательности задач нелинейной оптимизации. Приводятся результаты тестовых примеров.
format	Article
author	Панкратов, А.В. Романова, Т.Е. Суббота, И.А.
author_facet	Панкратов, А.В. Романова, Т.Е. Суббота, И.А.
author_sort	Панкратов, А.В.
title	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
title_short	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
title_full	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
title_fullStr	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
title_full_unstemmed	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
title_sort	математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2012
topic_facet	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/57700
citation_txt	Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов / А.В. Панкратов, Т.Е. Романова, И.А. Суббота // Штучний інтелект. — 2012. — № 4. — С. 89-96. — Бібліогр.: 10 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT pankratovav matematičeskoemodelirovanieotnošenijéllipsovvzadačahoptimalʹnojklasterizaciiobʺektov AT romanovate matematičeskoemodelirovanieotnošenijéllipsovvzadačahoptimalʹnojklasterizaciiobʺektov AT subbotaia matematičeskoemodelirovanieotnošenijéllipsovvzadačahoptimalʹnojklasterizaciiobʺektov AT pankratovav matematičnemodelûvannâvídnosinelípsívuzadačahoptimalʹnoíklasterizacííobêktív AT romanovate matematičnemodelûvannâvídnosinelípsívuzadačahoptimalʹnoíklasterizacííobêktív AT subbotaia matematičnemodelûvannâvídnosinelípsívuzadačahoptimalʹnoíklasterizacííobêktív AT pankratovav mathematicalmodelingofrelationsofellipsesinoptimalobjectclustering AT romanovate mathematicalmodelingofrelationsofellipsesinoptimalobjectclustering AT subbotaia mathematicalmodelingofrelationsofellipsesinoptimalobjectclustering
first_indexed	2025-11-26T17:24:16Z
last_indexed	2025-11-26T17:24:16Z
_version_	1849874563688562688
fulltext	«Штучний інтелект» 4’2012 89 2П УДК 004:519.6;519.859 А.В. Панкратов, Т.Е. Романова, И.А. Суббота Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, г. Харьков Украина, 61046, г. Харьков, ул. Дм. Пожарского, 2/10, tarom27@yahoo.com Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов A.V. Pankratov, Т.E. Romanova, I.А. Subbota Institute for Mechanical Engineering Problems of the National Academy of Sciences Ukraine, 61046, Kharkov, Pozharsky Str., 2/10, tarom27@yahoo.com Mathеmatical Modeling of Relations of Ellipses in Optimal Object Clustering О.В. Панкратов, Т.Є. Романова, І.О. Субота Iнститут проблем машинобудування iм. А.М. Пiдгорного НАН України Україна, 61046, м. Харків, вул. Дм. Пожарського, 2/10, tarom27@yahoo.com Математичне моделювання відносин еліпсів у задачах оптимальної кластеризації об’єктів В статье рассматриваются конструктивные средства математического и компьютерного моделирования отношений (включения, пересечения, касания, непересечения) эллиптических объектов. Определяется полный класс свободных от радикалов аппроксимаций phi-функций для эллипсов и их дополнений. Строится математическая модель задачи оптимальной кластеризации эллиптических объектов в виде последовательности задач нелинейной оптимизации. Приводятся результаты тестовых примеров. Ключевые слова: математическое моделирование, эллипсы, phi-функция, оптимальная кластеризация. У статті розглянуті конструктивні засоби математичного та комп’ютерного моделювання відносин (включення, перетину, дотику, неперетину) еліптичних об’єктів. Визначено повний клас апроксимацій phi- функцій (що вільні від радикалів) для еліпсів та їх доповнень. Побудовано математичну модель задачі оптимальної кластеризації еліптичних об’єктів у вигляді послідовності задач нелінійної оптимізації. Наведено результати тестових прикладів. Ключові слова: математичне моделювання, еліпси, phi-функція, оптимальна кластеризація. The article considers constructive tools of mathematical modeling and computer simulation technique of relations (inclusion, non-intersecting, touching, intersecting) between elliptic objects. A complete class of free radical approximations of phi-functions for ellipses and their complements are defined. We provide a mathematical model of the optimal clustering of elliptic objects in the form of constrained optimisation problem. A number of computational results are given. Key words: mathematical modeling, ellipses, phi-function, optimal clustering. При создании систем искусственного интеллекта, предназначенных для решения оптимизационных задач размещения (Packing&Cutting) [например, 1-4], в частности задач кластеризации, конструктивным средством аналитического описания отношений (включения, пересечения, касания, непересечения) геометрических объектов является метод phi-функций Стояна [5-7]. mailto:tarom27@yahoo.com mailto:tarom27@yahoo.com mailto:tarom27@yahoo.com Панкратов А.В., Романова Т.Е., Суббота И.А. «Искусственный интеллект» 4’201290 2П В работах [6-8] приводится полный класс phi-функций для неориентированных базовых объектов, а также уникальный метод генерации математических моделей, основой которого является построение phi-деревьев. Поскольку класс односвязных базовых объектов не включает объекты, обладающих формой эллипса, целью данного исследования является построение phi-функций для эллипсов. В работе [9] построен нулевой уровень phi-функции (годограф) для пары эллипсов в параметрическом виде. Вопрос построения phi-функции с учетом непрерывных транс- ляций и вращений является по-прежнему открытым. При этом для формирования phi- функций важным является использование свободных от радикалов функций, имеющих степень не выше второй, поскольку методы решения оптимизационных задач размеще- ния используют методы локальной оптимизации. Цель статьи – разработка конструктивных средств математического модели- рования (phi-функций) для описания отношений эллиптических объектов в анали- тическом виде. Объекты и их отношения Пусть имеется эллипс  , заданный большой и малой полуосями а и b, круг С радиуса r и объекты вида: * 2 \ intR   , * 2 \ intC R C . Полагаем, что начало собственной системы координат объекта * { , , , }A C C   находится в его центре симметрии. Вектор ( , , , )u x y h  характеризует параметры размещения ( , , )x y  и коэффи- циент гомотетии h объекта A , где ( , )x y – вектор трансляции,  – угол поворота, 0h  . Рассматриваются следующие отношения между объектами A( 1u ) и B( 2u ): – пересечение: intA( 1u )  intB( 2u )  ; (1) – касание: intA( 1u )  intB( 2u ) =  и frA( 1u )  frB( 2u )  ; (2) – непересечение: A( 1u )  B( 2u ) = ; (3) – включение: A( 1u ) B( 2u )  intA( 1u )  intB( 2u ) = , * 2 \ intB R B . (4) Phi-функция AB [5-7] определена для пары phi-объектов A( 1u ) и B( 2u ), непре- рывна и удовлетворяет следующим свойствам: 0AB  , если выполняется условие (3), 0AB  , если выполняется условие (2), 0AB  в случае (1). Отношение включения (4) описывается * 0AB  . В работе [3] доказано, что произвольный phi-объект, граница которого форми- руется дугами окружности и отрезками прямых, всегда может быть декомпозирован на базовые объекты. Тогда phi-функции AB  { 1 2 ,E E * ,EC * }CE для рассматриваемых пар объек- тов A и B определяются как  min , 1, ..., ,AB i i n    где i – phi-функции для базовых объектов, A Bn n n  , ( )A Bn n – число базовых объектов, реализующих декомпо- зицию объекта A ( B ). В работах [7], [8] построен полный класс phi-функции для базовых объектов. В этой связи представим аппроксимации объектов E и E в виде объединения базо- вых объектов. Математическое моделирование отношений эллипсов в задачах.... «Штучний інтелект» 4’2012 91 2П Аппроксимация объектов ,  . Для построения phi-функций ,AB , { , , , }A B C C   * , { , , , }A B C C   , осуществим  -аппроксимацию объектов ,  базовыми объектами. Погрешность  зависит от значений а и b. Аппроксимируем границу эллипса  дугами окружности. Построенный овальный объект   является  -аппроксимацией эллипса  . При этом выполняется соотношение:     . Объект   представим в виде объединения базовых объектов вида  5 1 ,i i B     (рис. 1), где  , ,iB C D K , а именно  1 2 3 4 5,C D C D K      (5) 1C – круг радиуса r с центром в точке 1( , 0), 3C – круг радиуса r с центром в точке 1( , 0) , где 1r a   , 2 2 1 1 ( )( ) 2 a b a b a b a       ; 2D – круговой сегмент ' ' 2 2 2D C T  , здесь ' 2C – круг радиуса 2R b   с центром в точке 2 2(0, )O   , 2 2 2 1 ( )( ) 2 a b a b a b b       ; ' 2T – треугольник, ' 2 1 2 1{ , , },T conv v v l две стороны которого образованы касательными к кругу ' 2C в точках 1,v 2v : 1 1( , ),v b a    2 1( , ),v b a   2 1 2 2 (0, ) R l a        , 2 2 r a b    ; 4D – круговой сегмент '' '' 4 4 4D C T  , образованный пересечением круга '' 4C и треугольника '' 4T , где '' 4C – круг радиуса 2R b   с центром в точке 2(0, ) ; '' 4T – треугольник, '' 4 3 4 2T conv v v l '' 4 3 4 2{ , , },T conv v v l две стороны которого образованы касательными к кругу '' 4C в точках 3,v 4v : 3 1( , ) ,v b a         4 1( , ),v b a        2 2 2 2 (0, ) R l a        ; 5K – выпуклый многоугольник, 5 1 2 3 4{ , , , }K conv v v v v . Заметим, что полюса объ- ектов 1 2 3 4 5, , , ,C D C D K совпадают с центром эллипса  . Рассмотрим объект  . Пусть  – эллипс, заданный большой и малой полуосями 0a и 0b . Рассмотрим эллипс  с метрическими характеристиками 0a a   и 0b b   . Полагаем  , при котором выполняется соотношение  *    . Аппроксимируем объект *  объединением базовых объектов вида (рис. 3):  * ' '' 2 4 1 2 ,C C G G     (6) где ' 2C – круг радиуса R с центром в точке 2(0, ) , '' 4C – круг радиуса R с центром в точке 2(0, ) , 2R b   ; 1G – объект * 1 1 1G P C  (рис. 2), где 1C – круг радиуса 1r a   с центром в точке 1( , 0) , 1P – полуплоскость, проходящая через точки 1v , 4v : 1 1 4 1( , ) , ( , ) ,v b a v b a                2G – объект * 2 2 2G P C  , где 2C – круг радиуса r с центром в точке 1( , 0) , 2P – полуплоскость, проходящая через точки 2v , 3v : 2 1( , ),v b a   3 1( , ).v b a     Панкратов А.В., Романова Т.Е., Суббота И.А. «Искусственный интеллект» 4’201292 2П Рисунок 1 – Аппроксимация эллипса  базовыми объектами Рисунок 2 – Объект * 1 1 1G P C  Рисунок 3 – Аппроксимация объекта  базовыми объектами 4D 5K 1C 3C 2D X R r v1v2 v3 v4 v4 P1 G1 v1 1C r Y Математическое моделирование отношений эллипсов в задачах.... «Штучний інтелект» 4’2012 93 2П Phi-функция для объектов 1  и  2  . Пусть имеются эллипсы 1 и 2 . Осуще- ствим аппроксимацию эллипсов 1 и 2 вида (5). Тогда phi-функция для объектов 1  и  2  определяется так:   1 2 1 2 3 4 5min , , , , ,E E       (7) 1 1 1 min ,i i C B B     1 2 2 min ,i i D B B     1 3 3 min ,i i C B B     1 4 4 m in ,i i D B B     1 5 5 m in ,i i K B B     где  2 2 2 2 2 1 2 3 4 5, , , ,C D C D K  , CC – phi-функция для двух кругов, CD –phi- функция для C и D, CK – phi-функция для C и K, DD – phi-функция для двух круговых сегментов, DK – phi-функция для D и K, KK – phi-функция для двух выпуклых многоугольников. Phi-функция для объектов   и C . Пусть имеется эллипс  и круг C . Осу- ществим аппроксимацию эллипса  вида (5). Тогда phi-функция для   и C определяется так:   1 * 1 1 1 * 1 ** 3 51 2 4min , , , , ,C C K CC C D C D CC       (8) где CC – phi-функция для C и C , DC – phi-функция для D и C , KC – phi-функция для K и C . Phi-функция для объектов  *  и C . Осуществим аппроксимацию объекта  вида (6). Тогда phi-функцию  C можно представить таким образом:   * * * 1 2 1 2min , , , ,CC CC CG CGC      (9) где CC – phi-функция для C и C , CG – phi-функция для С и G . Phi-функция для объектов   и  *  . Пусть имеются эллипс  и объект  . Осуществим аппроксимацию эллипса  и объекта  вида (5), (6). Тогда phi- функцию  *  можно представить так:       * * * 1 2 1 2m in , , , ,C C G G         (10) где  C – phi-функция вида (8),   1 11 1 1 3 51 2 4min , , , , ,C G K GC G D G D GG       здесь CG , DG , KG – phi-функции для G и базового объекта C , G , K соответственно. Phi-функции (7) – ( 10) являются  -аппроксимацией phi-функций для пар объектов 1 и 2 ,  и C , C и  ,  и  соответственно. Phi-функция AB в общем случае является композицией минимумов и макси- мумов гладких функций. Поэтому для каждого phi-неравенства 0AB  можно по- строить phi-дерево, концевым вершинам которого соответствуют системы phi-не- равенств с гладкими функциями. Панкратов А.В., Романова Т.Е., Суббота И.А. «Искусственный интеллект» 4’201294 2П Математическая модель. Рассматриваются оптимизационные задачи кластериза- ции N непересекающихся объектов { , },i NT C i I   в контейнер { , }C E минимальных размеров. Размещаемые объекты ,i NT i I характеризуются переменными ( , , )i i ix y  , т.е. допускаются непрерывные трансляции и повороты, при этом полагаем 1ih  . Область размещения  характеризуется переменным параметром h , при этом полагаем 0, 0, 0x y    . Пусть u R – вектор переменных метрических характеристик контейнера  и размещаемых объектов ,i NT i I , R – арифметическое евклидово пространство. Математическая модель задачи кластеризации имеет вид min ( ) u W R F u   , (11) { : ( ) 0}W u R u    , ' ''( ) min{ ( ), ( ), 1, 2, ..., , 1, 2, ..., }lu u u l N        , (12) где ( ) ,F u h ' ( )u – phi-функция непересечения для пары phi-объектов, ''( )l u – phi-функция включения phi-объекта в  , 0.5 ( 1)N N    . Из соотношения (12) следует, что ( ) 0u  , когда '( ) 0u  для каждой пары объектов A и B, 1 2, { , , ..., }NA B T T T , A B и ''( ) 0u  для каждой пары объектов  и A, 1 2{ , , ..., }NA T T T , 2 \ intR   , int  – внутренность области  . Поскольку 1 k k W W    , где { : ( ) 0}k kW u R u    , задача (11) – (12) сводится к оптимизационной задаче [6]: * * * * 1 2( ) min{ ( ), ( ),..., ( )}F u F u F u F u , (13) ( ) min ( ), k k u W R F u F u    1,2,...,k    . (14) Для решения задачи (13) – (14) используется подход, основанный на методе ветвей и границ, с набором правил отсечения, учитывающих оценки решения сверху, симметрию дерева решений и вырожденность неполных систем. Численные эксперименты. В качестве тестовых примеров рассматриваются задачи оптимальной кластеризации объектов в круге и эллипсе (рис. 4). (а) (б) Рисунок 4 – Размещение объектов в области, соответствующее точке локального минимума * * * * * * * * 1 1 1( , , ,..., , , , )N N Nu x y x y h  , (а) пример – 1; (б) – пример 2  1  2 3C 2C  1 C      Математическое моделирование отношений эллипсов в задачах.... «Штучний інтелект» 4’2012 95 2П Пример 1. Исходные данные: C  ,  11T   ,  22T   , 3 3T C , 0 1r  , 1 1 1 2 2 2 3 3 3( , , , , , , , , , )u x y x y x y h    , 1a =4, 1b =3, 2a =5, 2b =3, 3r =3. Точка локального минимума: u  (-2.667336, -2.498968, -12.057380, 3.696938, - 0.113279, -4.681757, -1.620644, 3.494998, 0, 6.852467).Значение функции цели в точке * * * * * * * 1 1 1( , , ,..., , , , )N N Nu x y x y h  : * ( )h F u =6.852467. Пример 2. Исходные данные: C  ,  11T   , 2 2T C , 0 04, 3a b   , 1 1 1 2 2 2( , , , , , , )u x y x y h   , 1a =5, 1b =3, 2r =3. Точка локального минимума: u  (-2.371988605, 1.625690207, -0.540419525, 3.482693316, -1.121795491, 0, 1.760897765). Значение функции цели в точке * * * * * * * * 1 1 1( , , ,..., , , , )N N Nu x y x y h  : * *( )h F u =1.760897765. Для решения задач локальной оптимизации вида (14) используется IPOPT [10]. Выводы Приведенные phi-функции позволяют описывать математические модели задач оп- тимальной кластеризации эллиптических объектов в виде задач нелинейной оптимизации и применять для их решения известные методы математического программирования. Литература 1. Wascher G. An improved typology of cutting and packing problems / G. Wascher, H. Hausner and H. Schumann // Europ. J. Oper. Res. – 2007. – № 183. – Р. 1109-1130. 2. Birgin E.G. Orthogonal packing of rectangular items within arbitrary convex regions bynonlinear optimization / E.G. Birgin, J.M. Martinez, F.H. Nishihara [et al.] // Comput. Oper. Res. – 2006. – № 33. – Р. 3535-3548. 3. Bennell J.A. The geometry of nesting problems: A tutorial / J.A. Bennell, JF. Oliveira // European J. Operational Research. – 2008. – № 184. – Р. 397-415. 4. Burke E. Irregular packing using the line and arc no-fit polygon / E. Burke, R. Hellier, G. Kendall [et al.] // Operations Research. – 2010. – № 58(4). – Р. 948-970. 5. Bennell J.A. Tools of mathematical modelling of arbitrary object packing problems / J.A. Bennell, G. Scheithauer, Yu. Stoyan [et al.] // J. Annals of Operations Research, Publisher Springer Netherlands. – 2010. – V. 1, № 179. – Р. 343-368. 6. Chernov N. Mathematical model and efficient algorithms for object packing problem / N. Chernov, Y. Stoyan, T. Romanova // Computational Geometry: Theory and Applications. – 2010. – № 43(5). – Р. 535-553. 7. Chernov N. Phi-functions for 2D objects formed by line segments and circular arcs / N. Chernov, Y. Stoyan, T. Romanova [et al.] // Advances in Operations Research. – 2012. – doi:10.1155/2012/346358. 8. Scheithauer G. Containment of a pair of rotating objects within a container of minimal area or perimeter / G. Scheithauer, Y. Stoyan, J. Bennell [et al.]. – 2012. – (Preprint MATH-NM-02-2012, TU Dresden). 9. Стоян Ю.Г. Некоторые вопросы аналитического предствления функции плотного размещения / Ю.Г. Стоян, Н.И. Гиль, А.М. Бондаренко // Вычислительная техника в машиностроениии. – Минск : ИТК АН БССР, 1973. – С. 48-49. 10.Wachter. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming / Wachter, L.T. Biegler // Math. Programming {106}. – 2006. – Р. 25-57. Literatura 1. G. Wascher, H. Hausner, and H. Schumann, An improved typology of cutting and packing problems, Europ. J. Oper. Res., 183 (2007), 1109-1130. 2. E.G. Birgin, J. M. Martinez, F. H. Nishihara, D. P. Ronconi, Orthogonal packing of rectangular items within arbitrary convex regions bynonlinear optimization, Comput. Oper. Res. 33 (2006) 3535-3548. Панкратов А.В., Романова Т.Е., Суббота И.А. «Искусственный интеллект» 4’201296 2П 3. Bennell JA and Oliveira JF (2008) The geometry of nesting problems: A tutorial. European J. Operational Research 184: 397-415. 4. Burke E, Hellier R, Kendall G and Whitwell G (2010) Irregular packing using the line and arc no-fit polygon. Operations Research 58(4): 948-970. 5. Bennell JA, Scheithauer G, Stoyan Yu and Romanova T (2010) Tools of mathematical modelling of arbitrary object packing problems, J. Annals of Operations Research, Publisher Springer Netherlands 179, 1: 343-368. 6. Chernov N, Stoyan Y, Romanova T (2010) Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications 43(5): 535-553. 7. Chernov N, Stoyan Y, Romanova T and Pankratov A (2012) Phi-functions for 2D objects formed by line segments and circular arcs, Advances in Operations Research, doi:10.1155/2012/346358 8. G. Scheithauer, Y. Stoyan, J. Bennell, T. Romanova, A. Pankratov (2012) Containment of a pair of rotating objects within a container of minimal area or perimeter/ Preprint MATH-NM-02-2012, TU Dresden 9. Stojan Ju.G. Vychislitel’naja tehnika v mashinostroeniii. Minsk: ITK AN BSSR 1973. S. 48 - 49. 10. Wachter and L. T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Programming {106} (2006), 25-57. RESUME A.V. Pankratov, Т.E. Romanova, I.А. Subbota Mathеmatical Modeling of Relations of Ellipses in Optimal Object Clustering The cutting and packing problem is a part of computational geometry that has rich applications in garment industry, sheet metal cutting, furniture making, shoe manufacturing, etc. The common task is to place a certain set of figures of specified shapes and sizes within a given area (corresponding to a sheet of metal, a strip of textile, etc.). The objects must be packed into a given container or cut out of a given piece of material. To minimize waste, or minimize the space used, or maximize the number of objects, one wants to pack the latter as tightly as possible. Such problems are known as cutting and packing (C&P) problems. In some applications they are called nesting problems, marker making, stock cutting, containment problems, etc. The problem is NP-complete, and as a result nearly all practical algorithms utilize heuristics and are restricted to objects of certain simple shapes, and impose various limitations on their layout. In two dimensions, most methods work with polygons only, other shapes are simply approximated by polygons (a notable exception being which allows circular shapes). Objects usually have a fixed orientation, i.e., they cannot be freely rotated. The article considers constructive tools of mathematical modeling and computer simulation technique of relations (inclusion, non-intersecting, touching, intersecting) between rotating elliptic objects. A complete class of radical-free approximations of phi-functions for ellipses and their complements are defined. We provide a mathematical model of the optimal clustering of elliptic objects in the form of constrained optimisation problem. A number of computational results for optimal clustering of elliptic objects are given. Статья поступила в редакцию 16.07.2012.

Математическое моделирование отношений эллипсов в задачах оптимальной кластеризации объектов

Institution

Ähnliche Einträge