Задача упаковки интервальных параллелепипедов
Построена интервальная математическая модель оптимизационной задачи упаковки интервальных параллелепипедов. Осуществлен переход к двухкритериальной задаче в евклидовом пространстве. Предложена стратегия решения, основанная на использовании метода оптимизации по группам переменных и модифицированного...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2008 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101604 |
| 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: | Задача упаковки интервальных параллелепипедов / Л.Г. Евсеева, О.В. Панкратов // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 35-47. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859943735549231104 |
|---|---|
| author | Евсеева, Л.Г Панкратов, О.В. |
| author_facet | Евсеева, Л.Г Панкратов, О.В. |
| citation_txt | Задача упаковки интервальных параллелепипедов / Л.Г. Евсеева, О.В. Панкратов // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 35-47. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Построена интервальная математическая модель оптимизационной задачи упаковки интервальных параллелепипедов. Осуществлен переход к двухкритериальной задаче в евклидовом пространстве. Предложена стратегия решения, основанная на использовании метода оптимизации по группам переменных и модифицированного метода сужающихся окрестностей.
Побудовано інтервальну математичну модель оптимізаційної задачі упакування інтервальних паралелепіпедів. Здійснено перехід до двохкритеріальної задачі в евклідовому просторі. Запропоновано стратегію розв’язання, яка базується на використанні методу оптимізації за групами змінних і модифікованого методу околів, що звужуються.
The interval mathematical model of optimization problem of packing the interval parallelepipeds is built. Transition is made to the two-criteria problem in Euclidean space. The solution strategy, based on the use of the optimization on the groups of variables and of modified method of narrowing environs, is suggested.
|
| first_indexed | 2025-12-07T16:12:37Z |
| format | Article |
| fulltext |
ÓÄÊ 519.859
Ë. Ã. Åâñååâà, êàíä. ôèç.-ìàò. íàóê
Ïîëòàâñêèé óíèâåðñèòåò ïîòðåáèòåëüñêîé êîîïåðàöèè Óêðàèíû
(Óêðàèíà, 36014, Ïîëòàâà, óë. Êîâàëÿ, 3,
òåë.: (0532) 668286, Å-mail: yevseeva@satel.com.ua),
Î. Â. Ïàíêðàòîâ, êàíä. òåõí. íàóê
Èíñòèòóò ïðîáëåì ìàøèíîñòðîåíèÿ èì. À.Í. Ïîäãîðíîãî ÍÀÍ Óêðàèíû
(Óêðàèíà, 61046, Õàðüêîâ, óë. Ïîæàðñêîãî, 2/10,
òåë.: (0572) 959536, Å-mail: pankratov@ipmach.kharkov.ua)
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
Ïîñòðîåíà èíòåðâàëüíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü îïòèìèçàöèîííîé çàäà÷è óïàêîâêè èíòåð-
âàëüíûõ ïàðàëëåëåïèïåäîâ. Îñóùåñòâëåí ïåðåõîä ê äâóõêðèòåðèàëüíîé çàäà÷å â åâêëèäîâîì
ïðîñòðàíñòâå. Ïðåäëîæåíà ñòðàòåãèÿ ðåøåíèÿ, îñíîâàííàÿ íà èñïîëüçîâàíèè ìåòîäà îïòèìè-
çàöèè ïî ãðóïïàì ïåðåìåííûõ è ìîäèôèöèðîâàííîãî ìåòîäà ñóæàþùèõñÿ îêðåñòíîñòåé.
Ïîáóäîâàíî ³íòåðâàëüíó ìàòåìàòè÷íó ìîäåëü îïòèì³çàö³éíî¿ çàäà÷³ óïàêóâàííÿ ³íòåð-
âàëüíèõ ïàðàëåëåï³ïåä³â. Çä³éñíåíî ïåðåõ³ä äî äâîõêðèòåð³àëüíî¿ çàäà÷³ â åâêë³äîâîìó
ïðîñòîð³. Çàïðîïîíîâàíî ñòðàòåã³þ ðîçâ’ÿçàííÿ, ÿêà áàçóºòüñÿ íà âèêîðèñòàíí³ ìåòîäó
îïòèì³çàö³¿ çà ãðóïàìè çì³ííèõ ³ ìîäèô³êîâàíîãî ìåòîäó îêîë³â, ùî çâóæóþòüñÿ.
Ê ë þ ÷ å â û å ñ ë î â à: èíòåðâàëüíûé ïàðàëëåëåïèïåä, èíòåðâàëüíîå Ô-îòîáðàæåíèå,
èíòåðâàëüíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü, äâóõêðèòåðèàëüíàÿ îïòèìèçàöèîííàÿ çàäà÷à,
ñòðàòåãèÿ ðåøåíèÿ.
Çàäà÷è óïàêîâêè ïàðàëëåëåïèïåäîâ 3DBP (3D Bin Packing) ïðèíàäëåæàò
êëàññó çàäà÷ ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ [1] è çàíèìàþò îñîáîå ìåñ-
òî â êëàññå çàäà÷ Cutting & Packing (3D C&P) [2], ÷òî îáóñëîâëåííî èõ
àêòóàëüíîñòüþ è øèðîêèì ñïåêòðîì ïðèëîæåíèé. Â ðàáîòå [2] óêàçàíû
íàèáîëåå èçâåñòíûå ïîäõîäû ê ðåøåíèþ çàäà÷ òðåõìåðíîé óïàêîâêè, à
èìåííî ïîäõîäû, îñíîâàííûå íà ãåíåòè÷åñêîì àëãîðèòìå, àëãîðèòìå «èìèòà-
öèîííîãî îáæèãà», èñïîëüçîâàíèè ðàçëè÷íûõ ýâðèñòè÷åñêèõ ïîäõîäîâ.
Áîëüøèíñòâî ñîâðåìåííûõ ìåòîäèê ðåøåíèÿ äàííîãî êëàññà çàäà÷ ÿâëÿþòñÿ
ýâðèñòè÷åñêèìè (ñì., íàïðèìåð, [3, 4]) è ðàññìàòðèâàþòñÿ â êîíòåêñòå
êîíêðåòíîãî ïðàêòè÷åñêîãî ïðèìåíåíèÿ çàäà÷è. Ïîýòîìó ïîëó÷åííûå ðå-
øåíèÿ, â îáùåì ñëó÷àå, ïðåäñòàâëÿþò ñîáîé ëèøü íåêîòîðûå ïðèáëè-
æåíèÿ ê îïòèìàëüíûì.
Ýôôåêòèâíûå ìåòîäû ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ ðàçìåùåíèÿ
ðàçðàáîòàíû íàó÷íîé øêîëîé Þ.Ã. Ñòîÿíà [1, 5, 6]: ìîäèôèêàöèè ìåòîäîâ
ëîêàëüíîé è ãëîáàëüíîé îïòèìèçàöèè. Îäíàêî, êàê ïðàâèëî, ìàòåìàòè-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 35
÷åñêîå ìîäåëèðîâàíèå è ðåøåíèå çàäà÷ ðàçìåùåíèÿ îñóùåñòâëÿëîñü áåç
ó÷åòà ïîãðåøíîñòåé èñõîäíûõ äàííûõ, ò. å. â èäåàëèçèðîâàííîé ôîðìå.
Ðàçâèòèå ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ êàê íàó÷íîãî íàïðàâëåíèÿ òðå-
áóåò ó÷åòà ïîãðåøíîñòåé äëÿ ïîñòðîåíèÿ àäåêâàòíûõ ìàòåìàòè÷åñêèõ ìîäå-
ëåé îïòèìèçàöèîííûõ çàäà÷ ðàçìåùåíèÿ è ðàçðàáîòêè ìåòîäîâ èõ ðåøåíèÿ.
 ðàìêàõ ðàçâèòèÿ êîíöåïöèè ó÷åòà ïîãðåøíîñòåé ïðè ìîäåëèðîâà-
