Узагальнена математична модель задачі покриття області ідентичними колами та її основні реалізації
Наукові видання Харківського національного університету Повітряних Сил
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Узагальнена математична модель задачі покриття області ідентичними колами та її основні реалізації
Обобщенная математическая модель задачи покрытия области идентичными кругами и ее основные реализации A generalized mathematical model of the problems of covering the area by identical circles and its major implementations |
|
| Creator |
О.А. Антошкін
О.В. Панкратов А.А. Антошкин А.В. Панкратов O. Antoshkin O. Pankratov |
|
| Subject |
Математичні моделі та методи
УДК 519.85 кругове покриття, критерій повноти, phi-функції, функції належності, математична модель, нелінійна оптимізація круговое покрытие, критерий полноты, phi-функции, функции принадлежности, математическая модель, нелинейная оптимизация circular coverage, completeness criterion, phi-functions, membership functions, mathematical model, nonlinear optimization |
|
| Description |
Розглянуто задачу покриття довільної області ідентичними колами. На основі формалізації критеріїв повноти покриття побудовано узагальнену математичну модель задачі кругового покриття у вигляді задачі негладкої оптимізації. Область допустимих розв’язків задачі описано системою нерівностей, що виникає при запису функцій належності для формування умов покриття і додатковою системою нерівностей для врахування технологічних обмежень, що записується за допомогою phi-функцій. Негладкість моделі виникає внаслідок мінімаксного характеру деяких phi-функцій та функцій належності. Розроблено засоби генерації множини реалізацій узагальненої математичної моделі покриття для широкого класу прикладних задач. Запропоновано стратегію розв’язку виникаючих задач нелінійного програмування.
Рассмотрена задача покрытия произвольной области идентичными кругами. На основе формализации критериев полноты покрытия построена математическая модель задачи кругового покрытия в виде задачи негладкой оптимизации. Область допустимых решений задачи описана системой неравенств, которая возникает при записи функций принадлежности для формирования условий покрытия и дополнительной системой неравенств для учета технологических ограничений, записывается с помощью phi-функций. Негладкость модели возникает вследствие минимаксного характера некоторых phi-функций и функций принадлежности. Разработаны средства генерации множества реализаций обобщенной математической модели покрытия для широкий класса прикладных задач. Предложена стратегия решения возникающих задач нелинейного программирования. There is a rapidly growing interest in an effective solution to the problems of optimal coverage of regions of arbitrary shape by circles at the present stage. This is due to the variety of practical applications, the difficult formalizability of the conditions of the problem and the lack of a common approach for its solution. The situation is complicated by the presence of technological limitations on the mutual position of the circles and the position of the circles relative to the region. Most of the approaches proposed in the literature are heuristic for the reasons listed above. This leads to the loss of optimal and locally optimal solutions. The efficiency of solving the problem decreases as a result. The available exact approaches are implemented for particular cases of the problem. Thus, it seems relevant to build an adequate mathematical model of the problem of covering with identical circles of an arbitrary area, whose implementation covers the main tasks of a circular covering that arises in practice. The problem of covering an arbitrary region with identical circles is considered in the paper. A generalized mathematical model of the circular coverage problem is constructed in the form of a nonsmooth optimization problem based on the formalization of the criteria for completeness of the coverage. The feasible region of the problem is described by a system of inequalities consisting of two subsystems. The first of them occurs when writing membership functions for the formation of coating conditions. The second, an additional system of inequalities, serves to take into account technological constraints and is written using phi-functions. The model is nonsmooth due to the minimax nature of some phi-functions and membership functions. The tools for generating a set of implementations of a generalized mathematical model have been developed, covering a wide class of applied problems, including such problems: minimizing the length of wires; minimizing the radius of the circles; minimizing the number of laps; adjusting invalid coverage and adjusting invalid sensor placement. An effective strategy for solving the problem is proposed, based on the combination of the multi-start method with a set of constraint generators and objective functions for the basic implementations of the generalized model. |
|
| Publisher |
Харківський національний університет Повітряних Сил ім. І. Кожедуба
Харьковский национальный университет Воздушных Сил им. И. Кожедуба Kharkiv national Air Force University named after I. Kozhedub |
|
| Date |
2019
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion Рецензована стаття |
|
| Format |
application/pdf
|
|
| Identifier |
http://www.hups.mil.gov.ua/periodic-app/article/19223
|
|
| Source |
Системи обробки інформації. — 2019. — № 1(156). 44-49
Системы обработки информации. — 2019. — № 1(156). 44-49 Information Processing Systems. — 2019. — № 1(156). 44-49 1681-7710 |
|
| Language |
ukr
|
|
| Relation |
http://www.hups.mil.gov.ua/periodic-app/article/19223/soi_2019_1_8.pdf
|
|