Метод искусственного расширения пространства в задачах размещения геометрических объектов
Рассматривается задача оптимального размещения геометрических объектов с заданными формой и физико-метрическими параметрами. Выделяется комбинаторная структура задачи. На основе искусственного расширения размерности пространства сформулирована эквивалентная постановка исходной задачи, в которой физи...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2017 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144792 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод искусственного расширения пространства в задачах размещения геометрических объектов / С.В. Яковлев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 82–89. — Бібліогр.: 30 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859642752125370368 |
|---|---|
| author | Яковлев, С.В. |
| author_facet | Яковлев, С.В. |
| citation_txt | Метод искусственного расширения пространства в задачах размещения геометрических объектов / С.В. Яковлев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 82–89. — Бібліогр.: 30 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассматривается задача оптимального размещения геометрических объектов с заданными формой и физико-метрическими параметрами. Выделяется комбинаторная структура задачи. На основе искусственного расширения размерности пространства сформулирована эквивалентная постановка исходной задачи, в которой физико-метрические параметры являются независимыми переменными. Рассмотрен пример построения равновесной модели задачи упаковки кругов в круг минимального радиуса.
Розглянуто задачу оптимального розміщення геометричних об’єктів із заданими формою і фізико-метричними параметрами. Виділено комбінаторну структуру задачі. На основі штучного розширення розмірності простору сформульовано еквівалентну постановку вихідної задачі, у якої фізико-метричні параметри є незалежними змінними. Розглянуто приклад побудови рівноважної моделі задачі упаковки кругів у круг мінімального радіусу.
The problem of optimal placement of geometric objects with specified shape and physical-metric parameters is considered. The combinatorial structure of the problem is defined. An equivalent problem is formulated based on the artificial expansion of space dimension with physical-metric parameters being independent variables. The proposed approach is illustrated by the solution of balanced circular packing problem.
|
| first_indexed | 2025-12-07T13:24:35Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Ñ.Â. ßÊÎÂËÅÂ
ÌÅÒÎÄ ÈÑÊÓÑÑÒÂÅÍÍÎÃÎ ÐÀÑØÈÐÅÍÈß ÏÐÎÑÒÐÀÍÑÒÂÀ
 ÇÀÄÀ×ÀÕ ÐÀÇÌÅÙÅÍÈß ÃÅÎÌÅÒÐÈ×ÅÑÊÈÕ ÎÁÚÅÊÒÎÂ
