RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
 Общая информация Последний выпуск Архив Поиск публикаций Поиск ссылок RSS Последний выпуск Текущие выпуски Архивные выпуски Что такое RSS

 Компьютерные исследования и моделирование: Год: Том: Выпуск: Страница: Найти

 Персональный вход: Логин: Пароль: Запомнить пароль Войти Забыли пароль? Регистрация

 Компьютерные исследования и моделирование, 2019, том 11, выпуск 6, страницы 1101–1110 (Mi crm766)

THE 3RD BRICS MATHEMATICS CONFERENCE

Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles

Sh. I. Galiev, A. V. Khor'kov

Tupolev Kazan National Research Technical University–KAI, 10 ul. Karla Marksa, Kazan, 420111, Russia

Аннотация: Problems of multiple covering ($k$-covering) of a bounded set $G$ with equal circles of a given radius are well known. They are thoroughly studied under the assumption that $G$ is a finite set. There are several papers concerned with studying this problem in the case where $G$ is a connected set. In this paper, we study the problem of minimizing the number of circles that form a $k$-covering, $k\geq 1$, provided that $G$ is a bounded convex plane domain.
For the above-mentioned problem, we state a $0$$1 linear model, a general integer linear model, and a nonlinear model, imposing a constraint on the minimum distance between the centers of covering circles. The latter constraint is due to the fact that in practice one can place at most one device at each point. We establish necessary and sufficient solvability conditions for the linear models and describe one (easily realizable) variant of these conditions in the case where the covered set G is a rectangle. We propose some methods for finding an approximate number of circles of a given radius that provide the desired k-covering of the set G, both with and without constraints on distances between the circles' centers. Wetreat the calculated values as approximate upper bounds for the number of circles. We also propose a technique that allows one to get approximate lower bounds for the number of circles that is necessary for providing a k-covering of the set G. In the general linear model, as distinct from the 0$$1$ linear model, we require no additional constraint. The difference between the upper and lower bounds for the number of circles characterizesv the quality (acceptability) of the constructed $k$-covering.
We state a nonlinear mathematical model for the $k$-covering problem with the above-mentioned constraints imposed on distances between the centers of covering circles. For this model, we propose an algorithm which (in certain cases) allows one to find more exact solutions to covering problems than those calculated from linear models.
For implementing the proposed approach, we have developed computer programs and performed numerical experiments. Results of numerical experiments demonstrate the effectiveness of the method.

Ключевые слова: linear models of the multiple covering problem, $k$-covering of a bounded set, nonlinear models of the $k$-covering problem with circles of a given radius, solvability conditions for linear models of the $k$-covering problem.

DOI: https://doi.org/10.20537/2076-7633-2019-11-6-1101-1110

Полный текст: PDF файл (110 kB)
Полный текст: http://crm.ics.org.ru/.../2869
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.6:519.147
Поступила в редакцию: 30.05.2019
Принята в печать:14.11.2019
Язык публикации: английский

Образец цитирования: Sh. I. Galiev, A. V. Khor'kov, “Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles”, Компьютерные исследования и моделирование, 11:6 (2019), 1101–1110

Цитирование в формате AMSBIB
\RBibitem{GalKho19} \by Sh.~I.~Galiev, A.~V.~Khor'kov \paper Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles \jour Компьютерные исследования и моделирование \yr 2019 \vol 11 \issue 6 \pages 1101--1110 \mathnet{http://mi.mathnet.ru/crm766} \crossref{https://doi.org/10.20537/2076-7633-2019-11-6-1101-1110} 

Образцы ссылок на эту страницу:
• http://mi.mathnet.ru/crm766
• http://mi.mathnet.ru/rus/crm/v11/i6/p1101

 ОТПРАВИТЬ:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Просмотров: Эта страница: 57 Полный текст: 3 Литература: 4
 Обратная связь: math-net2020_12 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020