Аннотация:
Рассматривается задача о построении оптимальной упаковки из фиксированного числа $n>1$ кругов в общем случае различного радиуса в плоское компактное множество $M$. Считается, что для каждого элемента упаковки задано положительное число такое, что радиус круга равен его произведению на общий для всей упаковки параметр $r$. Критерием оптимальности выбран максимум $r$, что приводит в том числе и к увеличению плотностиупаковки - отношения ее площади к площади фигуры $M$. Основу метода решения задачи составляет итерационное изменение координат центров элементов упаковки $S_n$, дающее возможность увеличивать радиусы кругов. Разработанные вычислительные процедуры реализуют имитацию отталкивания центра каждого элемента упаковки от близко лежащих других центров и от границы множества $M$. Исследованы дифференциальные свойства функции двух переменных $(x,y)$, значение которой равно максимальному радиусу круга упаковки, располагающегося с центром в точке $(x,y)$. При это координаты центров остальных элементов упаковки считаются фиксированными. При программной реализации используется конструкция чебышевского центра компактного множества. Создан программный комплекс, с его помощью рассмотрен ряд примеров для множеств $M$ различной геометрии. Выполнена визуализация полученных результатов.
Ключевые слова:
задача об упаковке кругов, оптимизация, чебышевский центр, супердифференциал, итерационный алгоритм.
Образец цитирования:
П. Д. Лебедев, А. Л. Казаков, “Итерационные методы построения упаковок из кругов различного диаметра на плоскости”, Тр. ИММ УрО РАН, 24, № 2, 2018, 141–151