Математическое моделирование взаимодействия неориентированных выпуклых многогранников
Побудовано Ф-функцію для пари неорієнтованих опуклих багатогранників. Ця функція може використовуватися для побудови математичної моделі оптимізаційної задачі розміщення неорієнтованих багатогранників. Наведено приклад Ф-функції для двох неорієнтованих паралелепіпедів An Ф-function for two non-orien...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84158 |
| 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. — Т. 48, № 6. — С. 36-44. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860006799393947648 |
|---|---|
| author | Стоян, Ю.Г. Чугай, А.М. |
| author_facet | Стоян, Ю.Г. Чугай, А.М. |
| citation_txt | Математическое моделирование взаимодействия неориентированных выпуклых многогранников / Ю.Г. Стоян, А.М. Чугай // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 36-44. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Побудовано Ф-функцію для пари неорієнтованих опуклих багатогранників. Ця функція може використовуватися для побудови математичної моделі оптимізаційної задачі розміщення неорієнтованих багатогранників. Наведено приклад Ф-функції для двох неорієнтованих паралелепіпедів
An Ф-function for two non-oriented convex polytopes is set up. The Ф-function can be used to construct a mathematical model of optimization packing problem of non-oriented polytopes. An example of an Ф-function for two non-oriented parallelepipeds is given.
|
| first_indexed | 2025-12-07T16:39:08Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Þ.Ã. ÑÒÎßÍ, À.Ì. ×ÓÃÀÉ
ÌÀÒÅÌÀÒÈ×ÅÑÊÎÅ ÌÎÄÅËÈÐÎÂÀÍÈÅ ÂÇÀÈÌÎÄÅÉÑÒÂÈß
ÍÅÎÐÈÅÍÒÈÐÎÂÀÍÍÛÕ ÂÛÏÓÊËÛÕ ÌÍÎÃÎÃÐÀÍÍÈÊÎÂ
Êëþ÷åâûå ñëîâà: ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå, �-ôóíêöèÿ, íåîðèåíòèðî-
âàííûå âûïóêëûå ìíîãîãðàííèêè, îïòèìèçàöèîííàÿ çàäà÷à óïàêîâêè.
ÂÂÅÄÅÍÈÅ
Øèðîêèé êðóã âàæíûõ ïðàêòè÷åñêèõ çàäà÷, êîòîðûå âîçíèêàþò â ðàçëè÷íûõ
îòðàñëÿõ ïðîìûøëåííîñòè è íàóêè, ñâîäÿòñÿ ê ìîäåëèðîâàíèþ âçàèìîäåé-
ñòâèÿ ìíîãîãðàííèêîâ. Ê òàêèì çàäà÷àì îòíîñÿòñÿ, íàïðèìåð, ïðèêëàäíûå çà-
äà÷è ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ [1], êîòîðûå ñâÿçàíû ñ îáðàáîòêîé
ñëîæíîé ãåîìåòðè÷åñêîé, àíàëèòè÷åñêîé è ëîãè÷åñêîé èíôîðìàöèè ñ öåëüþ
îïòèìèçàöèè ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ â ñîîòâåòñòâèè ñ çàäàííûì
êðèòåðèåì êà÷åñòâà, à òàêæå çàäà÷è, âîçíèêàþùèå â ðîáîòîòåõíèêå [2].
 íàñòîÿùåå âðåìÿ â êëàññå çàäà÷ ðàçìåùåíèÿ òðåõìåðíûõ ãåîìåòðè÷åñêèõ
îáúåêòîâ íàèìåíåå èçó÷åííûìè ÿâëÿþòñÿ çàäà÷è ðàçìåùåíèÿ òðåõìåðíûõ íåîðè-
åíòèðîâàííûõ îáúåêòîâ, äëÿ êîòîðûõ äîïóñêàþòñÿ àôôèííûå ïðåîáðàçîâàíèÿ íå
òîëüêî òðàíñëÿöèè, íî è íåïðåðûâíîãî ïîâîðîòà. Ýòè çàäà÷è èìåþò âàæíîå òåî-
ðåòè÷åñêîå è ïðàêòè÷åñêîå çíà÷åíèå [3]. Òàê, íàïðèìåð, çàäà÷à ðàçìåùåíèÿ íå-
îðèåíòèðîâàííûõ ìíîãîãðàííèêîâ ìîæåò ïðèìåíÿòüñÿ â ÑÀÏÐ ïðè ñîçäàíèè
ïðîòîòèïîâ ïðîìûøëåííûõ èçäåëèé ñ èñïîëüçîâàíèåì ëàçåðíîé òåõíîëîãèè èç-
áèðàòåëüíîãî ñïåêàíèÿ ñïåöèàëüíîãî ïîðîøêà [4]. Êðîìå òîãî, äàííàÿ çàäà÷à
ïðèìåíÿåòñÿ äëÿ òðåõìåðíîãî ìîäåëèðîâàíèÿ, âèçóàëüíîãî è êîëè÷åñòâåííîãî
àíàëèçà ñòðóêòóðíûõ îñîáåííîñòåé è ìåõàíè÷åñêèõ ñâîéñòâ ðàçëè÷íûõ òâåðäûõ,
æèäêèõ, ñòåêëîâèäíûõ ìàòåðèàëîâ, ãðàíóëèðîâàííûõ ñðåä, ãåòåðîãåííûõ ìàòå-
ðèàëîâ è áèîëîãè÷åñêèõ ñèñòåì [5, 6]. Ñëåäóåò îòìåòèòü, ÷òî çàäà÷à óïàêîâêè
ìíîãîãðàííèêîâ òàêæå ïðèìåíÿåòñÿ ïðè âíåäðåíèè ìàòåðèàëîñáåðåãàþùèõ
òåõíîëîãèé [7] è ïðè îïðåäåëåíèè îáúåìà áàãàæíèêà àâòîìîáèëÿ â ñîîòâåòñòâèè
ñ åâðîïåéñêèìè íîðìàìè [8].
Ïî ñâîåé ïîñòàíîâêå çàäà÷è ðàçìåùåíèÿ òðåõìåðíûõ ãåîìåòðè÷åñêèõ îáúåêòîâ
ÿâëÿþòñÿ îïòèìèçàöèîííûìè. Îäíàêî â íàñòîÿùåå âðåìÿ ñóùåñòâóåò ïðîáëåìà ïðè-
ìåíåíèÿ ìåòîäîâ ëîêàëüíîé è ãëîáàëüíîé îïòèìèçàöèè äëÿ ðåøåíèÿ çàäà÷ ðàçìåùå-
íèÿ íåîðèåíòèðîâàííûõ 3D îáúåêòîâ. Ýòî îáóñëîâëåíî îòñóòñòâèåì êîíñòðóêòèâ-
íûõ ñðåäñòâ ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ âçàèìîäåéñòâèÿ ýòèõ îáúåêòîâ.
 íàñòîÿùåå âðåìÿ ïðè ðåøåíèè çàäà÷è òðåõìåðíîé óïàêîâêè ââèäó ñëîæíî-
