Математичні моделі та алгоритми оптимальної упаковки куль та кубів у сферичний та кубічний контейнери

Abstract

Розглянуто математичні моделі та алгоритми оптимальної збалансованої розрідженої упаковки куль та кубів у сферичний та кубічний контейнери. Збалансованою розрідженою (задаються допустимі відстані між обʼєктами)упаковкою об’єктів у зовнішній контейнер є така їх упаковка, коли центр ваги сімейства об’єктів збігається з центром зовнішнього контейнера, а відстані між об’єктами та відстані від них до зовнішнього контейнера булине менші за наперед задані величини. Наведено математичні моделі, послідовні та паралельні алгоритми розв’язання задач знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний та кубічний контейнери. Наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у куб мінімального обʼєму за умови, що сторони всіх кубів паралельні осям координат, та опис негладкої штрафної функції для пошуку локальних мінімумів задачі. Досліджувані задач і відносяться до класу NP-важких задач. Математичні моделі представлені багатоекстремальними задачами нелінійного програмування. Для пошуку найкращого допустимого розвʼязку застосовується метод мультистарту у сполученні з r-алгоритмом Шора. Для цього задача зводиться до задачі безумовної оптимізації за допомогою штрафних функцій у вигляді функцій максимуму, а для пошуку локальних мінімумів із набору стартових точок застосовуються методи мінімізації негладких функцій, що базуються на використанні програмних реалізацій r-алгоритму. Математичні моделі та послідовні і паралельні алгоритми, що розглядаються, можна використати для розробки програмних засобів розв’язування задач знаходження збалансованої розрідженої упаковки сферичних та кубічних обʼєктів у сферичні та кубічні контейнери. Матеріал представлено в трьох розділах. У розд. 1 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у сферичний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 2 наведено математичну модель та алгоритми розв’язання задачі знаходження збалансованої розрідженої упаковки куль різних радіусів у кубічний контейнер. Описано послідовний та паралельний алгоритми знаходження найкращого допустимого розв’язку задач. У розд. 3 наведено математичну модель задачі знаходження збалансованої розрідженої упаковки кубів у кубічний контейнер. Наведено опис негладкої штрафної функції для пошуку локальних мінімумів задачі.Mathematical models and algorithms for optimal balanced sparse packing of spheres and cubes in spherical and cubic containers are considered. The balanced sparse packing (where permissible distances between objects are specified) is such that the center of gravity of the object family coincides with the center of the external container, and the distances between the objects and from them to the external container are no less than predefined values. Mathematical models are presented, along with sequential and parallel algorithms for solving the tasks of finding balanced sparse packing of spheres of different radii in spherical and cubic containers. A mathematical model of the task of finding balanced sparse packing of cubes in a cube of minimal volume is provided, under the condition that the sides of all cubes are parallel to the coordinate axes, along with the description of a non-smooth penalty function for searching local minima of the problem.