|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Динамические системы и оптимальное управление
On covering bounded sets by collections of circles of various radii
[О покрытии ограниченных множеств наборами кругов различных радиусов]
A. L. Kazakovab, P. D. Lebedevc, A. A. Lemperta a Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russian Federation
b Irkutsk National Research Technical University, Irkutsk, Russian Federation
c Krasovskii Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, Russian Federation
Аннотация:
Рассмотрена задача о построении оптимального покрытия плоской фигуры объединением кругов. Радиусы кругов, вообще говоря, различны. Каждый из них равен произведению некоторого положительного коэффициента на общий для всех параметр $r$, который и является целевой функцией, подлежащей минимизации. Проведено аналитическое исследование задачи. Получены выражения, позволяющие описать обобщенные зоны Дирихле для рассмотренного случая. Показано, что они существенно отличаются от классических зон Дирихле. Предложена итерационная процедура коррекции координат центров кругов, образующих покрытие, которая основана на отыскании чебышевских центров областей влияния точек. Показано, что она не ухудшает свойства покрытия. Предложен вычислительный алгоритм, использующий метод мультистарта для генерации начальных положений точек и итерационную процедуру. Выполнена его реализация в виде компьютерной программы. Проведены численные эксперименты по построению оптимальных покрытий наборами кругов при различных коэффициентах, определяющих радиус каждого из них. Рассмотрены случаи двух и трех различных типов кругов. В качестве покрываемых множеств взяты многоугольники: как выпуклые, так и невыпуклые, выполнена визуализация вычислений. Проведен анализ результатов расчетов, который позволил сделать содержательные выводы о свойствах построенных покрытий.
Ключевые слова:
оптимизация, покрытие кругами, обобщенная зона Дирихле, чебышевский центр, итерационный алгоритм, вычислительный эксперимент.
Поступила в редакцию: 30.10.2019
Образец цитирования:
A. L. Kazakov, P. D. Lebedev, A. A. Lempert, “On covering bounded sets by collections of circles of various radii”, Известия Иркутского государственного университета. Серия Математика, 31 (2020), 18–33
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum403 https://www.mathnet.ru/rus/iigum/v31/p18
|
Статистика просмотров: |
Страница аннотации: | 167 | PDF полного текста: | 102 | Список литературы: | 14 |
|