Àííîòàöèÿ. Ðàññìàòðèâàåòñÿ çàäà÷à îïòèìàëüíîãî ðàçìåùåíèÿ ãåîìåòðè÷åñ-
êèõ îáúåêòîâ ñ çàäàííûìè ôîðìîé è ôèçèêî-ìåòðè÷åñêèìè ïàðàìåòðàìè.
Âûäåëÿåòñÿ êîìáèíàòîðíàÿ ñòðóêòóðà çàäà÷è. Íà îñíîâå èñêóññòâåííîãî
ðàñøèðåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà ñôîðìóëèðîâàíà ýêâèâàëåíòíàÿ ïî-
ñòàíîâêà èñõîäíîé çàäà÷è, â êîòîðîé ôèçèêî-ìåòðè÷åñêèå ïàðàìåòðû ÿâëÿ-
þòñÿ íåçàâèñèìûìè ïåðåìåííûìè. Ðàññìîòðåí ïðèìåð ïîñòðîåíèÿ ðàâíî-
âåñíîé ìîäåëè çàäà÷è óïàêîâêè êðóãîâ â êðóã ìèíèìàëüíîãî ðàäèóñà.
Êëþ÷åâûå ñëîâà: îïòèìàëüíîå ðàçìåùàíèå, êîìáèíàòîðíîå ìíîæåñòâî,
ðàâíîâåñíàÿ óïàêîâêà.
ÂÂÅÄÅÍÈÅ
Çàäà÷è îïòèìàëüíîãî ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ âûçûâàþò ïîñòî-
ÿííûé èíòåðåñ èññëåäîâàòåëåé [1–9]. Âàæíûì íàïðàâëåíèåì èññëåäîâàíèé ÿâ-
ëÿåòñÿ âûäåëåíèå è ôîðìàëèçàöèÿ ñïåöèàëüíûõ êëàññîâ çàäà÷, äëÿ êîòîðûõ
ìîæíî èñïîëüçîâàòü êàê íîâûå ýôôåêòèâíûå ìåòîäû ðåøåíèÿ, òàê è êëàññè-
÷åñêèå ìåòîäû ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ ðåøåíèÿ çàäà÷ â äî-
âîëüíî îáùåé ïîñòàíîâêå. Èìïóëüñîì ê ðàçâèòèþ ýòîãî íàïðàâëåíèÿ ïîñëó-
æèëî ñîçäàíèå òåîðèè Ô-ôóíêöèé Þ.Ã. Ñòîÿíà [10, 11]. Ôîðìàëèçàöèÿ
Ô-ôóíêöèé äëÿ ðàçëè÷íûõ êëàññîâ îáúåêòîâ çíà÷èòåëüíî ðàñøèðèëà îáëàñòü
ïðèìåíåíèÿ ýòîãî àïïàðàòà äëÿ îïèñàíèÿ óñëîâèé âçàèìíîãî íåïåðåñå÷åíèÿ
îáúåêòîâ è ðàçìåùåíèÿ èõ âíóòðè îáëàñòè. Â íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ
íîâûé âçãëÿä íà ôîðìàëèçàöèþ è ìåòîäû ðåøåíèÿ çàäà÷ ðàçìåùåíèÿ êàê çà-
äà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ ïóòåì âûäåëåíèÿ èõ êîìáèíàòîðíîé
ñòðóêòóðû. Ïðåäëàãàåòñÿ ïîäõîä ê ïîñòðîåíèþ ýêâèâàëåíòíîé ìàòåìàòè÷åñêîé
ìîäåëè çàäà÷è, îñíîâàííûé íà èñêóññòâåííîì ðàñøèðåíèè ðàçìåðíîñòè ïðî-
ñòðàíñòâà ïåðåìåííûõ â èñõîäíîé ïîñòàíîâêå.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ðàññìîòðèì çàäà÷ó ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ â ñëåäóþùåé ïîñòà-
íîâêå. Çàäàíû îáúåêòû S S S n0 1, , ..., ôèêñèðîâàííîé ôîðìû, êàæäûé èç êîòî-
ðûõ â ñîîòâåòñòâóþùåì ïðîñòðàíñòâå õàðàêòåðèçóåòñÿ ñâîèìè ïàðàìåòðàìè
ðàçìåùåíèÿ p p p pi i i i� ( , .., )
1 2 � è ôèçèêî-ìåòðè÷åñêèìè ïàðàìåòðàìè
w w w wi i i i� ( , , ..., )
1 2 �
, i Jn� �{ }0 , J nn � { }1 2, , ..., , i Jn� �{ }0 . Ðàçîáüåì ôèçè-
êî-ìåòðè÷åñêèå ïàðàìåòðû íà ãðóïïû ôèçè÷åñêèõ u u u ui i i i� ( , , ..., )
1 2 1�
è ìåò-
ðè÷åñêèõ r r r ri i i i� ( , , ..., )
1 2 2�
ïàðàìåòðîâ, ò.å. w u ri i i� ( , ), i Jn� �{ }0 ,
� � �� �1 2 .
Ïàðàìåòðû ðàçìåùåíèÿ îïðåäåëÿþò ïîëîæåíèå îáúåêòà â ïðîñòðàíñòâå, à ôè-
çèêî-ìåòðè÷åñêèå ïàðàìåòðû çàäàþò ëèíåéíûå ðàçìåðû îáúåêòà, åãî ìàññó è ò.ä.
Îáúåêò S 0 íàçîâåì îáëàñòüþ ðàçìåùåíèÿ. Çàôèêñèðóåì åãî ïîëîæåíèå
â ïðîñòðàíñòâå, ïîëîæèâ p0 0 0 0� ( , , ..., ) . Îáúåêòû S i ñ ïàðàìåòðàìè ðàçìåùå-
íèÿ pi íàçîâåì ðàçìåùàåìûìè îáúåêòàìè è îáîçíà÷èì S pi
i( ), i Jn� . Áóäåì ñ÷è-
82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
© Ñ.Â. ßêîâëåâ, 2017
òàòü, ÷òî ôèçèêî-ìåòðè÷åñêèå ïàðàìåòðû ðàçìåùàåìûõ îáúåêòîâ ïðèíèìàþò
ôèêñèðîâàííûå çíà÷åíèÿ, ò.å. êàæäîìó S pi
i( ) ñîîòâåòñòâóåò åäèíñòâåííûé íà-
áîð w w w wi i i i� ( , , ..., )
1 2 �
, i Jn� . Ïðè ýòîì ôèçèêî-ìåòðè÷åñêèå ïàðàìåòðû îáëàñ-
òè ðàçìåùåíèÿ w w w w0
1
0
2
0 0� ( , , ..., )
�
èëè èõ ÷àñòü ìîãóò áûòü ïåðåìåííûìè.
Ñôîðìóëèðóåì îïòèìèçàöèîííóþ çàäà÷ó ðàçìåùåíèÿ â âèäå
F w p p p u u un n( , , ..., , , , ..., )0 1 2 1 2 � extr (1)
ïðè îãðàíè÷åíèÿõ
�ij
i jp p( , ) � 0 , i Jn� , j Jn� , i j , (2)
�0
0 0i
ip r( , ) � , i Jn� , (3)
ãäå F ( )
— çàäàííàÿ ôóíêöèÿ, à íåðàâåíñòâà (2), (3) çàäàþò ñîîòâåòñòâåííî
óñëîâèÿ âçàèìíîãî íåïåðåñå÷åíèÿ îáúåêòîâ S pi
i( ) è S pj
j( ) è èõ ðàçìåùåíèÿ
âíóòðè îáëàñòè S p0
0( ) . Çàìåòèì, ÷òî óêàçàííûå óñëîâèÿ íå çàâèñÿò îò ôèçè-
÷åñêèõ ïàðàìåòðîâ îáúåêòîâ è ÿâëÿþòñÿ õàðàêòåðíûìè äëÿ êëàññà çàäà÷ ðàç-
ìåùåíèÿ. Ýôôåêòèâíûì àïïàðàòîì äëÿ ôîðìàëèçàöèè óñëîâèé âçàèìíîãî íå-
ïåðåñå÷åíèÿ è ðàçìåùåíèÿ â îáëàñòè ÿâëÿåòñÿ òåîðèÿ Ô-ôóíêöèé Þ.Ã. Ñòîÿíà.
ÌÅÒÎÄ ÈÑÊÓÑÑÒÂÅÍÍÎÃÎ ÐÀÑØÈÐÅÍÈß ÏÐÎÑÒÐÀÍÑÒÂÀ  ÇÀÄÀ×ÀÕ ÐÀÇÌÅÙÅÍÈß
Îñóùåñòâèì ñëåäóþùèå ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ çàäà÷è (1)–(3). Ñ îä-
íîé ñòîðîíû, îñëàáèì óñëîâèÿ äëÿ ôèçèêî-ìåòðè÷åñêèõ ïàðàìåòðîâ wi , i Jn� ,
è áóäåì ñ÷èòàòü èõ íåçàâèñèìûìè ïåðåìåííûìè, ñ äðóãîé — ñôîðìèðóåì òà-
êóþ ñèñòåìó îãðàíè÷åíèé çàäà÷è, â ðåçóëüòàòå êîòîðîé äîïóñòèìûìè áóäóò òå
è òîëüêî òå çíà÷åíèÿ ïåðåìåííûõ wi , i Jn� , êîòîðûå ñîâïàäàþò ñ èñõîäíûìè
ôèêñèðîâàííûìè çíà÷åíèÿìè.
Äëÿ ýòîãî âûäåëèì ñëåäóþùóþ êîìáèíàòîðíóþ ñòðóêòóðó çàäà÷è. Êàæäîìó
îáúåêòó S i ïîñòàâèì â ñîîòâåòñòâèå âåêòîð åãî ôèçèêî-ìåòðè÷åñêèõ ïàðàìåòðîâ
w w w wi i i i� ( , , ..., )
1 2 �
, i Jn� . Îáúåêò S i ñ ïàðàìåòðàìè ðàçìåùåíèÿ pi è ôèçè-
êî-ìåòðè÷åñêèìè ïàðàìåòðàìè wi îáîçíà÷èì S p wi
i i( , ) , i Jn� �{ }0 .
Ïóñòü � � �� ( , ..., )1 n — ïðîèçâîëüíàÿ ïåðåñòàíîâêà ÷èñåë èç Jn . Êàæäîìó
ýëåìåíòó � � �� ( , ..., )1 n ïîñòàâèì â ñîîòâåòñòâèå òî÷êó x R m� , m n� �, ïî ñëå-
äóþùåìó ïðàâèëó:
x x xm� �( , ..., )1 ( , ..., , , ..., , ..., , ..., ,u u r r u un n
1 1 1
1
1
1 1
2
1
1
�
�
� �
�
� �
�
�
r rn n
1 2
�
�
�
, ..., ) . (4)
Ñîâîêóïíîñòü òî÷åê âèäà (4) îáîçíà÷èì E w w wn( , , ..., )1 2 . Íåòðóäíî óâè-
äåòü, ÷òî ìíîæåñòâî E w w wn( , , ..., )1 2 ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïåðåñòàíî-
âîê âåêòîðîâ wi , i Jn� , è ÿâëÿåòñÿ êîíå÷íûì â ïðîñòðàíñòâå R m . Âàæíûì ÿâëÿ-
åòñÿ òîò ôàêò, ÷òî ìíîæåñòâî E w w wn( , , ..., )1 2 ÿâëÿåòñÿ âåðøèííî ðàñïîëîæåí-
íûì, ò.å.
E w w w E w w wn n( , , ..., ) ( , , ..., )1 2 1 2� vert conv .
Äëÿ àíàëèòè÷åñêîãî îïèñàíèÿ ìíîæåñòâà E w w wn( , , ..., )1 2 â ïðîñòðàíñòâå
R m ïðåäëîæèì ñëåäóþùèé ïîäõîä.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 83
Ðàññìîòðèì ìóëüòèìíîæåñòâî
A a a a w w w w w wm� �{ } {1 2 1
1
2
1 1
1
2
2
2 2, , ..., , , ..., , , , ..., ,
� �
..., , , ...,w w wn n n
1 2 �
}
è óïîðÿäî÷èì åãî ýëåìåíòû ïî íåóáûâàíèþ, ò.å. ïîëîæèì, ÷òî
a a am1 2� � �� . Ìóëüòèìíîæåñòâî A ïîðîæäàåò åâêëèäîâî ìíîæåñòâî ïåðå-
ñòàíîâîê (â îáùåì ñëó÷àå ñ ïîâòîðåíèÿìè) E Am ( ) [12, 13].
Ñôîðìèðóåì ñèñòåìó îãðàíè÷åíèé
z ai
i
m
i
i
m
� �
� ��
1 1
, (5)
z a Ji
i
i
i
m
� �
� ��
�
�
�
�
1
| |
, (6)
( ) ( )z ai
i
m
i
i
m
� � �
� �
� �� �2
1
2
1
, (7)
ãäå | |� �� card , � �
�
�
1
1m
ai
i
m
.
Èçâåñòíî [13, 14], ÷òî òî÷êè ìíîæåñòâà E Am ( ) è òîëüêî îíè óäîâëåòâîðÿþò
ñèñòåìå (5)–(7). Çàìåòèì, ÷òî ìíîæåñòâî E Am ( ) ÿâëÿåòñÿ íàäìíîæåñòâîì ìíî-
æåñòâà E w w wn( , , ..., )1 2 . Äëÿ îòñå÷åíèÿ òî÷åê E w w wn( , , ..., )1 2 , êîòîðûå íå
ïðèíàäëåæàò ìíîæåñòâó E Am ( ), ïðèìåíèìû ñëåäóþùèå ñóæäåíèÿ.
Ïóñòü ñóùåñòâóåò òàêîå j J0 � � , ÷òî âñå ýëåìåíòû ìíîæåñòâà A j0
�
� �{ } { }a a a w w wn j j j
n
1
0
2
0 0 1 2
0 0 0
, , ..., , , ..., ðàçëè÷íû. Íå òåðÿÿ îáùíîñòè, ïîëîæèì
a a an1
0
2
0 0 � . Ïîñòðîèì çàâèñèìîñòè
w f w i J j J jj
i
j j
i
n� � �( ), , /
0
0� { }. (8)
Ôîðìàëèçàöèÿ ôóíêöèé f j J jj ( ), /
� � { }0 íå âûçûâàåò çàòðóäíåíèé. Äëÿ
ýòîãî äîñòàòî÷íî ïîñòðîèòü èíòåðïîëÿöèîííûå ïîëèíîìû äëÿ ïàð òî÷åê
( , ),w w i J
j
i
j
i
n
0
� , ñ ïîìîùüþ ëþáîãî ìåòîäà èíòåðïîëÿöèè. Ïðè ýòîì ñèñòåìà
(5)–(7) ñòàíîâèòñÿ èçáûòî÷íîé è ìîæåò áûòü ïðåîáðàçîâàíà ê âèäó
z ai
i
n
i
i
n
� �
� ��
1
0
1
, (9)
z a Ji
i
i
i
n
� �
� ��
�
�
�
�0
1
| |
, (10)
( ) ( )z ai
i
n
i
i
n
� � �
� �
� �� �0
2
1
0
0
2
1
, (11)
�0
0
1
1
�
�
�
n
ai
i
n
.
Ðåøåíèÿ ñèñòåìû (9)–(11) îäíîçíà÷íî îïðåäåëÿþò òî÷êè ìíîæåñòâà
E w w wn( , , ..., )1 2 â ñîîòâåòñòâèè ñ ñîîòíîøåíèÿìè
w z
j
i
i
0
� , w f z i J j J jj
i
j i n� � �( ), , / { }� 0 . (12)
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
Òàêèì îáðàçîì, ìîæíî óòâåðæäàòü, ÷òî òî÷êè ìíîæåñòâà E w w wn( , , ..., )1 2 è
òîëüêî îíè óäîâëåòâîðÿþò ñèñòåìå (9)–(12). Áîëåå òîãî, ïîñêîëüêó ìíîæåñòâî
E w w wn( , , ..., )1 2 âåðøèííî ðàñïîëîæåíî, òî äëÿ ôóíêöèé f j J jj ( ), /
� � { }0 , ñó-
ùåñòâóþò âûïóêëûå ïðîäîëæåíèÿ íà âûïóêëîå íàäìíîæåñòâî
X E w w wn� conv ( , , ..., )1 2 [15–17].
Äëÿ ñëó÷àÿ, êîãäà êàæäîå èç ìóëüòèìíîæåñòâ A a a aj
j j
n
j� �{ }
1 2
, , ...,
� { }w w wj j j
n1 2, , ..., , j J� � , ñîäåðæèò îäèíàêîâûå ýëåìåíòû, îïèøåì ìíîæåñòâî
E w w wn( , , ..., )1 2 ñëåäóþùèì îáðàçîì. Ïóñòü A a a a Jn n� �{ }
1 2
, , ..., , ò.å.
a i i Ji n� �, . Ïîñêîëüêó êàæäîìó îáúåêòó S i , i Jn� , ñîîòâåòñòâóåò åäèíñòâåí-
íûé âåêòîð åãî ôèçèêî-ìåòðè÷åñêèõ ïàðàìåòðîâ, òî ìîæíî óñòàíîâèòü çàâèñè-
ìîñòü ìåæäó íîìåðîì i ýòîãî îáúåêòà è âåêòîðîì w w w wi i i i� ( , , ..., )
1 2 �
, i Jn� .
 ñîîòâåòñòâèè ñ ýòèì ñôîðìèðóåì òàêîå ñåìåéñòâî ôóíêöèé f j ( )
