УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта


јвтор:   азаков ј.Ћ., Ћемперт ј.ј., “а „.“.
Ќазвание:  ќ задачах упаковок неравных шаров в трехмерном пространстве
¬ыпуск:  87
–убрика:  ћатематическа€ теори€ управлени€
√од:  2020
Ѕиблиографи€:   азаков ј.Ћ., Ћемперт ј.ј., “а „.“. ќ задачах упаковок неравных шаров в трехмерном пространстве // ”правление большими системами. ¬ыпуск 87. ћ.: »ѕ” –јЌ, 2020. —.47-66. DOI: https://doi.org/10.25728/ubs.2020.87.3
 лючевые слова:  упаковка шаров разных типов, трехмерное пространство, оптико-геометрический подход, метод биль€рдного моделировани€, вычислительный алгоритм, неевклидова€ метрика
 лючевые слова (англ.):  unequal balls packing, three dimensional space, optical-geometric approach, billiard simulation method, computational algorithm, non-Euclidean metric
јннотаци€:  —тать€ посв€щена построению оптимальных упаковок набора шаров разных радиусов в трехмерное замкнутое множество: требуетс€ найти такое расположение фиксированного числа шаров, чтобы их радиусы были максимальными. ƒанна€ проблема €вл€етс€ NP-трудной. ƒл€ ее решени€ предложен вычислительный алгоритм, основанный на использовании оптико-геометрического подхода и метода биль€рдного моделировани€. ѕрименение данного подхода позвол€ет решать задачи упаковки не только в евклидовом, но и в других метрических пространствах. “ак, рассмотрена задача, в которой вместо рассто€ни€ между центрами шаров параметром оптимизации €вл€етс€ минимальное врем€ перемещени€ между ними. ѕодобные постановки нередко возникают при решении задач охраны периметра, когда врем€ перемещени€ Ђнарушител€ї до охран€емого объекта играет существенно более важную роль, чем пройденное при этом рассто€ние, а также в логистике, где врем€ доставки имеет первостепенное значение. јлгоритм реализован в виде программного комплекса, с помощью которого проведены вычислительные эксперименты, причем в качестве множества-контейнера выбирались как выпуклые, так и невыпуклые множества. –езультаты расчетов позвол€ют оценить работоспособность и эффективность предложенного алгоритма. ¬ыполнена 3D-визуализаци€ полученных†результатов.
јннотаци€ (англ.):  The article is devoted to the construction of optimal packings of unequal balls in a three-dimensional closed set. It is required to find such an arrangement of a fixed number of balls that their radii are maximal. This problem is NP-hard. To solve it, we propose a computational algorithm based on the optical-geometric approach and billiard modeling. Using this approach allows us to solve packing problems not only in Euclidean, but also in other metric spaces. We consider a problem in which, instead of the distance between the centers of the balls, the optimization parameter is the minimum traveling time between them. Such statements often arise if we consider problems of protecting the perimeter, in which the time of movement of the "intruder" to the protected object plays a much more significant role than the distance traveled, as well as in logistics, where the delivery time is paramount important. The algorithm was implemented, and computational experiments were performed. Both convex and non-convex sets were selected as container sets. The results of calculations allow us to positively assess the efficiency and effectiveness of the proposed algorithm. We performed a 3-D visualization of the results.

¬ формате PDF

ѕросмотров: 105, загрузок: 14, за мес€ц: 5.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены