Введение к работе
Актуальность темы исследования
В современном мире всё чаще приходится проектировать, строить, обслуживать системы, состоящие из большого количества элементов, соединённых многими связями друг с другом, так называемые «сложные системы». При этом связи (бинарные отношения) между элементами с навешиваемыми на них скалярными характеристиками могут изменяться во времени. Порождение и исследование процессов изменения связей между элементами системы или способов изменения инцидентора графа (сети) и другие структурные преобразования в системе относят к новой математической дисциплине, называемой «структурной динамикой». К таким практическим системам в первую очередь следует отнести современные коммуникационные и информационные сети, объём и масштаб которых в процессе роста, развития и эксплуатации могут претерпевать значительные топологические, пространственные и количественные метрические изменения, оставаясь структурно инвариантными.
В таких сетях хорошо известная в дискретной математике задача о назначениях, в частности, о размещении центров, приобретает новый смысл. Для решения современных задач структурной динамики становится где-то сложно, а где-то невозможно использовать классическую теорию графов, поскольку необходимо приходится моделировать динамические структуры с большим количеством элементов и ещё большим количеством отношений (связей) между ними. Связи между элементами перестают быть тривиальными бинарными отношениями, они часто приобретают фрактальную природу. Для успешного математического моделирования подобных систем приходится пользоваться достаточно новыми математическими объектами – «фрактальными и предфрактальными графами».
В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования или средств обслуживания в сетях или на графах. В частности, если граф представляет сеть дорог, а вершины графа соответствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, полицейских участков, пожарных частей и многих других крайне необходимых предприятий и служб. В таких случаях критерий оптимальности может состоять в минимизации суммарного расстояния, максимального расстояния, стоимости или времени проезда и т.д. от пункта обслуживания до самой удалённой вершины графа, т.е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить не один, а несколько таких пунктов обслуживания. При этом самая отдалённая вершина графа должна находиться на минимально возможном расстоянии по крайней мере от одного пункта обслуживания. К таким задачам прежде всего относят задачи размещения аварийных служб, поэтому объективным требованием в них является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. По очевидным причинам задачи такого типа называются «минимаксными задачами размещения». Полученные при решении этих задач места размещения пунктов обслуживания называются «центрами» графа.
В некоторых задачах размещения лучше всего было бы минимизировать сумму всех расстояний от вершин графа до центра графа (центра обслуживания), если предполагать, что ищется место для размещения только одного такого пункта обслуживания. Такой критерий является наиболее подходящим, например, в задаче о размещении склада в сети дорог, где вершины сети представляют потребителей, обслуживаемых этим складом, или в задаче размещения телефонных станций в телефонной сети, где вершины сети представляют собой абонентов. Задачи такого типа вообще относятся к «минисуммным задачам размещения», хотя целевая функция является часто не просто суммой расстояний, а суммой различных функций от расстояний. Места размещения пунктов обслуживания, полученные в результате решения минисуммной задачи, называются «медианами» графа.
В более общих и более сложных практических задачах появляется возможность рассматривать и строить не один центр в одной вершине, а множество из р-точек или р-вершин, которые и образуют «кратный центр» или «р-центр».
В классической теории графов перечень работ и список исследователей, которые решали задачу размещения центров, огромен. Достаточно сослаться на работы Н. Кристофидеса, С.Л. Хакими, Д. Дейкстра, С. Сингера, К. Бержа, А.А. Зыкова, Ф. Харари, Г. Фрэнка, И. Фриша, О. Оре, Р. Басакера, Т. Саати, Г.М. Адельсон-Вельского, Е.А. Диница, А.В. Карзанова, Р. Уилсона, Л. Форда, Д. Фалкерсона, В.А. Евстигнеева, Р.В. Флойда.
Исследования в области структурной динамики сложных систем с привлечением фрактальных и предфрактальных графовых структур ведутся в России в научных школах Института проблем управления имени В.А. Трапезникова РАН, Института прикладной математики имени М.В. Келдыша РАН, Вычислительного центра имени А.А. Дородницына РАН.
Благодаря исследованиям, проводимым в научной школе профессора А.М. Кочкарова в Северо-Кавказской государственной гуманитарно-технологической академии, фрактальные (предфрактальные) графы получили распространение как инструмент моделирования «сложных динамических систем». Это происходит из-за нарастающей потребности построения многокритериальных моделей и решения оптимизационных задач в сложных системах, обогащённых и отягощённых быстрым изменением во времени нестационарных переменных современных конъюнктур.
В диссертационной работе проводится математическое моделирование, исследование процесса и решение задач «многокритериального размещения р-центра на предфрактальных графах» с их алгоритмической и программной реализацией.
Соответствие темы диссертации требованиям паспорта специальности
Диссертация выполнена в соответствие с пунктами 1 «Разработка новых математических методов моделирования объектов и явлений»; 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; 6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; 8 «Разработка систем компьютерного и имитационного моделирования» «Паспорта специальности 05.13. 18 – математическое моделирование, численные методы и комплексы программ (физико-математические науки)» ВАК Министерства образования и науки РФ.
Объектом исследования являются
структуры сложных сетевых систем природы, общества, техники с их саморазвитием и инфотелекоммуникационными отношениями.
Предмет исследования составляют
предфрактальные графы как модели сетей, их обобщённые показатели (раскраски, центры, кратные центры, р-центры, хроматические числа) и метрические характеристики (степени вершин, длины цепей, радиусы, диаметры, медианы).
Цели и задачи диссертационного исследования
Целью диссертационного исследования является разработка, построение и исследование математической модели размещения кратных или р-центров на предфрактальных графах как структурных образах самоподобных сетевых систем.
Реализация цели диссертационного исследования потребовала решения следующих задач:
-
Обозрение классических подходов к построению математических моделей и к решению задач размещения центра и кратных центров на графах и сетях;
-
Формулировка многокритериальной задачи размещения р-центра на предфрактальном графе с интерпретацией предложенных критериев;
-
Построение и исследование математической модели размещения кратного центра или р-центра на предфрактальном графе;
-
Исследование свойств отдельного класса предложенных математических моделей - предфрактальных графов, порождённых затравкой-звездой;
-
Получение аналитических формул и построение алгоритмов нахождения оптимальных решений сформулированной задачи с подсчётом гарантированных временных оценок для алгоритмов, выделяющих неоптимальные решения;
-
Полезное использование того важного свойства предфрактальных структур, по которому вычислимость алгоритмов на этих структурах полиномиальна, ибо базируется на трудоёмкости анализа только его затравок;
-
Разработка вариативной архитектуры программного комплекса, алгоритмов и самих программ, допускающих реализацию на персональных компьютерах применительно ко всем этапам предложенной методологии.
Методы исследования
В диссертационной работе использовались математические методы моделирования объектов, методы многокритериальной оптимизации, синергетики, теории фракталов и теории хаоса, теории графов и сетей, теории алгоритмов, кластерный анализ. Вычислительная сложность, вычислительная трудоёмкость или труднорешаемость алгоритмов оценивалась согласно теории сложности алгоритмов.
Достоверность и обоснованность
всех результатов диссертационного исследования подтверждается строгостью и точностью конструкций математических моделей, логическими последовательными умозаключениями при построении структур моделей, аналитикой доказательств лемм, теорем и следствий из них, предложение алгоритмов, чья труднорешаемость полиномиальна, реализацией эффективных численных и программных методов.
Научная новизна диссертационного исследования:
-
Предложена структура математической модели размещения центров на графе или сети, для этого сформулирована и решена многокритериальная задача размещения р-центра на предфрактальном графе, что позволило для разномасштабных сетей, саморазмножающихся по фиксированному алгоритму, найти аналитически и численно положение единственного центра или кратного центра с р вершинами;
-
Построена оригинальная математическая модель астрофизической задачи на предфрактальных графах, отличающаяся по сути от классических работ тем, что в ней удалось по-новому представить известные задачи исследования космоса, в частности, в этой модели решается задача оптимального размещения спутников-наблюдателей в процессе изучения небесных объектов;
-
Найдено подтверждение принципиального положения о полиномиальной сложности алгоритмов на предфрактальных графах, поскольку их вычислительная труднорешаемость при работе со всем предфрактальным графом определяется более простой структурой затравок;
-
Для предложенной модели на предфрактальных графах найдено, что вычислительная трудоёмкость известных NP-алгоритмов классической задачи выделения р-центра сведена к полиномиальной, это позволяет предварительно знать, планировать время работы алгоритма и прогнозировать объёмы вычислительных ресурсов.
Теоретическая значимость и практическая ценность результатов исследования заключается в следующем:
Полученные результаты диссертационного исследования, связанные с математическим моделированием размещения р-центров в предфрактальных графах, имеют важную общетеоретическую значимость и вызывают интерес у специалистов по теории графов и сетей, дискретных аналитиков, специалистов по структурной динамике для дальнейшего использования в последующих многочисленных научных обобщениях. В целом, настоящая работа помогает расширить области приложений теории графов, теории сетей, теории фрактальных и предфрактальных графов и многокритериальной оптимизации на фрактальные сети и их р-центры.
Предложенная математическая модель крупномасштабной кластеризации материи во Вселенной позволяет обобщить подход к проблеме исследования космоса, в частности, решать более сложную фрактальную задачу оптимального размещения спутников с минимумом расстояний между ними при исследовании небесных тел.
Построенная в диссертационной работе математическая модель и сформулированная многокритериальная задача размещения р-центра на предфрактальных графах позволяет с большей эффективностью решать сводимые к ней хорошо известные практические задачи – задачи наилучшего размещения аварийных и специальных служб, пожарных депо, больниц и постов скорой помощи, магазинов шаговой доступности в новых кварталах, распределения коммутаторов в телефонной сети, подстанций в электросетях, отделов сортировки в почтовой и телеграфной сетях.
Построенные математические модели и алгоритмы выделения р-центров на предфрактальных графах используют принципиальное положение об их полиномиальной вычислительной труднорешаемости, что позволят находить оптимальные решения не только на существующих сетях, но и закладывают необходимые свойства в строящиеся обширные сети, планируя и прогнозируя их оптимальный состав.
Результаты программной реализации диссертационного исследования переданы в Федеральную службу по интеллектуальной собственности, патентам и товарным знакам, зарегистрированы в Реестре программ для ЭВМ (свидетельство № 2011618548 от 31 октября 2011 г.), могут быть открыто и широкого использованы и внедрены аналитиками и практиками.
Личный вклад соискателя
Результаты диссертационного исследования, предложенные модели, алгоритмы и аналитические построения получены автором самостоятельно.
На защиту выносятся следующие основные положения:
-
Показано, что задачи на предфрактальных графах принципиально отличаются от задач на обычных графах и сетях, они позволяют все алгоритмические построения выполнять за полиномиальное время при невысокой степени полиномов, что открывает возможности их применения в больших сетях, вплоть до глобальных;
-
Математические модели размещения р-центра удаётся построить на предфрактальном графе. Проведено исследование метрических характеристик новых модельных объектов - предфрактальных графов, порождённых затравкой-звездой;
-
На теоретической основе математической модели размещения р-центра предложена модель крупномасштабной кластеризации материи во Вселенной;
-
Обоснована практическая необходимость многокритериальности постановки задач математического моделирования сетей принципиально нового типа. Сформулирована многокритериальная задача размещения р-центра на взвешенных предфрактальных графах. Очерчен круг задач, сводимых к задаче о р-центре на графах;
-
Предложены, обоснованы и исследованы полиномиальные алгоритмы поиска решений многокритериальной задачи размещения р-центра на предфрактальных графах. Каждый из алгоритмов оптимизирует один или несколько критериев сформулированной многокритериальной задачи. Даны гарантированные оценки по критериям, где оптимум не достигается. Для некоторых алгоритмов выделения р-центра выявлена меньшая вычислительная сложность по сравнению с известными алгоритмами поиска центров графа или сети;
-
Модели и теоретические положения реализованы с помощью программного комплекса, структура которого инвариантна от задачи к задаче, а реализованные алгоритмы покрывают все решаемые задачи исследования.
Апробация результатов исследования
Основные результаты работы докладывались и были одобрены на:
VI-ой Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001);
II-ой Международной конфер. «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001);
IV-ой Научной конференции «Региональная экономика, управление и право» (Черкесск, 2001);
IV-ой научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (Черкесск, 2002);
V-ом Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);
Международном Российско-Узбекском симпозиуме «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик, 2003);
XVI-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-16)» (Санкт-Петербург, 2003);
XVII-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-17)» (Кострома, 2004);
VI-ом Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2004);
Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2004);
Всероссийской научно-практической конфер. «Инвестиционная привлекательность туристических фирм и мест рекреации регионов» (Нижний Архыз, 2004);
III-ей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической проблемы математической биологии, информатики и физики» (Нальчик, 2006):
I-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2006);
II-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007);
Региональной научно-практической конфер. «Рациональные пути решения социально-экономических и научно-технических проблем региона» (Черкесск, 2008);
III-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2008);
VI-ой Всероссийской научно-практической конфер. «Перспективные системы и задачи управления» и III-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011» (Таганрог, 2011);
научных семинарах филиала Южного федерального университета в г. Черкесске (Черкесск, 2002-2011).
Публикации
Основные результаты диссертационного исследования изложены в 33 опубликованных научных работах (общим объёмом 9.5 п.л.) автора (в том числе 8.5 п.л. самого автора), в их числе 4 - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК.
Структура и объём диссертации
Диссертация состоит из введения, трёх разделов, заключения, библиографического списка использованных материалов, приложения. Текст диссертации изложен на 157 страницах, включает 30 рисунков, описание программного комплекса насчитывает 10 страниц. Список использованной литературы содержит 160 источников.