ñòè çàäà÷ àâòîðû òðàäèöèîííî èñïîëüçóþò òîëüêî øàðû è ïðàâèëüíûå îðèåíòèðîâàí-
íûå ìíîãîãðàííèêè. Ïðè ýòîì äëÿ ðåøåíèÿ çàäà÷ ïðèìåíÿþò ñóììó Ìèíêîâñêîãî,
êîòîðàÿ ìîæåò óñïåøíî èñïîëüçîâàòüñÿ äëÿ ðåøåò÷àòîé óïàêîâêè îáúåêòîâ [9].
Îáçîðó ñîâðåìåííûõ ìåòîäîâ ìîäåëèðîâàíèÿ îòíîøåíèé âêëþ÷åíèÿ, ïåðå-
ñå÷åíèÿ è êàñàíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ ïîñâÿùåíà ñòàòüÿ [10].  íàñòîÿùåé
ðàáîòå îòìå÷åíî, ÷òî îäíèì èç ïåðñïåêòèâíûõ ïîäõîäîâ äëÿ ïîñòðîåíèÿ àäåêâàò-
íûõ ìàòåìàòè÷åñêèõ ìîäåëåé çàäà÷ ðàçìåùåíèÿ è óïàêîâêè ÿâëÿåòñÿ ìåòîä
Ô-ôóíêöèé [11]. Â ðàáîòå [12] ïîêàçàíî, ÷òî ìåòîä Ô-ôóíêöèé ïîçâîëÿåò óëó÷-
øèòü ðåçóëüòàòû ðåøåíèÿ çàäà÷ óïàêîâêè ãåîìåòðè÷åñêèõ îáúåêòîâ â ðåçóëüòàòå
ïðèìåíåíèÿ ñîâðåìåííûõ ìåòîäîâ îïòèìèçàöèè.
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
© Þ.Ã. Ñòîÿí, À.Ì. ×óãàé, 2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 37
 ðàáîòå [13] ïîñòðîåíû Ô-ôóíêöèè äëÿ áàçîâûõ îðèåíòèðîâàííûõ 3D îáú-