íèè è ðåøåíèè çàäà÷ ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ ïðåäëàãàåòñÿ
ïîäõîä ê ó÷åòó ïîãðåøíîñòåé íà îñíîâå èñïîëüçîâàíèÿ ïðèëîæåíèÿ èíòåð-
âàëüíîãî àíàëèçà [7] â ãåîìåòðè÷åñêîì ïðîåêòèðîâàíèè [1], èíòåðâàëüíîé
ãåîìåòðèè [8]. Ïðèìåíåíèå ïðè ìîäåëèðîâàíèè îïòèìèçàöèîííîé çàäà÷è
òàêèõ ïîíÿòèé èíòåðâàëüíîé ãåîìåòðèè, êàê èíòåðâàëüíàÿ ãèïåðïëîñêîñòü,
èíòåðâàëüíûé ïàðàëëåëåïèïåä, èíòåðâàëüíîå êàñàíèå ãåîìåòðè÷åñêèõ îáúåê-
òîâ, èíòåðâàëüíîå ðàññòîÿíèå ìåæäó âûïóêëûìè èíòåðâàëüíûìè ìíîãîãðàí-
íèêàìè, èíòåðâàëüíîå íàïðàâëåííîå ìíîæåñòâî, äàåò âîçìîæíîñòü, ñ îäíîé
ñòîðîíû, ðàöèîíàëüíûì îáðàçîì ó÷èòûâàòü ïîãðåøíîñòè èñõîäíûõ äàí-
íûõ, à ñ äðóãîé,— ïðåäñòàâèòü ìàòåìàòè÷åñêóþ ìîäåëü çàäà÷è â âèäå,
ïîçâîëÿþùåì ðåàëèçîâàòü åå ñîâðåìåííûìè ýôôåêòèâíûìè ìåòîäàìè
îïòèìèçàöèè.
Ïîñòàíîâêà çàäà÷è. Ðàññìîòðèì îïòèìèçàöèîííóþ çàäà÷ó ãåîìåòðè-
÷åñêîãî ïðîåêòèðîâàíèÿ [1] â òàêîé ïîñòàíîâêå. Ïóñòü â åâêëèäîâîì ïðîñò-
ðàíñòâå R 3
èìååòñÿ êîíå÷íîå ìíîæåñòâî ïàðàëëåëåïèïåäîâ Pi ñ ìåòðè÷åñ-
êèìè õàðàêòåðèñòèêàìè
m a v b v c vi
v
i a i b i ci i i
� � � �2( , , ), (1)
a Ri �
�
, v Rai
�
�
, b Ri �
�
, v Rbi
�
�
, c Ri �
�
, v Rci
�
�
, (2)
a ai0
� , b bi0
� , c ci0
� ,
v aa ii
� � , v bb ii
� � , v cc ii
� � , �� ( , )0 1
1R , i J n�{ }0 � ,
ãäå J nn �{ , ,..., }1 2 — èíäåêñíîå ìíîæåñòâî. Çíà÷åíèå � çàâèñèò îò êîíêðåò-
íîãî ñìûñëà ïðèêëàäíîé èëè íàó÷íîé çàäà÷è è õàðàêòåðèçóåò òî÷íîñòü
çàäàíèÿ èñõîäíûõ äàííûõ.
 äàííîì èññëåäîâàíèè äëÿ óïàêîâêè ïàðàëëåëåïèïåäîâ Pi , i J n� , â