, ÷òî
w f ij
i
j� ( ) , i J j Jn� �, � . (13)
Ñîñòàâèì ñèñòåìó ñëåäóþùèõ óðàâíåíèé è íåðàâåíñòâ:
z
n n
i
i
n
�
� �
�
1
1
2
( )
, (14)
z
k k
J ki
i
n
�
� �
�
� �
�
� �
( )
, | |
1
2
, (15)
z
n
ii
i
n
i
n
�
��
�
�
�
�
� �
� �
� �
1
2
2
1
2
1
. (16)
Ïðè ýòîì îãðàíè÷åíèÿ (14), (15) îïèñûâàþò ìíîãîãðàííèê ìíîæåñòâà ïåðåñòà-
íîâîê ïåðâûõ n íàòóðàëüíûõ ÷èñåë, à ðåøåíèÿ ñèñòåìû (13)–(16) îäíîçíà÷íî
îïðåäåëÿþò òî÷êè ìíîæåñòâà E w w wn( , , ..., )1 2 , äëÿ êîòîðûõ â ñîîòâåòñòâèè ñ
ñîîòíîøåíèÿìè (13)
w f z i J j Jj
i
j i n� � �( ), , � .
Íà îñíîâàíèè ïðèâåäåííûõ ðåçóëüòàòîâ ôîðìàëèçóåì çàâèñèìîñòü ìåæäó
ôèçèêî-ìåòðè÷åñêèìè ïàðàìåòðàìè îáúåêòîâ, ÷òî ïîçâîëèò ñôîðìèðîâàòü ôóíê-
öèîíàëüíûå îãðàíè÷åíèÿ çàäà÷è (1)–(3). Ïðè ýòîì ñàìè óñëîâèÿ (2), (3) èçìåíÿò-
ñÿ ñ ó÷åòîì ïåðåìåííûõ ìåòðè÷åñêèõ ïàðàìåòðîâ è ïðèìóò âèä
~
( , , , )�ij
i i j jp r p r � 0, i Jn� , j Jn� , i j , (17)
~
( , , )�0
0 0i
i ip r r � , i Jn� , (18)
ãäå
~
( )�ij
— ôóíêöèè, îïèñûâàþùèå óñëîâèÿ âçàèìíîãî íåïåðåñå÷åíèÿ îáúåê-
òîâ S p ri
i i( , ) è S p rj
j j( , ), i Jn� , j Jn� , i j , à
~
( )�0i
— ôóíêöèè, îïèñûâà-
þùèå óñëîâèÿ âçàèìíîãî íåïåðåñå÷åíèÿ cS p r0
0 0( , ) è îáúåêòîâ S p ri
i i( , ),
i Jn� , ãäå c — òåîðåòèêî-ìíîæåñòâåííàÿ îïåðàöèÿ äîïîëíåíèÿ.
Òàêèì îáðàçîì, èñõîäíàÿ çàäà÷à (1)–(3) ðàçìåðíîñòè n( )� � �� �1 â ïðîñòðàí-
ñòâå ïåðåìåííûõ w p p p u u un n0 1 2 1 2, , , ..., , , , ..., ýêâèâàëåíòíî ôîðìóëèðóåòñÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 85
êàê îïòèìèçàöèîííàÿ çàäà÷à (1), (13)–(18) ðàçìåðíîñòè n n� �� �( )1 â ïðîñòðàíñòâå
ïåðåìåííûõ p p pn1 2, , ..., , w0 , w w wn1 2, , ..., . Òàêîé ïîäõîä âïåðâûå îïèñàí
â [18] è íàçâàí ìåòîäîì èñêóññòâåííîãî ðàñøèðåíèÿ ïðîñòðàíñòâà. Ïðåèìóùåñòâî
ìåòîäà ïðè ðåàëèçàöèè ðàçëè÷íûõ âû÷èñëèòåëüíûõ ñõåì íåëèíåéíîé îïòèìèçà-
öèè ñîñòîèò â âîçìîæíîñòè ïðåîäîëåíèÿ îáëàñòè ïðèòÿæåíèÿ ëîêàëüíûõ ýêòðåìó-
ìîâ èñõîäíîé çàäà÷è. Ýòîò ôàêò ïîçâîëÿåò ðàññìàòðèâàòü ìåòîä èñêóññòâåííîãî
ðàñøèðåíèÿ ïðîñòðàíñòâà êàê ñïîñîá óëó÷øåíèÿ ëîêàëüíûõ ðåøåíèé èëè ïðèáëè-
æåíèé ê íèì â çàäà÷àõ ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ.
Çàìåòèì, ÷òî êîëè÷åñòâî ëèíåéíûõ îãðàíè÷åíèé â çàäà÷å (1), (13)–(18) íåïî-
ëèíîìèàëüíî è îöåíèâàåòñÿ ïîðÿäêîì 2n . Ïîýòîìó â çàäà÷àõ ëîêàëüíîé îïòèìè-
çàöèè áîëüøîé ðàçìåðíîñòè ïðåäëàãàåòñÿ îñóùåñòâëÿòü èõ äåêîìïîçèöèþ. Ðàñ-
ñìîòðèì ìíîæåñòâî Q w w wn� { }1 2, , ..., è îñóùåñòâèì åãî ðàçáèåíèå íà q ïî-
ïàðíî íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ. Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:
Q Q k
k
q
�
�1
� , Q r r rk m m mlk� { }1 2, , ..., , (19)
M m m mk
lk
� { }1 2, , ..., , m m mlk1 2 � , k Jq� , (20)
l nk
k
q
�
�
�
1
.
 ñîîòâåòñòâèè ñ ðàçáèåíèåì (19), (20) ïðåäñòàâèì ìíîæåñòâî E w w wn( , , ..., )1 2
