Интернет конференция по проблемам теории и практики управленияНазвание: Оптимальное покрытие компактного
множества кругами с фиксированными
центрами
Автор: Александр Витальевич Карпычев
Аннотация:
В статье рассматривается задача покрытия компактного плоского мно-
жества кругами с заданными центрами. Каждый круг имеет перемен-
ный радиус. Ставится задача условной оптимизации с критерием мини-
мизации суммарной длины радиусов кругов при их полном покрытии
заданного множества и выполнении ряда дополнительных ограничений.
В качестве решения предложен метод основанный на построении зон Ди-
рихле и использовании их свойств, дополненный примером алгоритми-
ческой реализации на языке программирования python. Доказана сходи-
мость предлагаемого метода решения к глобальному минимуму целевой
функции. Численное моделирование подтвердило корректность работы
алгоритма и возможность его применения для решения практических
задач, что позволяет говорить о применимости предложенного метода к
решению различных задач планирования и управления, в частности –
задачи планирования инфраструктуры, анализа зон влияния на общих
рынках сбыта, оптимизации беспроводных сетей при фиксированной кон-
фигурации объектов.
Ключевые слова:
Покрытие, зоны доминирования, ячейки Дирихле, конкуренция
множества кругами с фиксированными
центрами
Автор: Александр Витальевич Карпычев
Аннотация:
В статье рассматривается задача покрытия компактного плоского мно-
жества кругами с заданными центрами. Каждый круг имеет перемен-
ный радиус. Ставится задача условной оптимизации с критерием мини-
мизации суммарной длины радиусов кругов при их полном покрытии
заданного множества и выполнении ряда дополнительных ограничений.
В качестве решения предложен метод основанный на построении зон Ди-
рихле и использовании их свойств, дополненный примером алгоритми-
ческой реализации на языке программирования python. Доказана сходи-
мость предлагаемого метода решения к глобальному минимуму целевой
функции. Численное моделирование подтвердило корректность работы
алгоритма и возможность его применения для решения практических
задач, что позволяет говорить о применимости предложенного метода к
решению различных задач планирования и управления, в частности –
задачи планирования инфраструктуры, анализа зон влияния на общих
рынках сбыта, оптимизации беспроводных сетей при фиксированной кон-
фигурации объектов.
Ключевые слова:
Покрытие, зоны доминирования, ячейки Дирихле, конкуренция