Том 27, номер 4, 2020 г., Стр. 58-79

УДК 514.174.2
Лебедев П. Д., Ушаков В. Н., Успенский А. А.
Численные методы построения субоптимальных упаковок в невыпуклых фигурах с криволинейной границей

Аннотация:
Изучается задача о построении оптимальных упаковок наборами конгруэнтных кругов в компактные невыпуклые односвязные плоские множества. В качестве критерия оптимальности рассматривается максимизация радиуса кругов при фиксированном их количестве. Развиты теоретические методы решения задачи, основанные на конструкциях субдифференциального исчисления, и предложен подход к построению субоптимальных упаковок — упаковок, в общем случае близких к оптимальным. Основу разработанных численных алгоритмов составляют итерационные процедуры, учитывающие по существу расположение текущего центра элемента упаковки, центров ближайших к нему соседних элементов и точек границы фигуры. В алгоритмах используется схема суперградиентного подъёма, параметры которого могут варьироваться в зависимости от числа элементов упаковки и геометрии множества. Создан программный комплекс, эффективность работы которого продемонстрирована на примерах численного построения субоптимальных упаковок в невыпуклые фигуры, ограниченные овалом Кассини, гипотрохоидой и кардиоидой.
Ил. 6, библиогр. 37.

Ключевые слова: упаковка, максимизация, оптимизация, алгоритм, численная процедура, производная по направлению, супердифференциал, аппроксимация, суперградиентный подъём.

DOI: 10.33048/daio.2020.27.678

Лебедев Павел Дмитриевич ¹
Ушаков Владимир Николаевич ¹
Успенский Александр Александрович ¹
1. Институт математики и механики им. Н. Н. Красовского,
ул. Софьи Ковалевской, 16, 620990 Екатеринбург, Россия
е-mail: pleb@yandex.ru, ushak@imm.uran.ru, uspen@imm.uran.ru

Статья поступила 27 декабря 2019 г.
После доработки — 27 июля 2020 г.
Принята к публикации 29 июля 2020 г.

Литература

[1] Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М.: Наука, 1974. 456 с.

[2] Ушаков В. Н., Успенский А. А., Малев А. Г. Оценка дефекта стабильности множества позиционного поглощения, подвергнутого дискриминантным преобразованиям // Тр. Ин-та математики и механики. 2011. Т. 17, № 2. С. 209–224.

[3] Ушаков В. Н., Лебедев П. Д., Лавров Н. Г. Алгоритмы построения оптимальных упаковок в эллипсы // Вестн. ЮУрГУ. Сер. Мат. моделирование и программирование. 2017. Т. 10, № 3. С. 67–79.

[4] Лебедев П. Д., Казаков А. Л. Итерационные методы построения упаковок из кругов различного радиуса на плоскости // Тр. Ин-та математики и механики. 2018. Т. 24, № 2. С. 141–151.

[5] Machchhar J., Elber G. Dense packing of congruent circles in free-form nonconvex containers // Comput. Aided Geom. Des. 2017. Vol. 52–53. P. 13–27.

[6] Meng L., Wang C., Yao X. Non-convex shape effects on the dense random packing properties of assembled rods // Physica A. Vol. 490. 2017. P. 212–221.

[7] Locatelli M., Raber U. Packing equal circles in a square: A deterministic global optimization approach // Discrete Appl. Math. 2017. Vol. 122. P. 139–166.

[8] Li Y., Akeb H. Basic heuristics for packing a large number of equal circles. Amiens: Univ. Picardie Jules Verne, 2005. 19 p. Available at www.researchgate.net/publication/250761942_Basic_Heuristics_for_
Packing_a_Great_Number_of_Equal_Circles (accessed Aug. 13, 2020).

[9] Litvinchev I., Ozuna L. Approximate packing circles in a rectangular container: Valid inequalities and nesting // J. Appl. Res. Technology. 2014. Vol. 12, No. 4. P. 716–723.

[10] Stoyan Yu. G., Yas’kov G. A mathematical model and a solution method for the problem of placing various-sized circles into a strip // Eur. J. Oper. Res. 2004. Vol. 156. P. 590–600.

[11] Stoyan Yu. G., Yas’kov G. Packing identical spheres into a rectangular parallelepiped // Intelligent Decision Support: Current Challenges and Approaches. Wiesbaden: Gabler-Verl., 2008. P. 46–67.

[12] Hifi M., M’Hallah R. Approximate algorithms for constrained circular cutting problems // Comput. Oper. Res. 2004. Vol. 31. P. 675–694.