åêòîâ, ãðàíèöû êîòîðûõ èìåþò îäíó èç ñëåäóþùèõ ôîðì: øàð, ïàðàëëåëåïèïåä,
êîíóñ, öèëèíäð. Ñòàòüÿ [14] ïîñâÿùåíà ïîñòðîåíèþ Ô-ôóíêöèè äëÿ äâóõ âûïóê-
ëûõ îðèåíòèðîâàííûõ ìíîãîãðàííèêîâ. Ìåòîäû ðåøåíèÿ çàäà÷è óïàêîâêè îðè-
åíòèðîâàííûõ ìíîãîãðàííèêîâ ðàññìîòðåíû â [4, 15].
Ïîñêîëüêó ôóíäàìåíòàëüíîé îñíîâîé ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ
îïòèìèçàöèîííûõ çàäà÷ óïàêîâêè íåîðèåíòèðîâàííûõ ìíîãîãðàííèêîâ ÿâëÿåòñÿ
àíàëèòè÷åñêîå îïèñàíèå îòíîøåíèé èõ âêëþ÷åíèÿ, ïåðåñå÷åíèÿ è êàñàíèÿ, òî
öåëüþ äàííîé ñòàòüè ÿâëÿåòñÿ ïîñòðîåíèå Ô-ôóíêöèè äëÿ äâóõ íåîðèåíòèðîâàí-
íûõ âûïóêëûõ ìíîãîãðàííèêîâ.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü çàäàíû âûïóêëûå ìíîãîãðàííèêè
P X x y z R f X A x B y C z D
i ij ij ij ij ij
� � � � � � � �{ ( , , ) : ( ) ,
3
0
j G i
i i
� � �{ }}1 2 1 2, , , , ,� � .
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: H
ij
— ãðàíè P
i
, j G
i
� ; p x y z
ij ij ij ij
� ( , , ) —
âåðøèíû P
i
, j W w
i i
� � ( , , , )1 2 � , çàäàííûå îòíîñèòåëüíî ñîáñòâåííîé ñèñòåìû
êîîðäèíàò O x y z
i i i i
� � � ìíîãîãðàííèêà P
i
; e p p
it it it
� [ , ]
1 2
— ðåáðà P
i
, t T
i
� �
= { }1 2, , ,� �
i
, t t W
i1 2, � (ñîãëàñíî ôîðìóëå Ýéëåðà � �
i i i
w� � �2).
Ìíîãîãðàííèê P
i
ìîæåò áûòü òðàíñëèðîâàí íà âåêòîð �
i i i i
x y z� ( , , ) è ïî-
âåðíóò íà óãëû � � �
i i i
, , , i �1 2, , âîêðóã îñåé Ox Oy, è Oz ñîîòâåòñòâåííî. Ìàòðè-
öó ïðåîáðàçîâàíèÿ ïîâîðîòà, êîòîðàÿ ïåðåâîäèò òî÷êó, çàäàííóþ îòíîñèòåëüíî
ïîâåðíóòîé íà óãëû � � �
i i i
, , ñîáñòâåííîé ñèñòåìû êîîðäèíàò O x y z
i i i i
� � � ìíîãî-
ãðàííèêà P
i
, â òî÷êó, çàäàííóþ îòíîñèòåëüíî íåïîäâèæíîé ñèñòåìû êîîðäèíàò
Oxyz, ïðåäñòàâèì â âèäå
R
g
r
q
g g g
r r r
q q q
i
i
i
i
i i i
i i i
i i i
�
�
�
�
�
�
�
�
�
�
1 2 3
1 2 3
1 2 3
�
�
�
�
�
�
, (1)
ãäå g g g
i i i i i i i i1 2 3� � � �cos cos , cos sin , sin� � � � � ; r
i i i i1 � �sin sin cos� � �
�cos sin ,� �
i i
r r
i i i i i i i i i2 3� � � � �sin sin sin cos cos , sin cos ;� � � � � � � q
i1 �
� � � � �cos sin cos sin sin , cos sin sin s� � � � � � � �
i i i i i i i i i
q 2 in cos ,� �
i i
q
i3 �
� cos cos .� �
i i
Èñõîäÿ èç âèäà ìàòðèöû (1), ïîëó÷èì ìàòðèöó ïðåîáðàçîâàíèÿ, êîòîðàÿ ïå-
ðåâîäèò òî÷êó èç íåïîäâèæíîé ñèñòåìû êîîðäèíàò Oxyz â òî÷êó â ñèñòåìå êîîð-
äèíàò O x y z
i i i i
� � � :
� �
�
�
�
�
�
�
�
�
�
�
�
� � �
� � �
�
R
g
r
q
g g g
r r r
q
i
i
i
i
i i i
i i i
1 2 3
1 2 3
i i i
q q1 2 3� �
�
�
�
�
�
�
�
,
ãäå � � � � �g g
i i i i i i i i i1 2cos cos , sin cos cos sin sin ,� � � � � � � � � �g
i i i3 sin sin� �
�cos sin cos ;� � �
i i i
� � � � � �r r
i i i i i i i i i1 2sin cos , cos cos sin sin sin ,� � � � � � �
� � � � � � � �r q q
i i i i i i i i i3 1 2sin cos sin sin cos ; sin , c� � � � � � os sin ,� �
i i
� �q
i3
� cos cos .� �
i i
Âåêòîð äâèæåíèÿ P
i
îáîçíà÷èì u R
i i i
� �( , )� �
6
, ãäå � � � �
i i i i
� ( , , ) . Òîã-
äà ìíîãîãðàííèê P i
i i
( ), ,� �1 2, çàäàäèì ñëåäóþùåé ñèñòåìîé íåðàâåíñòâ:
f R X
f R X
f R X
i i
T
i i
T
i i
T
i
1
2
0
0
0
( ) ,
( ) ,
( ) .
� �
� �
� �
�
�
�
�
�
�
�
�
�
(2)
Äëÿ âåðøèí è ðåáåð ìíîãîãðàííèêà P u
i i
( ) , i �1 2, , çàäàäèì ñëåäóþùèå îáîçíà÷åíèÿ
(ðèñ. 1): p u p
ij i i ij i
( ) ( ),� �� � p R p
ij i i ij
T
( ) ,� � j W
i
� , e u p u p u
it i it i it i
( ) [ ( ), ( )]�
1 2
,
t T
i
� .
Çàäà÷à. Ïðåäñòàâèòü â àíàëèòè÷åñêîì âèäå îïèñàíèå îòíîøåíèé âêëþ÷åíèÿ,
ïåðåñå÷åíèÿ è êàñàíèÿ äëÿ ïàðû íåîðèåíòèðîâàííûõ âûïóêëûõ ìíîãîãðàííèêîâ.
Äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è âîñïîëüçóåìñÿ ìåòîäîì Ô-ôóíêöèé [11]
è ïîñòðîèì äëÿ ïàðû íåîðèåíòèðîâàííûõ âûïóêëûõ ìíîãîãðàííèêîâ P u1 1( ) è
P u2 2( ) Ô-ôóíêöèþ �( , ):u u R R1 2
12 1
� , êîòîðàÿ óäîâëåòâîðÿåò ñëåäóþùèì
õàðàêòåðèñòè÷åñêèì ñâîéñòâàì:
1) �( , ) ,u u1 2 0� åñëè cl clP u P u1 1 2 2( ) ( )� � �;
2) �( , ) ,u u1 2 0� åñëè int intP u P u1 1 2 2( ) ( )� � � è fr frP u P u1 1 2 2( ) ( )� � � ;
3) �( , ) ,u u1 2 0� åñëè int intP u P u1 1 2 2( ) ( )� � �,
ãäå cl A , fr A è int A — ñîîòâåòñòâåííî çàìûêàíèå, ãðàíèöà è âíóòðåííîñòü
ìíîæåñòâà A [16].
ÌÅÒÎÄ ÏÎÑÒÐÎÅÍÈß Ô-ÔÓÍÊÖÈÈ ÄËß P u1 1( ) È P u2 2( )
Ïðåäëàãàåìûé ìåòîä ïîñòðîåíèÿ Ô-ôóíêöèè îñíîâàí ôàêòè÷åñêè íà ìîäå-
ëèðîâàíèè êàñàíèÿ äâóõ ïðîèçâîëüíûõ íåîðèåíòèðîâàííûõ ìíîãîãðàííèêîâ.
Î÷åâèäíî, ÷òî ïðè ëþáîì êàñàíèè âûïóêëûõ ìíîãîãðàííèêîâ èìååò ìåñòî îäèí
èëè êîìáèíàöèÿ íåñêîëüêèõ òèïîâ êàñàíèÿ ýëåìåíòîâ èõ ãðàíèö: âåðøèíà
P u1 1( ) êàñàåòñÿ ãðàíè P u2 2( ) ; ðåáðî P u1 1( ) êàñàåòñÿ (èìååò îáùèå òî÷êè) ãðàíè
P u2 2( ) ; ãðàíü P u1 1( ) êàñàåòñÿ (èìååò îáùèå òî÷êè) ãðàíè P u2 2( ) ; âåðøèíà
P u2 2( ) êàñàåòñÿ ãðàíè P u1 1( ) ; ðåáðî P u2 2( ) êàñàåòñÿ (èìååò îáùèå òî÷êè) ãðà-
íè P u1 1( ); ðåáðî P u1 1( ) êàñàåòñÿ (èìååò îäíó îáùóþ òî÷êó) ðåáðà P u2 2( ) .
Äëÿ íåîðèåíòèðîâàííûõ âûïóêëûõ ìíîãîãðàííèêîâ âñå âîçìîæíûå êàñàíèÿ
ìîæíî ñìîäåëèðîâàòü, èñïîëüçóÿ ñëåäóþùèå òðè âèäà êàñàíèé:
1) âåðøèíà P u
2 2( ) êàñàåòñÿ ãðàíè P u1 1( ), ò.å. p u P u P u
j2 2 1 1 2 2( ) ( ) ( )� �fr fr ,
j W� 2 , è int intP u P u1 1 2 2( ) ( )� � � (ðèñ. 2, à);
2) âåðøèíà P u
1 1( ) êàñàåòñÿ ãðàíè P u2 2( ), ò.å. p u P u P u
j1 1 1 1 2 2( ) ( ) ( )� �fr fr ,
j W�
1
, è int intP u P u1 1 2 2( ) ( )� � � (ðèñ. 2, á);
3) ðåáðî P u1 1( ) êàñàåòñÿ (èìååò îäíó îáùóþ òî÷êó) ðåáðà P u2 2( ) (ðèñ. 2, â).
×òîáû â àíàëèòè÷åñêîì âèäå îïèñàòü óêàçàííûå òðè âèäà êàñàíèÿ, çàïèøåì
ñëåäóþùåå óñëîâèå êàñàíèÿ ìíîãîãðàííèêîâ. Åñëè P u1 1( ) è P u2 2( ) êàñàþòñÿ, òî
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
Ðèñ. 1. Ìíîãîãðàííèê P u
i i
( ), ïîëó÷åííûé èç ìíîãîãðàííèêà P
i
ñóùåñòâóåò, ïî êðàéíåé ìåðå, îäíà ïàðà òî÷åê � �* ( ) ( )1 1 1�fr P u è
� �** ( ) ( )2 2 2�fr P u , äëÿ êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî (ðèñ. 3)
� � � � � �* **( ) ( )1 2 1 2� � � . (3)
Èñïîëüçóÿ äàííîå óñëîâèå, âûïîëíèì àíàëèòè÷åñêîå îïèñàíèå êàæäîãî âèäà
êàñàíèÿ.
Ïåðâûé âèä êàñàíèÿ. Ïóñòü âåðøèíà p u P u
j2 2 2 2( ) ( )� êàñàåòñÿ ãðàíè
H P u
p1 1 1� ( ). Äëÿ ïðîñòîòû ïîëîæèì ñíà÷àëà, ÷òî u1 0� . Òîãäà, êàê ñëåäóåò
èç (3), ïëîñêîñòü, ïðîõîäÿùàÿ ÷åðåç ãðàíü H P
p1 1
0� ( ), êîòîðàÿ îïðåäåëÿåòñÿ ðà-
âåíñòâîì f p
p j1 2 2 2 0( ( ))� �� � , ðàçäåëÿåò P1 0( ) è P u2 2( ) . Äðóãèìè ñëîâàìè,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 39
Ðèñ. 2. Âèäû êàñàíèÿ ìíîãîãðàííèêîâ
à á
â
Ðèñ. 3. Êàñàíèå ìíîãîãðàííèêîâ
åñëè äëÿ u R2
6
� âûïîëíÿåòñÿ äàííîå ðàâåíñòâî, òî P1 0( ) è P u2 2( ) êàñàþòñÿ, ïî
êðàéíåé ìåðå, â òî÷êå p u P P u
j2 2 1 2 20( ) ( ) ( )� �fr fr . Ñëåäîâàòåëüíî, åñëè äëÿ
u R2
6
� âûïîëíÿåòñÿ íåðàâåíñòâî f p
p j1 2 2 2 0( ( ))� �� � , òî p u P
j2 2 1 0( ) ( )� int .
Èç ýòîãî ñëåäóåò, ÷òî åñëè íåðàâåíñòâî min ( ( )),{ }f p j W
pj j1 2 2 2 2 0� �� � � âû-
ïîëíÿåòñÿ, òî p u P
j2 2 1 0( ) ( )� int , j W� 2 . Îòñþäà åñëè âûïîëíÿåòñÿ íåðàâåíñòâî
max min ( ( )), ,{ { } }f p j W p G
pj j1 2 2 2 2 1 0� �� � � � , (4)
òî ìíîãîãðàííèêè P1 0( ) è P u2 2( ) íå ïåðåñåêàþòñÿ.
Ïîëîæèì òåïåðü, ÷òî u R1
6
� òàêæå ÿâëÿåòñÿ ïåðåìåííîé. Íà îñíîâàíèè
óðàâíåíèÿ f R X
p1 1
0( )� � èç ñèñòåìû (2) è âûðàæåíèÿ (3) ïîñòðîèì óðàâíåíèå
ïëîñêîñòè, ïðîõîäÿùåé ÷åðåç ãðàíü H P u
p1 1 1� ( ) â ñëåäóþùåì âèäå:
F u u f R R p
pj pj
j
1 1 2 1 1 2 1 2 2
0( , ) ( ( ) ) .� � � �
�
�
�
�
�
�� �
T T T
(5)
Î÷åâèäíî, ÷òî åñëè F u u
pj1 1 2 0( , ) � äëÿ j W� 2 , òî äàííàÿ ïëîñêîñòü ðàçäåëÿ-
åò P u1 1( ) è P u2 2( ), ò.å. p u P u
j2 2 1 1( ) ( )� int , j W�
1
, è int intP u P u1 1 2 2( ) ( )� � �.
Èñõîäÿ èç âûðàæåíèé (4) è (5), ïîñòðîèì ôóíêöèþ
�1 1 2 1 1 2 2 1( , ) max min ( , ), ,u u F u u j W p G
pj
� � �{ { } }, (6)
êîòîðàÿ îáëàäàåò ñëåäóþùèì ñâîéñòâîì: åñëè �1 1 2 0( , )u u � , òî ìíîãîãðàííè-
êè P u1 1( ) è P u2 2( ) íå ïåðåñåêàþòñÿ.
Âòîðîé âèä êàñàíèÿ. Ïóñòü âåðøèíà p u P u
j1 1 1 1( ) ( )� êàñàåòñÿ ãðàíè
H P u
k2 2 2� ( ) . Òîãäà, îñíîâûâàÿñü íà óðàâíåíèè f R X
k2 2
0( )� � èç ñèñòåìû (2) è
âûðàæåíèè (3), ìîæíî ïîñòðîèòü óðàâíåíèå ïëîñêîñòè, ïðîõîäÿùåé ÷åðåç ãðàíü
H P u
k2 2 2� ( ), â âèäå
F u u f R R p
kj kj
j
2 1 2 2 2
2 1 1 1
0( , ) ( ( ) ) .� � � �
�
�
�
�
�
�� �
T T T
(7)
Î÷åâèäíî, ÷òî åñëè F u u
kj2 1 2 0( , ) � äëÿ j W� 1, òî äàííàÿ ïëîñêîñòü ðàçäåëÿ-
åò P u1 1( ) è P u2 2( ) , ò.å. p u P u
j1 1 2 2
( ) ( )� int , j W� 1, è int intP u P u1 1 2 2( ) ( )� � �.
Îñíîâûâàÿñü íà âûðàæåíèè (7), ïîñòðîèì ôóíêöèþ
�2 1 2 2 1 2 1 2( , ) max min ( , ), ,u u F u u j W k G
kj
� � �{ { } }, (8)
êîòîðàÿ îáëàäàåò ñëåäóþùèì ñâîéñòâîì: åñëè �2 1 2 0( , )u u � , òî ìíîãîãðàííè-
êè P u1 1( ) è P u2 2( ) íå ïåðåñåêàþòñÿ.
Ñëåäóåò îòìåòèòü, ÷òî ïðè ìîäåëèðîâàíèè âçàèìîäåéñòâèÿ P u1 1( ) è P u2 2( )
ìîæåò âîçíèêíóòü ñèòóàöèÿ, êîãäà �
i
u u( , )1 2 0� , i �1 2, , îäíàêî
int intP u P u1 1 2 2
( ) ( ) .� � � Òàêàÿ ñèòóàöèÿ ìîæåò âîçíèêíóòü, íàïðèìåð, êîãäà
ìíîãîãðàííèêè êàñàþòñÿ ðåáðàìè (ðèñ. 3, â).
Òðåòèé âèä êàñàíèÿ. Ïóñòü ðåáðî e u p u p u P u
j j j1 1 1 1 1 1 1 11 2
( ) [ ( ), ( )] ( )� � êàñà-
åòñÿ ðåáðà e u p u p u P u
t t t2 2 2 2 2 2 2 21 2
( ) [ ( ), ( )] ( )� � . Òîãäà ïëîñêîñòü, ðàçäåëÿþ-
ùàÿ ìíîãîãðàííèêè, áóäåò ïðîõîäèòü ÷åðåç ýòè äâà ðåáðà. ×òîáû ïîñòðîèòü ðàç-
äåëÿþùóþ ïëîñêîñòü, ñîâìåñòèì âåðøèíû p u
j1 11
( ) è p u
t2 21
( ) .  ýòîì ñëó÷àå
âåêòîð � �
jt
( , )1 , êîòîðûé îïðåäåëÿåò ðàñïîëîæåíèå ñîáñòâåííîé ñèñòåìû êî-
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
îðäèíàò P u
2 2( ) ïî îòíîøåíèþ ê ñîáñòâåííîé ñèñòåìå êîîðäèíàò P u1 1( ) , îïðåäå-
ëÿåòñÿ ôîðìóëîé � � � �
jt j t
p p( , ) ( ) ( )1 2 1 1 2 21 1
� � . Èñõîäÿ èç ýòîãî, âåêòîð
� � �
jt
( , )
1 2 , êîòîðûé îïðåäåëÿåò êîîðäèíàòû p
t2 22
( )� ïî îòíîøåíèþ ê ñîáñòâåííîé
ñèñòåìå êîîðäèíàò P u
1 1( ), èìååò âèä � � � � � �
jt j t t
p p p( , ) ( ) ( ) ( )1 2 1 1 2 2 2 21 1 2
� � �
(ðèñ. 4). Òîãäà ïëîñêîñòü E
jt
( , )� �1 2 , ïðîõîäÿùàÿ ÷åðåç òî÷êè p
j1 11
( )� , p
j1 12
( )�
è � � �
jt
( , )1 2 , îïðåäåëÿåòñÿ óðàâíåíèåì
�
jt
j
T
jt
j
T
j
X x g p A y r p B( , , ) ( )
~
( , ) ( )
~
� � � �1 2 1 1 1 2 1 11 1
� � � �
t
( , )� �1 2 �
� � �( )
~
( , ) ,z q p C
j
T
jt1 1 1 2
1
0� � j T t T� �1 2, , (9)
ãäå êîýôôèöèåíòû
~
( , )A
jt
� �1 2 ,
~
( , )B
jt
� �1 2 è
~
( , )C
jt
� �1 2 îïðåäåëÿþòñÿ ÷åðåç
êîîðäèíàòû òî÷åê p
j1 1
1
( )� , p
j1 12
( )� è � � �
jt
( , )1 2 .
Íà îñíîâàíèè âûðàæåíèé (3) è (9) ïîñòðîèì óðàâíåíèå
� �
jt jt t
u u p( , ) ( ( ), , ) ,1 2 2 1 2 2 1 21
0� � � �� � � � � j T t T� �1 2, . (10)
Î÷åâèäíî, ÷òî åñëè òî÷êà ( , )u u R1 2
12
� óäîâëåòâîðÿåò ðàâåíñòâó (10), òî
e u e u E
j t jt1 1 2 2( ), ( ) � .
Ïóñòü ïëîñêîñòü E
jt
äåëèò ïðîñòðàíñòâî R
3
íà ïîëîæèòåëüíîå �
jt
�
è îòðèöà-
òåëüíîå �
jt
�
ïîëóïðîñòðàíñòâà. Ñëåäóåò îòìåòèòü, ÷òî ôóíêöèÿ �
jt
u u( , )1 2 èñïîëü-
çóåòñÿ â ôîðìèðîâàíèè Ô-ôóíêöèè â îäíîì èç ñëó÷àåâ, êîãäà P u
jt2 2( ) �
�
� è
P u
jt1 1( ) �
�
� èëè P u
jt2 2( ) �
�
� è P u
jt1 1( ) �
�
� .
×òîáû îïðåäåëèòü óñëîâèå ó÷àñòèÿ �
jt
u u( , )1 2 â ôîðìèðîâàíèè Ô-ôóíêöèè,
äîñòàòî÷íî âû÷èñëèòü çíà÷åíèÿ óðàâíåíèÿ (9) â âåðøèíàõ
~
( )p
j1
1
1
1
� è
~
( )p
j1
2
1
1
� ,
ñìåæíûõ ê âåðøèíå p
j1 1
1
( )� ðåáðà e
j1 1( )� ìíîãîãðàííèêà P u1 1( ) , à òàêæå â âåð-
øèíàõ
~
( )p
t2
1
2
1
� è
~
( )p
t2
2
2
1
� , ñìåæíûõ ê âåðøèíå p
t2 21
( )� ðåáðà e
t2 2( )� ìíîãî-
ãðàííèêà P u2 2( ) (ðèñ. 5).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 41
Ðèñ. 4. Ïîñòðîåíèå ðàçäåëÿþùåé ïëîñêîñòè äëÿ
òðåòüåãî âèäà êàñàíèÿ
Ðèñ. 5. Âåðøèíû, â êîòîðûõ ïðîâåðÿåòñÿ
óñëîâèå ó÷àñòèÿ �
jt
u u( , )
1 2
â ôîðìèðîâàíèè
Ô-ôóíêöèè
Íà îñíîâàíèè èçëîæåííîãî ïîñòðîèì ôóíêöèþ
F u u
u u
u u
jt
jt jt
jt3 1 2
1 2 1 2
1( , )
( , ), ( , )
( ,�
�
�
�
�
åñëè 0,1� � �
2 1 2
1 2
), ( , )
, ( , )
åñëè 0,
åñëè 0,
2
3
� � �
� � �
jt
jt
�
�
�
�
�
�
�
(11)
ãäå
� � � � � � 1 {
jt jt
j
i
jt jt
j
p p( , ) min (
~
( ), , ), (
~
1 2 1 1 1 2 2
� � �� �
i
i( ), , ), , ,� � �2 1 2 1 2� }
� � � � � � 2 {
jt jt
j
i
jt jt
p p( , ) min (
~
( ), , ), ( (
~
1 2 1 1 1 2 2
� � �� �
j
i
i( ), , )), , ,� � �2 1 2 1 2� }
� � � � � � � � �3 1 2max{ }
jt jt jt
( , ) ( , ), ( , )1 2 1 2 1 2� .
Ïîñêîëüêó ëþáàÿ Ô-ôóíêöèÿ îãðàíè÷åíà ñíèçó äëÿ îãðàíè÷åííûõ ãåîìåòðè-
÷åñêèõ îáúåêòîâ, òî
� min ( , )� u u1 2 . Ýòî çíà÷èò, ÷òî �
jt
u u( , )1 2 ïðèíèìàåò
ó÷àñòèå â ôîðìèðîâàíèè �( , )u u1 2 òîëüêî â ñëó÷àå, åñëè � � �3 0
jt
( , )1 2 � .
Ñëåäóåò îòìåòèòü, ÷òî ïëîñêîñòü E
jt
ðàçäåëÿåò P u1 1( ) è P u2 2( ), êîãäà
F u u
jt3 1 2 0( , ) � .
Îñíîâûâàÿñü íà âûðàæåíèè (11), ïîñòðîèì ôóíêöèþ
�3 1 2 3 1 2( , ) max ( , ),u u F u u
jt
� {
j T t T� �1 2, }, (12)
êîòîðàÿ îáëàäàåò ñëåäóþùèì ñâîéñòâîì: åñëè �3 1 2 0( , )u u � , òî ìíîãîãðàííè-
êè P u1 1( ) è P u2 2( ) íå ïåðåñåêàþòñÿ.
Ïîñêîëüêó ðàññìîòðåííûå òðè âèäà êàñàíèé ïîçâîëÿþò îïèñàòü âñå âîçìîæ-
íûå âèäû êàñàíèÿ, òî íà îñíîâàíèè ôóíêöèé (6), (8) è (12) Ô-ôóíêöèÿ äëÿ äâóõ
íåîðèåíòèðîâàííûõ âûïóêëûõ ìíîãîãðàííèêîâ ìîæåò áûòü ïðåäñòàâëåíà
ñëåäóþùèì îáðàçîì:
� �( , ) max ( , ), , ,u u u u i
i1 2 1 2 1 2 3� � �{ }
� � � �max min ( , ), , , min ( , ),{ { } {F u u j J p K F u u j
pj kj1 1 2 1 1 2 1 2 J2 },
k K F u u j T t T
jt
� � �2 3 1 2 1 2, ( , ), , }. (13)
Ðàññìîòðèì ïðèìåð. Ôóíêöèÿ (13) ìîæåò áûòü èñïîëüçîâàíà ïðè ïîñòðî-
åíèè ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è óïàêîâêè íåîðèåíòèðîâàííûõ ïàðàëëåëåïè-
ïåäîâ â ïàðàëëåëåïèïåä äëÿ àíàëèòè÷åñêîãî îïèñàíèÿ äâóõ îñíîâíûõ âèäîâ
îãðàíè÷åíèé çàäà÷è:
1) ïîïàðíîãî íåïåðåñå÷åíèÿ ðàçìåùàåìûõ ïàðàëëåëåïèïåäîâ;
2) ïðèíàäëåæíîñòè êàæäîãî ïàðàëëåëåïèïåäà îáëàñòè ðàçìåùåíèÿ.
Ïåðâûé òèï îãðàíè÷åíèÿ ìîæíî ôîðìàëèçîâàòü, èñïîëüçóÿ Ô-ôóíêöèþ äëÿ
äâóõ íåîðèåíòèðîâàííûõ ïàðàëëåëåïèïåäîâ:
P x y z R l x l w y w h z h
i i i i i i i
� � � � � � � � � � �{ }( , , , ) : , ,
3
, i �1 2, .
 ýòîì ñëó÷àå ôóíêöèÿ (6) ïðèìåò âèä
