Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників

Розглянуто задачу пакування неопуклих багатогранників у контейнер мінімального об'єму. Побудовано точну математичну модель задачі пакування неопуклих багатогранників, для яких можливі неперервні трансляції та повороти. Проаналізовано властивості математичної моделі, на основі яких розроблено ба...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2020
Автори:	Стоян, Ю.Г., Чугай, А.М.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Назва видання:	Кибернетика и системный анализ
Теми:	Системний аналіз
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/190364
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників / Ю.Г. Стоян, А.М. Чугай // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 108–118. — Бібліогр.: 18 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-190364
record_format	dspace
spelling	irk-123456789-1903642023-06-03T16:10:59Z Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників Стоян, Ю.Г. Чугай, А.М. Системний аналіз Розглянуто задачу пакування неопуклих багатогранників у контейнер мінімального об'єму. Побудовано точну математичну модель задачі пакування неопуклих багатогранників, для яких можливі неперервні трансляції та повороти. Проаналізовано властивості математичної моделі, на основі яких розроблено багатоетапний підхід до розв'язання задачі, що дає змогу знайти оптимальний розв'язок, який в загальному випадку не є глобальним мінімумом, але є доведеним локальним мінімумом. Наведено чисельні приклади. Рассматривается задача упаковки невыпуклых многогранников в контейнер минимального объема. Построена точная математическая модель задачи упаковки невыпуклых многогранников, которые допускают непрерывные трансляции и повороты. Анализируются свойства математической модели, на основании которых разработан многоэтапный подход к решению задачи. Такой подход позволяет получить оптимальное решение, которое в общем случае не является глобальным минимумом, но является доказанным локальным минимумом. Приведены численные примеры. The paper considers the problem of packing concave polyhedra into a container of minimal volume. The aim of our investigations is construction of an exact mathematical model of the packing problem of concave polyhedra with continuous translations and rotations. Characteristics of the mathematical model are analyzed and are used as the basid to develop a multistage solution approach to obtain a nearly optimal solution which is not a global minimum solution but a proved local minimum. Numerical examples are given. 2020 Article Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників / Ю.Г. Стоян, А.М. Чугай // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 108–118. — Бібліогр.: 18 назв. — укр. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190364 519.85 uk Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Системний аналіз Системний аналіз
spellingShingle	Системний аналіз Системний аналіз Стоян, Ю.Г. Чугай, А.М. Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників Кибернетика и системный анализ
description	Розглянуто задачу пакування неопуклих багатогранників у контейнер мінімального об'єму. Побудовано точну математичну модель задачі пакування неопуклих багатогранників, для яких можливі неперервні трансляції та повороти. Проаналізовано властивості математичної моделі, на основі яких розроблено багатоетапний підхід до розв'язання задачі, що дає змогу знайти оптимальний розв'язок, який в загальному випадку не є глобальним мінімумом, але є доведеним локальним мінімумом. Наведено чисельні приклади.
format	Article
author	Стоян, Ю.Г. Чугай, А.М.
author_facet	Стоян, Ю.Г. Чугай, А.М.
author_sort	Стоян, Ю.Г.
title	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
title_short	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
title_full	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
title_fullStr	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
title_full_unstemmed	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
title_sort	багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
topic_facet	Системний аналіз
url	http://dspace.nbuv.gov.ua/handle/123456789/190364
citation_txt	Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників / Ю.Г. Стоян, А.М. Чугай // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 108–118. — Бібліогр.: 18 назв. — укр.
series	Кибернетика и системный анализ
work_keys_str_mv	AT stoânûg bagatoetapnijpídhíddorozvâzannâoptimízacíjnoízadačípakuvannâneopuklihbagatogrannikív AT čugajam bagatoetapnijpídhíddorozvâzannâoptimízacíjnoízadačípakuvannâneopuklihbagatogrannikív
first_indexed	2025-07-16T13:11:29Z
last_indexed	2025-07-16T13:11:29Z
_version_	1837809260817285120
fulltext	ÓÄÊ 519.85 Þ.Ã. ÑÒÎßÍ, À.Ì. ×ÓÃÀÉ ÁÀÃÀÒÎÅÒÀÏÍÈÉ Ï²ÄÕ²Ä ÄÎ ÐÎÇÂ’ßÇÀÍÍß ÎÏÒÈÌ²ÇÀÖ²ÉÍÎ¯ ÇÀÄÀ×² ÏÀÊÓÂÀÍÍß ÍÅÎÏÓÊËÈÕ ÁÀÃÀÒÎÃÐÀÍÍÈÊ²Â Àíîòàö³ÿ. Ðîçãëÿíóòî çàäà÷ó ïàêóâàííÿ íåîïóêëèõ áàãàòîãðàííèê³â ó êîíòåé- íåð ì³í³ìàëüíîãî îá’ºìó. Ïîáóäîâàíî òî÷íó ìàòåìàòè÷íó ìîäåëü çàäà÷³ ïàêó- âàííÿ íåîïóêëèõ áàãàòîãðàííèê³â, äëÿ ÿêèõ ìîæëèâ³ íåïåðåðâí³ òðàíñëÿö³¿ òà ïîâîðîòè. Ïðîàíàë³çîâàíî âëàñòèâîñò³ ìàòåìàòè÷íî¿ ìîäåë³, íà îñíîâ³ ÿêèõ ðîçðîáëåíî áàãàòîåòàïíèé ï³äõ³ä äî ðîçâ’ÿçàííÿ çàäà÷³, ùî äàº çìîãó çíàéòè îïòèìàëüíèé ðîçâ’ÿçîê, ÿêèé â çàãàëüíîìó âèïàäêó íå º ãëîáàëüíèì ì³í³ìó- ìîì, àëå º äîâåäåíèì ëîêàëüíèì ì³í³ìóìîì. Íàâåäåíî ÷èñåëüí³ ïðèêëàäè. Êëþ÷îâ³ ñëîâà: ïàêóâàííÿ, íåîïóêë³ íåîð³ºíòîâàí³ áàãàòîãðàííèêè, Ô-ôóíêö³ÿ, íåë³í³éíå ïðîãðàìóâàííÿ. ÂÑÒÓÏ Îïòèì³çàö³éí³ çàäà÷³ ïàêóâàííÿ 3D-îá’ºêò³â º ÷àñòèíîþ òåîð³¿ äîñë³äæåííÿ îïå- ðàö³é ³ ìàþòü øèðîêèé ñïåêòð ïðàêòè÷íèõ çàñòîñóâàíü, íàïðèêëàä äëÿ ðîçâ’ÿ- çàííÿ ñó÷àñíèõ ïðîáëåì á³îëîã³¿, ì³íåðàëîã³¿, ìåäèöèíè, ìàòåð³àëîçíàâñòâà, íà- íîòåõíîëîã³é, ðîáîòîòåõí³êè, â ñèñòåìàõ ðîçï³çíàâàííÿ îáðàç³â, 3D-äðóêó. Àêòóàëüí³ñòü ðîçâ’ÿçàííÿ òàêèõ çàäà÷ ïîëÿãàº â òîìó, ùî âîíè äàþòü çìîãó çàì³íèòè ïîâíîìàñøòàáí³ äîðîã³ åêñïåðèìåíòè êîìï’þòåðíèì ìîäåëþâàííÿì ðåàëüíèõ ïðîöåñ³â ³ ñòðóêòóð ìàòåð³àë³â. Öå ïðèçâîäèòü äî çíà÷íî¿ åêîíîì³¿ ÷àñó ³ ô³íàíñîâèõ ðåñóðñ³â. Íàïðèêëàä, ³ííîâàö³éíèì çàñòîñóâàííÿì çàäà÷ ðîçì³ùåííÿ áàãàòîãðàííèê³â º òðèâèì³ðíå ìîäåëþâàííÿ ì³êðîñòðóêòóð ð³çíèõ ìàòåð³àë³â (ó òîìó ÷èñë³ íàíî- ìàòåð³àë³â). Îñòàíí³ äîñÿãíåííÿ â ö³é ãàëóç³ ïîâ’ÿçàí³ ç ðîçðîáëåííÿì êîìï’þ- òåðíî¿ òåõíîëîã³¿ 3D òîìîãðàô³÷íîãî àíàë³çó ì³íåðàëüíèõ ÷àñòèíîê [1]. Ó ðî- áîò³ [2] îïèñàíî çàñòîñóâàííÿ çàäà÷³ ïàêóâàííÿ áàãàòîãðàííèê³â ó ïîðîøêîâ³é ìåòàëóðã³¿. Òàê³ æ çàäà÷³ çàñòîñîâóþòü äëÿ åôåêòèâíîãî ðîçâ’ÿçàííÿ ïðîáëåìè óòèë³çàö³¿ íåáåçïå÷íèõ â³äõîä³â ³ àâòîìàòèçàö³¿ ïðîöåñó ïàêóâàííÿ òèãë³â ó âè- ðîáíèöòâ³ íàï³âïðîâ³äíèêîâèõ ïëàñòèí. Çàäà÷³ ïàêóâàííÿ 3D-îá’ºêò³â º NP-ñêëàäíèìè, ³, çàçâè÷àé, äëÿ ðîçâ’ÿçàííÿ òàêèõ çàäà÷ âèêîðèñòîâóþòüñÿ ð³çí³ åâðèñòèêè. Â³äîì³ ï³äõîäè äî ðîçâ’ÿçàííÿ òðèâèì³ðíèõ çàäà÷ ïàêóâàííÿ ìîæíà êëàñèô³êóâàòè íà òàê³ ãðóïè: — åâðèñòè÷í³ ìåòîäè (åâðèñòèêè, ùî áàçóþòüñÿ íà ðåëàêñàö³¿ ³íôîðìàö³¿ ïðî ôîðìó îá’ºêò³â [3]; ãåíåòè÷í³ àëãîðèòìè [4]; àëãîðèòìè, îñíîâàí³ íà ³äå¿ ³ì³òàö³éíîãî â³äïàëó [5]; ìóðàøèí³ àëãîðèòìè [6]; àëãîðèòìè, ùî âèêîðèñòîâó- þòü ðîçøèðåíèé ïîøóê çà çðàçêîì [7]); — òðàäèö³éí³ ìåòîäè ë³í³éíîãî òà íåë³í³éíîãî ïðîãðàìóâàííÿ [8]; — êîìá³íîâàí³ ï³äõîäè, ÿê³ âèêîðèñòîâóþòü åâðèñòèêè ³ ìåòîäè ìàòåìàòè÷- íîãî ïðîãðàìóâàííÿ [9]. Ó á³ëüøîñò³ ðîá³ò, ïðèñâÿ÷åíèõ ðîçì³ùåííþ òðèâèì³ðíèõ ò³ë, óíåìîæëèâ- ëåí³ ¿õí³ áåçïåðåðâí³ ïîâîðîòè. Òàê, íàïðèêëàä, ó ðîáîò³ [10] çàñòîñîâóâàëèñÿ ò³ëüêè ïåðåòâîðåííÿ òðàíñëÿö³¿. Ó äîñë³äæåíí³ [11] ðîçãëÿíóòî îðòîãîíàëüí³ ïî- âîðîòè îá’ºêò³â. Ó äîñë³äæåíí³ [12] çàïðîïîíîâàíî àëãîðèòì HAPE3D, ÿêèé óìîæëèâëþº ïîâîðîòè áàãàòîãðàííèê³â íàâêîëî êîæíî¿ êîîðäèíàòíî¿ îñ³ äèñê- ðåòíî íà êóòè, êðàòí³ 45�. 108 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 © Þ.Ã. Ñòîÿí, À.Ì. ×óãàé, 2020 Îñê³ëüêè íàéìåíø äîñë³äæåíèìè º çàäà÷³ ïàêóâàííÿ òðèâèì³ðíèõ ò³ë, ÿê³ ðàçîì ç íåïåðåðâíèìè òðàíñëÿö³ÿìè äîïóñêàþòü ³ íåïåðåðâí³ ïîâîðîòè, òî âèíè- êàº íåîáõ³äí³ñòü â ðîçðîáëåíí³ ìåòîäîëîã³¿ ìàòåìàòè÷íîãî òà êîìï’þòåðíîãî ìî- äåëþâàííÿ ïðîöåñó îïòèì³çàö³¿ ïàêóâàííÿ òàêèõ òðèâèì³ðíèõ îá’ºêò³â. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×² Íåõàé çàäàíî ìíîæèíó íåîïóêëèõ áàãàòîãðàííèê³â Pi , i I n� � { }1 2, , ,� , ³ êîíòåéíåð ó âèãëÿä³ êóáî¿äà � � � � � � � � �{X R w x w l x l3 1 2 1 20 0, , , 0 1 2� � �� x }, äå w1, w2 , l1, l2 , �1 òà � 2 º çì³ííèìè, òîáòî âåêòîð u w w l l� � ( , , , , , )1 2 1 2 1 2� � âèçíà÷àº ðîçì³ðè � . Áàãàòîãðàííèêè Pi º îá’ºäíàí- íÿì îïóêëèõ áàãàòîãðàííèê³â P Pi ik k i � �1 � � , i I n� , à áàãàòîãðàííèêè Pik âèçíà÷à- þòüñÿ âåðøèíàìè pikt � ( , , ),p p p ikt ikt ikt 1 2 3 i I� , k Ki i� � { }1 2, , ,� � , t Tik� � = { }1 2, , ,� � ik . Ðîçì³ùåííÿ áàãàòîãðàííèêà Pi â àðèôìåòè÷íîìó åâêë³äîâîìó ïðîñòîð³ R 3 âèçíà÷àºòüñÿ âåêòîðîì òðàñëÿö³¿ � i i i ix y z� ( , , ) ³ êóòàìè ïîâîðî- òó � � � i i i i� ( , , ), i I� . Îòæå, âåêòîð u x y zi i i i i i i i i� �( , ) ( , , , , , )� � � � âè- çíà÷àº ðîçì³ùåííÿ Pi ó R 3 . Çâ³äñè âåêòîð u u u u Rn n� �( , , , )1 2 6 � âèçíà÷àº ì³ñöå ðîçì³ùåííÿ Pi , i I� , â R 3 ; îòæå, ïîâíèé íàá³ð çì³ííèõ çàäà÷³ áóäå âè- çíà÷àòèñü âåêòîðîì X u u� �( , )� ( , , , , )u u u u Rn m 1 2 � � � , äå m n� �6 6. Íàäàë³ áàãàòîãðàííèê Pi , òðàíñëüîâàíèé íà âåêòîð � i ³ ïîâåðíóòèé íà êóòè � �i i, òà i , ïîçíà÷èìî ÿê P ui i( ), à êîíòåéíåð � ç³ çì³ííèìè ðîçì³ðàìè, ùî çàäàþòüñÿ âåêòî- ðîì u� , ïîçíà÷èìî ÿê � �( )u . Íåõàé Vir , r J i i� � { }1 2, , ,� , º âåðøèíà îïóêëî¿ îáîëîíêè Pi . Îòæå, V u R Vi i i T i ir r ( ) � � � , i I� , r J i� , p u R pikt i i T ikt i( ) � � � , i j I, � , k Ki� , t Tik� , äå Ri — îïåðàòîð ïîâîðîòó. Çàäà÷à. Çíàéòè âåêòîð u R m� , ÿêèé çàáåçïå÷óº ðîçì³ùåííÿ P ui i( ), i I� , áåç âçàºìíèõ ïåðåòèí³â ó êîíòåéíåð³ � �( )u òàêèì ÷èíîì, ùîá îá’ºì H u( )� äîñÿãàâ ì³í³ìàëüíîãî çíà÷åííÿ. ÌÀÒÅÌÀÒÈ×ÍÀ ÌÎÄÅËÜ ÒÀ ¯¯ ÂËÀÑÒÈÂÎÑÒ² Ìàòåìàòè÷íó ìîäåëü ïîñòàâëåíî¿ çàäà÷³, âèêîðèñòîâóþ÷è ìåòîä �-ôóíêö³é [13], ìîæíà çàïèñàòè ó âèãëÿä³ H u H u X W ( ) min ( )� � � � , (1) W X R u um ij i j� � { : ( , )� 0, i j I� � , � �i iu u( , ) 0, i I� , F u( )� 0}, (2) äå H u w w l l( ) ( )( )( )� � � � �2 1 2 1 2 1� � , F u w w l l( ) min , ,� � � � �{ }2 1 2 1 2 1� � , � � �i i io r iu u u u( , ) min ( , )� {� , o O� � { }1 2 6, , ,� , r J i� }, � � � i r i ir i i r i ir i i u u V u w u u w V u 1 1 1 2 2 1( , ) ( ) , ( , ) ( ),� �� 3 2 1 r i ir iu u V u l( , ) ( )� � � , � � � �i r i ir i i r i ir i iu u l V u u u V u4 2 2 5 3 1( , ) ( ), ( , ) ( ) ,� �� 6 2 3 r i ir iu u V u( , ) ( )� � �� . Äî òîãî æ íåð³âí³ñòü �ij i ju u( , ) 0 çàáåçïå÷óº íåïåðåòèíàííÿ Pi ³ Pj , à íå- ð³âí³ñòü �i i ju u( , ) 0 çàáåçïå÷óº çíàõîäæåííÿ Pi ó � �( )u , òîáòî � �i iu u( , ) º �-ôóíêö³ºþ Pi ³ B u R u( ) \ int ( )� �� 3 . Ñë³ä çàçíà÷èòè, ùî �ij i ju u( , ) � � � �min ( , ), ,{ }�ij sp i j i ju u s K p K , äå �ij sp i ju u( , ) — �-ôóíêö³ÿ äëÿ ïàðè îïóê- ëèõ áàãàòîãðàííèê³â [14]. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 109 Ðîçãëÿíåìî äåÿê³ âàæëèâ³ îñîáëèâîñò³ ìàòåìàòè÷íî¿ ìîäåë³ (1), (2), ÿê³ âïëè- âàþòü íà ðîçðîáëåííÿ ìåòîäîëîã³¿ ðîçâ’ÿçàííÿ çàäà÷³. 1. Îáëàñòü W äîïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³ â çàãàëüíîìó âèïàäêó º íåçâ’ÿç- íîþ ìíîæèíîþ, ³ êîæíà ¿¿ êîìïîíåíòà çâ’ÿçíîñò³ º áàãàòîçâ’ÿçíîþ òà ìàº «ÿðóæ- íèé» õàðàêòåð. 2. Íåð³âí³ñòü �i X( ) 0 º ñèñòåìîþ ç íåïåðåðâíî-äèôåðåíö³éîâàíèõ ôóíêö³é. 3. Îñê³ëüêè êîæíà ôóíêö³ÿ �ij X( ) ÿâëÿº ñîáîþ ñèñòåìó ìàêñèì³ííèõ ôóíêö³é, îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â ìîæíà ïðåäñòàâèòè ó âèãëÿä³ îá’ºäíàííÿ ï³äîáëàñòåé, òîáòî W Wq q � �1 � � , äå êîæíà ï³äîáëàñòü Wq âèçíà÷àºòüñÿ ñèñòåìîþ íåð³âíîñòåé ç íåïåðåðâíî-äèôåðåíö³éîâàíèõ ôóíêö³é. Îòæå, çàäà÷ó (1), (2) ìîæíà çâåñòè äî ïîñë³äîâíîñò³ çàäà÷ F X F X qq( ) ( ), , , , � �extr { }1 2 � � , äå F X F Xq X Wq ( ) ( ) � � extr . 4. Êîæíà ï³äçàäà÷à F X F X qq( ) ( ), , , ,* � � extr { }1 2 � � º áàãàòîåêñòðå- ìàëüíîþ çàäà÷åþ íåë³í³éíîãî ïðîãðàìóâàííÿ. 5. Çàäà÷à (1), (2) íàëåæèòü äî êëàñó NP-ñêëàäíèõ. ÇÀÃÀËÜÍÀ ÑÒÐÀÒÅÃ²ß ÁÀÃÀÒÎÅÒÀÏÍÎÃÎ Ï²ÄÕÎÄÓ Äëÿ ñêîðî÷åííÿ âåëèêèõ îá÷èñëþâàëüíèõ òà ÷àñîâèõ âèòðàò çä³éñíèìî äåêîìïî- çèö³þ ðîçâ’ÿçàííÿ çàäà÷³ íà ï³äãîòîâ÷èé åòàï òà åòàï áàãàòîðàçîâîãî çàïóñêó. Íà ï³äãîòîâ÷îìó åòàï³ âèêîíóºòüñÿ ðîçâ’ÿçàííÿ íèçêè äîïîì³æíèõ çàäà÷ íåë³í³éíîãî ïðîãðàìóâàííÿ, ÿê³ äîçâîëÿþòü îòðèìàòè äàí³ äëÿ ïîáóäîâè ïî÷àòêîâèõ òî÷îê îñíîâíî¿ çàäà÷³ (1), (2). Íà åòàï³ áàãàòîðàçîâîãî çàïóñêó â³äáóâàºòüñÿ ïîáóäî- âà ð³çíèõ ïî÷àòêîâèõ äîïóñòèìèõ òî÷îê òà ïîøóê â³äïîâ³äíèõ ¿ì ëîêàëüíèõ ì³í³ìóì³â. Äëÿ ðîçâ’ÿçàííÿ öèõ çàäà÷ âèêîðèñòîâóþòü ñòðàòåã³þ, ÿêà ´ðóíòóºòüñÿ íà ãîìîòåòè÷íèõ ïåðåòâîðåííÿõ òà ïîáóäîâ³ ïåðñïåêòèâíèõ òî÷îê [15, 16]. ßê íàáëèæåííÿ äî ãëîáàëüíîãî ì³í³ìóìó çàäà÷³ îáèðàþòü íàéêðàùèé ëîêàëü- íèé ì³í³ìóì, îòðèìàíèé ó ðåçóëüòàò³ âèêîíàííÿ åòàïó áàãàòîðàçîâîãî çàïóñêó. ÏÎÁÓÄÎÂÀ ÄÎÏÓÑÒÈÌÎ¯ ÏÎ×ÀÒÊÎÂÎ¯ ÒÎ×ÊÈ Äëÿ òîãî ùîá ïîáóäóâàòè äîïóñòèìó ïî÷àòêîâó òî÷êó äëÿ çàäà÷³ (1), (2), ïðî- ïîíóºìî ìåòîä êëàñòåðèçàö³¿, ÿêèé ìàº òàêèé àëãîðèòì. Çàäàí³ áàãàòîãðàííèêè ïîïàðíî ïàêóþòü â êóáî¿äè (êëàñòåðè) ì³í³ìàëüíîãî îá’ºìó. ²ç îòðèìàíî¿ ìíîæèíè êëàñòåð³â ôîðìóþòü ï³äìíîæèíó êëàñòåð³â, ÿêà ïîêðèâàº ìíîæèíó çàäàíèõ áàãàòîãðàííèê³â. Ôîðìóâàííÿ òàêî¿ ï³äìíîæèíè â³äáóâàºòüñÿ çà êðèòåð³ºì ìàêñèìàëüíîãî êîåô³ö³ºíòà çàïîâíåííÿ êëàñòåð³â áàãà- òîãðàííèêàìè. Ó ïîäàëüøîìó ðîçâ’ÿçóþòü çàäà÷ó ïàêóâàííÿ ñôîðìîâàíî¿ ï³ä- ìíîæèíè êëàñòåð³â ó êóáî¿ä ì³í³ìàëüíîãî îá’ºìó. Ïîò³ì äëÿ êîæíîãî áàãàòî- ãðàííèêà çã³äíî ç îòðèìàíèì ðîçì³ùåííÿì êëàñòåð³â âèçíà÷àþòü ïàðàìåòðè ðîçì³ùåííÿ áàãàòîãðàííèê³â (ðèñ. 1). Äëÿ îá÷èñëåííÿ êóò³â ïîâîðîòó êîæíîãî áàãàòîãðàííèêà ðîçâ’ÿçóºòüñÿ çàäà÷à íåë³í³éíîãî ïðîãðàìóâàííÿ. Ðîçãëÿíåìî á³ëüø äåòàëüíî çàïðîïîíîâàíèé ï³äõ³ä. Íåõàé ìíîæèíà áàãàòîãðàí- íèê³â Pi , i I n� , ñêëàäàºòüñÿ ç k ãðóï, êîæíà ç ÿêèõ ì³ñòèòü lk ³äåíòè÷íèõ áàãàòîãðàí- íèê³â. Íà ïåðøîìó åòàï³ êîæåí íåîïóêëèé áàãàòîãðàííèê Pi òà êîæíà éîãî îïóêëà êîìïîíåíòà ïîêðèâàþòüñÿ êóëÿìè S i ì³í³ìàëüíîãî ðàä³óñà ri * òà êóëÿìè S ik ì³í³ìàëüíîãî ðàä³óñà rik * , i I k Kn i� �, . Äëÿ öüîãî ðîçâ’ÿçóþòüñÿ çàäà÷³ íåë³í³éíîãî ïðîãðàìóâàííÿ: r r i Ii r D R i n i i i � � �min , ( , )� 4 , D r R r x x y y zi i i ij i ij i ij i ij� � � � � � � � � � �{( , ) : ( ) ( ) (� 4 2 2 2� � �z j Ti i) , }2 0 . 110 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 Íåõàé ( , )� i ir º òî÷êîþ ëîêàëüíîãî ì³í³ìóìó ö³º¿ çàäà÷³. Ïîëþñ êîæíîãî áàãàòîãðàííèêà Pi òà êîæíî¿ éîãî îïóêëî¿ êîìïîíåíòè çì³ùóºòüñÿ íà âåêòîð � i . Íà äðóãîìó åòàï³ ðîçâ’ÿçóþòü C nn 2 � çàäà÷ ïîïàðíîãî ïàêóâàííÿ Pi , i I n� , ó êóáî¿äè Cij ì³í³ìàëüíîãî îá’ºìó Dij C D u D uij C Ñ u u u W R ij C Cij i j Cij ij ij ( ) min ( ) ( , , ) � � 18 , (3) W u u u R u u u uij i j C ij i j i i Cij ij � � {( , , ) : ( , ) , ( , ) ,18 0 0� � � j j C Cu u F u ij ij ( , ) , ( ) 0 0}, (4) äå i j I n, � , u l l w w h hCij � ( , , , , , )2 1 2 1 2 1 , D u l l w w h hij Ñ Cij ( ) ( )( )( )� � � �2 1 2 1 2 1 , F u l l w w h hCij ( ) min , ,� � � �{ }2 1 2 1 2 1 . Íåð³âí³ñòü �ij i ju u( , ) 0 ãàðàíòóº, ùî int intP Pi j� � �, à íåð³âíîñò³ �i i Cu u ij ( , ) 0 òà � j j Cu u ij ( , ) 0 ãàðàíòóþòü ðîçì³ùåííÿ â³äïîâ³äíî Pi òà Pj ó C uij Cij ( ). Ðåçóëüòàòîì ðîçâ’ÿçàííÿ çàäà÷ âèäó (3), (4) áóäå ìíîæèíà � êëàñòåð³â, ÿêà ñêëàäàºòüñÿ ç C nn 2 � ïàðàëåëåï³ïåä³â. Íà òðåòüîìó åòàï³ ³ç îòðèìàíî¿ ìíîæèíè � êëàñòåð³â íåîáõ³äíî âèîêðåìèòè çà êðèòåð³ºì ìàêñèìàëüíîãî êîåô³ö³ºíòà çàïîâíåííÿ ï³äìíîæèíè ~ K êëàñòåð³â, â ÿê³é ìîæíà ðîçì³ñòèòè âñ³ áàãàòîãðàííèêè Pi , i I n� . Îòæå, êîæåí êëàñòåð Qi ì³ñòèòü ïàðó áàãàòîãðàííèê³â Pki ³ Pti ç ïàðàìåòðàìè ðîçì³ùåííÿ u k Q i ³ u t Q i â³äíîñíî éîãî ëîêàëüíî¿ ñèñòåìè êîîðäèíàò Qi . Äàë³ ðîçâ’ÿçóºìî çàäà÷ó ïàêóâàííÿ ñôîðìîâàíî¿ ï³äìíîæèíè êëàñòåð³â Qi , i M� , ó êóáî¿ä � ì³í³ìàëüíîãî îá’ºìó. Íà îñíîâ³ ð³âíÿíü (1), (2) çàïèøåìî ìàòå- ìàòè÷íó ìîäåëü çàäà÷³ â òàêîìó âèãëÿä³: H u H u u u W R (~ ) min (~ ) (~,~ ) ~� � � � � �6 6� , (5) ~ (~, ~ ) : (~ , ~ ) , ,W u u R u u i j Mij i j� � � ��{ � �6 6 0� � � �i iu u i M F u(~ , ~ ) , , (~ ) � 0 0}, (6) ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 111 Ðèñ. 1. Ïîáóäîâà ïî÷àòêîâî¿ òî÷êè çà ìåòîäîì êëàñòåðèçàö³¿: à — çàäàí³ ôîðìè áàãàòîãðàííèê³â; á — îáðàí³ êëàñòåðè çà êðèòåð³ºì ìàêñèìàëüíîãî êîåô³ö³ºíòó çàïîâíåííÿ; â — ðåçóëüòàò ïàêó- âàííÿ ñôîðìîâàíî¿ ï³äìíîæèíè êëàñòåð³â; ã — äîïóñòèìà ïî÷àòêîâà òî÷êà, ÿêà â³äïîâ³äàº ðîçì³ùåííþ êëàñòåð³â à á ãâ äå ~ ( , , , , , )u l l w w h h� � 2 1 2 1 2 1 , H u l l w w h h(~ ) ( )( )( )� � � � �2 1 2 1 2 1 , F u l l w w h h(~ ) min , ,� � � � �{ }2 1 2 1 2 1 . Íåõàé òî÷êà (~ , ~ )u u R �� 6 6� º íàáëèæåííÿì äî òî÷êè ãëîáàëüíîãî ì³í³ìóìó çàäà÷³ (5), (6). ¯é â³äïîâ³äàº ïàêóâàííÿ êëàñòåð³â Q ui i( ) , i M� , â êóáî¿ä � �( )u , ³ êîæåí êëàñòåð ì³ñòèòü ïàðó áàãàòîãðàííèê³â Pki ³ Pti ç ïàðàìåòðàìè ðîçì³ùåííÿ u k Q i ³ u t Q i â³äíîñíî ëîêàëüíî¿ ñèñòåìè êîîðäèíàò êëàñòåðà Qi . Äëÿ òîãî ùîá ïåðåéòè äî äîïóñòèìî¿ ïî÷àòêîâî¿ òî÷êè ( , )u u W0 0 � � çàäà÷³ (1), (2), íåîáõ³äíî â³äïîâ³äíî äî ðîçì³ùåííÿ êëàñòåð³â Qi , i M� , âèçíà÷èòè ïàðàìåòðè ðîçì³ùåííÿ áàãàòî- ãðàííèê³â Pi , i I n� . Âñòàíîâèìî u u� � 0 � ~ , êîîðäèíàòè ïîëþñ³â áàãàòîãðàííèê³â Pi , i I n� , âèçíà÷èìî çà ôîðìóëîþ � � �i i i Q0 � �~ * . Ùîá âèçíà÷èòè êóòè ïîâîðîòó � i 0 áàãàòî- ãðàííèê³â Pi , i I n� , íåîáõ³äíî ðîçâ’ÿçàòè n çàäà÷ íåë³í³éíîãî ïðîãðàìóâàííÿ âèãëÿäó r ri R D R i i i 13 139 � � min , (7) D R R V R V V R V V R Vi i i i i i i i i i i� � � � � � � �9 1 1 2 2 3 3 : ~ , ~ , ~ , r r r r iij ik i jk ji ki i jk� �� , , , ,1 2 3 , (8) äå i I n� , V i 1 , V i 2 , V i 3 — âåêòîðè âèõ³äíèõ êîîðäèíàò ïåðøèõ òðüîõ âåðøèí áà- ãàòîãðàííèêà Pi ; ~ ~ ( )V R R Vj i i i Q j i i Q� � � , j �1 2 3, , ; Ri — øóêàíà ìàòðèöÿ îáåð- òàíü. Íåõàé Ri — ðîçâ’ÿçîê çàäà÷³ (7), (8). Òîä³ êóòè ïîâîðîòó áàãàòîãðàííè- êà Pi ìîæíà âèçíà÷èòè ÿê � i i r� arcsin 13 , � �i i ir� � arcsin ( / cos ) 23 , �i i ir� � arccos ( / cos )12 . ËÎÊÀËÜÍÀ ÎÏÒÈÌ²ÇÀÖ²ß Ñë³ä çàçíà÷èòè, ùî îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³ (1), (2) îïèñóþòü âå- ëèêîþ ê³ëüê³ñòþ íåë³í³éíèõ íåð³âíîñòåé [17]. Öå âèìàãàº ðîçðîáëåííÿ ìå- òîä³â, ÿê³ äàþòü çìîãó åôåêòèâíî ðîçâ’ÿçóâàòè ïðîáëåìó âåëèêî¿ ðîçì³ðíîñò³ çàäà÷. ²äåÿ ìåòîäó ëîêàëüíî¿ îïòèì³çàö³¿ ´ðóíòóºòüñÿ íà äåêîìïîçèö³¿ îñíîâíî¿ çàäà÷³ íà ï³äçàäà÷³ ç³ çíà÷íî ìåíøîþ ê³ëüê³ñòþ îáìåæåíü òà ìåíøî¿ ðîç- ì³ðíîñò³. Äëÿ öüîãî âèîêðåìëþºìî òàê³ åòàïè: ïîñë³äîâíà ãåíåðàö³ÿ ï³äîáëà- ñòåé îáëàñò³ äîïóñòèìèõ ðîçâ’ÿçê³â, ÿê³ ì³ñòÿòü ïî÷àòêîâó òî÷êó; âèçíà÷åííÿ ï³äñèñòåìè �-àêòèâíèõ îáìåæåíü; ïîøóê çà äîïîìîãîþ ñó÷àñíèõ ðîçâ’ÿçóâà÷³â çàäà÷ íåë³í³éíîãî ïðîãðàìóâàííÿ äðóãîãî ïîðÿäêó ëîêàëüíèõ åêñòðåìóì³â íà îáðàíèõ ï³äîáëàñòÿõ; îðãàí³çàö³ÿ ïåðåõîäó äî ³íøèõ ï³äîáëàñòåé. Ðîçãëÿíåìî á³ëüø äåòàëüíî ðîçðîáëåí³ ìåòîäè. Ìåòîä âíóòð³øíüî¿ òî÷êè ðàçîì ç³ ñòðàòåã³ºþ äåêîìïîçèö³¿. Íåõàé òî÷êà X W� � º ïî÷àòêîâîþ òî÷êîþ. Ïîøóê ëîêàëüíîãî åêñòðåìóìó ïî÷èíàºòüñÿ ç âèä³ëåííÿ ï³äîáëàñò³ W0 òàêî¿, ùî X W W�� 0 . Äëÿ ïîáóäîâè ï³äîáëàñò³ W0 íå- îáõ³äíî ï³äñòàâèòè òî÷êó X � â íåð³âíîñò³, ùî ôîðìóþòü ñèñòåìó âèãëÿäó (2). Îñê³ëüêè Ô-ôóíêö³ÿ ìàº âèãëÿä � � � �� ij i j ij s i j iju u u u s( , ) max ( , ), , ,{ }1 � , òî äîïóñòèìà ï³äîáëàñòü W0 ìàòèìå âèãëÿä ñèñòåìè íåð³âíîñòåé, ÿêà ôîðìóºòüñÿ çà 112 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 ðàõóíîê âèáîðó â êîæí³é Ô-ôóíêö³¿ ��ij i ju u( , ) îäí³º¿ ç ôóíêö³é �ij a i j ij u u( , ), aij ij� �{ }1, ,� , i j I� � , òàêî¿, ùî � � �� ij i j ij a i j iju u u uij( , ) ( , ) � . Àíàëîã³÷íèì ñïîñîáîì âèä³ëÿþòü íåð³âíîñò³ ç � �i iu u( , ) 0, i I� . Ó ðåçóëüòàò³ îòðèìóºìî ñèñòåìó íåð³âíîñòåé � 0 0( )X , ÿêà ³ îïèñóº ï³äîáëàñòü W0 . Ïîò³ì ðîçâ’ÿçóºìî çàäà÷ó F u F u X W R ( ) min ( )� � 0 0 � � ³ îá÷èñëþºìî òî÷êó ëîêàëüíîãî ì³í³ìóìó X 0* äëÿ ïî÷àòêîâî¿ òî÷êè X W� � 0 . Äàë³ â ñèñòåì³ � 0 0 0( )X âèîêðåìëþºìî àê- òèâí³ íåð³âíîñò³ � j j0 0 0( )� , j � � �� 0 01 2 1 2{ } { }, , , , , ,� �� . Íåõàé ö³ íåð³âíîñò³ íàëåæàòü ï³äñèñòåì³ íåð³âíîñòåé �ij a i ju u( , ) 0, i I I� 0 1� , j I I� 0 2� . Öå äàº çìîãó âèáðàòè ôóíêö³¿ � � �ij i ju u( , ), ÿê³ ì³ñòÿòü â ñîá³ ôóíêö³¿ �ij a i ju u( , ), i I� 0 1� , j I� 0 2� , òà îá÷èñëèòè ¿õí³ çíà÷åííÿ â òî÷ö³ X 0* . Íåõàé � � �ij i ju u( , )0 0 �ij c i j iju u( , )0 0 0 � � , i I� 0 1� , j I� 0 2� . ßêùî � ij 0 0� , i I� 0 1� , j I� 0 2� , òî çàì³íþºìî ï³äñèñòåìè �ij a i ju u( , ) 0 íà ï³äñèñòåìè �ij c i ju u( , ) 0, i I� 0 1� , j I� 0 2� . Ó ðåçóëüòàò³ îòðèìóºìî íîâó ï³äñèñòåìó íåð³âíîñòåé, ÿêà âè- çíà÷àº íîâó äîïóñòèìó ï³äîáëàñòü W W1 . Âî÷åâèäü, X W0 1 � . Äëÿ ïî÷àòêîâî¿ òî÷êè X 0 ðîçâ’ÿçóºìî çàäà÷ó F u F u X W R m ( ) min ( )� � 1 1 � � ³ îá÷èñëþºìî òî÷êó ëî- êàëüíîãî ì³í³ìóìó X 1 . Îá÷èñëþâàëüíèé ïðîöåñ ïîâòîðþºìî � ðàç äî òèõ ï³ð, äîêè íå áóäå âèêîíàíî óìîâó F u F u( ) ( )( ) � � � �� 1 . Çìåíøåííÿ ê³ëüêîñò³ îáìåæåíü. Ñèñòåìè íåð³âíîñòåé � � ( )X 0, ùî çàäàþòü ï³äîáëàñò³ W� , � ��{ }0, ,� , òàêîæ ñêëàäàþòüñÿ ç âåëèêî¿ ê³ëüêîñò³ íåð³â- íîñòåé. Âî÷åâèäü, ùî äëÿ åôåêòèâíîãî ðîçâ’ÿçàííÿ çàäà÷ ïàêóâàííÿ íåîáõ³äíå ñóòòºâå çìåíøåííÿ ê³ëüêîñò³ îáìåæåíü. Äëÿ öüîãî ó ñòàòò³ çàïðîïîíîâàíî ñïåö³àëüíèé ìåòîä äåêîìïîçèö³¿, ñóòü ÿêîãî ïîëÿãàº ó çâåäåíí³ ðîçâ’ÿçàííÿ çà- äà÷ âèãëÿäó (1), (2) äî ðîçâ’ÿçàííÿ ïîñë³äîâíîñò³ îïòèì³çàö³éíèõ ï³äçàäà÷. Äëÿ êîæíî¿ òàêî¿ ï³äçàäà÷³ ââîäèòüñÿ äîäàòêîâà ñèñòåìà îáìåæåíü íà çì³íí³, ùî äîç- âîëÿº íà êîæíîìó åòàï³ ïîøóêó ëîêàëüíîãî åêñòðåìóìó ðîçãëÿäàòè ëèøå äåÿê³ îáìåæåííÿ ç³ âñ³º¿ ñèñòåìè � � ( )X 0. Ïåðåâàãà öüîãî ï³äõîäó ïîëÿãàº â ³ñòîò- íîìó ñêîðî÷åíí³ ê³ëüêîñò³ îáìåæåíü, ÿê³ çàäàþòü äîïóñòèì³ îáëàñò³ ï³äçàäà÷. Ðîçãëÿíåìî äåòàëüí³øå îïèñàíèé ìåòîä äåêîìïîçèö³¿. Ïåðø çà âñå, çàäàìî âåëè÷èíó � � 0 ³ ñåðåä íåð³âíîñòåé �ij i ju u( , ) 0, i j I� � , òà � �i iu u( , ) 0 âèîêðåìèìî íåð³âíîñò³ �ij i ju u( , ) 0 òàê³, ùî \| \| \| \| ( )( ) ( )� � �� i j i jr r� � � � � �1 1 0 0 , i j I� � , (9) ³ íåð³âíîñò³ � �i iu u( , ) 0 òàê³, ùî âèêîíàíà õî÷à á îäíà ç óìîâ x r l y r wi i i i ( ) ( ) ( ) ( ),� � � �� 1 0 1 1 1 0 1 1 , z r h l x ri i i i ( )* ( )* ( )* ( ),� � � �� 1 0 1 1 2 1 1 0 , (10) w y r h z r ii i i i2 1 1 0 2 1 1 0( ) ( )* ( )* ( )*, ,� � � �� I . Âèîêðåìèìî ç ñèñòåìè � � ( )X 0 íåð³âíîñò³ âèãëÿäó � t t� �( ) 0, ÿê³ º ÷àñ- òèíàìè íåð³âíîñòåé � �ij i ju u( , ) 0, i j I� � , ³ � �i iu u( , ) 0, i I� . Ö³ íåð³âíîñò³ ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 113 ôîðìóþòü ï³äñèñòåìó � � 0 0( )X , ùî ñêëàäàºòüñÿ ç t �0 íåð³âíîñòåé ³ âèçíà÷àº ï³äìíîæèíó W W� �0 . Âî÷åâèäü, � � �0 1 0( )( )X � òà t � �� 0 � . Ï³äñèñòåìà � � 0 0( )X îïèñóº ï³äìíîæèíó òî÷îê X W R m� � 0 0� . Äëÿ ïî÷àòêîâî¿ òî÷êè X W( )� � � �1 0 0 ðîçâ’ÿæåìî çàäà÷ó F u F u X W R ( ) min ( )� � � � � 0 0 0 � � , (11) W X R X i Im i i� � � � �� 0 0 0 0 10 1 2 0� � � � �� : ( ) , \| \| \| \| ,( ) � � � � . (12) Äàë³ äëÿ òî÷êè X � 0 áóäóºìî íîâó ñèñòåìó íåð³âíîñòåé � �1 0( )X . Ç óðà- õóâàííÿì ö³º¿ òî÷êè ñôîðìóºìî òî÷êó X W� � 1 1� ÿê ïî÷àòêîâó ³ áóäåìî ðîçâ’ÿ- çóâàòè çàäà÷ó F u F u X W R m ( ) min ( )� � � � � 1 1 1 � � . Îòæå, ðîçâ’ÿçóºòüñÿ ïîñë³äîâí³ñòü ï³äçàäà÷ F u F uk X W Rk k m ( ) min ( )� � � � � � � , k �1 2 3, , , äî òèõ ï³ð, äîêè íå áóäå âèêîíà- íà óìîâà F u F uk k( ) ( )( ) � � � �� 1 . Ëåãêî áà÷èòè, ùî ÷èì ìåíøà âåëè÷èíà �, òèì ìåíøà ê³ëüê³ñòü íåð³âíîñòåé, ÿê³ çàäàþòü W k� , ³ òèì á³ëüøó ê³ëüê³ñòü k ï³äçàäà÷ íåîáõ³äíî ðîçâ’ÿçàòè, ùîá çíàé- òè òî÷êó ëîêàëüíîãî ì³í³ìóìó. Ç ³íøîãî áîêó, ÷èì á³ëüøà �, òèì á³ëüøå íåð³âíîñ- òåé ì³ñòèòü ñèñòåìà, ÿêà çàäàº W k� , ³ ïîòð³áíî âèòðàòèòè á³ëüøå ÷àñó äëÿ ðîçâ’ÿ- çàííÿ ï³äçàäà÷. ßê ïîêàçàëè ÷èñåëüí³ åêñïåðèìåíòè, çíà÷åííÿ âåëè÷èíè � ìîæíà îáðàòè ð³âíèì ñåðåäíüîìó ðàä³óñó êóëü, ùî ïîêðèâàþòü áàãàòîãðàííèêè. Çàçíà÷èìî, ùî ïîøóê ëîêàëüíîãî ì³í³ìóìó çàäà÷³ (1), (2) ìîæå áóòè ðîçä³ëåíèé íà äâà åòàïè: åòàï îïòèì³çàö³¿ ç ñèñòåìîþ ë³í³éíèõ îáìåæåíü òà åòàï íåë³í³éíîãî ïðîãðàìóâàííÿ. Åòàï îïòèì³çàö³¿ ìîæíà ðåàë³çóâàòè çà ðàõóíîê ô³êñàö³¿ êóò³â ïîâîðîòó � i 0 � const áàãàòîãðàííèê³â Pi , i I n� , ó ïî÷àòêîâ³é òî÷ö³ ( , )u u W0 0 � � . Ô³êñàö³ÿ êóò³â ïîâîðîòó äîçâîëÿº çíà÷íî ñêîðîòèòè ðîçì³ðí³ñòü çà- äà÷³ (1), (2), ïåðåéòè äî ë³í³éíèõ îáìåæåíü, ÿê³ ôîðìóþòü îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â W, òà ìîäèô³êóâàòè àëãîðèòì äåêîìïîçèö³¿ ç ìåòîþ çìåíøåííÿ ê³ëüêîñò³ îáìåæåíü. Öå äîçâîëÿº çíà÷íî ñêîðîòèòè îá÷èñëþâàëüí³ âèòðàòè òà øâèäøå çíàéòè íàáëèæåííÿ äî ëîêàëüíîãî ì³í³ìóìó. Íà öüîìó åòàï³ ìàòåìàòè÷íà ìîäåëü çàäà÷³ ìàòèìå âèãëÿä H u H u X W ( ) min ( )� � � � , W X u R i j I u in ij i j i i� � � � � �{ ( , ) : ( , ) , , ( , ) ,� � � �� 3 6 0 0 � I F u, ( )� 0}. Îñê³ëüêè êóòè ïîâîðîòó ô³êñóþòüñÿ, òî ñèñòåìè íåð³âíîñòåé W k� (12) º ë³í³éíèìè. ÎÁ×ÈÑËÞÂÀËÜÍ² ÅÊÑÏÅÐÈÌÅÍÒÈ Åêñïåðèìåíòè ïðîâîäèëèñü çà äîïîìîãîþ ïðîãðàìíîãî çàáåçïå÷åííÿ, ðîçðîá- ëåíîãî ìîâîþ C#. Ïðîãðàìíå çàáåçïå÷åííÿ ðîçðîáëåíî çà ïðèíöèïîì ìîäóëü- íîñò³ ³ ñêëàäàºòüñÿ ç òàêèõ ìîäóë³â: ââåäåííÿ ïî÷àòêîâèõ äàíèõ; îá÷èñëåííÿ Ô-ôóíêö³é; ôîðìóâàííÿ ï³äçàäà÷; ôîðìóâàííÿ ïî÷àòêîâèõ òî÷îê; ëîêàëüíà îïòèì³çàö³ÿ; ãëîáàëüíà îïòèì³çàö³ÿ. Ìîäóëüí³ñòü ïðîãðàìíîãî çàáåçïå÷åííÿ äàëà çìîãó âèêîíàòè äåêîìïîçèö³þ àëãîðèòìó òà çàñòîñóâàòè òåõíîëîã³¿ ïàðà- ëåëüíèõ îá÷èñëåíü, ùî çóìîâèëî ñêîðî÷åííÿ ÷àñó ðîçâ’ÿçàííÿ çàäà÷. Äëÿ ïî- øóêó ëîêàëüíèõ åêñòðåìóì³â âèêîðèñòàíî ñó÷àñíèé ðîçâ’ÿçóâà÷ çàäà÷ íå- 114 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 ë³í³éíîãî ïðîãðàìóâàííÿ ó âèãëÿä³ áåçêîøòîâíî¿ á³áë³îòåêè IPOPT v.3.9.1 (Interior Point OPTimizer) [18]. Ñë³ä çàçíà÷èòè, ùî åôåêòèâí³ñòü á³áë³îòåêè IPOPT çóìîâëåíà âèêîðèñòàííÿì ìåòîäó âíóòð³øí³õ òî÷îê. Ïàðàìåòðàìè êîì- ï’þòåðà, íà ÿêîìó ïðîâîäèëèñü îá÷èñëþâàëüí³ åêñïåðèìåíòè, º ïðîöåñîð Intel Ñore I5-750, 2,5 GHz, 6 Gb îïåðàòèâíî¿ ïàì’ÿò³. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 115 Ðèñ. 4. Ïàêóâàííÿ 36 áàãàòîãðàííèê³â: à — ìåòîä HAPE3D (îá’ºì 12480, ÷àñ — 9637 ñ); á — ðîç- ðîáëåíèé ï³äõ³ä (îá’ºì 10720, ÷àñ — 4789 ñ) à á Ðèñ. 2. Ïàêóâàííÿ 20 áàãàòîãðàííèê³â: à — ìåòîä HAPE3D (îá’ºì 32550, ÷àñ — 26202 ñ); á — ðîç- ðîáëåíèé ï³äõ³ä (îá’ºì 28500, ÷àñ — 6656 ñ) à á Ðèñ. 3. Ïàêóâàííÿ 30 áàãàòîãðàííèê³â: à — ìåòîä HAPE3D (îá’ºì 48300, ÷àñ — 53741 ñ); á — ðîç- ðîáëåíèé ï³äõ³ä (îá’ºì 42450, ÷àñ — 9543 ñ) à á Äëÿ ïåðåâ³ðêè åôåêòèâíîñò³ ðîçðîáëåíîãî ï³äõîäó áóëî ðîçâ’ÿçàíî íèçêó íà- âåäåíèõ ó ðîáîò³ [12] òåñòîâèõ ïðèêëàä³â çà äîïîìîãîþ ìåòîäó HAPE3D. Ðåçóëü- òàòè ïàêóâàííÿ áàãàòîãðàííèê³â ïðåäñòàâëåíî íà ðèñ. 2–5. ßê âèäíî çà íàâåäåíèõ ðèñóíê³â, â óñ³õ òåñòîâèõ ïðèêëàäàõ îòðèìàíî ïîêðà- ùåííÿ ÿê çà ðåçóëüòàòîì, òàê ³ çà ÷àñîì ðîçâ’ÿçàííÿ. Îòæå, ïðîâåäåí³ îá÷èñëþâàëüí³ åêñïåðèìåíòè ï³äòâåðäæóþòü åôåêòèâí³ñòü òà äîñòîâ³ðí³ñòü ðîçðîáëåíèõ ìåòîä³â. Çàäà÷ó ïàêóâàííÿ áóëî ðîçâ’ÿçàíî äëÿ ìíîæèíè ³ç 150 òà ³ç 200 áàãàòîãðàí- íèõ ò³ë, ôîðìà ÿêèõ çîáðàæåíà íà ðèñ. 6. Â³äïîâ³äí³ ðåçóëüòàòè çîáðàæåíî íà ðèñ. 7. ×àñ ðîçâ’ÿçàííÿ çàäà÷ ñêëàâ 32 òà 41 ãîäèíó â³äïîâ³äíî. 116 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 Ðèñ. 5. Ïàêóâàííÿ 40 áàãàòîãðàííèê³â: à — ìåòîä HAPE3D (îá’ºì 6150, ÷àñ — 99952 ñ); á — ðîç- ðîáëåíèé ï³äõ³ä (îá’ºì 56012, ÷àñ — 24543 ñ) áà Ðèñ. 6. Ôîðìè áàãàòîãðàííèõ ò³ë Ðèñ. 7. Ïàêóâàííÿ íåîïóêëèõ áàãàòîãðàííèõ ò³ë: 150 áàãàòîãðàííèõ ò³ë (à); 200 áàãàòîãðàííèõ ò³ë (á) áà ÂÈÑÍÎÂÊÈ Ó ðîáîò³ ïîáóäîâàíî òî÷íó ìàòåìàòè÷íó ìîäåëü çàäà÷³ îïòèìàëüíîãî ïàêóâàííÿ íåîïóêëèõ íåîð³ºíòîâàíèõ áàãàòîãðàííèê³â. Çàñòîñîâàíèé ìåòîä Ô-ôóíêö³é äàº çìîãó âèêîðèñòîâóâàòè ñó÷àñí³ ìåòîäè íåë³í³éíîãî ïðîãðàìóâàííÿ íà âñ³õ åòà- ïàõ ðîçâ’ÿçàííÿ çàäà÷³ (1), (2), ó òîìó ÷èñë³ ïîáóäîâó ïî÷àòêîâèõ òî÷îê, îá÷èñ- ëåííÿ ëîêàëüíèõ ì³í³ìóì³â òà ïîøóê «íàáëèæåíü» äî ãëîáàëüíîãî ì³í³ìóìó. Çàâäÿêè ìåòîäó êëàñòåðèçàö³¿ íåîïóêëèõ íåîð³ºíòîâàíèõ áàãàòîãðàííèõ òðè- âèì³ðíèõ ò³ë ïîáóäîâà ïî÷àòêîâèõ òî÷îê çâîäèòüñÿ äî ðîçâ’ÿçàííÿ çàäà÷³ ïàêóâàííÿ âäâ³÷³ ìåíøî¿ ê³ëüêîñò³ îïóêëèõ ò³ë çíà÷íî ïðîñò³øî¿ ïðîñòîðîâî¿ ôîðìè. Îòæå, çíà÷íî ñêîðî÷åíî ÷àñ ïîáóäîâè ïî÷àòêîâèõ òî÷îê. Ñë³ä çàçíà÷èòè, ùî çìåíøåííþ îá÷èñëþâàëüíèõ âèòðàò ñïðèÿº òå, ùî ïîøóê ëîêàëüíîãî åêñòðåìóìó çàäà÷³ ðîçáè- âàºòüñÿ íà äâà ï³äåòàïè: åòàï ðîçâ’ÿçàííÿ ë³í³éíî¿ çàäà÷³ çà ðàõóíîê ô³êñàö³é êóò³â ïîâîðîòó òà åòàï ðîçâ’ÿçàííÿ çàäà÷³ íåë³í³éíîãî ïðîãðàìóâàííÿ (1), (2). ²òåðàö³éí³ ïðîöåñè, ÿê³ âèêîðèñòîâóþòüñÿ äëÿ ðîçâ’ÿçàííÿ çàäà÷³, ìîæóòü áóòè ëåãêî ðîçïàðàëåëåí³. Íàâåäåí³ ðåçóëüòàòè ïîêàçàëè åôåêòèâí³ñòü çàïðîïî- íîâàíîãî ï³äõîäó äî ðîçâ’ÿçàííÿ çàäà÷³. ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ 1. Wang Y., Lin C.L., Miller J.D. 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Technology. 2016. Vol. 301. P. 160–168. 2. Korte A.C.J., Brouwers H.J.H. Random packing of digitized particles. Powder Technology. 2013. Vol. 233. P. 319–324. 3. Li S.X., Zhao J., Lu P., Xie Y. Maximum packing densities of basic 3D objects. China Science Bulletin. 2010. Vol. 55, Iss. 2. P. 114–119. 4. Karabulut K., �nceo � glu M. A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. In: Advances in Information Systems. ADVIS 2004. Lecture Notes in Computer Science. T. Yakhno (Eds.). 2004. Vol. 3261. Berlin; Heidelberg: Springer, 2004. P. 441–450. 5. Pei Cao, Zhaoyan Fan, Robert Gao, Jiong Tang. A multi-objective simulated annealing approach towards 3D packing problems with strong constraints. ASME 2015. International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. Vol. 2A. Paper No DETC2015-47670, V02AT03A052; 12 p. https://doi.org/10.1115/DETC2015-47670. 6. Guangqiang Li, Fengqiang Zhao, Rubo Zhang, Jialu Du, Chen Guo, Yiran Zhou. A parallel particle bee colony algorithm approach to layout optimization. Journal of Computational and Theoretical Nanoscience. 2016. Vol. 13, N 7. P. 4151–4157. 7. Torczon V., Trosset M. From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Science and Statistics. 1998. Vol. 29. P. 396–401. 8. Birgin E.G., Lobato R.D., Mart³nez J.M. Packing ellipsoids by nonlinear optimization. Journal of Global Optimization. 2016. Vol. 65. P. 709–743. 9. Fasano G.A. Global optimization point of view for non-standard packing problems. Journal of Global Optimization. 2013. Vol. 55. P. 279–299. 10. Stoyan Y.G., Semkin V.V., Chugay A.M. Optimization of 3D objects layout into a multiply connected domain with account for shortest distances. Cybernetics and Systems Analysis. 2014. Vol. 50, N 3. P. 374–385. 11. Grebennik I.V., Pankratov A.V., Chugay A.M., Baranov A.V. Packing n-dimensional parallele- pipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallele- piped. Cybernetics and Systems Analysis. 2010. Vol. 46, N 5. P. 393–802. 12. Liu X., Liu J., Cao A. HAPE3D-a new constructive algorithm for the 3D irregular packing problem. Frontiers Inf. Technol. Electronic Eng. 2015. Vol. 16. P. 380–390. 13. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. Theory and Application. 2010. Vol. 43, Iss. 5. P. 535–553. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 117 14. Stoyan Y., Chugay À. Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 837–845. 15. Stoyan Y.G., Chugay A.M. Packing different cuboids with rotations and spheres into a cuboid. In: Advances in Decision Sciences, 2014. URL: https://www.hindawi.com/journals/ads/2014/571743. 16. Stoyan Y.G., Semkin V.V., Chugay A.M. Modeling close packing of 3D objects. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 296–304. 17. Stoian Y.E., Chugay A.M., Pankratov A.V., Romanova T.E. Two approaches to modeling and solving the packing problem for convex polytopes. Cybernetics and Systems Analysis. 2018. Vol. 54, N 4. P. 585–593. 18. Wachter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. Vol. 106, Iss. 1. P. 25–57. Íàä³éøëà äî ðåäàêö³¿ 18.03.2019 Þ.Ã. Ñòîÿí, À.Ì. ×óãàé ÌÍÎÃÎÝÒÀÏÍÛÉ ÏÎÄÕÎÄ Ê ÐÅØÅÍÈÞ ÎÏÒÈÌÈÇÀÖÈÎÍÍÎÉ ÇÀÄÀ×È ÓÏÀÊÎÂÊÈ ÍÅÂÛÏÓÊËÛÕ ÌÍÎÃÎÃÐÀÍÍÈÊÎÂ Àííîòàöèÿ. Ðàññìàòðèâàåòñÿ çàäà÷à óïàêîâêè íåâûïóêëûõ ìíîãîãðàííèêîâ â êîíòåéíåð ìèíèìàëüíîãî îáúåìà. Ïîñòðîåíà òî÷íàÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è óïàêîâêè íåâûïóêëûõ ìíîãîãðàííèêîâ, êîòîðûå äîïóñêàþò íåïðåðûâ- íûå òðàíñëÿöèè è ïîâîðîòû. Àíàëèçèðóþòñÿ ñâîéñòâà ìàòåìàòè÷åñêîé ìîäå- ëè, íà îñíîâàíèè êîòîðûõ ðàçðàáîòàí ìíîãîýòàïíûé ïîäõîä ê ðåøåíèþ çàäà- ÷è. Òàêîé ïîäõîä ïîçâîëÿåò ïîëó÷èòü îïòèìàëüíîå ðåøåíèå, êîòîðîå â îá- ùåì ñëó÷àå íå ÿâëÿåòñÿ ãëîáàëüíûì ìèíèìóìîì, íî ÿâëÿåòñÿ äîêàçàííûì ëîêàëüíûì ìèíèìóìîì. Ïðèâåäåíû ÷èñëåííûå ïðèìåðû. Êëþ÷åâûå ñëîâà: óïàêîâêà, íåâûïóêëûå íåîðèåíòèðîâàííûå ìíîãîðàííèêè, Ô-ôóíêöèÿ, íåëèíåéíîå ïðîãðàììèðîâàíèå. Y.G. Stoyan, A.M. Chugay MULTISTAGE APPROACH TO SOLVING THE OPTIMIZATION PACKING PROBLEM FOR CONCAVE POLYHEDRA Abstract. The paper considers the problem of packing concave polyhedra into a container of minimal volume. The aim of our investigations is construction of an exact mathematical model of the packing problem of concave polyhedra with continuous translations and rotations. Characteristics of the mathematical model are analyzed and are used as the basid to develop a multistage solution approach to obtain a nearly optimal solution which is not a global minimum solution but a proved local minimum. Numerical examples are given. Keywords: packing, concave polytopes, Ô-function, nonlinear optimization. Ñòîÿí Þð³é Ãðèãîðîâè÷, ÷ë.-êîð. ÍÀÍ Óêðà¿íè, äîêòîð òåõí. íàóê, ïðîôåñîð, çàâ³äóâà÷ â³ää³ëó ²íñòèòóòó ïðîáëåì ìàøèíî- áóäóâàííÿ ³ì. À.Ì. Ï³äãîðíîãî ÍÀÍ Óêðà¿íè, Õàðê³â, e-mail: stoyan@ipmach.kharkov.ua. ×óãàé Àíäð³é Ìèõàéëîâè÷, äîêòîð òåõí. íàóê, ñòàðøèé íàóêîâèé ñï³âðîá³òíèê ²íñòèòóòó ïðîáëåì ìàøèíîáóäóâàííÿ ³ì. À.Ì. Ï³äãîðíîãî ÍÀÍ Óêðà¿íè, Õàðê³â, e-mail: chugay.andrey80@gmail.com. 118 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2

Багатоетапний підхід до розв’язання оптимізаційної задачі пакування неопуклих багатогранників

Репозитарії

Схожі ресурси