â âèäå ïðÿìîãî ïðîèçâåäåíèÿ:
E w w w E w w wn
k
q
k m m mlk( , , ..., ) ( , , ..., )1 2
1
1 2�
�
� .
Ïðè ýòîì îãðàíè÷åíèÿ âèäà (5)–(7) çàïèñûâàþòñÿ îòäåëüíî äëÿ êàæäîãî ìíî-
æåñòâà E w w wk m m mlk( , , ..., )1 2 , k Jq� . Âûáîð ñïîñîáà ðàçáèåíèÿ
Q w w wn� { }1 2, , ..., ñ ïîñëåäóþùèì ôîðìèðîâàíèåì îãðàíè÷åíèé, çàäàþùèõ
ìíîæåñòâà E w w wk m m mlk( , , ..., )1 2 , k Jq� , çàäàåò ñåìåéñòâî ìîäèôèêàöèé
ïðåäëîæåííîãî ïîäõîäà.
Ïóñòü ïîëó÷åíî íåêîòîðîå ëîêàëüíîå ðåøåíèå çàäà÷è (1)–(3) èëè åãî ïðè-
áëèæåíèå ïðè ôèêñèðîâàííûõ ôèçèêî-ìåòðè÷åñêèõ ïàðàìåòðàõ w wi i� , 0 ,
i Jn� . Ýòî ðåøåíèå ìîæíî óëó÷øèòü, âûáèðàÿ åãî â êà÷åñòâå íà÷àëüíîé òî÷êè è
ðàññìàòðèâàÿ w w wn1 2, , ..., êàê íåçàâèñèìûå ïåðåìåííûå. Ïðè ýòîì îñóùåñòâëÿ-
åòñÿ äåêîìïîçèöèÿ èñõîäíîé çàäà÷è ïóòåì âûáîðà íåêîòîðîãî ðàçáèåíèÿ ñèñòå-
ìû îãðàíè÷åíèé ïî ïðàâèëó (19), (20). Äàëåå íàõîäèòñÿ íîâîå ëîêàëüíîå ðåøå-
íèå çàäà÷è, êîòîðîå ìîæíî óëó÷øèòü, âûáèðàÿ åãî â êà÷åñòâå íà÷àëüíîé òî÷êè è
ôîðìèðóÿ íîâîå ðàçáèåíèå ìíîæåñòâà Q w w wn� { }1 2, , ..., .
ÏÎÑÒÐÎÅÍÈÅ ÝÊÂÈÂÀËÅÍÒÍÎÉ ÌÎÄÅËÈ Â ÇÀÄÀ×Å ÐÀÂÍÎÂÅÑÍÎÉ ÓÏÀÊÎÂÊÈ
 êà÷åñòâå èëëþñòðàöèè ïðåäëîæåííîãî ïîäõîäà ðàññìîòðèì ñëåäóþùóþ çàäà-
