DOI: https://doi.org/10.20998/2522-9052.2018.1.03

Кластерна упаковка неопуклих неорієнтованих багатогранників у кубоід

Andriy Chugay, Yurii Stoian

Анотація


Предметом вивчення у статті є розв’язання задачі оптимальної упаковки неопуклих багатогранників у прямий паралелепіпед мінімального об’єму. Метою є побудова математичної моделі даної задачі і розробка методу розв’язання. Задачі: розробити засоби математичного моделювання взаємодії двох неопуклих неорієнтованих багатогранників; побудувати математичну модель задачі упакування неопуклих неорієнтованих багатогранників в кубоід мінімального об’єму; дослідити особливості математичної моделі; розробити ефективний метод розв’язання і виконати його програмну реалізацію. Використовуваними методами є: метод phi-функцій, метод внутрішньої точки. Отримані наступні результати. Використовуючи phi-функцію для двох опуклих неорієнтованих багатогранників, побудована phi-функція для двох неопуклих неорієнтованих багатогранників. На основі цієї phi-функції побудована точна математична модель задачі упаковки неопуклих багатогранників, що допускають одночасно безперервні трансляції та повороти. Математична модель представлена у вигляді задачі нелінійного програмування. Проаналізовано властивості побудованої математичної моделі і на їх основі запропонований багатоетапний підхід, що дозволяє отримати гарний локально оптимальний розв’язок поставленої задачі. Оскільки при роботі з багатогранниками важливою задачею є визначення оптимальної кластеризації двох об'єктів, то одним з етапів запропонованого підходу є розв’язання задачі попарної кластеризації багатогранників. Наводиться чисельний приклад, який демонструє ефективність запропонованого підходу. Висновки. Наукова новизна отриманих результатів полягає в наступному: побудована точна математична модель задачі упаковки неопуклих неорієнтованих багатогранників у вигляді задачі нелінійної оптимізації та запропонований багатоетапний підхід, що дозволяє отримати гарне локально оптимальний розв’язок поставленої задачі.


Ключові слова


кластерна упаковка; неопуклі багатогранники; безперервне обертання; нелінійна оптимізація

Повний текст:

PDF

Посилання


Chugay, A.M., Pankratov, A.V., Romanova, Т.Е. and Stoian, Yu.E. (2017) “Optimization of the process of 3D-printing for SLS technologies of additive production”, Systems of control, navigation and communication, No. 6(46), pp. 127-130.

Wang, Y., Lin, C.L., Miller, J.D. (2016) “3D image segmentation for analysis of multisize particles in a packed particle bed”, Powder Technology. No. 301, pp. 160–168.

Stoyan, Y.G., Romanova, T., Pankratov, A. and Chugay, A. (2015) “Optimized object packings using quasi-phi-functions”, Springer Optimization and Its Applications, Vol. 105, pp. 265-293.

Liu, X., Liu, J. and Cao, A. (2015), “HAPE3D-a new constructive algorithm for the 3D irregular packing problem”, Frontiers Inf Technol Electronic Eng., No. 16., pp. 380-390.

Romanova, T., Bennell, J., Stoyan, Y. and Pankratov, A. (2018) “Packing of concave polyhedra with continuous rotations using nonlinear optimisation”, European Journal of Operational Research, No. 268 (1), pp. 37-53.

Pankratov, A.V. Romanova, T.E. and Chugay, A.M. (2015), “Optimal packing of convex polytopes using quasi-phi-functions, Problems of mechanical engineering, No. 18 (2), pp. 55-65.

Stoyan, Y.G. and Chugay, A.M. (2012), “Mathematical modeling of the interaction of non-oriented convex polytopes”, Cybernetics and Systems Analysis, No. 48 (6). pp. 837-845.

Grebennik, I.V, Pankratov, A.V., Chugay, A.M. and Baranov, A.V. (2010), “Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped”, Cybernetics and Systems Analysis, No. 46 (5). pp. 793-802.

Stoyan, Y.G. and Chugay, A.M. (2014), “Packing different cuboids with rotations and spheres into a cuboid Advances in Decision Sciences”, Advances in Decision Sciences, available at: http://dx.doi.org/10.1155/2014/571743.

Stoian, Y., Pankratov, A. and Romanova, T. (2017), “Optimal clustering of polyhedra”, Bionika intellekta, No. 2, pp. 12-22.




Copyright (c) 2021 Andriy Chugay, Yurii Stoian