Введение к работе
Актуальность темы. Работа посвящена решению задач многократных (в том числе и однократных) покрытий ограниченных множеств кругами. Многие практические задачи сводятся к задаче покрытия. Так, например, задачи расположения различных станций технического обслуживания, станций сотовой связи, беспроводного Интернета являются задачами покрытия кругами ограниченной области. Многократные покрытия не менее интересны и важны, чем однократные, в частности, навигационные системы GPS, Глонасс и разрабатываемая европейская система Галилео используют многократное покрытие обслуживаемых областей.
Пусть требуется разместить видеокамеры противопожарной системы наблюдения лесных массивов. Поворотная видеокамера может вращаться на 360 градусов и передавать информацию оператору в режиме реального времени. В этом случае можно считать, что зоной наблюдения (обслуживания) отдельной видеокамеры является круг. Для надежности системы и точного определения координат очагов возгорания необходимо покрывать этими кругами рассматриваемую область двукратно.
При размещении логистических, а также распределительных центров зоной обслуживания будет «круг», в котором расстояние от центра до потребителя измеряется по существующим дорогам. При этом расстояния можно оценивать, используя некоторую метрику на заданной области. К классу указанных задач можно отнести задачу расположения центров служб чрезвычайных событий, использующих существующие дороги. Также таковой является, например, задача определения местоположения пунктов хранения химических реагентов для нефтепромыслов. Важно расположить эти пункты таким образом, чтобы быстрее доставлять реагенты в нужную точку. При этом если в ближайшем пункте требуемого реагента не окажется, то желательно, чтобы второй
пункт оказался не очень далеко. В результате получим задачу двукратного покрытия заданной области.
При определении расстояний можно использовать готовые матрицы расстояний или геоинформационные системы, которые сложно использовать для качественного анализа областей обслуживания отдельных станций - областей Вороного. Поэтому во многих работах используются функции для оценки расстояний, порождающие некоторую метрику. В литературе используются различные метрики, в диссертации выбрана 1кв -метрика, как
наиболее подходящая для регионов Татарстана.
Оптимизации расположения различных станций
обслуживания посвящены специальные монографии и большое
число статей, исследующих как общие вопросы, так и решение
задач для
выбранных областей. Обзоры по этим задачам и достаточно детальное исследование приложений содержатся в монографиях Дрезнера Ц., Дрезнера Ц. и Гамахера Г., Шиллера Дж. и Войсарда А., Купера А., Фарахани Р. 3. и Гекматфара М., Финкелыптейна Ю. Ю., Ковалева М. М., Сигала И. X. и Ивановой А. П. и в ряде других работ.
По различным вариантам задач покрытий (и связанных с ними задач упаковок) имеется большое число работ, укажем только некоторые, а именно, работы Роджерса К., Конвея Дж. и СлоэнаН., Фейеша Тота Л., Фейеша Тота Г., Леонтьева В. К., Брусова В. С. и Пиявского С. А., Колоколова А. А., Еремеева А. В., Кузюрина Н. Н., Мухачевой Э. А., Залгаллера В. А., Галиева Ш. П., Заботина В. П., Захарова В. М., Бухараева Р. Г., Емалетдиновой Л. Ю. Задача однократного покрытия N кругами ограниченной части плоскости (как в евклидовой метрике, так и в некоторых других метриках) известна также как задача об N-центре, для которой многими авторами предложены различные алгоритмы.
В дискретной постановке задачи покрытия и упаковок являются вариантами дискретных оптимизационных задач. По задачам дискретной оптимизации и их интересным и важным приложениям имеется большое число монографий и научных
статей. Часть из них указана выше. Необходимо также указать важные работы Аардала К., Немхаузера Г. Л. и Вейсмантела Р., Леонтьева В. К., Журавлева Ю. Н., Коннова И. В., Емеличева В. А., Ковалева М. М. и Кравцова М. К., Ревелле К. С, Ейселта X. А. и Даскина М. С.
Цель работы:
анализ свойств математических моделей и развитие методов оптимизации многократных покрытий;
повышение эффективности алгоритмов решения непрерывных и дискретных задач многократного покрытия ограниченных множеств.
Задачи исследования:
выявить свойства математических моделей дискретных и непрерывных задач покрытия, условия существования решений;
разработать численные алгоритмы оптимизации числа кругов или (и) их расположения для ^-кратного (к > 1) покрытия заданных областей или заданного конечного множества точек;
получить оценки минимальных радиусов покрывающих кругов;
подобрать метрики и их параметры для выбранных районов Татарстана;
оптимизировать числа и расположения некоторых станций обслуживания на всей или части территории Татарстана.
Методы исследования. В работе использовались методы исследования операций, теория экстремальных задач, в том числе и на графах, методы численного решения экстремальных задач, в том числе и задач целочисленного программирования больших размерностей, и теория вероятностей с математической статистикой.
Научная новизна работы:
выявлены новые свойства математических моделей задач
покрытия:
- для дискретных моделей получены достаточные условия разрешимости некоторых дискретных задач однократного и многократного покрытия; необходимые и достаточные условия разрешимости для одного из вариантов дискретной задачи
многократного покрытия. Также установлены некоторые вспомогательные свойства этих моделей;
- для непрерывных моделей однократного и многократного
покрытия ограниченной области установлена
недифференцируемость целевых функций в точке (точках) глобального экстремума;
предложены новые численные алгоритмы для решения непрерывных и дискретных задач покрытия, для некоторых из них получены оценки минимальных радиусов покрывающих кругов;
получены экстремальные и предполагаемые значения радиусов п кругов для двукратного покрытия единичного квадрата при п<9 и и = 11,13,15,17,19,21;
подобраны метрики для отдельных районов Татарстана;
решена задача определения числа и расположения станций противопожарной системы наблюдения лесных массивов части территории Татарстана, а также задача определения числа станций хранения химических реагентов и их расположения для обслуживания нефтепромыслов на некоторой части Татарстана.
Достоверность результатов определяется четкими и обоснованными ограничениями рассматриваемых задач, использованием известных математических моделей, корректным применением математических методов и совпадением численных результатов с известными из литературы.
Апробация работы. Результаты исследований
докладывались и обсуждались на конференциях: Международная
конференция «Туполевские чтения» (г. Казань, 2008, 2009, 2010);
Международная научно-техническая конференция
«Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008); Международная научно-образовательная конференция «Наука в вузах: математика, физика, информатика» (г. Москва, 2009); Международная научно-практическая конференция «Современные достижения в науке и образовании: математика и информатика» (г. Архангельск, 2010); Общероссийская научно-практическая конференция на основе интернет-форума с международным участием «Актуальные вопросы современной науки
и образования» (г. Красноярск, 2010); Всероссийская межвузовская научная конференция «Наука и образование в развитии промышленной, социальной и экономической сфер регионов России» (г. Муром, 2011).
Публикации. Основные результаты исследований опубликованы в трех статьях в журналах из списка, рекомендованного ВАК РФ, и в 8 сборниках материалов конференций.
Структура и объем диссертации
Диссертация состоит из введения, 4 глав, заключения, списка цитированной литературы и приложения. Общий объем диссертации составляет 140 страниц машинописного текста, включая 35 рисунков и список цитированной литературы из 154 наименований.
