Численные методы построения упаковок из различных шаров в выпуклые компакты

Исследуется проблема оптимальной упаковки неравных шаров в выпуклый компакт. Рассматриваются наборы шаров, радиусы которых пропорциональны заданному параметру $r$. Максимизация последнего выбрана в качестве критерия оптимальности. Наибольшее возможное количество различных типов шаров равно трем. Задача относится к классу NP-трудных и исследуется численно. Предложены алгоритмы, основанные на сегментации заданного компакта на зоны влияния центров элементов упаковки (обобщенные зоны Дирихле). Разбиение строится с использованием оптико-геометрического подхода, развиваемого в последние годы авторами. После получения промежуточного результата выполняется процедура улучшения с помощью разработанного геометрического алгоритма. В качестве его основы использованы методы, базирующиеся на пошаговом сдвиге точек с целью максимизации радиуса текущего шара. Для отыскания направления сдвига строится супердифференциал функции, равной максимальному радиусу элемента упаковки с центром в текущей точке. Выведена формула, позволяющая определить направление максимального роста данной функции. Разработанные алгоритмы реализованы в виде программного комплекса для построения упаковок шаров в компакт. Выполнен численный эксперимент, в ходе которого рассмотрено несколько примеров. Построены упаковки шаров разного радиуса для тел различной формы: куба, шара, цилиндра.