Алгоритмы построения оптимальных упаковок шаров в эллипсоиды

  • Павел Дмитриевич Лебедев
    • Институт математики и механики УрО РАН
    • Уральский федеральный университет
  • Никита Георгиевич Лавров
    • Институт математики и механики УрО РАН
    • Уральский федеральный университет
Ключевые слова: упаковка, чебышёвский центр, супердифференциал, итерационный алгоритм, гранецентрированная кубическая решетка

Аннотация

В статье рассматривается задача о построении упаковки из набора конгруэнтных шаров в замкнутые выпуклые множества. В качестве формы контейнеров для упаковки выбраны эллипсоиды. В одном случае считается фиксированным число элементов упаковки, а критерием оптимизации выбрана максимизация радиусов элементов упаковки. В другом случае фиксирован радиус шаров и ставится задача об отыскании упаковки с наибольшим числом элементов. Предложены итерационные алгоритмы построения оптимальных упаковок, основанные на имитации отталкивания их центров друг от друга и от границы контейнера. Развиты алгоритмы построения упаковок на базе наиболее плотной упаковки трехмерного пространства, представляющей собой решетки различного типа и их комбинации. Выполнено моделирование решения ряда задач и визуализация результатов.

Литература

1. Слоэн Н.Дж.А. Упаковка шаров // В мире науки. 1984. № 3. С. 72-82.
2. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958. 364 c.
3. Красовский Н.Н. Теория управления движением. М.: Наука, 1968. 476 с.
4. Kurzhanski A.B. Ellipsoidal calculus for estimation and feedback control // Systems and control in the twenty-first century. Boston, MA: Birkhäuser, 1997. P. 229-243. DOI: 10.1007/978-1-4612-4120-1_12
5. Лебедев П.Д., Успенский А.А. Алгоритмы построения оптимальных упаковок в трехмерном евклидовом пространстве // Proceedings of the 47th international youth school-conference «Modern problems in mathematics and its applications» (MPMA 2016). Vol. 1662 of CEUR Workshop Proceedings (CEUR-WS.org). С. 84-93. http://ceur-ws.org/Vol-1662/opt5.pdf
6. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка, 1986. 266 c.
7. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. С. 50-57.
8. Субботин А.И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. М.-Ижевск: Институт компьютерных исследований, 2003. 336 с.
9. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.
10. Лебедев П.Д., Казаков А.Л. Итерационные методы построения упаковок из кругов различного диаметра на плоскости // Труды Института математики и механики УрО РАН. 2018. Т. 24. № 2. С. 141-151. DOI: 10.21538/0134-4889-2018-24-2-141-151
11. Ушаков В.Н., Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок в эллипсы // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. 2017. Т. 10. № 3. С. 67-79. DOI: 10.14529/mmp170306
12. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // УМН. 1964. Т. 19. Вып. 6 (120). С. 139-145. http://mi.mathnet.ru/umn6276
13. Гаркави А.Л. О наилучшей сети и наилучшем сечении множеств в нормированном пространстве // Известия АН СССР. Сер. матем. 1962. Т. 26. Вып. 1. С. 87-106.
14. Stoyan Yu., Yaskov G., Scheithauer G. Packing of various solid spheres into a parallelepiped // Central European Journal of Operational Research. 2003. Vol. 11. Issue 4. P. 389-407.
15. Liu J., Yao Y., Zheng Yu, Geng H., Zhou G. An effective hybrid algorithm for the circles and spheres packing problems // COCOA 2009: Combinatorial Optimization and Applications. Lecture Notes in Computer Science. Vol 5573. Berlin-Heidelberg: Springer, 2009. P. 135-144. DOI: 10.1007/978-3-642-02026-1_12
16. Lubachevsky B.D., Stillinger F.H. Geometric properties of random disk packings // Journal of Statistical Physics. 1990. Vol. 60. Issue 5-6. P. 561-583. DOI: 10.1007/BF01025983
17. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 1. М.: Мир, 1990. 415 с.
18. Barlow W. Probable nature of the internal symmetry of crystals // Nature. 1883. Vol. 29. Issue 738. P. 186-188. DOI: 10.1038/029186a0
19. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. 326 с.
20. Лебедев П.Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Свидетельство о государственной регистрации № 2015661543 от 29.10.2015.
21. Ушаков В.Н., Лебедев П.Д. Алгоритмы оптимального покрытия множеств на плоскости $\mathbb{R}^2 $ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2016. Т. 26. Вып. 2. С. 258-270. DOI: 10.20537/vm160212
Поступила в редакцию 2018-10-11
Опубликована 2018-11-20
Выпуск
Раздел
Математика
Страницы
59-74