ïàðàëëåëåïèïåä P
0
èñïîëüçóåòñÿ òðàíñëÿöèÿ Pi íà âåêòîðû:
u v x v y v z v Ri u i x i y i zi i i i
� � � � � �( , , )
3
, (3)
ãäå v Rxi
�
1
, v Ryi
�
1
, v Rzi
�
1
. Ïàðàëëåëåïèïåä Pi ñ ïàðàìåòðàìè ðàçìåùå-
íèÿ (3) îáîçíà÷èì P u vi i ui
( )� .
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
36 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Çàäà÷à. Íåîáõîäèìî íàéòè âåêòîð ïàðàìåòðîâ ðàçìåùåíèÿ u vu� �
� � � � �( , , )u v u v u v Ru u n u
n
n1 2
3
1 2
òàêîé, ÷òîáû ïàðàëëåëåïèïåäû P u vi i ui
( )� ,
i J n� , ïðèíàäëåæàëè P u vu0 0
0
( )� áåç âçàèìíûõ ïåðåñå÷åíèé è ÷òîáû ïðè
ýòîì âûñîòà h*
çàíÿòîé ÷àñòè ïàðàëëåëåïèïåäà P u vu0 0
0
( )� è åå ïîãðåø-
íîñòü vh
*
äîñòèãàëè ìèíèìàëüíûõ çíà÷åíèé.
Î÷åâèäíî, çàäàíèå ìåòðè÷åñêèõ õàðàêòåðèñòèê îáúåêòîâ â âèäå (1),
(2), à ïàðàìåòðîâ ðàçìåùåíèÿ â âèäå (3) ïîçâîëÿåò åñòåñòâåííûì îáðàçîì
ñîçäàòü ïàðû âèäà ( , )
v R�
2
, õàðàêòåðèçóþùèå íåêîòîðóþ âåëè÷èíó
�R1
è ïîãðåøíîñòü v R
�
1
çàäàíèÿ ýòîé âåëè÷èíû. Òîãäà âåùåñòâåííîå
÷èñëî
ñ ó÷åòîì ïîãðåøíîñòè åãî çàäàíèÿ ìîæíî ïðåäñòàâèòü äâóìÿ
÷èñëàìè — îöåíêîé ñíèçó è îöåíêîé ñâåðõó, îáðàçóþùèìè èíòåðâàëüíîå
÷èñëî
,v A s� �I R, ãäå I Rs — ðàñøèðåííîå ïðîñòðàíñòâî öåíòðèðî-
âàííûõ èíòåðâàëîâ [8].
Èíòåðâàëüíàÿ ìàòåìàòè÷åñêàÿ ìîäåëü. Íà îñíîâå ãîìåîìîðôèçìà
[8] ïðîñòðàíñòâ I Rs è R 2
çàäàäèì áèåêöèþ ìåæäó èñõîäíûìè äàííûìè è
ýëåìåíòàìè ïðîñòðàíñòâà I Rs :
R a v a v Ai a i a i si i
2
( , ) ,� � �I R, R b v b v Bi b i b i si i
2
( , ) ,� � �I R ,
R c v c v Ci c i c i si i
2
( , ) ,� � �I R, R a v x v Xx x i x i si i
2
( , ) ,� � �I R ,
R y v y v Yi y i y i si i
2
( , ) ,� � �I R, R z v z v Zi z i z i si i
2
( , ) ,� � �I R ,
i J n�{ }0 � .
Òîãäà óñëîâèþ (2) ñîîòâåòñòâóþò èíòåðâàëüíûå íåðàâåíñòâà [8] âèäà
Ai � 0 , Bi � 0, C i � 0, i J n�{ }0 � , 0 0 0� , ,
A Ai0
� , B Bi0
� , C C i0
� , i J n� .
Ðàññìîòðèì èíòåðâàëüíîå îòîáðàæåíèå [8] f I R I R: s s
3
� âèäà
f f( ) max { ( )}
, ,...,
U Ui
k
i
k
i�
�1 2 6
, i J n�{ }0 � . (4)
Çäåñü
f i i i iU X X A1
( ) ( )�
, f i i i iU X X A2
( ) ( )�
,
f i i i iU Y Y B3
( ) ( )�
, f i i i iU Y Y B4
( ) ( )�
, (5)
f i i i iU Z Z C5
( ) ( )�
, f i i i iU Z Z C6
( ) ( )�
,
ãäå U X Y Z s� �( , , ) I R
3
; X x v x vx x s� �
�, , ) I R — ýëåìåíò, ñîïðÿ-
æåííûé ýëåìåíòó X x vx s� �, I R [9].
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 37
Ìàêñèìóì â (4) çäåñü è äàëåå ïîíèìàåì òàê:
X x v X X X Xx j n
* * *
, max{ , ,..., }� � �
1 2
, j J n� .
Îòñþäà ñ ó÷åòîì îòíîøåíèÿ ëèíåéíîãî ïîðÿäêà â I Rs [8] ïîëó÷àåì
X
x x x v v x x i j i Jj
i n
i x x i j nj
*
*
, ,...,
*
max { }, , , ,
�
� � � � � �
�1 2
,
, max { } , ...
* *
, ,...,
*x x v v v x x x xj x x
i n
x nj i
� � � � � � �
�1 2
1 2
,
, max { } , ...
* *
, ,...,
*x x v v v x x xj x x
i m
x i ij it m
� � � � � �
�1 2
1
, , .i J m nt n� �
�
�
�
�
�
�
�
�
�
Èíòåðâàëüíûì ïàðàëëåëåïèïåäîì P I Ri s
3
ñ öåíòðîì ñîáñòâåííîé
ñèñòåìû êîîðäèíàò U X Y Zi i i i� ( , , ) íàçûâàåòñÿ òî÷å÷íîå èíòåðâàëü-
íîå ìíîæåñòâî âèäà
P I R I R I R I Ri i s s s sU( ) � � �
3
,
P P fr Pi i i i i iU U U( ) int ( ) ( )� � , i J n�{ }0 � ,
èíòåðâàëüíàÿ ãðàíèöà fr Pi iU( ) êîòîðîãî îïðåäåëÿåòñÿ óðàâíåíèåì
f 0,0( ) ,U i � � 00 . Ïðè ýòîì f 0i
k
iU( ) � , k J�
6
ÿâëÿþòñÿ óðàâíåíèÿìè èíòåð-
âàëüíûõ ãèïåðïëîñêîñòåé [8], ïðèíèìàþùèìè ó÷àñòèå â ôîðìèðîâàíèè
fr Pi iU( ).
Èñõîäÿ èç áèåêöèè ìåæäó èñõîäíûìè äàííûìè è ýëåìåíòàìè I Rs ñ
ó÷åòîì (3) èíòåðâàëüíîå íàïðàâëåííîå ìíîæåñòâî [9]
U X Y Zi i i i s� �( , , ) I R
3
,
X x vi i x si
� �, I R , Y y vi i y si
� �, I R ,
Z z vi i z si
� �, I R , i J n�{ }0 � ,
íàçîâåì èíòåðâàëüíûìè ïàðàìåòðàìè ðàçìåùåíèÿ èíòåðâàëüíîãî îáúåêòà
Pi . Îáúåêò Pi , òðàíñëèðóåìûé íà èíòåðâàëüíîå íàïðàâëåííîå ìíîæåñòâî
U i , îáîçíà÷èì Pi iU( ). Òîãäà îïòèìèçàöèîííóþ çàäà÷ó ðàçìåùåíèÿ îáúåê-
òîâ Pi iU( ) , ìåòðè÷åñêèå õàðàêòåðèñòèêè (1), (2) è ïàðàìåòðû ðàçìåùåíèÿ
(3) êîòîðûõ çàäàíû ñ íåêîòîðûìè ïîãðåøíîñòÿìè, ìîæíî ïðåäñòàâèòü êàê
îïòèìèçàöèîííóþ çàäà÷ó ðàçìåùåíèÿ èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
P I Ri i sU( )
3
, i J n� ,
â èíòåðâàëüíîé îáëàñòè P I R
0 0
3
( )U s .
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
38 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Ìàòåìàòè÷åñêóþ ìîäåëü îïòèìèçàöèîííîé çàäà÷è ðàçìåùåíèÿ èíòåð-
âàëüíûõ ïàðàëëåëåïèïåäîâ â èíòåðâàëüíûé ïàðàëëåëåïèïåä íàçîâåì èí-
òåðâàëüíîé ìàòåìàòè÷åñêîé ìîäåëüþ çàäà÷è 3DBIP (3D Bin Interval Pack-
ing). Äëÿ àíàëèòè÷åñêîãî îïèñàíèÿ âçàèìîäåéñòâèÿ îáúåêòîâ òðåõìåðíîãî
èíòåðâàëüíîãî ïðîñòðàíñòâà I Rs
3
íà îñíîâå îïðåäåëåíèÿ Ô-ôóíêöèè ïàðû
îáúåêòîâ åâêëèäîâà ïðîñòðàíñòâà [10] ââåäåíî ïîíÿòèå èíòåðâàëüíîãî
Ô-îòîáðàæåíèÿ ïàð îáúåêòîâ èíòåðâàëüíîãî ïðîñòðàíñòâà I Rs
3
.
Èíòåðâàëüíîå îòîáðàæåíèå [8]Ô I R I R:
6
s
s� íàçûâàåòñÿ èíòåðâàëüíûì
Ô-îòîáðàæåíèåì îáúåêòîâ T I R
1 1
3
( )U s è T I R
2 2
3
( )U s , åñëè îíî óäîâëåò-
âîðÿåò ñëåäóþùèì óñëîâèÿì:
�( , )U U
1 2
� 0, åñëè T T
1 1 2 2
( ) ( )U U� ��,
�( , )U U
1 2
� 0, åñëè
int ( ) int ( ) ,
( ) ( ) ,
T T
frT frT
1 1 2 2
1 1 2 2
U U
U U
�
�
��
��
�
�
�
�( , )U U
1 2
� 0, åñëè int ( ) int ( )T T
1 1 2 2
U U� ��.
Ïîíÿòèå èíòåðâàëüíîãî �-îòîáðàæåíèÿ ïîçâîëÿåò ñôîðìóëèðîâàòü
çàäà÷ó ðàçìåùåíèÿ èíòåðâàëüíûõ îáúåêòîâ êàê çàäà÷ó ìàòåìàòè÷åñêîãî
ïðîãðàììèðîâàíèÿ. Óñëîâèåì ðàçìåùåíèÿ èíòåðâàëüíîãî îáúåêòà Pi iU( ),
i J n� , â èíòåðâàëüíîé îáëàñòè P
0 0
( )U åñòü âûïîëíåíèå èíòåðâàëüíîãî
íåðàâåíñòâà
�
0 0i iU U( , ) � 0.
Çäåñü
�
0 0
1 2 6
0 0i i
k
i
k
iU U U U( , ) min { ( , )}
, ,...,
�
�
f , (6)
ãäå
f
0
1
0 0
0 0
i i i a a a aU U X X A v v v v
i i
( , ) ( ) ,�
� �
,
f
0
2
0 0
0 0
i i i a a a aU U X X A v v v v
i i
( , ) ,�
� �
,
f
0
3
0 0
0 0
i i i b b b bU U Y Y v v v v
i i
( , ) ( ) ,�
�
,
f
0
4
0 0
0 0
i i i b b b bU U Y Y B v v v v
i i
( , ) ,�
� �
,
f
0
5
0 0
0 0
i i i c c c cU U Z Z B v v v v
i i
( , ) ( ) ,�
� �
,
f
0
6
0 0
0 0
i i i c c c cU U Z Z C v v v v
i i
( , ) ,�
� �
,
A A Ai�
0
, B B Bi�
0
, C C C i�
0
,
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 39
�
0 0i iU U( , ), i J n� , — èíòåðâàëüíîå �-îòîáðàæåíèå îáúåêòîâ Pi iU( ) è
P
*
0 0
( )U .
Óñëîâèåì íåïåðåñå÷åíèÿ èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ Pi iU( ) è
Pj jU( ) , i J n� , j J n� , i j� , åñòü âûïîëíåíèå èíòåðâàëüíîãî íåðàâåíñòâà
� ij i jU U( , ) � 0.
Çäåñü
� ij i j
k
ij
k
i jU U U U( , ) max { ( , )}
, ,...,
�
�1 2 6
f , (7)
ãäå
f ij i j j i a a a aU U X X A v v v v
i j i j
1
( , ) ,�
�
,
f ij i j j i a a a aU U X X A v v v v
i j i j
2
( , ) ( ) ,�
�
�
,
f ij i j j i b b b bU U Y Y B v v v v
i j i j
3
( , ) ,�
�
�
,
f ij i j j i b b b bU U Y Y B v v v v
i j i j
4
( , ) ( ) ,�
�
�
,
f ij i j j i c c c cU U Z Z C v v v v
i j i j
5
( , ) ,�
�
�
,
f i i j j i c c c cU U Z Z C v v v v
i j i j
6
( , ) ( ) ,�
�
�
,
� � �A A Ai j , � � �B B Bi j , � � �C C Ci j ,
� ij i jU U( , )— èíòåðâàëüíîå�-îòîáðàæåíèå ïàðû îáúåêòîâ Pi iU( )è Pj jU( );
X Xj i
, Y Yj i
, Z Zj i
— êîîðäèíàòû èíòåðâàëüíîãî íàïðàâ-
ëåííîãî ìíîæåñòâà U U Uij j i�
,U X Y Zi i i i� ( , , ), i j� , � �i j J n, .
 ñîîòâåòñòâèè ñ ïîñòàíîâêîé çàäà÷è, íà îñíîâàíèè ãîìåîìîðôèçìà