[13] Чугай А. М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифицированного метода сужающихся окрестностей // Радиоэлектроника и информатика. 2005. № 1. С. 58–63.

[14] Лебедев П. Д., Успенский А. А. Построение функции оптимального результата и рассеивающих линий в задачах быстродействия с невыпуклым целевым множеством // Тр. Ин-та математики и механики. 2016. Т. 22, № 2. С. 188–198.

[15] Kazakov A. L., Lempert A. A., Ta T. T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFACPapersOnLine. 2018. Vol. 51, No. 32. P. 782–787.

[16] Казаков А. Л., Лемперт А. А., Нгуен Г. Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычисл. методы и программирование. 2016. Т. 17, № 2. С. 177–188.

[17] Kazakov A. L., Lempert A. A., Nguyen H. L. The problem of the optimal packing of the equal circles for special non-Euclidean metric // Commun. Comput. Inf. Sci. 2017. Vol. 661. P. 58–68.

[18] Lebedev P. D., Uspenskii A. A. Algorithms of optimal packing construction in a 3-dimensional Euclidian space // Modern Problems in Mathematics and Its Applications. Proc. 47th Int. Youth School-Conf. MPMA 2016 (Yekaterinburg, Russia, Jan. 31–Feb. 6, 2016). Aachen: RWTH Aachen Univ., 2016. P. 84–93. (CEUR Workshop Proc.; Vol. 1662). Available at www.ceur-ws.org/Vol-1662 (accessed Aug. 13, 2020).

[19] Субботин А. И. Обобщённые решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. М.; Ижевск: Ин-т компьют. технологий, 2003. 336 с.

[20] Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.

[21] Бычков И. В., Казаков А. Л., Лемперт А. А., Бухаров Д. С., Столбов А. Б. Интеллектная система управления развитием транспортно-логистической инфраструктурой региона // Пробл. управления. 2014. № 1. С. 27–35.

[22] Рвачёв В. Л., Стоян Ю. Г. Задача оптимального размещения круговых заготовок // Кибернетика. 1965. № 3. С. 77–83.

[23] Castillo I., Kampas F. J., Pinter J. D. Solving circle packing problems by global optimization: Numerical results and industrial applications // Eur. J. Oper. Res. 2008. Vol. 191, No. 3. P. 786–802.

[24] Harary F., Randolph W., Mezey P. G. A study of maximum unit-circle caterpillars – tools for the study of the shape of adsorption patterns // Discrete Appl. Math. 1996. Vol. 67, No. 1–3. P. 127–135.

[25] Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задачи о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 17, № 2. С. 22–46.

[26] Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 472 с.

[27] Лебедев П. Д., Ушаков А. В. Аппроксимация множеств на плоскости оптимальными наборами кругов // Автоматика и телемеханика. 2012. № 3. С. 79–90.

[28] Сухарев А. Г., Тимохов А. В., Фёдоров В. В. Курс методов оптимизации. М.: Наука, 1986. 326 с.

[29] Нурминский Е. А., Тьен Д. Метод сопряжённых субградиентов с ограниченной памятью // Автоматика и телемеханика. 2014. № 4. С. 67–80.

[30] Воронцова Е. А. Линейная задача о допусках для интервальной модели межотраслевого баланса // Вычисл. технологии. 2017. Т. 22, № 2. С. 67–84.

[31] Гасников А. В., Двуреченский П. Е., Камзолов Д. И., Нестеров Ю. Е., Спокойный В. Г., Стецюк П. И., Суворикова А. Л., Чернов А. В. Поиск равновесий в многостадийных транспортных моделях // Тр. Моск. физ.-тех. ин-та. 2015. Т. 7, № 4. С. 143–155.

[32] Лебедев П. Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Свид-во о гос. регистрации № 2015661543 от 29.10.2015.

[33] Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматгиз, 1958. 365 c.

[34] Местецкий Л. М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М.: ФИЗМАТЛИТ, 2009. 288 с.

[35] Лебедев П. Д., Успенский А. А. Конструирование негладкого решения задачи управления по быстродействию при низком порядке гладкости границы целевого множества // Тр. Ин-та математики и механики. 2019. Т. 25, № 1. С. 108–119.

[36] Савёлов А. А. Плоские кривые. Систематика, свойства, применения. М.: Либроком, 2010. 294 с.

[37] Specht E. Packomania. 2018. Available at www.packomania.com (accessed Aug. 13, 2020).