О некоторых классах пространственных конфигураций геометрических объектов и их формализации

Рассмотрена задача синтеза пространственных конфигураций геометрических объектов. Введено конфигурационное пространство, обобщенными переменными которого являются метрические параметры и параметры размещения объектов. Осуществлена классификация пространственных конфигураций с учетом отношений на мно...

Full description

Saved in:

Bibliographic Details
Date:	2018
Main Author:	Яковлев, С.В.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Series:	Проблемы управления и информатики
Subjects:	Математическое моделирование и исследование сложных управляемых систем
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/180614
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	О некоторых классах пространственных конфигураций геометрических объектов и их формализации / С.В. Яковлев // Проблемы управления и информатики. — 2018. — № 5. — С. 73-85. — Бібліогр.: 49 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-180614
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1806142025-02-09T09:35:12Z О некоторых классах пространственных конфигураций геометрических объектов и их формализации Про деякі класи просторових конфігурацій геометричних об’єктів та їх формалізацію On some classes of spatial configurations of geometric objects and their formalization Яковлев, С.В. Математическое моделирование и исследование сложных управляемых систем Рассмотрена задача синтеза пространственных конфигураций геометрических объектов. Введено конфигурационное пространство, обобщенными переменными которого являются метрические параметры и параметры размещения объектов. Осуществлена классификация пространственных конфигураций с учетом отношений на множестве геометрических объектов и их обобщенных переменных. Предложены способы формализации ограничений в задачах упаковки, компоновки и покрытия. Розглянуто задачу синтезу просторових конфігурацій геометричних об’єктів. Введено конфігураційний простір, узагальненими змінними якого є метричні параметри і параметри розміщення об’єктів. Здійснено класифікацію просторових конфігурацій з урахуванням відношень на множині геометричних об’єктів і їх узагальнених змінних. Запропоновано способи формалізації обмежень в задачах упаковки, компоновки та покриття. The problem of synthesis of spatial configurations of geometric objects is considered. A configuration space is introduced, the generalized variables of which are metric and placement parameters of objects. Typology of spatial configurations taking into account relations on the set of geometric objects and their generalized variables is proposed. Methods for formalizing constraints in packing, layout and covering problems are described. 2018 Article О некоторых классах пространственных конфигураций геометрических объектов и их формализации / С.В. Яковлев // Проблемы управления и информатики. — 2018. — № 5. — С. 73-85. — Бібліогр.: 49 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180614 519.85 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математическое моделирование и исследование сложных управляемых систем Математическое моделирование и исследование сложных управляемых систем
spellingShingle	Математическое моделирование и исследование сложных управляемых систем Математическое моделирование и исследование сложных управляемых систем Яковлев, С.В. О некоторых классах пространственных конфигураций геометрических объектов и их формализации Проблемы управления и информатики
description	Рассмотрена задача синтеза пространственных конфигураций геометрических объектов. Введено конфигурационное пространство, обобщенными переменными которого являются метрические параметры и параметры размещения объектов. Осуществлена классификация пространственных конфигураций с учетом отношений на множестве геометрических объектов и их обобщенных переменных. Предложены способы формализации ограничений в задачах упаковки, компоновки и покрытия.
format	Article
author	Яковлев, С.В.
author_facet	Яковлев, С.В.
author_sort	Яковлев, С.В.
title	О некоторых классах пространственных конфигураций геометрических объектов и их формализации
title_short	О некоторых классах пространственных конфигураций геометрических объектов и их формализации
title_full	О некоторых классах пространственных конфигураций геометрических объектов и их формализации
title_fullStr	О некоторых классах пространственных конфигураций геометрических объектов и их формализации
title_full_unstemmed	О некоторых классах пространственных конфигураций геометрических объектов и их формализации
title_sort	о некоторых классах пространственных конфигураций геометрических объектов и их формализации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2018
topic_facet	Математическое моделирование и исследование сложных управляемых систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/180614
citation_txt	О некоторых классах пространственных конфигураций геометрических объектов и их формализации / С.В. Яковлев // Проблемы управления и информатики. — 2018. — № 5. — С. 73-85. — Бібліогр.: 49 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT âkovlevsv onekotoryhklassahprostranstvennyhkonfiguracijgeometričeskihobʺektoviihformalizacii AT âkovlevsv prodeâkíklasiprostorovihkonfíguracíjgeometričnihobêktívtaíhformalízacíû AT âkovlevsv onsomeclassesofspatialconfigurationsofgeometricobjectsandtheirformalization
first_indexed	2025-11-25T07:46:55Z
last_indexed	2025-11-25T07:46:55Z
_version_	1849747658492608512
fulltext	© С.В. ЯКОВЛЕВ, 2018 Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 73 УДК 519.85 С.В. Яковлев О НЕКОТОРЫХ КЛАССАХ ПРОСТРАНСТВЕННЫХ КОНФИГУРАЦИЙ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ И ИХ ФОРМАЛИЗАЦИИ Введение При взаимодействии материальных объектов, участвующих при синтезе cлож- ных систем, необходимо учитывать их пространственную форму, метрические характеристики и различные ограничения на их взаимное расположение. В оте- чественной науке указанное направление исследований связано с теорией геомет- рического проектирования, основы которой заложены Ю.Г. Стояном [1–4]. Со- временное состояние теории базируется на фундаментальных результатах, связан- ных с математическим моделированием геометрических объектов и их взаимных отношений [5–8]. В общем случае синтез оптимальных конфигураций сложных систем непосредственно связан с задачами размещения пространственных объектов заданной формы. Важным классом таких задач являются оптимизационные за- дачи размещения, возникающие в различных прикладных областях науки и техники, прежде всего при компоновке летательных аппаратов, судов и субма- рин, в логистических системах при упаковке грузов для их транспортировки или хранения, в системах распознавания образов, в робототехнике, при коди- ровании информации и т.д. Особый интерес задачи синтеза пространственных конфигураций приобретают при проектировании ракетно-космической техни- ки. Актуальные проблемы упаковки, компоновки, разбиения и покрытия в со- временном ракетно-космическом машиностроении рассматриваются, в частно- сти, в ежегодных монографиях серии «Springer Optimization and Its Applica- tions» под редакцией G. Fasano и J.D. Pinter. Исследование конфигураций как математических объектов связано с по- нятием конфигурационного пространства [9–11], которое можно определить как совокупность обобщенных переменных, задающих расположение в про- странстве некоторой системы и ее частей как относительно одна другой, так и относительно заданной системы отсчета. Количество параметров системы за- висит от входящих в нее материальных тел, а также от характера наложенных на них связей. Таким образом, конфигурационное пространство задает конфи- гурацию системы, т.е. совокупность значений всех ее обобщенных координат. Число степеней свободы системы характеризует размерность конфигурацион- ного пространства. Конфигурационные пространства первоначально нашли широкое прило- жение в теоретических исследованиях, связанных с динамикой твердых тел. Однако свойства таких пространств с учетом различной формы, переменных размеров, а также ограничений на взаимное расположение тел, как правило, не изучались. В то же время указанные характеристики можно рассматривать как обобщенные переменные конфигурационного пространства. При этом учет ограничений на взаимное расположение тел требует привлечения специально- го математического аппарата, что позволяет интегрировать указанные иссле- дования с основными положениями теории геометрического проектирования. 74 ISSN 0572-2691 В настоящей статье цитируются современные источники, в которых рассмат- риваются различные классы задач синтеза пространственных конфигураций. Ав- тор преследовал цель — подтвердить интерес ученых к указанным классам, а не осуществлять обзор и анализ таких публикаций. 1. Конфигурационное пространство геометрического объекта Взаимодействие материальных объектов, участвующих в процессе синтеза системы, требует учитывать их геометрическую форму, размеры, а также различ- ные ограничения на их взаимное расположение. Для описания внешней структу- ры и вида совокупности материальных объектов или их частей в научной литера- туре используется термин конфигурация. С математической точки зрения под конфигурацией понимается отображение  некоторого исходного множества  элементов произвольной природы в абстрактное множество U определенной структуры при выполнении заданного набора ограничений  [12], т.е. .: U (1) В случае конечных множеств  и U конфигурация (1) называется комбинаторной. В [13] впервые введено конфигурационное пространство геометрических объектов, которое базируется на формализации понятия геометрической инфор- мации. В дальнейшем, если не оговаривается противное, рассматриваются гео- метрические объекты S в пространстве .3R Результаты естественным образом переносятся на случай .2RS  Геометрическая информация }){},{},({ psg  об объекте 3RS  включает следующее [13]:  пространственную форму }{s как класс эквивалентности на совокупности точечных множеств пространства ;3R метрические параметры формы }{ ),...,,( 1 k которые задают размеры ;S  параметры размещения ),...,,1(}{ kppp  которые определяют положение объекта S в пространстве .3R Для задания компонент }{s и }{ геометрической информации g об объекте 3RS  воспользуемся уравнением его границы: ,,0),( 3Rf  (2) где переменные k ,...,1 имеют область допустимых значений ,kRD  а функ- ция ),( f определена и непрерывна всюду на .3 DR  Для произвольного объекта S обозначим его топологическую внутренность, замыкание и границу соответственно S,int S,cl S.fr Положим, что геометрические объекты имеют одну и ту же пространственную форму, если их уравнения границы можно представить в виде (2) при некотором фиксированном ,ˆ D причем 0)ˆ,( f , если ;int S ,0)ˆ,( f если .cl\3 SR Таким образом задан класс эквивалентности на множестве геометрических объек- тов как точечных множеств пространства .3R Вектор )...,,( 1 k назовем метрическими параметрами пространственной формы  .s Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 75 Свяжем с объектом S собственную систему координат, начало которой назовем полюсом объекта .S В качестве полюса может быть выбрана произволь- ная внутренняя точка .S Исходя из физических соображений, полюс для объекта, представляющего собой твердое тело, предлагается совмещать с его центром инерции. Для простоты аналитического описания центрально-симметричного объекта его полюс выбирается в центре симметрии. Если объект S симметричен относительно некоторой оси, то с ней совмещается ось его собственной системы координат и т.д. Положение объекта S в пространстве 3R однозначно определяется расположе- нием его собственной системы координат относительно некоторой неподвижной си- стемы Oxyz пространства .3R Тогда параметры размещения }{p можно задать век- тором ),,()...,,( 61  vppp где ),,( 321 vvvv  — координаты полюса объек- та S в системе координат ,Oxyz а ),,( 321  — вектор угловых параметров, определяющий взаимное расположение осей собственной и неподвижной систем координат. В качестве угловых параметров могут быть выбраны углы Эйлера. Если уравнение границы объекта 3RS  задано в форме (1), то его располо- жение относительно неподвижной системы координат Oxyz задается так называ- емым уравнением общего положения .0),,(  pF (3) Если параметры размещения включают в себя угловые параметры, т.е. ),(v,p то ],),([),,(  vfpF A где ),,,( zyx а A — ортогональный оператор, выраженный через угловые па- раметры . Выбор независимых координат вектора параметров размещения не является единственным. Как и при задании полюса объекта, его параметры размещения )...,,( 61 ppp  определяются из уравнения общего положения (3) ввиду возмож- ностей описания различных ограничений на взаимное расположение объектов и других факторов. В качестве параметров размещения, например, можно выбрать координаты ),,(),,,( 2 3 2 2 2 1 21 3 1 2 1 1 1 vvvvvvvv  любых двух точек, принадлежащих объекту, т.е. ).,,,,,()...,,( 2 3 2 2 2 1 1 3 1 2 1 161 vvvvvvppp  Одной из таких точек есте- ственно выбирать полюс объекта. Заметим, что для задания положения объектов некоторых классов число параметров размещения может быть меньшим. Напри- мер, для сферы достаточно задать только координаты ее центра. При преобразо- ваниях трансляции угловые параметры объекта фиксированы. В дальнейшем бу- дем рассматривать общий случай, полагая )....,,( 61 ppp  Сформируем конфигурационное пространство )(Ξ S геометрического объек- та ,3RS  выбрав в качестве обобщенных переменных метрические парамет- ры  )...,,( 1 k и параметры размещения   )...,,( 61 ppp  , т.е. положим )p...,,p,...,,(),( 611 kpg  . Тогда всякая точка конфигурационного про- странства )(Ξ S будет определять параметризованный геометрический объект .)( 3RgS  Размерностью конфигурационного пространства )(Ξ S назовем число его независимых обобщенных координат. При фиксированных значениях обоб- щенных переменных )ˆ,ˆ(ˆ pg  точка )(ˆ Ξ Sg называется изображающей точкой и однозначно определяет геометрический объект ,)ˆ( 3RgS  т.е. изображение. 76 ISSN 0572-2691 2. Формирование пространственных конфигураций геометрических объектов и их классификация Пусть }...,,{ 1 nSS — исходное множество геометрических объектов, а  }...,,{ 01 n  — множество возможных пространственных форм объектов из . Введем обозначение }....,,2,1{ nJn  Осуществим параметризацию объектов ,iS .nJi Положим, что объект 3RSi  имеет форму ,}{s i метрические пара- метры )...,,( 1 i k ii i  и параметры размещения )...,,( 61 iii ppp  . Тогда его уравнение границы запишем как ,0),(  i if где функция ),( i if  определена и непрерывна всюду на ,,3 ik ii RDDR  причем ,0),,(  i if если ;int iS ,0),(  i if если .cl\3 iSR Уравнения общего положения объекта iS в неподвижной системе координат Oxyz пространства 3R примет вид .0),,(F  ii i p Рассмотрим конфигурационные пространства ),(Ξ iS ,ni J с обобщенными переменными ).,( iii pg  Каждой точке )S(Ξ i ig  в пространстве 3R будет соответствовать параметризованый геометрический объект .)(g 3RS i i  Сформи- руем конфигурационное пространство )( множества геометрических объектов как прямое произведение конфигурационных пространств ),(Ξ iS ,nJi т.е. ).(...)( 1)( nSS  (4) Обобщенными переменными этого пространства будет вектор )....,,( 1 nggg  Определение 1. Отображение )(:  множества геометрических объек- тов }...,,{ 1 nSS в конфигурационное пространство ),( удовлетворяющее заданному набору ограничений  , задает пространственную конфигурацию гео- метрических объектов ., ni JiS  В соответствии с этим определением пространственная конфигурация гео- метрических объектов ni JiS , должна удовлетворять системе ограничений , учет которых позволяет выделить соответствующий класс пространственных конфигураций. Указанные ограничения накладываются на обобщенные перемен- ные ngg ...,,1 конфигурационного пространства ).( Отметим, что в качестве обобщенных переменных могут выступать как метрические параметры, так и па- раметры размещения геометрических объектов. При этом указанные параметры (или часть из них) могут быть фиксированы. В большинстве практических задач мет- рические параметры формы геометрических объектов известны. В свою очередь, при фиксированных параметрах размещения имеем класс задач назначения, который яв- ляется предметом исследования в области дискретной оптимизации [14, 15]. С дру- гой стороны, как показано в работах [16, 17], синтез пространственных конфигу- раций предполагает выделение комбинаторной структуры задач. Это дает воз- Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 77 можность рассматривать геометрические объекты как комбинаторные [18] и при- влечь для их исследования результаты теории евклидовых комбинаторных конфи- гураций [19–22]. Особый интерес при этом имеет класс полиэдрально- сферических конфигураций [23–25]. Формализацию ограничений  осуществим путем введения на множестве гео- метрических объектов из  различных отношений, в том числе бинарных и много- местных. Определим на множестве  бинарные отношения непересечения   и включения  . Положим ,21 SS  если 21 intint SS  и ,21 SS  если .int 12 SS  Определение 2. Отображение )(:  задает конфигурацию упаковки (packing configuration), если )()( j j i i gSgS  .,, jiJji n  Задачи упаковки являются в настоящее время наиболее исследованными [26–29]. Рассмотрим объект ,0S который назовем контейнером, и обозначим его конфи- гурационное пространство )(Ξ 0S с обобщенными переменными ).,( 000 pg  Пусть }...,,,{ 00 n1 SSS и сформируем конфигурационное пространство ).(...)()( 100)( nSSS  Определение 3. Отображение )( 00:  задает конфигурацию компо- новки (layout configuration), если )()( 0 0 j j gSgS  , )()( j j i i gSgS  .,, jiJji n  Как правило, параметры размещения контейнера полагают равными нулю, т.е. ).0...,,0()...,,( 0 6 0 1 0  ppp Заметим, что отношение )()( 0 0 j j gSgS  эквива- лентно )()( 0 j ji gSgcS  .nJj Поэтому конфигурация компоновки является конфигурацией упаковки, один из объектов которой рассматривается как допол- нение к контейнеру. Подходы к классификации задач упаковки и компоновки геометрических объектов рассмотрены в [30–32]. Однако это касается случая, ко- гда метрические параметры геометрических объектов, кроме контейнера, фикси- рованы. При этом обобщенными переменными объектов являются только их па- раметры размещения и метрические параметры контейнера. При исследовании конфигураций компоновки, как правило, вводятся ограни- чения на минимально и максимально допустимые расстояния между объектами. Именно эта особенность положена в основу различия классов конфигураций упа- ковки и компоновки в работах [33–36]. Если геометрические объекты ,, ni JiS  представляют собой твердые тела заданной массы, в качестве дополнительных ограничений на их взаимное расположение могут накладываться условия, связан- ные с небалансом системы [37–39]. Такую конфигурацию назовем конфигурацией равновесной упаковки (balanced layout configuration). Рассмотрим множество геометрических объектов }...,,...,,...,,,...,,{ ~ 1111001 1 nnknkn SSSSSS и сформируем конфигурационное пространство )(...)(...)(...)()(...)() ~ 1111001 1 ( nnknkn SSSSSS  с обобщенными переменными ....,,...,,...,,,...,, 1111001 1 nnknkn gggggg 78 ISSN 0572-2691 Определение 4. Отображение )( ~~ :  задает конфигурацию мульти- контейнерной компоновки (multiply container configuration), если )()( 0 0 ij ij i i gSgS  и )()(      j j j j gSgS ,, ikJ  , ., nk JiJj i  В качестве контейнеров выступают ....,, 001 nSS К указанному классу конфи- гураций относится компоновка в многосвязную область [40, 41]. Рассмотрим еще один контейнер 00S с обобщенными переменными 00g и положим , ~~ 000  S ). ~ Ξ)(Ξ) ~ Ξ (( 000  S Определение 5. Отображение )( 00 ~~ :  задает конфигурацию вложен- ной компоновки (nesting configuration), если ),(g)( 0 0 00 00 i iSgS  )(g)(g0 0 ij ij i i SS  и )()(      j j j j gSgS ,, ikJ  , ., nk JiJj i  Некоторые классы вложенных компоновок рассмотрены в [42, 43] Как следует из определения 5, конфигурация вложения является конфигура- цией упаковки объектов ni JiS ,0 в контейнер ,00S причем каждый из объектов iS0 является контейнером в конфигурации упаковки объектов ,ijS , ikJj .nJi Ана- логичным образом можно формализовать вложения в контейнеры более высокого порядка. С использованием теоретико-множественных операций сформируем геомет- рический объект ,)...,,(= 1 nB SSBS (5) который назовем сложным, а объекты ni JiS , — базовыми. Будем говорить, что оператор B задает структуру сложного объекта .BS Таким образом, сложному объекту BS в конфигурационном пространстве )( соответствует параметри- зованный геометрический объект заданной структуры: )).(...,),(()...,,( 1 1 1 n n n B gSgSBggS  (6) Способы формирования конфигурационного пространства сложного объекта описаны в [17]. При фиксированных значениях обобщенных координат ,,ˆ n ii Jigg  точка )()ˆ...,,ˆ(ˆ 1  nggg является изображающей точкой конфигурационного про- странства ),( которой соответствует изображение )).ˆ(...,),ˆ((=)ˆ...,,ˆ( 1 1 1 n n n B gSgSBggS Пусть }...,,{ 1 mBBB SS — множество сложных объектов ,S...,,SBS n1jB j )(= mJj заданной структуры, а )( jBS — соответствующие им конфигурационные пространства с обобщенными переменными ., m j B Jjg j  Объекты ,S jB ,mJj назовем объектами первого порядка, а базовые объекты ,, ni JiS  — объектами нулевого порядка. С одной стороны, сложный объект заданной структуры пред- ставляет собой пространственную конфигурацию. С другой стороны, на множе- стве сложных объектов можно задать пространственную конфигурацию более вы- сокого порядка ),(...)( 1 : mBBB SS   удовлетворяющую определенному набору ограничений. В соответствии с определениями 2–5 пространственные Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 79 конфигурации сложных объектов можно классифицировать как конфигурации упаковки, компоновки и т.д. Зададим структуру сложного объекта в виде .)...,,( 11 i n inB SSSB=S   (7) Объект ,BS конфигурационная структура которого задается выражением (7), назовем составным. Обозначим ),...,( 1 n B ggS параметризованный объект структуры (7) в конфи- гурационном пространстве ).( Определение 6. Отображение )( 00:  задает конфигурацию покры- тия (covering configuration), если ).()...,,( 0 0 1 gSggS n B  При этом геометрический объект 0S называют областью покрытия, а геометрические объекты ,, ni JiS  — покрывающими объектами. Различные постановки задач покрытия приведены, например, в работах [44–47]. Рассмотрим конфигурацию покрытия области )( 0 0 gS объектами ,),( n i i JigS  при условии, что )()( j j i i gSgS  для любых .,, jiJji n  Тогда совокупность обобщенных переменных )( 0 10 )...,,,( nggg при выполнении указанных выше условий будет определять конфигурацию разбиения (partitioning configura- tion). Различные модели и методы решения задач разбиения множеств описаны в работах [48, 49]. Заметим, что на множестве объектов нулевого и первого порядков можно строить объекты второго порядка как пространственные конфигурации гео- метрических объектов из B и так далее. Вместе с тем все объекты выс- ших порядков и соответствующие пространственные конфигурации являются суперпозицией отображений над множеством базовых объектов  . Таким об- разом, любая пространственная конфигурация представляется как отображе- ние ),(...)(: 1 1 n mm SS n где nmm ...,,1 — кратности вхождения базо- вых объектов в конфигурацию. 3. Формализация отношений в конфигурационных пространствах геометрических объектов В настоящее время основное внимание уделяется задачам синтеза простран- ственных конфигураций при фиксированных форме и метрических параметрах базовых объектов. Переменными являются лишь размеры контейнера либо обла- сти покрытия. Использование конфигурационных пространств геометрических объектов позволяет значительно расширить класс задач. При этом синтез конфи- гураций упаковки, компоновки, покрытия, разбиения предполагает выбор обоб- щенных переменных nggg ...,,, 10 соответствующего конфигурационного про- странства и описание множества их допустимых значений в виде системы функциональных ограничений. Для формализации условий взаимного непересечения и включения геометри- ческих объектов Ю.Г. Стоян ввел понятие  -функции, свойства которых наиболее полно освещены в работах [3–8]. При этом предполагается, что над объектами осу- ществляются только собственные конгруэнтные преобразования, т.е. форма и мет- рические параметры объектов фиксированы. Параметризованный геометрический объект S с параметрами размещения p обозначим S(p). Заметим, что при выделении соответствующего класса  -функций важную роль играет размерность вектора па- 80 ISSN 0572-2691 раметров размещения. Например, при преобразованиях трансляции объектов их уг- ловые параметры фиксированы. В общем случае положим, что )....,,(= α1 ppp Определение 7. Непрерывная, определенная всюду на 2αR функция ), (Φ 2121 pp SS называется Ф-функцией геометрических объектов )( 1 1 pS и ),( 2 2 pS если она удовлетворяет следующим условиям: 0,>),(Φ 2121 pp SS если ,=)(cl)(cl 2 2 1 1 gSgS  ,0),( 2121  pp SS если ,)(int)(int 2 2 1 1 pSpS  ,)(fr)(fr 2 2 1 1 pSpS  ,0),(Φ 2121 <pp SS если .)(int)(int 2 2 1 1 pSpS  Определение 8.  -функция называется нормализованной, если ее значения равны евклидовым расстояниям между объектами )( 1 1 pS и )( 2 2 pS при условии, что ,),( 21 Gpp  где }.)(int)(int),{( 2 2 1 1 21  pSpSppG Для построения Ф-функций сложных геометрических объектов выделены классы базовых и составных 2D- и 3D- объектов. Базовыми объектами простран- ства 2R являются круги, прямоугольники, правильные и выпуклые многоуголь- ники, а также их замкнутые дополнения ко всему пространству .2R Базовыми трехмерными объектами являются шары, прямые параллелепипеды, прямые кру- говые цилиндры, круговые конусы, выпуклые многогранники и замыкания до- полнений этих объектов к пространству .3R Подходы к конструктивному постро- ению Ф-функций базовых 2D- и 3D-объектов освещены в [5–8]. При этом матема- тическое моделирование отношений сложных геометрических объектов основывается на основе Ф-функций базовых объектов. Исследование конфигураций пространственных объектов в общем случае тре- бует обобщения понятия Ф-функции с учетом обобщенных переменных геомет- рических объектов. Рассмотрим геометрические объекты ,1S ,2S которые име- ют обобщенные переменные ),,( 111 pg  ),,( 222 pg  где ),...,,( 111 11 l ),...,,( 222 21 l ),...,,( 11 1 1  ppp )....,,( 22 1 2  ppp Сформируем конфигура- ционное пространство ).()( 21 ΞΞ SS  Положим, что области определения метри- ческих параметров 1 и 2 соответственно 1 1 l RD  и .2 2 l RD  Определение 9. Непрерывную, определенную всюду на 21 2 DDR  функ- цию ),( 2121 gg SS  назовем обобщенной Ф-функцией геометрических объектов 1S и 2S с обобщенными переменными ),,( 111 pg  ),,( 222 pg  если она удо- влетворяет следующим условиям: ,0),( 2121  gg SS если ,)(cl)(gcl 2 2 1 1 gSS  ,0),( 2121  gg SS если ,)(int)(int 2 2 1 1 gSgS  ,)(fr)(fr 2 2 1 1 gSgS  0),( 2121  gg SS , если .)(int)(int 2 2 1 1 gSgS  Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 81 Заметим, что в данном случае термин обобщенная функция не связан с ее классическим определением, а лишь подчеркивает обобщение введенного ранее понятия  -функции. Определение 10. Обобщенную  -функцию назовем нормализованной, если ее значение при любых фиксированных метрических параметрах 1 1ˆ D и 2 2ˆ D равно евклидовому расстоянию между объектами )( 1 1 gS и )( 2 2 gS при условии, что , ~ ),( 21 Ggg  где },)(int)(int),{( ~ 2 2 1 1 21  gSgSgg G  ),,ˆ( 111 pg  ).,ˆ( 222 pg  Анализ существующих методов построения Ф-функции базовых 2D- и 3D-объектов при фиксированных метрических параметрах позволяет сделать вы- вод о возможности естественного обобщения этих результатов на случай пере- менных метрических параметров. Теория Ф-функций прежде всего эффективна для формализации ограничений при бинарных отношениях между геометрическими объектами. Действительно, условие непересечения геометрических объектов 1S и 2S с обобщенными пере- менными 1g и 2g задается неравенством .0),( 2121  gg SS При ограничениях на минимально и максимально допустимые расстояния между объектами (соответственно min 12d и )max 12d ) имеем ,),( max 12 21min 12 21 dggd SS  где 21SS  — нормализованная обобщенная Ф-функция. Однако применение Ф-функций для многоместных отношений сопряжено с большими вычислительными сложностями. В частности, речь идет о задачах по- крытия. В этом случае предложим подход, основанный на вычислении меры (площади, объема) параметризованного сложного объекта заданной структуры. Такой подход изложен в [3] и использован при формализации условий размеще- ния и покрытия для объектов заданной формы и фиксированных метрических ха- рактеристик. Рассмотрим параметризованный сложный объект )...,,( 1 n B ggS вида (6), структура которого задается выражением (5). Такой объект в конфигурационном пространстве )( вида (4) имеет обобщенные переменные ....,,1 ngg Определим функцию ),...,,( 1 n B gg значения которой при всяком фиксиро- ванном наборе обобщенных переменных )()ˆ...,,ˆ( 1 ngg равно объему (пло- щади) сложного геометрического объекта )).ˆ(...,),ˆ((=)ˆ...,,ˆ( 1 1 1 n n n B gSgSBggS Таким образом, установлена зависимость ).)...,,(()...,,( 11 n B n B ggSgg  (8) Определение 11. Функцию, определяемую выражением (8), назовем -функ- цией параметризованного объекта )....,,( 1 n B ggS Данный класс функций особенно удобен при формализации многоместных отношений геометрических объектов. Действительно, рассмотрим сложный пара- метризованный геометрический объект , B S  структура которого задается выра- жением 82 ISSN 0572-2691 .)...,,,( 00              n 1=i in1B SSSSSB=S c Тогда условие покрытия геометрического объекта 0S совокупностью объек- тов ,, ni JiS  можно задать равенством ,0))...,,,(()...,,,( 1010  n B n B gggSggg  где nggg ...,,, 10 — обобщенные переменные конфигурационного пространства ),(...)()( 100)( nSSS  а параметризованный объект )...,,,( 10 n B gggS  имеет вид .)()()...,,,( 1 0 0 10             n i i i n B gSgSgggS c С помощью -функций легко формализовать условия непересечения и включения для двух геометрических объектов: 1S и .2S Действительно, зададим структуру сложного объекта в виде 2121 ),( SSSSBSB  = и выберем обобщен- ные переменные 21, gg конфигурационного пространства ).(Ξ)(Ξ 21 SS  Тогда условие непересечения внутренностей объектов 21, SS задается равенством .0),( 21   ggB Если структуру сложного объекта записать ,),( 2121 SSSSBSB c=  то условие включения )()( 2 2 1 1 gSgS  примет вид .0),( 21   ggB Интересная особенность вычисления -функций — возможность привлечения современных методов компьютерной математики, связанных с обработкой изображе- ний. Действительно, всякой конфигурации при фиксированных значениях обобщен- ных переменных соответствует некоторое изображение. В свою очередь, попикселная обработка такого изображения при заданной структуре сложного объекта позволяет вычислять его основные характеристики, в частности площадь. Заключение Введение обобщенных переменных, порождающих соответствующие конфи- гурационные пространства, позволило значительно расширить область приложе- ния существующих методов синтеза пространственных конфигураций геометри- ческих объектов. Результаты статьи представляют интерес с точки зрения класси- фикации таких конфигураций. В настоящее время существуют общепризнанные подходы к классификации задач упаковки и компоновки [30–32]. Предложенные подходы естественным образом интегрируются с помощью дополнительного учета обобщенных переменных и структуры пространственных конфигураций. Обобщение понятия Ф-функций и новый класс -функций позволяют опи- сывать ограничения, характерные для различных классов конфигураций, в част- ности упаковки, компоновки и покрытия. В ближайшей перспективе будут форма- лизованы соответствующие аналитические зависимости для различных простран- ственных форм с учетом обобщенных переменных геометрических объектов. Важнейшим направлением дальнейших исследований является оптимизация пространственных конфигураций в соответствии с заданными критериями качества. Это позволит предложить новые математические модели и оптимизационные методы синтеза пространственных конфигураций. Естественно, такие подходы должны бази- Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 83 роваться как на выделении специальных классов геометрических объектов, так и на выборе их обобщенных переменных. При этом возникает необходимость формирова- ния нормализованных обобщенных Ф-функций базовых 2D- и 3D-объектов. Рассмот- рение метрических параметров объектов в качестве независимых переменных резко расширяет возможности приложения методов локальной и глобальной оптимизации применительно к решению задач синтеза пространственных конфигураций. С.В. Яковлев ПРО ДЕЯКІ КЛАСИ ПРОСТОРОВИХ КОНФІГУРАЦІЙ ГЕОМЕТРИЧНИХ ОБ’ЄКТІВ ТА ЇХ ФОРМАЛІЗАЦІЮ Розглянуто задачу синтезу просторових конфігурацій геометричних об’єктів. Введено конфігураційний простір, узагальненими змінними якого є метричні параметри і параметри розміщення об’єктів. Здійснено класифікацію просторо- вих конфігурацій з урахуванням відношень на множині геометричних об’єктів і їх узагальнених змінних. Запропоновано способи формалізації обмежень в за- дачах упаковки, компоновки та покриття. S.V. Yakovlev ON SOME CLASSES OF SPATIAL CONFIGURATIONS OF GEOMETRIC OBJECTS AND THEIR FORMALIZATION The problem of synthesis of spatial configurations of geometric objects is considered. A configuration space is introduced, the generalized variables of which are metric and placement parameters of objects. Typology of spatial configurations taking into account relations on the set of geometric objects and their generalized variables is proposed. Methods for formalizing constraints in packing, layout and covering prob- lems are described. 1. Стоян Ю.Г. Размещения геометрических объектов. — Киев : Наук. думка, 1975. — 239 с. 2. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. — Киев : Наук. думка, 1976. — 247 с. 3. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. — Киев : Наук. думка, 1986. — 268 с. 4. Stoyan Y.G. Mathematical methods for geometric design // Advances in CAD/CAM. Proceedings of PRO- LAMAT82, Leningrad, USSR, May 1982. P. 67–86, North-Holland, Amsterdam, The Netherlands, 2003. 5. Stoyan Yu., Scheithauer G., Romanova T. Mathematical modeling of interaction of primary geometric 3D objects // Cybernetics and Systems Analysis. — 2005. — 41, N 3. — P. 332–342. 6. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry: Theory and Applications. — 2010. — 43, N 5. — P. 535–553. 7. Bennell J., Scheithauer G., Stoyan Y. G., Romanova T. Tools of mathematical modelling of arbitrary ob- ject packing problems // J. Annals of Operations Research. — 2010. — 179, N 1. — P. 343–368. 8. Stoyan Yu., Romanova T. Mathematical models of placement optimization: Two- and Three- dimensional problems and applications // Modeling and Optimization in Space Engineering. — 2013. — 73. — P. 363–388. 9. Fadell E., Neuwirth L. Configuration space // Math. Scand. — 1962. — 10. — P. 111–118. 10. Edward R., Sufian F.,Husseini Y. Geometry and topology of configuration spaces // Springer Mono- graphs in Mathematics. — 2001. — 313 p. 11. Westerland C. Configuration spaces in geometry and topology // Australian Mathematical Society Ga- zette. — 2011. — 38, N 5. — P. 279–283. 12. Berge C. Principes de combinatoire. — Paris : Dunod, 1968. — 146 p. 13. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects // Cybernetics and Systems Analy- sis. — 2018. — 54. N 5. — P. 716–726. 14. Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. — Heidelberg; New York : Springer, 2002. — 660 p. https://ncatlab.org/nlab/show/Craig+Westerland 84 ISSN 0572-2691 15. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, иссле- дования. — Киев : Наук. думка, 2003. — 261 с. 16. Яковлев С.В. О комбинаторной структуре задач оптимального размещения геометрических объ- ектов // Доклады НАН Украины. — 2017. — № 9. — С. 63–68. 17. Yakovlev S.V. The method of artificial dilation in problems of optimal packing of geometric objects // Cybernetics and Systems Analysis. — 2017. — 53, N 5. — P. 725–731. 18. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems // Optimization Methods and Applications. — New York : Springer, 2017. — P. 239–250. 19. Стоян Ю.Г., Яковлев С.В., Пичугина О.С. Евклидовы комбинаторные конфигурации. — Харь- ков : Константа, 2017. — 404 с. 20. Yakovlev S. Convex extensions in combinatorial optimization and their applications // Optimization Methods and Applications. — New York : Springer, 2017. — P. 567–584. 21. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets // Cyber- netics. — 1989. — 25, N 3. — Р. 385–391. 22. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in combinatorial optimization // Cybernetics and Systems Analysis. — 2016. — 52, N 6. — P. 921–930. 23. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhedral- spherical sets // Ibid. — 2018. — 54, N 1. — P. 99–109. 24. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets // Cybernetics and Systems Analysis. — 1991. — 27, N 4. — P. 561–567. 25. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: theory and applications // In 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering(UKRCON). — 2017. — P. 1167–1175. 26. Fasano G. A modeling-based approach for non-standard packing problems // Optimized Packings with Applications. — New York : Springer, 2015. — 105. — P. 67–85. 27. Fasano, G.A. Global optimization point of view for nonstandard packing problems // Journal of Global Optimization. — 2013. — 155, N 2. — P. 279–299. 28. Sriramya P., Parvatha B.V. A state-of-the-art review of bin packing techniques // European Journal of Scientific Research. — 2012. — 86, N 3. — P. 360–364. 29. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: Model and methodolo- gies // Advances in Optimization Research. — 2009. — 22 p. 30. Dyckhoff H. A typology of cutting and packing problems // European Journal of Operational Research. — 1990. — 44. — P. 145–159. 31. Wascher G., Hausner H., Schumann H. An improved typology of cutting and packing problems // Ibid. — 2007. — 183. — P. 1109–1130. 32. Bortfeldt A., Wascher G. Constraints in container loading — A state-of-the-art review // Ibid. — 2013. — 229, N 1. — P. 1–20. 33. Drira A., Pierreval H., Hajri-Gabouj S. Facility layout problems: a survey // Annual Reviews in Con- trol. — 2007. — 31, N 2. — P. 255–267. 34. Fadel G.M., Wiecek M.M. Packing optimization of free-form objects in engineering design. Optimized Packings with Applications. — New York : Springer, 2015. — 105. — P. 37–66. 35. Coggan J., Shimada K., Yin S. A survey of computational approaches to three-dimensional layout prob- lems // CAD Computer Aided Design. — 2002. — 34, N 8. — P. 597–611. 36. Sun, Z.-G. Teng, H.-F. Optimal layout design of a satellite module // Engineering Optimization. — 2003. — 35, N 5. — P. 513–529. 37. Yi-Chun Xu, Ren-Bin Xiao, Amos M. A novel genetic algorithm for the layout optimization problem // In 2007 IEEE Congress on Evolutionary Computation (CEC 2007). — 2007. — P. 3938–3942. 38. Kovalenko A.A., Romanova T.E., Stetsyuk P.I. Balance layout problem for 3D-objects: mathematical model and solution methods // Cybernetics and Systems Analysis. — 2015. — 51, N 4. — P. 556–565. 39. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distributed mass- es // Energomashinostroenie. — 1982. — № 2. — P. 4–5. 40. Tian T., Zhu W., Lim A., Wei L. The multiple container loading problem with preference // European Journal of Operational Research. — 2016. — 248, N 1. — P. 84–94. 41. Stoyan Yu.G., Semkin V.V., Chugay A.M. Optimization of 3D `bjects layout into a multiply connected domain with account for shortest distances // Cybernetics and Systems Analysis. — 2014. — 150, N 3. — P. 374–385. 42. Bennell J.A., Oliveira J.F. The geometry of nesting problems: a tutorial // European Journal of Opera- tional Research. — 2008. — 184, N 2. — P. 397–415. 43. Litvinchev I., Infante L., Ozuna L. Approximate packing: integer programming models, valid inequalities and nesting // Optimized Packings with Applications. — New York : Springer, 2015. — 105. — P. 187–205. 44. Stoyan Y.G., Patsuk V.M. Covering a convex 3D polytope by a minimal number of congruent spheres // In- ternational Journal of Computer Mathematics. — 2014. — 91, N 9. — P. 2010–2020. 45. Yakovlev S.V. On a class of problems on covering of a bounded set // Acta Mathematica Hungarica. — 1989. — 53, N 3. — P. 253–262. 46. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations // Cybernetics and Systems Analysis. — 2008. — 43, N 3. — P. 333–340. https://www.scopus.com/authid/detail.uri?authorId=57198737466&eid=2-s2.0-0344464822 https://www.scopus.com/authid/detail.uri?authorId=7102579199&eid=2-s2.0-0344464822 https://www.scopus.com/sourceid/29114?origin=recordpage https://www.infona.pl/contributor/0@bwmeta1.element.elsevier-ffe688d6-bcb3-372c-ad83-2254378e5d9f/tab/publications https://www.infona.pl/contributor/1@bwmeta1.element.elsevier-ffe688d6-bcb3-372c-ad83-2254378e5d9f/tab/publications https://www.infona.pl/contributor/2@bwmeta1.element.elsevier-ffe688d6-bcb3-372c-ad83-2254378e5d9f/tab/publications https://www.infona.pl/contributor/3@bwmeta1.element.elsevier-ffe688d6-bcb3-372c-ad83-2254378e5d9f/tab/publications https://www.infona.pl/resource/bwmeta1.element.elsevier-e89acda4-81d7-3f85-9ac8-9896d0184159/tab/jContent https://www.infona.pl/resource/bwmeta1.element.elsevier-e89acda4-81d7-3f85-9ac8-9896d0184159/tab/jContent https://www.infona.pl/resource/bwmeta1.element.elsevier-e89acda4-81d7-3f85-9ac8-9896d0184159/tab/jContent/facet?field=%5ejournalYear&value=%5e_02016 https://www.infona.pl/resource/bwmeta1.element.elsevier-e89acda4-81d7-3f85-9ac8-9896d0184159/tab/jContent/facet?field=%5ejournalYear%5ejournalVolume&value=%5e_02016%5e_00248 https://www.infona.pl/resource/bwmeta1.element.elsevier-e89acda4-81d7-3f85-9ac8-9896d0184159/tab/jContent/facet?field=%5ejournalYear%5ejournalVolume%5ejournalNumber&value=%5e_02016%5e_00248%5e_00001 https://link.springer.com/journal/10559 Международный научно-технический журнал «Проблемы управления и информатики», 2018, № 5 85 47. Shekhovtsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in design of control and monitoring systems // Автоматика и телемеханика. — 1989. — N 5. — P. 160–168. 48. Киселева Е.М., Коряшкина Л.С. Модели и методы решения непрерывных задач оптимального разбие- ния множеств: линейные, нелинейные и динамические задачи. — Киев : Наук. думка, 2013. — 604 с. 49. Kiseleva E.M., Koriashkina, L.S. Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations // Cybernetics and Systems Analysis. — 2015. — 51, N 4. — P. 489–499. Получено 02.05.2018 https://www.scopus.com/authid/detail.uri?authorId=55844269100&eid=2-s2.0-84957845350

О некоторых классах пространственных конфигураций геометрических объектов и их формализации

Institution

Similar Items