ïðîñòðàíñòâ I Rs [8] è R 2
, çà èíòåðâàëüíîå öåëåâîå îòîáðàæåíèå ïðèíè-
ìàåì «èíòåðâàëüíóþ âûñîòó» H h vh� , çàíÿòîé ÷àñòè èíòåðâàëüíîãî
ïàðàëëåëåïèïåäà P
0 0
( )U êàê ðåçóëüòàò ðàçìåùåíèÿ â íåì èíòåðâàëüíûõ
ïàðàëëåëåïèïåäîâ Pi iU( ), i J n� . Î÷åâèäíî,
H
j J
j
n
�
�
max ( , )� � �
0
,
ãäå � ( , )� �
0 j — èíòåðâàëüíîå ðàññòîÿíèå [11] ìåæäó èíòåðâàëüíîé ãèïåð-
ïëîñêîñòüþ âèäà �
0 0
6
0
: ( )f 0U � , èíòåðâàëüíî ïàðàëëåëüíîé êîîðäèíàòíîé
ïëîñêîñòüþ X O Y è òîé, êîòîðàÿ ïðèíèìàåò ó÷àñòèå â ôîðìèðîâàíèè
èíòåðâàëüíîé ãðàíèöû frP
0 0
( )U , è èíòåðâàëüíûìè ãèïåðïëîñêîñòÿìè
� j j jU: ( )f 0
5
� , j J n� , ïðèíèìàþùèìè ó÷àñòèå â ôîðìèðîâàíèè frPi iU( ).
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
40 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Íà îñíîâå ââåäåííûõ âûøå ïîíÿòèé è ñîîòíîøåíèé èíòåðâàëüíóþ
ìàòåìàòè÷åñêóþ ìîäåëü îïòèìèçàöèîííîé çàäà÷è óïàêîâêè èíòåðâàëü-
íûõ ïàðàëëåëåïèïåäîâ Pi iU( ), i J n� , â èíòåðâàëüíîé îáëàñòè P
0 0
( )U ïðåä-
ñòàâèì â ñëåäóþùåì âèäå:
íàéòè
inf
( )U H s
n
H
�
�
D I R
3 1
, (8)
ãäå
D
0
0
:
( , ) , ,
( , ) , , , ,
�
�
0 0i i n
ij i j n n
U U i J
U U i J j J i j
� �
� � � �
�
�
�
(9)
U U U U n s
n
� �( , ,..., )
1 2
3
I R, U X Y Zi i i s� �( , , ) I R
3
, i J n� ,
à èíòåðâàëüíûå îòîáðàæåíèÿ �
0 0i iU U( , ) è � ij i jU U( , ) îïðåäåëÿþòñÿ
ñîîòâåòñòâåííî âûðàæåíèÿìè (6) è (7).
Åñëè âñå ïîãðåøíîñòè èñõîäíûõ äàííûõ ïîëîæèòü ðàâíûìè íóëþ, òî
(8), (9) áóäåò ìàòåìàòè÷åñêîé ìîäåëüþ èäåàëèçèðîâàííîé çàäà÷è óïàêîâ-
êè ïàðàëëåëåïèïåäîâ â ïàðàëëåëåïèïåä.
Ìåòîä ðåøåíèÿ. Îñóùåñòâèì ïîãðóæåíèå èíòåðâàëüíîé ìàòåìàòè-
÷åñêîé ìîäåëè (8), (9) â åâêëèäîâî ïðîñòðàíñòâî ñ ïîìîùüþ èíòåðâàëü-
íîãî îòîáðàæåíèÿ âèäà
� :I Rs R�
2
, � ( ) ( ) ( , )X X x vx� �H ,
ãäå H — ãîìåîìîðôèçì [8].  ðåçóëüòàòå ïîëó÷èì âåêòîðíóþ ôóíêöèþ
öåëè � ( ) ( ) ( , )H H h vh� �H è ìíîæåñòâî D Rn
n
�
�
�
H D
3 1
6 2
( ) , êîòîðîå,
èñõîäÿ èç îïåðàöèé è îòíîøåíèÿ ïîðÿäêà â èíòåðâàëüíûõ ïðîñòðàíñòâàõ,
ìîæíî ïðåäñòàâèòü â âèäå ñòðóêòóðû ëèíåéíûõ óðàâíåíèé è íåðàâåíñòâ:
D i
k
i
n
ij
k
i j
i j
n
�
�
�
�
�
!
"
"
�
�
�
�
�
!
"
"
"
�
�
�
�
�
� �
�
# #
0
1 1
� ��
,
!
"
"
"�t 1
6
� , (10)
# ij
j i a a
j i a a
x x a v v
x x a v v
j i
j i
1
0
:
( ) ( ) ,
( ) ( )
� � � �
� � � �
� �
�
�
�
�
�
$
%
&
&
&
0
0
,
( ) ( ) ,v v v vx x a aj i j i
# ij
j i a a
j i a a
x x a v v
x x a v v
i j
i j
2
0
0:
( ) ( ) ,
( ) ( )
� � � �
� � � � ,
( ) ( ) ,v v v vx x a aj i i j
� �
�
�
�
�
�
$
%
&
&
&
0
# ij
j i b b
j i b b
y y b v v
y y b v v
j i
j i
3
0
:
( ) ( ) ,
( ) ( )
� � � �
� � � �
� �
�
�
�
�
�
$
%
&
&
&
0
0
,
( ) ( ) ,v v v vy y b bj i j i
# ij
j i b b
j i b b
y y b v v
y y b v v
i j
j i
4
0
0:
( ) ( ) ,
( ) ( )
� � � �
� � � � ,
( ) ( ) ,v v v vy y b bj i j i
� �
�
�
�
�
�
$
%
&
&
&
0
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 41
# ij
j i c c
j i c c
z z c v v
z z c v v
i j
i j
5
0
:
( ) ( ) ,
( ) ( )
� � � �
� � � �
� �
�
�
�
�
�
$
%
&
&
&
0
0
,
( ) ( ) ,v v v vz z c cj i i j
# ij
j i c c
j i c c
z z c v v
z z c v v
i j
i j
6
0
0:
( ) ( ) ,
( ) ( )
� � � �
� � � � ,
( ) ( ) ,v v v vz z c cj i i j
� �
�
�
�
�
�
$
%
&
&
&
0
#
0
1
0
0
0
0
0
0i
i a a
i a a
x
x x a v v
x x a v v
v
i
i
i
:
( ) ,
( ) ,
(
� �
�
�
v v vx a ai0 0
0) ,�
�
�
�
�
$
%
&
&
&
#
0
2
0
0
0
0
0
0i
i a a
i a a i
x x a v v
x x a v v a
i
i
:
( ) ,
( ) ,
�
�
�
�
�
�
�
�
$
%
&
&
& ( ) ,v v v vx x a ai 0 0 0
0
(11)
#
0
3
0
0
0
0
0
0i
i b b
i b b
y
y y b v v
y y b v v
v
i
i
i
:
( ) ,
( ) ,
(
�
�
v v vy b bi0 0
0) ,�
�
�
�
�
$
%
&
&
&
#
0
4
0
0
0
0
0
0i
i b b
i b b
y y b v v
y y b v v
v
i
i
:
( ) ,
( ) ,
(
�
�
y y b bi
v v v
�
�
�
�
�
$
%
&
&
&
0 0 0
0) ,
#
0
5
0
0
0
0
0
0i
i c c
i c c
z
z z c v v
z z c v v
v
i
i
i
:
( ) ,
( ) ,
(
�
�
v v vz c ci0 0
0) ,�
�
�
�
�
$
%
&
&
&
#
0
6
0
0
0
0
0
0i
i c c
i c c
z
z z c v v
z z c v v
v
i
i
:
( ) ,
( ) ,
(
�
�
i i
v v vz c c
�
�
�
�
�
$
%
&
&
&
0 0
0) ,
ãäå a a ai�
0
, b b bi�
0
, c c ci�
0
, � � �a a ai j , � � �b b bi j , � � �c c ci j . Èñ-
ïîëüçóÿ ñîîòíîøåíèÿ (10), (11), äàëåå âìåñòî çàäà÷è (8), (9) áóäåì ðàñ-
ñìàòðèâàòü äâóõêðèòåðèàëüíóþ îïòèìèçàöèîííóþ çàäà÷ó âèäà
inf ( , )
( , , )U h v D R
h
n h
n
h v
�
�6 2
, (12)
U x v y v z v x v x v y vn x y z x n x n yn n
� ( , , , , , , , , ..., , , , ,
1 1 1 2
1 1 1 2
z v Rn z
n
n
, )�
6
,
ãäå îáëàñòü D îïðåäåëÿåòñÿ âûðàæåíèÿìè (10), (11).
Êàê è â ðàáîòå [12], ðàññìîòðèì ìàòåìàòè÷åñêèå ìîäåëè òàêèõ îäíî-
êðèòåðèàëüíûõ çàäà÷:
h h
U h v D Rn h
n1
6 2
�
�
�
min
( , , )
, (13)
v v
h
U h v D R
h
n h
n
( )
( , , )
min
1
6 2
�
�
�
, (14)
h h
U h v D Rn h
n2
6 2
�
�
�
min
( , , )
*
, (15)
ãäå
D U h v D v vn h h h
*
{( , , ) | }
( )
� � �
1
.
Êàê èçâåñòíî, òî÷êà ìíîæåñòâà D òîãäà è òîëüêî òîãäà ÿâëÿåòñÿ ðåøå-
íèåì äâóõêðèòåðèàëüíîé çàäà÷è (12), êîãäà îíà ÿâëÿåòñÿ åäèíñòâåííûì ñ
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
42 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
òî÷íîñòüþ äî ýêâèâàëåíòíîñòè [13] ðåøåíèåì ñëåäóþùåé îïòèìèçàöèîí-
íîé çàäà÷è:
íàéòè
min
( , , )U h v D R
h
n h
n
v
� �
�6 2
, (16)
ãäå
� � � � �D U h v D h hn h{( , , ) | }, ��h h h[ , ]
1 2
.
 äàííîì èññëåäîâàíèè äëÿ îïòèìèçàöèîííîé çàäà÷è (16) ðàçðàáîòàíà