÷ó [19, 20]. Ïóñòü â äâóìåðíîì åâêëèäîâîì ïðîñòðàíñòâå R 2 çàäàíû êðóã S 0
ñ öåíòðîì â òî÷êå p0 0 0� ( , ) è ñåìåéñòâî êðóãîâ S i Ji n, � , ñ ðàäèóñàìè ri è ìàñ-
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
ñàìè u i Ji n, � . Ïîëàãàåì, ÷òî öåíòð òÿæåñòè êðóãà S i íàõîäèòñÿ â åãî ãåîìåò-
ðè÷åñêîì öåíòðå. Óïàêîâêó íàçîâåì ðàâíîâåñíîé, åñëè öåíòð òÿæåñòè ñåìåéñòâà
êðóãîâ S i Ji n, � , ñîâïàäàåò ñ öåíòðîì êðóãà S 0 . Òðåáóåòñÿ íàéòè ðàâíîâåñíóþ
óïàêîâêó êðóãîâ S S n1, ..., â êðóãå S 0 ìèíèìàëüíîãî ðàäèóñà r0 .
Îáîçíà÷èì p x yi
i i� ( , ) , i Jn� , êîîðäèíàòû öåíòðîâ êðóãîâ. Òîãäà ìàòåìà-
òè÷åñêàÿ ïîñòàíîâêà çàäà÷è ïðèìåò âèä
r0 � min (21)
ïðè îãðàíè÷åíèÿõ
x y r ri i i
2 2
0
2� � �( ) , i Jn� , (22)
( ) ( ) ( )x x y y r ri j i j i j� � � � �2 2 2 , i Jn� , j Jn� , i j , (23)
x ui i
i
n
�
� �
1
0, y ui
i
n
i
�
� �
1
0. (24)
Òàêèì îáðàçîì, èìååì çàäà÷ó ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ 2 1n � ïå-
ðåìåííûìè r0 , x yi i, , i Jn� . Çàìåòèì, ÷òî â ïðèâåäåííîé ïîñòàíîâêå ðàäèóñû
r r rn1 2, , ..., è ìàññû u u un1 2, , ..., ÿâëÿþòñÿ êîíñòàíòàìè. Çàôèêñèðóåì r ri i
0 � ,
u ui i
0 � , i Jn� , è ïðåäïîëîæèì, ÷òî r r rn1
0
2
0 0 � . Â ñîîòâåòñòâèè ñ ìåòî-
äîì ðàñøèðåíèÿ ïðîñòðàíñòâà îñëàáèì îãðàíè÷åíèÿ íà ðàäèóñû êðóãîâ è áó-
äåì ñ÷èòàòü èõ íåçàâèñèìûìè ïåðåìåííûìè. Ïîñòðîèì òàêîé èíòåðïîëÿöèîí-
íûé ïîëèíîì u f r� ( ) â îáùåì ñëó÷àå (n-1)-é ñòåïåíè, ÷òî äëÿ ïàð òî÷åê
( , )r ui i
0 0 âûïîëíÿþòñÿ óñëîâèÿ
u f r i Ji i n
0 0� �( ), . (25)
Ñôîðìèðóåì ñèñòåìó îãðàíè÷åíèé
r ri
i
n
i
i
n
� �
� ��
1
0
1
, (26)
r r Ji
i
i
i
n
� �
� ��
�
�
�
�0
1
| |
, (27)
( ) ( )r ri
i
n
i
i
n
� � �
� �
� �� �2
1
0 2
1
, (28)
ãäå � �
�
�
1 0
1n
ri
i
n
.
Ñèñòåìà óðàâíåíèé è íåðàâåíñòâ (26)–(28) îïèñûâàåò ìíîæåñòâî âñåâîçìîæ-
íûõ ïåðåñòàíîâîê èç ÷èñåë { }r r rn1
0
2
0 0, , ..., . Òàêèì îáðàçîì, ìåòîä èñêóññòâåííî-
ãî ðàñøèðåíèÿ ïðîñòðàíñòâà ïîçâîëèë ñôîðìèðîâàòü çàäà÷ó (21)–(28)
â ïðîñòðàíñòâå ïåðåìåííûõ r0 , x y r u i Ji i i i n, , , , � .
Ñóùåñòâåííûì ïðåèìóùåñòâîì ôîðìàëèçàöèè çàäà÷è ðàâíîâåñíîé óïàêîâ-
êè êðóãîâ â âèäå (21)–(28) ÿâëÿåòñÿ åå êâàäðàòè÷íîå ïðåäñòàâëåíèå. Îäíàêî êî-
ëè÷åñòâî ëèíåéíûõ îãðàíè÷åíèé â ñèñòåìå (26), (27) ðàâíî 2n . Ïîýòîìó ðåàëèçà-
öèÿ êëàññè÷åñêèõ ìåòîäîâ íåëèíåéíîé îïòèìèçàöèè îãðàíè÷èâàåòñÿ ðàçìåðíî-
ñòüþ çàäà÷è. Ïðè ýòîì ó÷åò ñâîéñòâ ëèíåéíûõ è êâàäðàòè÷íûõ ôóíêöèé íà
êîìáèíàòîðíûõ ìíîãîãðàííèêàõ ïîçâîëÿåò â ðÿäå ñëó÷àåâ îáõîäèòü
âîçíèêàþùèå òðóäíîñòè [21–24].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 87
Çàìåòèì, ÷òî èñïîëüçîâàíèå ðàäèóñîâ êðóãîâ êàê íåçàâèñèìûõ ïåðåìåííûõ
â ðàìêàõ èíîãî êîíöåïòóàëüíîãî ïîäõîäà ê ðåøåíèþ íåêîòîðûõ êëàññîâ çàäà÷
óïàêîâêè ðàññìàòðèâàëîñü â ðàáîòàõ [25–27], ïîäòâåðæäàÿ ïåðñïåêòèâíîñòü óêà-
çàííîãî íàïðàâëåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå ïðåäëîæåí íîâûé âçãëÿä íà ôîðìàëèçàöèþ çàäà÷ ðàçìå-
ùåíèÿ êàê çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ ïóòåì âûäåëåíèÿ èõ
êîìáèíàòîðíîé ñòðóêòóðû. Â ðåçóëüòàòå ââåäåíèÿ èñêóññòâåííûõ ïåðåìåííûõ
óäàëîñü ñôîðìèðîâàòü äîïîëíèòåëüíóþ ñèñòåìó îãðàíè÷åíèé, çàäàþùèõ ìíî-
æåñòâî ïåðåñòàíîâîê ôèçèêî-ìåòðè÷åñêèõ ïàðàìåòðîâ. Ïðåäëîæåí ïîäõîä ê
ïîñòðîåíèþ ýêâèâàëåíòíîé ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è ïóòåì ðàñøèðåíèÿ
ðàçìåðíîñòè ïðîñòðàíñòâà ïåðåìåííûõ â èñõîäíîé ïîñòàíîâêå. Ýòî ïîçâîëÿåò
çà ñ÷åò èñêóññòâåííûõ ïåðåìåííûõ ïðåîäîëåòü îáëàñòü ïðèòÿæåíèÿ ëîêàëüíûõ
ýêòðåìóìîâ èñõîäíîé çàäà÷è. Òàêèì îáðàçîì, óêàçàííûé ìåòîä, â ïåðâóþ î÷å-
ðåäü, ñëåäóåò ðàññìàòðèâàòü êàê ñïîñîá óëó÷øåíèÿ ëîêàëüíûõ ðåøåíèé çàäà-
÷è. Ïåðñïåêòèâíûì ïðåäñòàâëÿåòñÿ èñïîëüçîâàíèå ìåòîäà â ðàçëè÷íûõ ñõåìàõ
ãëîáàëüíîé îïòèìèçàöèè â çàäà÷àõ ïîêðûòèÿ [28–30].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Stoyan Yu., Pankratov A., Romanova T. Cutting and packing problems for irregular objects with
continuous rotations: Mathematical modeling and nonlinear optimization. Journal of Operational Research
Society. 2016. Vol. 67, N 5. P. 786–800.
2. Bennell J.A., Scheithauer G., Stoyan Yu., Romanova T., Pankratov A. Optimal clustering of a pair of
irregular objects. Journal of Global Optimization. 2015. Vol. 61, N 3. P. 497–524.
3. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal
of Global Optimization. 2016. Vol. 65, N 2. P. 283–307.
4. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object
packing problem. Computational Geometry: Theory and Applications. 2010. Vol. 43, N 5.
P. 535–553.
5. Bortfeldt A., W��ascher G. Constraints in container loading: A state-of-the-art review. European
Journal of Operational Research. 2013. Vol. 229, N 1. P. 1–20.
6. Fasano G. Optimized packings with applications. Optimization and Its Applications. G. Fasano,
J.D. Pinte' r (Eds.). New York: Springer. 2015. Vol. 105. 326 p.
7. Hifi M., Yousef L. Handling lower bound and hill-climbing strategies for sphere packing problems.
S. Fidanova (Ed.), Recent Advances in Computational Optimization Studies in Computational
Intelligence. New York: Springer. 2016. Vol. 610. P. 145–164.
8. M’Hallah R., Alkandari A., Mladenovic N. Packing unit spheres into the smallest sphere using VNS
and NLP. Computers and Operations Research. 2013. Vol. 40, N 2. P. 603–615.
9. Vancroonenburg W., Verstichel J., Tavernier K., Berghe G.V. Transportation research. Part E:
Logistics and transportation review. Pergamon, 2014. P. 70–83.
10. Ñòîÿí Þ.Ã. Îá îäíîì îáîáùåíèè ôóíêöèè ïëîòíîãî ðàçìåùåíèÿ. Äîêë. ÀÍ ÓÑÑÐ. 1980. ¹ 8.
Ñ. 70–74.
11. Stoyan Yu.G., Scheithauer G., Romanova T. Ô-functions for primary 2D-objects. Studia Informatica
Universalis: Int. J. Informatics. 2002. Vol. 2. P. 1–32.
12. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in
combinatorial optimization. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 921–930.
13. Pichugina O.S., Yakovlev S.V. Functional and analytic representations of the general permutations.
Eastern-European Journal of Enterprise Technologies. 2016. Vol. 1, N 4. P. 27–38.
14. Åìåëè÷åâ Â.À., Êîâàëåâ Ì. Ì., Êðàâöîâ Ì. Ê. Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ (êîìáè-
íàòîðíàÿ òåîðèÿ ìíîãîãðàííèêîâ). Ìîñêâà: Íàóêà. Ãëàâíàÿ ðåäàêöèÿ ôèçèêî-ìàòåìàòè÷åñêîé
ëèòåðàòóðû, 1981. 344 ñ.
15. Yakovlev S.V. The theory of convex continuations of functions on vertices of convex polygons.
Computational Mathematics and Mathematical Physics. 1994. Vol. 34, N 7. P. 1112–1119.
16. Pichuginà O., Yakovlev S. Convex extensions and continuous functional representations in
optimization with their applications. J. Coupled Syst. Multiscale Dyn. 2016. Vol. 4, N 2. P. 129–152.
17. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets.
Cybernetics and Systems Analysis. 1989. Vol. 25, N 3. P. 385–391.
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
18. ßêîâëåâ Ñ.Â. Î êîìáèíàòîðíîé ñòðóêòóðå çàäà÷ îïòèìàëüíîãî ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ
îáúåêòîâ. Äîêëàäû ÍÀÍ Óêðàèíû. 2017. ¹ 9. C. 55–61.
19. Íåíàõîâ Ý.À., Ðîìàíîâà Ò.Å., Ñòåöþê Ï.È. Ðàâíîâåñíàÿ óïàêîâêà êðóãîâ â êðóã ìèíèìàëüíîãî
ðàäèóñà. Òåîðèÿ îïòèìàëüíûõ ðåøåíèé. 2013. Ñ. 143–153.
20. Stetsyuk P.I., Romanova T.E., Scheithauer G. On the global minimum in a balanced circular packing
problem. Optimization Letters. 2015. Vol. 10, N 6. P. 1347–1360.
21. Pichuginà O., Yakovlev S. Continuous approaches to the unconstrained binary quadratic problems.
Mathematical and computational approaches in advancing modern science and engineering.
Edited J. Be'lair et al. Switzerland: Springer, 2016. P. 689–700.
22. Stoyan Yu.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in Rn.
Cybernetics and Systems Analysis. 1991. Vol. 27, N 4. P. 562–567.
23. Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer
optimization. Cybernetics and Systems Analysis. 1993. Vol. 29, N 5. P. 419–426.
24. Yakovlev S.V., Valuiskaya O.A. Optimization of linear functions at the vertices of a permutation
polyhedron with additional linear constraints. Ukrainian Mathematical Journal. 2001. Vol. 53, N 9.
P. 1535–1545.
25. Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal spheres into various containers.
Cybernetics and Systems Analysis. 2016. Vol. 52, N 3. P. 419–426.
26. Stoyan Yu., Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm.
Optimization Letters. 2014. Vol. 8, N 3. P. 949–970.
27. Yaskov G.N. Packing non-equal hyperspheres into a hypersphere of minimal radius. Ïðîáëåìû ìà-
øèíîñòðîåíèÿ. 2014. Ò. 17, ¹ 2. C. 48–53.
28. Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungarica.
1989. Vol. 53, N 3. P. 253–262.
29. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cybernetics and
Systems Analysis. 2008, Vol. 44, N 3. P. 333–340.
30. Shekhovtsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in
design of control and monitoring systems. Autom. Remote Control. 1989, Vol. 50, N 5. P. 705–710.
Íàä³éøëà äî ðåäàêö³¿ 10.04.2017
Ñ.Â. ßêîâëºâ
ÌÅÒÎÄ ØÒÓ×ÍÎÃÎ ÐÎÇØÈÐÅÍÍß ÏÐÎÑÒÎÐÓ Ó ÇÀÄÀ×ÀÕ
ÐÎÇ̲ÙÅÍÍß ÃÅÎÌÅÒÐÈ×ÍÈÕ ÎÁ’ªÊÒ²Â
Àíîòàö³ÿ. Ðîçãëÿíóòî çàäà÷ó îïòèìàëüíîãî ðîçì³ùåííÿ ãåîìåòðè÷íèõ îá’ºêò³â
³ç çàäàíèìè ôîðìîþ ³ ô³çèêî-ìåòðè÷íèìè ïàðàìåòðàìè. Âèä³ëåíî êîìá³íà-
òîðíó ñòðóêòóðó çàäà÷³. Íà îñíîâ³ øòó÷íîãî ðîçøèðåííÿ ðîçì³ðíîñò³ ïðîñòîðó
ñôîðìóëüîâàíî åêâ³âàëåíòíó ïîñòàíîâêó âèõ³äíî¿ çàäà÷³, ó ÿêî¿ ô³çèêî-ìåò-
ðè÷í³ ïàðàìåòðè º íåçàëåæíèìè çì³ííèìè. Ðîçãëÿíóòî ïðèêëàä ïîáóäîâè
ð³âíîâàæíî¿ ìîäåë³ çàäà÷³ óïàêîâêè êðóã³â ó êðóã ì³í³ìàëüíîãî ðàä³óñó.
Êëþ÷îâ³ ñëîâà: îïòèìàëüíå ðîçì³ùåííÿ, êîìá³íàòîðíà ìíîæèíà, ð³âíîâàæ-
íå ïàêóâàííÿ.
S.V. Yakovlev
THE METHOD OF ARTIFICIAL SPACE EXPANSION IN PROBLEMS
OF OPTIMAL PLACEMENT OF GEOMETRIC OBJECTS
Abstract. The problem of optimal placement of geometric objects with specified
shape and physical-metric parameters is considered. The combinatorial structure
of the problem is defined. An equivalent problem is formulated based on the
artificial expansion of space dimension with physical-metric parameters being
independent variables. The proposed approach is illustrated by the solution of
balanced circular packing problem.
Keywords: optimal packing problem, combinatorial set, balanced packing.
ßêîâëåâ Ñåðãåé Âñåâîëîäîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà èì. Í.Å. Æóêîâñêîãî
«Õàðüêîâñêèé àâèàöèîííûé èíñòèòóò», e-mail: svsyak7@gmail.com.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 89
|
| id | nasplib_isofts_kiev_ua-123456789-144792 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T13:24:35Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Яковлев, С.В. 2019-01-04T18:18:17Z 2019-01-04T18:18:17Z 2017 Метод искусственного расширения пространства в задачах размещения геометрических объектов / С.В. Яковлев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 82–89. — Бібліогр.: 30 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144792 519.85 Рассматривается задача оптимального размещения геометрических объектов с заданными формой и физико-метрическими параметрами. Выделяется комбинаторная структура задачи. На основе искусственного расширения размерности пространства сформулирована эквивалентная постановка исходной задачи, в которой физико-метрические параметры являются независимыми переменными. Рассмотрен пример построения равновесной модели задачи упаковки кругов в круг минимального радиуса. Розглянуто задачу оптимального розміщення геометричних об’єктів із заданими формою і фізико-метричними параметрами. Виділено комбінаторну структуру задачі. На основі штучного розширення розмірності простору сформульовано еквівалентну постановку вихідної задачі, у якої фізико-метричні параметри є незалежними змінними. Розглянуто приклад побудови рівноважної моделі задачі упаковки кругів у круг мінімального радіусу. The problem of optimal placement of geometric objects with specified shape and physical-metric parameters is considered. The combinatorial structure of the problem is defined. An equivalent problem is formulated based on the artificial expansion of space dimension with physical-metric parameters being independent variables. The proposed approach is illustrated by the solution of balanced circular packing problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Метод искусственного расширения пространства в задачах размещения геометрических объектов Метод штучного розширення простору у задачах розміщення геометричних об’єктів The method of artificial space expansion in problems of optimal placement of geometric objects Article published earlier |
| spellingShingle | Метод искусственного расширения пространства в задачах размещения геометрических объектов Яковлев, С.В. Системний аналіз |
| title | Метод искусственного расширения пространства в задачах размещения геометрических объектов |
| title_alt | Метод штучного розширення простору у задачах розміщення геометричних об’єктів The method of artificial space expansion in problems of optimal placement of geometric objects |
| title_full | Метод искусственного расширения пространства в задачах размещения геометрических объектов |
| title_fullStr | Метод искусственного расширения пространства в задачах размещения геометрических объектов |
| title_full_unstemmed | Метод искусственного расширения пространства в задачах размещения геометрических объектов |
| title_short | Метод искусственного расширения пространства в задачах размещения геометрических объектов |
| title_sort | метод искусственного расширения пространства в задачах размещения геометрических объектов |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144792 |
| work_keys_str_mv | AT âkovlevsv metodiskusstvennogorasšireniâprostranstvavzadačahrazmeŝeniâgeometričeskihobʺektov AT âkovlevsv metodštučnogorozširennâprostoruuzadačahrozmíŝennâgeometričnihobêktív AT âkovlevsv themethodofartificialspaceexpansioninproblemsofoptimalplacementofgeometricobjects |