Страница публикации

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

Авторы: Лебедев П.Д., Казаков А.Л., Лемперт А.А.

Журнал: Труды Института математики и механики УРО РАН

Том: 26

Номер: 2

Год: 2020

Отчётный год: 2020

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI: 10.21538/0134-4889-2020-26-2-173-187

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

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0