ñëåäóþùàÿ ñòðàòåãèÿ ðåøåíèÿ.
1. Ðåøàåì çàäà÷ó (13):
à) ãåíåðèðóåì ïîñëåäîâàòåëüíîñòè îáúåêòîâ, êîòîðûå ðàçìåùàþòñÿ
ìîäèôèöèðîâàííûì ìåòîäîì ñóæàþùèõñÿ îêðåñòíîñòåé [5, 14];
á) ñòðîèì íà÷àëüíûå òî÷êè ìåòîäîì îïòèìèçàöèè ïî ãðóïïàì ïåðå-
ìåííûõ [1, 6] ñîãëàñíî ñãåíåðèðîâàííûì ïîñëåäîâàòåëüíîñòÿì;
â) îñóùåñòâëÿåì ïîèñê òî÷åê ëîêàëüíîãî ìèíèìóìà ìåòîäîì âîçìîæ-
íûõ íàïðàâëåíèé (ñì., íàïðèìåð, [14]);
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 43
i ai bi ci i ai bi ci i ai bi ci
0 11,9 10,2
1 1 2 7 21 2 5 4 41 3 2 8
2 4 1 2 22 1 1 4 42 4 1 3
3 2 1 2 23 4 1 2 43 2 2 2
4 3 1 1 24 2 1 3 44 2 1 1
5 5 1 4 25 1 1 1 45 5 3 4
6 4 1 2 26 2 2 1 46 4 3 2
7 1 1 2 27 1 2 4 47 1 1 1
8 4 2 2 28 7 5 3 48 2 2 2
9 5 4 2 29 1 8 2 49 3 4 3
10 2 3 4 30 4 3 4 50 4 3 4
11 3 2 8 31 1 2 7 51 2 5 4
12 4 1 3 32 4 1 2 52 1 1 4
13 2 2 2 33 2 1 2 53 4 1 2
14 2 1 1 34 3 1 1 54 2 1 3
15 5 3 4 35 5 1 4 55 1 1 1
16 4 3 2 36 4 1 2 56 2 2 1
17 1 1 1 37 1 1 2 57 1 2 4
18 2 2 2 38 4 2 2 58 7 5 3
19 3 4 3 39 5 4 2 59 1 8 2
20 4 3 4 40 2 3 4 60 4 3 4
Òàáëèöà 1
2. Ðåøàåì çàäà÷ó (14) àíàëîãè÷íî (13).
3. Íàõîäèì ìíîæåñòâî Ïàðåòî [13] ìåòîäîì ïðÿìîóãîëüíèêîâ.
4. Íàõîäèì ðåøåíèå çàäà÷è (16) ìåòîäîì ïîñëåäîâàòåëüíîé îïòèìèçà-
öèè [12—14].
5. Âûáèðàåì ìèíèìàëüíîå çíà÷åíèå âåêòîðíîé ôóíêöèè öåëè ( , )
*
*h v
h
êàê ïðèáëèæåíèå ê ãëîáàëüíîìó ìèíèìóìó çàäà÷è.
Ðàçðàáîòàííîå ïðîãðàììíîå îáåñïå÷åíèå «Packing interval parallelepi-
peds» (INTPAR) ðåàëèçóåò äàííóþ ñòðàòåãèþ óïàêîâêè èíòåðâàëüíûõ ïà-
ðàëëåëåïèïåäîâ.
Ðàññìîòðèì ïðèìåð ðåøåíèÿ çàäà÷è óïàêîâêè ïàðàëëåëåïèïåäîâ â
ïàðàëëåëåïèïåä ñ ó÷åòîì ïîãðåøíîñòåé ìåòðè÷åñêèõ õàðàêòåðèñòèê äàí-
íûõ ãåîìåòðè÷åñêèõ îáúåêòîâ è ïàðàìåòðîâ èõ ðàçìåùåíèÿ.
Äàíî n �60 ïàðàëëåëåïèïåäîâ ñ ìåòðè÷åñêèìè õàðàêòåðèñòèêàìè
2( )a vi ai
� , 2( )b vi bi
� , 2( )c vi ci
� . Çíà÷åíèÿ ai , bi , ci , i J�
60
0�{ } ïðèâåäåíû
â òàáë. 1. Ïîãðåøíîñòè vai
, vbi
, vci
ïðèíèìàåì ðàâíûìè 1% çíà÷åíèé ñîîò-
âåòñòâóþùèõ ìåòðè÷åñêèõ õàðàêòåðèñòèê, ò. å. v aa ii
�001, , v bb ii
�001, ,
v cc ii
�001, .
Ïóñòü äëÿ ïàðàìåòðîâ ðàçìåùåíèÿ
u v x v y v z v Ri u i x i y i zi i i i
� � � � � �( , , )
3
ïàðàëëåëåïèïåäà P ui i( ), i J�
60
0�{ }, ñïðàâåäëèâû ñîîòíîøåíèÿ
v ax ii
�001, , v by ii
�001, , v cz ii
�001, , i J�
60
0�{ }.
Ïðè ðåøåíèè äâóõêðèòåðèàëüíîé çàäà÷è âûñîòà çàíÿòîé ÷àñòè îáëàñòè
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
44 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Ðèñ. 1. Ðåçóëüòàò ðàçìåùåíèÿ ïàðàëëå-
ëåïèïåäîâ ñ ó÷åòîì ïîãðåøíîñòåé
Ðèñ. 2. Ðåçóëüòàò ðåøåíèÿ èäåàëèçèðî-
âàííîé çàäà÷è
ðàçìåùåíèÿ è ïîãðåøíîñòü âûñîòû ïðèíèìàþò ìèíèìàëüíûå çíà÷åíèÿ,
îïòèìàëüíûå çíà÷åíèÿ ñîñòàâëÿþò h �14 35, , vh �0 12, íà ïåðåñòàíîâêå
'
*
= (21 6 43 38 16 59 20 25 56 19 46 37 10 29 41 3 44 52 58 34 30 15 1 55
27 14 57 60 28 23 39 13 9 51 2 45 40 31 12 47 33 36 8 18 11 50 54 49 53 24
48 32 26 4 22 17 35 7 5 42 ).
Òàêèì îáðàçîì, ïîëó÷åí èíòåðâàë [14,23 14,47], â êîòîðûé ñ ó÷åòîì
ïîãðåøíîñòåé ìåòðè÷åñêèõ õàðàêòåðèñòèê è ïàðàìåòðîâ ðàçìåùåíèÿ ãà-
ðàíòèðîâàííî ïîïàäàåò çíà÷åíèå ôóíêöèè öåëè ïîñòàâëåííîé çàäà÷è.
Íà îñíîâå èçîìîðôèçìà [8] äàííîìó ðåøåíèþ ñîîòâåòñòâóåò òî÷êà
H I R
� �
1
14 23 14 47 14 35 0 24([ , , ]) , , s .
Ñîîòâåòñòâóþùàÿ óïàêîâêà èçîáðàæåíà íà ðèñ. 1. Öåíòðû ( , , )x y zi i i èí-
òåðâàëîâ ( , , )X Y Zi i i ïîëþñîâ ïàðàëëåëåïèïåäîâ Pi , i J n� , ïðèâåäåíû
â òàáë. 2.
Äëÿ àíàëèçà òî÷íîñòè ïîëó÷åííîãî ðåçóëüòàòà íàéäåíû íèæíÿÿ è
âåðõíÿÿ îöåíêè çíà÷åíèÿ ôóíêöèè öåëè ïîñòàâëåííîé çàäà÷è: âåðõíÿÿ
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 45
n x y z n x y z n x y z
21 8,31 3,71 10,79 30 2,19 6,79 14,36 33 4,25 1,64 1,08
6 9,38 8,32 0,56 15 4,24 8,85 3,61 36 2,19 1,65 2,59
43 10,36 3,17 10,78 1 10,40 2,16 2,60 8 5,26 6,26 12,33
38 2,68 7,79 0,56 55 1,67 3,67 6,19 18 3,19 7,79 2,612
16 2,69 7,29 8,74 27 1,651 8,82 0,56 11 9,39 6,78 4,68
59 2,19 8,32 1,59 14 10,36 1,12 10,78 50 6,27 7,32 9,77
20 5,26 7,80 1,57 57 8,31 2,16 9,77 54 3,69 8,83 0,56
25 4,22 1,12 13,35 60 3,71 2,68 9,78 49 5,25 1,13 6,21
56 9,37 6,79 2,11 28 8,32 4,23 6,71 53 5,79 6,29 3,63
19 9,89 2,16 1,07 23 2,19 7,30 10,77 24 9,34 7,31 8,75
46 1,65 4,22 4,16 39 5,76 3,17 13,83 48 9,34 2,68 12,32
37 1,67 6,28 12,81 13 10,35 2,16 9,765 32 3,70 5,249 3,627
10 5,26 3,17 6,21 9 5,27 8,31 0,56 26 9,39 6,26 0,56
29 0,63 8,31 0,56 51 3,69 1,65 3,61 4 5,77 8,85 2,09
41 6,84 2,17 3,66 2 2,69 2,16 11,83 22 2,67 8,82 0,56
3 5,78 5,23 1,08 45 10,40 2,16 3,63 17 1,15 8,31 2,61
44 6,81 7,79 0,56 40 7,81 4,20 0,56 35 10,39 2,15 13,83
52 5,27 8,30 12,33 31 1,14 2,15 13,35 7 3,72 6,80 6,69
58 2,18 1,63 6,68 12 9,32 2,69 8,24 5 6,27 3,19 14,83
34 9,33 7,28 12,81 47 10,42 2,15 5,67 42 2,20 5,24 1,60
Òàáëèöà 2
îöåíêà h�
�14 93, ïîëó÷åíà êàê ðåçóëüòàò ðåøåíèÿ çàäà÷è óïàêîâêè ïàðàë-
ëåëåïèïåäîâ Pi
, i J n� , â ïàðàëëåëåïèïåä P
0
�
, íèæíÿÿ îöåíêà h
�11 38, —
êàê ðåçóëüòàò ðåøåíèÿ çàäà÷è óïàêîâêè ïàðàëëåëåïèïåäîâ Pi
�
, i J n� , â
ïàðàëëåëåïèïåä P
0
, ãäå P
0
�
è Pi
�
, i J n� , — ãåîìåòðè÷åñêèå îáúåêòû åâêëè-
äîâà ïðîñòðàíñòâà, âñå ìåòðè÷åñêèå õàðàêòåðèñòèêè êîòîðûõ óâåëè÷åíû
íà ñîîòâåòñòâóþùèå ïîãðåøíîñòè, à P
0
è Pi
, i J n� — ãåîìåòðè÷åñêèå
îáúåêòû ñ óìåíüøåííûìè íà ïîãðåøíîñòè ìåòðè÷åñêèìè õàðàêòåðèñòè-
êàìè. Äëÿ èäåàëèçèðîâàííîé çàäà÷è h
0
12� . Ðåçóëüòàò óïàêîâêè áåç ó÷åòà
ïîãðåøíîñòåé èçîáðàæåí íà ðèñ. 2.
Äëèíà èíòåðâàëà [14,23 14,47], â êîòîðûé ãàðàíòèðîâàííî ïîïàäàåò
ðåøåíèå ïîñòàâëåííîé çàäà÷è, ðàâíà 2 0 48vh � , . Îíà çíà÷èòåëüíî ìåíüøå
äëèíû èíòåðâàëà
% (
h h
�
�, [ , , ]11 38 14 93 .
Òàêèì îáðàçîì, èñïîëüçîâàíèå ïðè ìîäåëèðîâàíèè çàäà÷è ýëåìåíòîâ
èíòåðâàëüíîãî àíàëèçà ïîçâîëÿåò ïîëó÷èòü áîëåå óçêèé èíòåðâàë, â êîòî-
ðûé ãàðàíòèðîâàííî ïîïàäàåò ðåøåíèå ïîñòàâëåííîé çàäà÷è. Ðåøåíèå
äàííîé çàäà÷è äàåò âîçìîæíîñòü ïî çíà÷åíèÿì è ïîãðåøíîñòÿì âõîäíûõ
äàííûõ ïðîãíîçèðîâàòü çíà÷åíèÿ âûõîäíûõ äàííûõ.
Âûâîäû. Ïðåäëîæåííàÿ ñòðàòåãèÿ ðåøåíèÿ çàäà÷è îñíîâàíà íà êîìáè-
íàöèè òàêèõ ìåòîäîâ îïòèìèçàöèè, êàê ìåòîä îïòèìèçàöèè ïî ãðóïïàì ïåðå-
ìåííûõ, ìåòîä ñóæàþùèõñÿ îêðåñòíîñòåé è ìåòîä âîçìîæíûõ íàïðàâëåíèé.
Ðàçðàáîòàííàÿ ïðîãðàììà óïàêîâêè ïàðàëëåëåïèïåäîâ «Packing inter-
val parallelepipeds», ïðåäíàçíà÷åííàÿ äëÿ àâòîìàòèçàöèè ðåøåíèÿ çàäà÷è
îïòèìàëüíîé óïàêîâêè ïàðàëëåëåïèïåäîâ â ïàðàëëåëåïèïåäå ñ ó÷åòîì
ïîãðåøíîñòåé ìåòðè÷åñêèõ õàðàêòåðèñòèê è ïàðàìåòðîâ ðàçìåùåíèÿ, ìî-
æåò áûòü èñïîëüçîâàíà ïðè ïðîåêòèðîâàíèè êàðò òðåõìåðíîãî ðàñêðîÿ
ïðîìûøëåííûõ ìàòåðèàëîâ, ïðè ñîçäàíèè ìàëîîòõîäíûõ òåõíîëîãèé äëÿ
ïðîãíîçèðîâàíèÿ ðåçóëüòàòîâ óïàêîâêè, ïðè ðåøåíèè çàäà÷ ìèíèìèçàöèè
òðàíñïîðòíûõ ðàñõîäîâ ãðóçîâ è äðóãèõ çàäà÷, ìîäåëèðóåìûõ êàê çàäà÷è
óïàêîâêè ïàðàëëåëåïèïåäîâ ñ ó÷åòîì ïîãðåøíîñòåé.
The interval mathematical model of optimization problem of packing the interval parallelepipeds
is built. Transition is made to the two-criteria problem in Euclidean space. The solution strategy,
based on the use of the optimization on the groups of variables and of modified method of
narrowing environs, is suggested.
1. Ñòîÿí Þ. Ã., ßêîâëåâ Ñ. Â. Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû
ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Êèåâ : Íàóê. äóìêà, 1986. — 267 ñ.
2. Dyckhoff H., Scheithauer G., Terno J. Cutting and Packing //Annotated bibliographies in
Combinatorial Optimization. Ed. M. Dell’Amico, F. Maffioli and S. Martello. — Chichester:
John Wiley & Sons, 1997. — P. 393—412.
3. Fekete S., Guhrer A. Neumann U. van der Veen J., Jan C. Packing a trunk — repeatedly //
3rd Meeting Euro Special Interest Group on Cutting and Packing (ESICUP). Instituto Supe-
rior de Engerharla do Porto. Portugal. March. 16/18. — 2006. — P. 3.
Ë. Ã. Åâñååâà, Î. Â. Ïàíêðàòîâ
46 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
4. Moura A., Oliveira H. A heuristic approach to container loading problem with load bearing
strength considerations // Ibed.—Portugal.March. 16/18. — 2006. — P. 17.
5. Ñòîÿí Þ. Ã., Ñîêîëîâñêèé Â. Ç. Ðåøåíèå íåêîòîðûõ ìíîãîýêñòðåìàëüíûõ çàäà÷
ìåòîäîì ñóæàþùèõñÿ îêðåñòíîñòåé. — Êèåâ : Íàóê. äóìêà, 1980. — 208 ñ.
6. Ñòîÿí Þ. Ã., Ïîíîìàðåíêî Ë. Ä., Ïàíêðàòîâ À. Â., Ëîéêî À. Ô. Ïðîãðàììíàÿ ñèñòåìà
ÊÒÑ àâòîìàòè÷åñêîé êîìïîíîâêè áîêñà ñëîæíîé òåõíè÷åñêîé ñèñòåìû áëî÷íîé êîíñò-
ðóêöèè: Ïðåïð. / ÍÀÍ Óêðàèíû. ÈÏÌàø. — Õàðüêîâ, 1987. — 37 ñ.
7. Kaucher E. Interval analysis in the extended interval space IR // Computing, Supple-
ment. — 1980. — ¹ 2. — P. 33—49.
8. Ñòîÿí Þ. Ã. Ââåäåííÿ â ³íòåðâàëüíó ãåîìåòð³þ: Íàâ÷àëüíèé ïîñ³áíèê. — Õàðê³â :
ÕÍÓÐÅ, 2006. — 98 ñ.
9. Åâñååâà Ë. Ã., Ðîìàíîâà Ò. Å, Øåõîâöîâ Ñ. Á. Èíòåðâàëüíûå íàïðàâëåííûå ìíîæåñòâà
â ìíîãîìåðíûõ èíòåðâàëüíûõ ïðîñòðàíñòâàõ // Èñêóññòâåííûé èíòåëëåêò. — 2005. —
¹ 4. — C. 169—176.
10. Stoyan Yu. G. Ô-function and its basic properties // Äîêë. ÍÀÍ Óêðàèíû. Ñåð. A. — 2001. —
¹ 8. — Ñ. 112—117.
11. Åâñååâà Ë. Ã. Èíòåðâàëüíàÿ ìåòðèêà íà n-ìåðíîì ìíîæåñòâå öåíòðèðîâàííûõ èíòåð-
âàëîâ // ÀÑÓ è ïðèáîðû àâòîìàòèêè. — 2006. — Âûï. 136. — Ñ. 50—56.
12. Ñòîÿí Þ. Ã., Ðîìàíîâà Ò. Å., Ñûñîåâà Þ. Ã. Îïòèìèçàöèîííàÿ çàäà÷à ðàçìåùåíèÿ
ïðàâèëüíûõ èíòåðâàëüíûõ ìíîãîóãîëüíèêîâ // Äîï. ÍÀÍ Óêðà¿íè. — 1998. — ¹ 9. —
Ñ. 114—120.
13. Ïîäèíîâñêèé Â.Â., Íîãèí Â.Ä. Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ
çàäà÷. — Ì. : Íàóêà, 1982. — 256 ñ.
14. ×óãàé À. Ì. Ðåøåíèå çàäà÷è óïàêîâêè êðóãîâ â âûïóêëûé ìíîãîóãîëüíèê ñ ïîìîùüþ
ìîäèôèöèðîâàííîãî ìåòîäà ñóæàþùèõñÿ îêðåñòíîñòåé // Ðàäèîýëåêòðîíèêà è èíôîð-
ìàòèêà. — 2005. — ¹ 1. — Ñ. 58—63.
Ïîñòóïèëà 16.02.08;
ïîñëå äîðàáîòêè 02.09.08
ÅÂÑÅÅÂÀ Ëþäìèëà Ãðèãîðüåâíà, êàíä. ôèç.-ìàò. íàóê, ïðîôåññîð êàô. âûñøåé ìàòåìàòèêè è
ôèçèêè Ïîëòàâñêîãî óíèâåðñèòåòà ïîòðåáèòåëüñêîé êîîïåðàöèè Óêðàèíû.  1975 ã. îêîí÷èëà
Õàðüêîâñêèé ãîñóíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêîå ìîäåëè-
ðîâàíèå, âû÷èñëèòåëüíûå ìåòîäû.
ÏÀÍÊÐÀÒÎÂ Àëåêñàíäð Âèêòîðîâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. Èí-òà ïðîáëåì ìàøè-
íîñòðîåíèÿ èì. À.Í. Ïîäãîðíîãî ÍÀÍ Óêðàèíû.  1983 ã. îêîí÷èë Õàðüêîâñêèé èí-ò ðàäèî-
ýëåêòðîíèêè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå è ìåòîäû
îïòèìàëüíîãî ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ (çàäà÷è ðàçìåùåíèÿ, ðàñêðîÿ, óïàêîâêè è
ïîêðûòèÿ).
Çàäà÷à óïàêîâêè èíòåðâàëüíûõ ïàðàëëåëåïèïåäîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 47
|
| id | nasplib_isofts_kiev_ua-123456789-101604 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T16:12:37Z |
| publishDate | 2008 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Евсеева, Л.Г Панкратов, О.В. 2016-06-05T15:37:31Z 2016-06-05T15:37:31Z 2008 Задача упаковки интервальных параллелепипедов / Л.Г. Евсеева, О.В. Панкратов // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 35-47. — Бібліогр.: 14 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101604 519.859 Построена интервальная математическая модель оптимизационной задачи упаковки интервальных параллелепипедов. Осуществлен переход к двухкритериальной задаче в евклидовом пространстве. Предложена стратегия решения, основанная на использовании метода оптимизации по группам переменных и модифицированного метода сужающихся окрестностей. Побудовано інтервальну математичну модель оптимізаційної задачі упакування інтервальних паралелепіпедів. Здійснено перехід до двохкритеріальної задачі в евклідовому просторі. Запропоновано стратегію розв’язання, яка базується на використанні методу оптимізації за групами змінних і модифікованого методу околів, що звужуються. The interval mathematical model of optimization problem of packing the interval parallelepipeds is built. Transition is made to the two-criteria problem in Euclidean space. The solution strategy, based on the use of the optimization on the groups of variables and of modified method of narrowing environs, is suggested. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Задача упаковки интервальных параллелепипедов Interval Parallelepiped Packing Problem Article published earlier |
| spellingShingle | Задача упаковки интервальных параллелепипедов Евсеева, Л.Г Панкратов, О.В. Математические методы и модели |
| title | Задача упаковки интервальных параллелепипедов |
| title_alt | Interval Parallelepiped Packing Problem |
| title_full | Задача упаковки интервальных параллелепипедов |
| title_fullStr | Задача упаковки интервальных параллелепипедов |
| title_full_unstemmed | Задача упаковки интервальных параллелепипедов |
| title_short | Задача упаковки интервальных параллелепипедов |
| title_sort | задача упаковки интервальных параллелепипедов |
| topic | Математические методы и модели |
| topic_facet | Математические методы и модели |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101604 |
| work_keys_str_mv | AT evseevalg zadačaupakovkiintervalʹnyhparallelepipedov AT pankratovov zadačaupakovkiintervalʹnyhparallelepipedov AT evseevalg intervalparallelepipedpackingproblem AT pankratovov intervalparallelepipedpackingproblem |