�1 1 2 1 1 2 1 2 8 1 2( , ) max min ( , ), , , , , , ,u u F u u j p
pj
� � �{ { { }} {� � , 6}},
ãäå
F u u g g p x g r p y g q p
j
j
T
j
T
11 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � �
2 1
j
T
z l� �) ,
F u u g g p x g r p y g q
j
j
T
j
T
12 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � � � p z l
j
T
2 1� �) ,
F u u r g p x r r p y r q p
j
j
T
j
T
13 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � �
2 1
j
T
z w� �) ,
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
F u u r g p x r r p y r q
j
j
T
j
T
14 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � � � p z w
j
T
2 1� �) ,
F u u q g p x q r p y q q p
j
j
T
j
T
15 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � �
2 1
j
T
z h� �) ,
F u u q g p x q r p y q q
j
j
T
j
T
16 1 2 11 2 2 12 2 2 13 2( , ) ( ) ( ) (� � � � � � � � � p z h
j
T
2 1� �) ,
x x x y y y z z z� � � � � �2 1 2 1 2 1, , .
Ôóíêöèÿ (8) ïðèìåò âèä
�2 1 2 2 1 2 1 2 8 1 2( , ) max min ( , ), , , , , , ,u u F u u j k
kj
� � �{ { { }} {� � , ,6}}
ãäå
F u u g x g p g y r p g z q
j
j
T
j
T
21 1 2 21 1 1 22 1 1 23( , ) ( ) ( ) (� � � � � � � � � 1 1 2p l
j
T
) ,�
F u u g x g p g y r p g z
j
j
T
j
T
22 1 2 21 1 1 22 1 1 23( , ) ( ) ( ) (� � � � � � � � � � q p l
j
T
1 1 2) ,�
F u u r x g p r y r p r z q
j
j
T
j
T
23 1 2 21 1 1 22 1 1 23( , ) ( ) ( ) (� � � � � � � � � 1 1 2p w
j
T
) ,�
F u u r x g p r y r p r z
j
j
T
j
T
24 1 2 21 1 1 22 1 1 23( , ) ( ) ( ) (� � � � � � � � � � q p w
j
T
1 1 2) ,�
F u u q x g p q y r p q z q
j
j
Ò
j25 1 2 31 1 1 32 1 1 33 1( , ) ( ) ( ) (� � � � � � � � � p h
j1 2) ,�
F u u q x g p q y r p q z q
j
j
Ò
j26 1 2 31 1 1 32 1 1 33( , ) ( ) ( ) (� � � � � � � � � � 1 1 2p h
j
) .�
Ôóíêöèÿ (12) ïðèìåò âèä
�3 1 2 3 1 2 1 2 12( , ) max ( , ), , , , ,u u F u u j t
jt
� �{ { }}� ,
ãäå
F u u
u u
jt
jt jt
jt3 1 2
1 2 1 2
( , )
( , ), ( , )
�
�
�
�
�
åñëè 0,1� � �
( , ), ( , )
, ( ,
u u
jt
jt
1 2 1 2
1
åñëè 0,
åñëè
2
3
� � �
� �
�
�2 )�
�
�
�
�
�
0,
� �max , , , ,{ }2 2 2 1 2l w h i
i i i
.
Òîãäà Ô-ôóíêöèþ äëÿ äâóõ ïàðàëëåëåïèïåäîâ ìîæíî çàïèñàòü â âèäå
�( , ) max min ( , ), ( , , ..., ) , minu u F u u j F
pj1 2 1 1 2 21 2 8� �{ { } {
kj
u u( , ),1 2
j p k� �( , , ..., ) , , , , ,1 2 8 1 2 6} { };� F u u j t
jt3 1 2 1 2 12( , ), , , , ,�{ }}� .
Âòîðîé òèï îãðàíè÷åíèÿ ìîæíî ôîðìàëèçîâàòü, èñïîëüçóÿ Ô-ôóíêöèþ äëÿ íå-
îðèåíòèðîâàííîãî ïàðàëëåëåïèïåäà P x y z R l x l
i i i
� � � � �{( , , ) : ,
3
� � �w y w
i i
,
� � �h z h
i i
} è îáúåêòà cl ( \ )R S
3
, ãäå S x y z R l x l w y w� � � � � � � �{( , , ) : , ,
3
� � �h z h} — îáëàñòü ðàçìåùåíèÿ, ïðåäñòàâëåííàÿ â âèäå ïàðàëëåëåïèïåäà. Ïðè
ýòîì ïîëþñ ïàðàëëåëåïèïåäà S ñîâïàäàåò ñ íà÷àëîì ñèñòåìû êîîðäèíàò Oxyz.
Òîãäà Ô-ôóíêöèÿ äëÿ P
i
è îáúåêòà cl ( \ )R S
3
ïðèìåò âèä
�( ) min ( ), , , , , , , ,u F u k j
i kj i
� � �{ { } { }}1 2 6 1 2 8� � ,
ãäå
F u x g p l
j i i i ij1 ( ) � � � �
T
, F u x g p l
j i i i ij2 ( ) � � �
T
,
F u y r p w
j i i i ij3 ( ) � � � �
T
,
F u y r p w
j i i i ij4 ( ) � � �
T
, F u z q p h
j i i i ij5 ( ) � � � �
T
,
F u z q p h
j i i i ij6 ( ) � � �
T
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 43
ÇÀÊËÞ×ÅÍÈÅ
Íà îñíîâå ïîñòðîåííîé Ô-ôóíêöèè (13) ëåãêî ìîæíî ïîñòðîèòü Ô-ôóíêöèþ
äëÿ ïàðû íåîðèåíòèðîâàííûõ íåâûïóêëûõ ìíîãîãðàííèêîâ. Äëÿ ïîñòðîåíèÿ
òàêîé Ô-ôóíêöèè íåîáõîäèìî âîñïîëüçîâàòüñÿ ìåòîäîì ïîñòðîåíèÿ Ô-ôóíê-
öèè äëÿ ñëîæíûõ ãåîìåòðè÷åñêèõ îáúåêòîâ [17].
Ïðåäñòàâëåííàÿ â ðàáîòå Ô-ôóíêöèÿ (13) ïîçâîëÿåò ñòðîèòü ìàòåìàòè÷åñêèå
ìîäåëè îïòèìèçàöèîííûõ çàäà÷ ðàçìåùåíèÿ íåîðèåíòèðîâàííûõ ìíîãîãðàííè-
êîâ, â êîòîðûõ îáëàñòü äîïóñòèìûõ ðåøåíèé îïòèìèçàöèîííîé çàäà÷è ìîæåò
áûòü ïðåäñòàâëåíà â âèäå îáúåäèíåíèÿ ïîäîáëàñòåé. Ïðè ýòîì êàæäàÿ òàêàÿ ïîä-
îáëàñòü îïèñûâàåòñÿ ñèñòåìîé íåðàâåíñòâ, ëåâûå ÷àñòè êîòîðûõ ÿâëÿþòñÿ íåïðå-
ðûâíûìè áåñêîíå÷íî äèôôåðåíöèðóåìûìè ôóíêöèÿìè. Ýòî ñâîéñòâî äàåò âîç-
ìîæíîñòü èñïîëüçîâàòü ñîâðåìåííûå ìåòîäû îïòèìèçàöèè äëÿ ðåøåíèÿ ïðè-
êëàäíûõ îïòèìèçàöèîííûõ çàäà÷ óïàêîâêè íåîðèåíòèðîâàííûõ ìíîãîãðàííèêîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû
ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1986. — 268 ñ.
2. M a y e r N . , F o g e l E . , H a l p e r i n D . Fast and robust retrieval of Minkowski sums of rotat-
ing convex polyhedra in 3-space // Proceedings of the 14-th ACM Symposium on Solid and Physical
Modeling. — Haifa, Israel, 2010. — P. 1–10.
3. T a k a y u k i O . Approaches to 3D free-form cutting and packing problems and their applications:
A survey. — Tokyo: IBM Research Laboratory, 1998. — P. 13.
4. E g e b l a d J . , N i e l s e n B . K . , B r a z i l M . Translational packing of arbitrary polytopes //
Computational Geometry: Theory and Applications. — 2009. — 42, N 4. — P. 269–288.
5. T o r q u a t o S . , S t i l l i n g e r F . H . Jammed hard-particle packings: From Kepler to Bernal and
beyond // Reviews of Modern Physics. — 2010. — 82, N 3. — P. 2633–2672.
6. G a n M . , G o p i n a t h a n N . , J i a X . , W i l l i a m s R . A . Predicting packing characteristics
of particles of arbitrary shapes // KONA. — 2004. — N 22. — P. 82–93.
7. Ä î ð î ø å í ê î  . Ñ . 3D-òåõíîëîãèè â ëèòåéíîì ïðîèçâîäñòâå // Âèíàõ³äíèê ³ ðàö³îíà-
ë³çàòîð. — 2009. — ¹ 2. — Ñ. 12–15.
8. E i s e n b r a n d F . , F u n k e S . , K a r r e n b a u e r A . , R e i c h e l J . , S c h ��o m e r E . Packing
a trunk — now with a twist! // Proceedings SPM 2005 ACM Symposium on Solid and Physical
Modeling. — New York, USA, 2005. — P. 197–206.
9. B e t k e U . , H e n k M . Densest lattice packings of 3-polytopes // Computational Geometry. —
2000. — 16, N 3. — P. 157–186.
10. B e n n e l l J . , O l i v e i r a J . The geometry of nesting problems: A tutorial // European Journal of
Operational Research. — 2008. — N 184. — P. 397–415.
11. S t o y a n Y u . G . Ô-function and its basic properties // Äîêë. ÍÀÍ Óêðàèíû. Ñåð. A. — 2001. —
N 8. — Ñ. 112–117.
12. C h e r n o v N . , S t o y a n Y . , R o m a n o v a T . Mathematical model and efficient algorithms
for object packing problem // Computational Geometry: Theory and Applications. — 2010. — 43,
N 5. — P. 535–553.
13. Ñ ò î ÿ í Þ . à . , Ð î ì à í î â à Ò . Å . , Ø à é ò õ à ó ý ð à . Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå
âçàèìîäåéñòâèé áàçîâûõ ãåîìåòðè÷åñêèõ 3D îáúåêòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2005. — ¹ 3. — Ñ. 19–31.
14. S t o y a n Y . , T e r n o J . , S c h e i t h a u e r G . , G i l M . , R o m a n o v a T . Construction of
a Phi-function for two convex polytopes // Applicationes Mathematicae. — 2002. — 29, N 2. —
P. 199–218.
15. S t o y a n Y u . , P a n k r a t o v A . , S h e i t h a u e r G . Translational packing non-convex polytopes
into a parallelepiped // Journal of Mechanical Engineering. — 2009. — 12, N 3. — Ñ. 67–76.
16. Ê ó ð à ò î â ñ ê è é Ê . Òîïîëîãèÿ. — Ò. 1. — Ì.: Ìèð, 1966. — 594 ñ.
17. S t o y a n Y . , S c h e i t h a u e r G . , G i l M . , R o m a n o v a Ò . �-function for complex 2D ob-
jects // 4OR. Quarterly Journal of the Belgian, French and Italian Operations Research Societies. —
2004. — 2, N 1. — Ð. 69–84.
Ïîñòóïèëà 06.04.2011
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages false
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 290
/ColorImageMinResolutionPolicy /Warning
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 290
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 800
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/PDFX3:2003
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError false
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox false
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020>
/ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /NoConversion
/DestinationProfileName ()
/DestinationProfileSelector /NA
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure true
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles true
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /NA
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /LeaveUntagged
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-84158 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:39:08Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Чугай, А.М. 2015-07-03T10:51:28Z 2015-07-03T10:51:28Z 2012 Математическое моделирование взаимодействия неориентированных выпуклых многогранников / Ю.Г. Стоян, А.М. Чугай // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 36-44. — Бібліогр.: 17 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84158 519.85 Побудовано Ф-функцію для пари неорієнтованих опуклих багатогранників. Ця функція може використовуватися для побудови математичної моделі оптимізаційної задачі розміщення неорієнтованих багатогранників. Наведено приклад Ф-функції для двох неорієнтованих паралелепіпедів An Ф-function for two non-oriented convex polytopes is set up. The Ф-function can be used to construct a mathematical model of optimization packing problem of non-oriented polytopes. An example of an Ф-function for two non-oriented parallelepipeds is given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Математическое моделирование взаимодействия неориентированных выпуклых многогранников Математичне моделювання взаємодії неорієнтованих опуклих багатогранників Mathematical modeling of interactions of non-oriented convex polytopes Article published earlier |
| spellingShingle | Математическое моделирование взаимодействия неориентированных выпуклых многогранников Стоян, Ю.Г. Чугай, А.М. Системный анализ |
| title | Математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| title_alt | Математичне моделювання взаємодії неорієнтованих опуклих багатогранників Mathematical modeling of interactions of non-oriented convex polytopes |
| title_full | Математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| title_fullStr | Математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| title_full_unstemmed | Математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| title_short | Математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| title_sort | математическое моделирование взаимодействия неориентированных выпуклых многогранников |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84158 |
| work_keys_str_mv | AT stoânûg matematičeskoemodelirovanievzaimodeistviâneorientirovannyhvypuklyhmnogogrannikov AT čugaiam matematičeskoemodelirovanievzaimodeistviâneorientirovannyhvypuklyhmnogogrannikov AT stoânûg matematičnemodelûvannâvzaêmodííneoríêntovanihopuklihbagatogrannikív AT čugaiam matematičnemodelûvannâvzaêmodííneoríêntovanihopuklihbagatogrannikív AT stoânûg mathematicalmodelingofinteractionsofnonorientedconvexpolytopes AT čugaiam mathematicalmodelingofinteractionsofnonorientedconvexpolytopes |