автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Многокритериальная математическая модель размещения P-центра на предфрактальных графах

На правах рукописи

005007670

Узденов Ахмат Абдуллахович

МНОГОКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАЗМЕЩЕНИЯ Р-ЦЕНТРА НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

? 2 янв тг

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Ставрополь-2011

005007670

Работа выполнена на кафедре математики в ФГБОУ ВПО «Северо-Кавказская государственная гуманитарно-технологическая академия» (Карачаево-Черкесская Республика, г. Черкесск)

Научный руководитель:

доктор физико-математических наук, профессор

Кочкаров Ахмат Магомедович .

Официальные оппоненты:

доктор физико-математических наук, доцент

Наац Виктория Игоревна;

доктор физико-математических наук, главный научный сотрудник Броневич Андреи Георгиевич

Ведущая организация:

Кубанский государственный университет

Защита состоится « 18 » января 2012 г. в 14 часов 30 минут на заседании совета по защите докторских и кандидатских диссертаций Д212.256.08 ФГБОУ ВПО «Ставропольский государственный университет» по адресу: 355009, г. Ставрополь, ул. Пушкина, 1, корп. 1, ауд. 214.

С диссертацией можно ознакомиться в научной библиотеке Ставропольского государственного университета

Автореферат разослан « 15 » декабря 2011 г.

Учёный секретарь совета Д212.256.08 по защите докторских и кандидатских диссертаций, кандидат физико-математических наук, доцент

Копыткова Л.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА?АБОТЫ

Актуальность темы исследования

В современном мире всё чаще приходится проектировать, строить, обслуживать системы, состоящие из большого количества элементов, соединённых многими связями друг с другом, так называемые «сложные системы». При этом связи (бинарные отношения) между элементами с навешиваемыми на них скалярными характеристиками могут изменяться во времени. Порождение и исследование процессов изменения связей между элементами системы или способов изменения инцидентора графа (сети) и другие структурные преобразования в системе относят к новой математической дисциплине, называемой «структурной динамикой». К таким практическим системам в первую очередь следует отнести современные коммуникационные и информационные сети, объём и масштаб которых в процессе роста, развития и эксплуатации могут претерпевать значительные топологические, пространственные и количественные метрические изменения, оставаясь структурно инвариантными.

В таких сетях хорошо известная в дискретной математике задача о назначениях, в частности, о размещении центров, приобретает новый смысл. Для решения современных задач структурной динамики становится где-то сложно, а где-то невозможно использовать классическую теорию графов, поскольку необходимо приходится моделировать динамические структуры с большим количеством элементов и ещё большим количеством отношений (связей) между ними. Связи между элементами перестают быть тривиальными бинарными отношениями, они часто приобретают фрактальную природу. Для успешного математического моделирования подобных систем приходится пользоваться достаточно новыми математическими объектами - «фрактальными и предфрактальными графами».

В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования или средств обслуживания в сетях или на графах. В частности, если граф представляет сеть дорог, а вершины графа соответствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, полицейских участков, пожарных частей и многих других крайне необходимых предприятий и служб. В таких случаях критерий оптимальности может состоять в минимизации суммарного расстояния, максимального расстояния, стоимости или времени проезда и т.д. от пункта обслуживания до самой удалённой вершины графа, т.е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить не один, а несколько таких пунктов обслуживания. При этом самая отдалённая вершина графа должна находиться на минимально возможном расстоянии по крайней мере от одного пункта обслуживания. К таким задачам прежде всего относят задачи размещения аварийных служб, поэтому объективным требованием в них является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. По очевидным причинам задачи такого типа называются «минимаксными задачами размещения». Полученные при решении этих задач места размещения пунктов обслуживания называются «центрами» графа.

В некоторых задачах размещения лучше всего было бы минимизировать сумму всех расстояний от вершин графа до центра графа (центра обслуживания), если предполагать, что ищется место для размещения только одного такого пункта обслуживания. Такой критерий является наиболее подходящим, например, в задаче о

размещении склада в сети дорог, где вершины сети представляют потребителей, обслуживаемых этим складом, или в задаче размещения телефонных станций в телефонной сети, где вершины сети представляют собой абонентов. Задачи такого типа вообще относятся к «минисуммным задачам размещения», хотя целевая функция является часто не просто суммой расстояний, а суммой различных функций от расстояний. Места размещения пунктов обслуживания, полученные в результате решения минисуммной задачи, называются «медианами» графа.

В более общих и более сложных практических задачах появляется возможность рассматривать и строить не один центр в одной вершине, а множество из р-точек илир-вершин, которые и образуют «кратный центр» или '«р-центр».

В классической теории графов перечень работ и список исследователей, которые решали задачу размещения центров, огромен. Достаточно сослаться на работы Н. Кристофидеса, C.JI. Хакими, Д. Дейкстра, С. Сингера, К. Бержа, A.A. Зыкова, Ф. Харари, Г. Фрэнка, И. Фриша, О. Ope, Р. Басакера, Т. Саати, Г.М. Адельсон-Вельского, Е.А. Диница, A.B. Карзанова, Р. Уилсона, JI. Форда, Д. Фалкерсона, В.А. Евстигнеева, Р.В. Флойда.

Исследования в области структурной динамики сложных систем с привлечением фрактальных и предфрактальных графовых структур ведутся в России в научных школах Института проблем управления имени В.А. Трапезникова РАН, Института прикладной математики имени М.В. Келдыша РАН, Вычислительного центра имени A.A. Дородницына РАН.

Благодаря исследованиям, проводимым в научной школе профессора A.M. Кочкарова в Северо-Кавказской государственной гуманитарно-технологической академии, фрактальные (предфрактальные) графы получили распространение как инструмент моделирования «сложных динамических систем». Это происходит из-за нарастающей потребности построения многокритериальных моделей и решения оптимизационных задач в сложных системах, обогащенных и отягощенных быстрым изменением во времени нестационарных переменных современных конъюнктур.

В диссертационной работе проводится математическое моделирование, исследование процесса и решение задач «.многокритериального размещения р-центра на предфрактальных графах» с их алгоритмической и программной реализацией.

Соответствие темы диссертации требованиям паспорта специальности

Диссертация выполнена в соответствие с пунктами 1 «Разработка новых математических методов моделирования объектов и явлений»; 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; 6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; 8 «Разработка систем компьютерного и имитационного моделирования» «Паспорта специальности 05.13. 18 - математическое моделирование, численные методы и комплексы программ (физико-математические науки)» ВАК Министерства образования и науки РФ.

Объектом исследования являются

структуры сложных сетевых систем природы, общества, техники с их саморазвитием и инфотелекоммуникационными отношениями.

Предмет исследования составляют

предфрактальные графы как модели сетей, их обобщённые показатели (раскраски, центры, кратные центры, р-центры, хроматические числа) и метрические характеристики (степени вершин, длины цепей, радиусы, диаметры, медианы). Цели и задачи диссертационного исследования

Целью диссертационного исследования является разработка, построение и исследование математической модели размещения кратных или р-центров на пред-фрактальных графах как структурных образах самоподобных сетевых систем.

Реализация цели диссертационного исследования потребована решения следующих задач:

1 Обозрение классических подходов к построению математических моделей и к решению задач размещения центра и кратных центров на графах и сетях;

2 Формулировка многокритериальной задачи размещения р-центра на пред-фрактальном графе с интерпретацией предложенных критериев;

3 Построение и исследование математической модели размещения кратного центра или р-центра на предфрактальном графе;

4 Исследование свойств отдельного класса предложенных математических моделей - предфрактальных графов, порождённых затравкой-звездой;

5 Получение аналитических формул и построение алгоритмов нахождения оптимальных решений сформулированной задачи с подсчётом гарантированных временных оценок для алгоритмов, выделяющих неоптимальные решения;

6 Полезное использование того важного свойства предфрактальных структур, по которому вычислимость алгоритмов на этих структурах полиномиальна, ибо базируется на трудоёмкости анализа только его затравок;

7 Разработка вариативной архитектуры программного комплекса, алгоритмов и самих программ, допускающих реализацию на персональных компьютерах применительно ко всем этапам предложенной методологии.

Методы исследования

В диссертационной работе использовались математические методы моделирования объектов, методы многокритериальной оптимизации, синергетики, теории фракталов и теории хаоса, теории графов и сетей, теории алгоритмов, кластерный анализ. Вычислительная сложность, вычислительная трудоёмкость или трудноре-шаемость алгоритмов оценивалась согласно теории сложности алгоритмов. Достоверность и обоснованность

всех результатов диссертационного исследования подтверждается строгостью и точностью конструкций математических моделей, логическими последовательными умозаключениями при построении структур моделей, аналитикой доказательств лемм, теорем и следствий из них, предложение алгоритмов, чья труднорешаемость полиномиальна, реализацией эффективных численных и программных методов. Научная новизна диссертационного исследования:

1 Предложена структура математической модели размещения центров на графе или сети, для этого сформулирована и решена многокритериальная задача размещения р-центра на предфрактальном графе, что позволило для разномасштабных сетей, саморазмножающихся по фиксированному алгоритму, найти аналитически и численно положение единственного центра или кратного центра с р вершинами;

2 Построена оригинальная математическая модель астрофизической задачи на

предфрактальных графах, отличающаяся по сути от классических работ тем, что в ней удалось по-новому представить известные задачи исследования космоса, в частности, в этой модели решается задача оптимального размещения спутников-наблюдателей в процессе изучения небесных объектов;

3 Найдено подтверждение принципиального положения о полиномиальной сложности алгоритмов на предфрактальных графах, поскольку их вычислительная труднорешаемость при работе со всем предфрактальным графом определяется более простой структурой затравок;

4 Для предложенной модели на предфрактальных графах найдено, что вычислительная трудоёмкость известных ///'-алгоритмов классической задачи выделения р-центра сведена к полиномиальной, это позволяет предварительно знать, планировать время работы алгоритма и прогнозировать объёмы вычислительных ресурсов.

Теоретическая значимость и практическая ценность результатов исследования заключается в следующем:

Полученные результаты диссертационного исследования, связанные с математическим моделированием размещения р-центров в предфрактальных графах, имеют важную общетеоретическую значимость и вызывают интерес у специалистов по теории графов и сетей, дискретных аналитиков, специалистов по структурной динамике для дальнейшего использования в последующих многочисленных научных обобщениях. В целом, настоящая работа помогает расширить области приложений теории графов, теории сетей, теории фрактальных и предфрактальных графов и многокритериальной оптимизации на фрактальные сети и их р-центры.

Предложенная математическая модель крупномасштабной кластеризации материи во Вселенной позволяет обобщить подход к проблеме исследования космоса, в частности, решать более сложную фрактальную задачу оптимального размещения спутников с минимумом расстояний между ними при исследовании небесных тел.

Построенная в диссертационной работе математическая модель и сформулированная многокритериальная задача размещения р-центра на предфрактальных графах позволяет с большей эффективностью решать сводимые к ней хорошо известные практические задачи - задачи наилучшего размещения аварийных и специальных служб, пожарных депо, больниц и постов скорой помощи, магазинов шаговой доступности в новых кварталах, распределения коммутаторов в телефонной сети, подстанций в электросетях, отделов сортировки в почтовой и телеграфной сетях.

Построенные математические модели и алгоритмы выделения р-центров на предфрактальных графах используют принципиальное положение об их полиномиальной вычислительной труднорешаемости, что позволят находить оптимальные решения не только на существующих сетях, но и закладывают необходимые свойства в строящиеся обширные сети, планируя и прогнозируя их оптимальный состав.

Результаты программной реализации диссертационного исследования переданы в Федеральную службу по интеллектуальной собственности, патентам и товарным знакам, зарегистрированы в Реестре программ для ЭВМ (свидетельство № 2011618548 от 31 октября 2011 г.), могут быть открыто и широкого использованы и внедрены аналитиками и практиками.

Личный вклад соискателя

Результаты диссертационного исследования, предложенные модели, алгорит-

мы и аналитические построения получены автором самостоятельно. На защиту выносятся следующие основные положения:

1 Показано, что задачи на предфрактальных графах принципиально отличаются от задач на обычных графах и сетях, они позволяют все алгоритмические построения выполнять за полиномиальное время при невысокой степени полиномов, что открывает возможности их применения в больших сетях, вплоть до глобальных;

2 Математические модели размещения р-центра удаётся построить на пред-фрактальном графе. Проведено исследование метрических характеристик новых модельных объектов - предфрактальных графов, порождённых затравкой-звездой;

3 На теоретической основе математической модели размещения р-центра предложена модель крупномасштабной кластеризации материи во Вселенной;

4 Обоснована практическая необходимость многокритериальное™ постановки задач математического моделирования сетей принципиально нового типа. Сформулирована многокритериальная задача размещения р-центра на взвешенных предфрактальных графах. Очерчен круг задач, сводимых к задаче о ^-центре на графах;

5 Предложены, обоснованы и исследованы полиномиальные алгоритмы поиска решений многокритериальной задачи размещения р-центра на предфрактальных графах. Каждый из алгоритмов оптимизирует один или несколько критериев сформулированной многокритериальной задачи. Даны гарантированные оценки по критериям, где оптимум не достигается. Для некоторых алгоритмов выделения ^-центра выявлена меньшая вычислительная сложность по сравнению с известными алгоритмами поиска центров графа или сети;

6 Модели и теоретические положения реализованы с помощью программного комплекса, структура которого инвариантна от задачи к задаче, а реализованные алгоритмы покрывают все решаемые задачи исследования.

Апробация результатов исследования

Основные результаты работы докладывались и были одобрены на:

• У1-ой Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001);

• И-ой Международной конфер. «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001);

• 1У-ои Научной конференции «Региональная экономика, управление и право» (Черкесск, 2001);

• 1У-ой научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (Черкесск, 2002);

• У-ом Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2002);

• Международном Российско-Узбекском симпозиуме «Уравнения1 смешанного типа и родственные проблемы анализа и информатики» (Нальчик, 2003);

• ХУ1-ОЙ Международной научной конференции «Математические методы в технике и технологиях (ММТТ-16)» (Санкт-Петербург, 2003);

• ХУН-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-17)» (Кострома, 2004);

• У1-ом Всероссийском симпозиуме «Математическое моделирование и компь-

ютерные технологии» (Кисловодск, 2004);

• Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2004);

• Всероссийской научно-практической конфер. «Инвестиционная привлекательность туристических фирм и мест рекреации регионов» (Нижний Архыз, 2004);

III -ей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической проблемы математической биологии, информатики и физики» (Нальчик, 2006):

• 1-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2006);

• П-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007);

• Региональной научно-практической конфер. «Рациональные пути решения социально-экономических и научно-технических проблем региона» (Черкесск, 2008);

• Ш-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2008);

VI -ой Всероссийской научно-практической конфер. «Перспективные системы и задачи управления» и Ш-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011» (Таганрог, 2011);

• научных семинарах филиала Южного федерального университета в г. Черкесске (Черкесск, 2002-2011).

Публикации

Основные результаты диссертационного исследования изложены в 33 опубликованных научных работах (общим объёмом 9.5 п.л.) автора (в том числе 8.5 п.л. самого автора), в их числе 4 - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК.

Структура и объём диссертации

Диссертация состоит из введения, трёх разделов, заключения, библиографического списка использованных материалов, приложения. Текст диссертации изложен на 157 страницах, включает 30 рисунков, описание программного комплекса насчитывает 10 страниц. Список использованной литературы содержит 160 источников.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении обоснован выбор темы диссертационного исследования, актуальность диссертации, её новизна, практическая значимость. Обосновывается необходимость исследования классических задач теории графов в многокритериальной постановке для случая предфрактальных графов. Сформулированы цель и задачи исследования, представлены основные положения, выносимые на защиту. Даётся краткое изложение содержания диссертации.

В первом разделе «Задача размещения на графах» дана постановка классических теоретико-графовых задач размещения центров и представлен обзор сводимых к ним задач. Если снять ограничение, согласно которому точки (вершины) р-центра должны лежать только в вершинах графа и допустить размещение точек на рёбрах или дугах, то получающееся при этом множество из р-точек называется «абсолютным р-цеитром». Столь же особенно сложны, но и интересны задачи разме-

щения центров для графов (точнее, для сетей) с весами Су их рёбер. Веса могут представлять длины, пропускные способности, стоимости, время движения от вершины / к вершине у и пр. Вершины могут иметь веса V,, которые могут быть важностью у'-го объёкта, его ценой, размерами и т.д. Не рассматривая многих задач размещения центров (внешние и внутренние разделения и их числа, внешние и внутренние центры, внешне-внутренние центры и радиусы, абсолютные центры), скажем только, что все они достаточно трудны и их не так много (метод С.Л. Хакими, модифицированный метод С.Л. Хакими, итерационный метод, методология С. Сингера). В разделе предложено рассмотреть известные последовательные алгоритмы решения задач размещения на графах с их вычислительными (труднорешаемыми) характеристики.

Теорема 1 Вычислительная сложность алгоритма Флойда на графе О = (У,Е), где V —множество вершин, Е - множество рёбер, равна 0(пъ), где

Н1-

Теорема 2 Вычислительная сложность метода взвешенных расстояний на графе С = (У,Е) равна 0(пъ +п' +п), где п = \У\.

В первом разделе рассмотрена также обобщённая задача размещения кратного центра и алгоритмы её решения.

Во втором разделе «Многокритериальная задача размещения центров на предфрактальных графах» рассмотрены и определены новые математические конструкции, называемые фрактальными и предфрактальными графами, порождаемыми различными условиями смежности (пересечения) их «старых» рёбер.

Суть построения и определения фрактальных графов основана на операции «замены вершины затравкой» (ЗВЗ). Термином «затравка» условимся называть какой-либо связный граф Н ~ (1У,<2) . Суть операции ЗВЗ заключается в следующем. В графе б = (V, Е) у намеченной для замещения вершины V е V выделяется множество У = , у = 1, 2,... |к| смежных ей вершин. Далее из графа в удаляется вершина V и все инцидентные ей рёбра. Затем каждая вершина е V, у = 1, 2,... |к|

соединяется ребром с одной из вершин затравки Я. Вершины соединяются произвольно (случайным образом) или по некоторому правилу при необходимости.

«Предфрактальный граф» будем обозначать через = (^, £/), где ~ множество вершин графа, а Е1 — множество его рёбер. Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе / = 1,2...., I -1 графе 01 = (У/, Е[) каждую его вершину затравкой Н. На этапе / = 1 предфракталь-ному графу соответствует затравка Н. Об описанном процессе говорят, что «предфрактальный граф С]! порождён затравкой Н» (рис. 1). Процесс порождения предфрактального графа 6'£ по существу есть процесс построения последовательности предфрактальных графов С),(72,...,С/,...,(7£, называемый «траекторией». Фрактальный же граф С = {У,Е), порождённый затравкой Н, определяется «бесконечной траекторией».

Рёбра предфрактального графа С1, появившиеся на /-ом / е{1,2,..., 1} этапе порождения, будем называть «рёбрами ранга I». «Новыми» рёбрами предфракталь-

ного графа С1 назовем рёбра ранга Ь, а все остальные рёбра предфрактального графа назовем «старыми».

С, = Н С2=(¥2,Е2)

X

.0) 21

Рисунок 1 - Траектория предфрактального графа

При удалении из предфрактального графа всех рёбер рангов

/ = 1,2,..., £ - г получим множество г е {1,2,..., ¿-1} «блоков г-го ранга», где

i = \,2,...,nL r - порядковый номер блока. Термином «подграф-затравка» будем называть блок BiJ'}, s = 1..п'~' первого ранга предфрактального графа Gi, I = 1..L, из

порождающей траектории. Мощность множества 2(Gi) = {zf}, / = 1, L, s-\,n! 1

nL -1

всех подграф-затравок из траектории графа GL равна \Z(GL )j =-—.

На рис. 1. изображена траектория предфрактального графа G3 =(F3,£3), порождённого затравкой Н = (IV, Q) - 4-вершинным графом. Самыми «жирными» линиями нарисованы рёбра подграф-затравки Линиями «средней жирности» на-

(2) (2) (2) (2)

рисованы рёбра подграф-затравок z[ , z\ , и z\'. И, наконец, «тонкими» линиями нарисованы новые рёбра предфрактального графа (73, которые образуют подграф-затравки г<3\ 5 = 1,25.

Предфрактальный граф GL =(VL,EL) условимся называть «(n,q,Ь)-графом», если он порождён и-вершинной, q-рёберной связной затравкой Н = (IV, О).

Обобщением описанного процесса порождения предфрактального графа GL является случай, когда вместо единственной затравки Я используется множество затравок Н = {Н, )= {Я,,//,,..., Я, ,...,НТ}, Т>2. С уть этого обобщения состоит в том, что при переходе от графа Gl_l к графу Gt каждая вершина замещается некоторой затравкой Н, е Н, которая выбирается случайно или согласно определённому правилу, отражающему специфику моделируемого процесса или структуры.

Будем говорить, что «предфрактальный граф G[ = (VL, Е,) вершинно взвешен», если каждой вершине veVL приписано действительное число n(i') s [a,b], где a,b >0.

Сформулирована многокритериальная задача размещения р-центра на взвешенных предфрактальных графах. Каждый из критериев имеет конкретную содержательную интерпретацию.

Пусть j - подмножество (содержащее р вершин) множества вершин предфрактального графа С/. Через d{x,v,) будем обозначать наикратчайшее из расстояний между вершинами множества х и вершиной v,, то есть

d{x,vi) = min[d(v,,v:)]. v,.ex

«Число разделения s(x)» для множества вершин х определяется следующим образом: s(x) = max[d(x,v ■)]■ Множество х* для которого ,у(х* ) = min[.s(x)] называется «р-центром предфрактального графа G; ».

Рассмотрим взвешенный предфрактальный граф GL =(Vl,EL), порождённый затравкой Н = (W,Q), у которой мощность множества вершин \lV\ = п, а мощность множества рёбер |g| = q.

Всевозможные подмножества {*} предфрактального графа GL образуют мно-

жество допустимых решений (МДР) X = X{GL) = {х}.

На множестве х определим векторно-целевую функцию:

fw =

Fj (х) = s(x) —> min,

где j(jc) - число разделения;

(1) (2)

(3)

(=1

где р1 - радиус отдельного центра; Fз(д;) = й->min,

где Ь. - количество типов центров; /*4 {х) =

(4)

(5)

где р - количество вершин, составляющих /нцентр.

Все критерии (2)-(5) векторно-целевой функции (1) имеют конкретную сс держательную интерпретацию.

Базируясь на математическом аппарате теории фрактальных и предфракташ ных графов, предложим математическую модель крупномасштабной кластеризаци материи во Вселенной. На основе данной модели предлагается решать проблему ог тимального размещения одного или нескольких спутников в космосе. Можно говс рить о многокритериальной задаче размещения, когда необходимо максимизироват количество охватываемых для изучения небесных объектов и минимизировать pat стояния от Земли до спутников или расстояния между спутниками.

Отметим важное для этой задачи понятие «кластера». «Кластером» в матем; тике принято называть некоторое множество связанных элементов (в частност] атомов или молекул), сохраняющих внутри системы свою индивидуальность, pas стояния (Эйлерово, манхеттеново или //-норма, сюпремум-норма, Махалонобиса др.) между элементами в кластере ограничены. Термин «кластер» получил распрс странение при описании систем, состоящих из большого числа связанных макрс скопических частиц, так чтобы в один кластер помещались только близко связанны частицы. «.Фракттъными кластерами» называют структуры, образующиеся при ас социации твёрдых аэрозолей в газе в случае диффузионного характера их движени: Основной особенностью фрактального кластера является уменьшение средне плотности частиц по мере удаления от некоего образующего кластер «центра».

За последние 30 лет были получены данные, свидетельствующие о существс зании сверхскоплений или, в другой терминологии, скоплений второго структурно го уровня. Сверхскопления сами содержат в себе несколько скоплений и имеют не правильную форму. Концентрация галактик в сверхскоплениях имеет волокнистс или сплющенное распределение. Преобладающая часть объёма Вселенной лишен галактик. В качестве скопления третьего уровня рассматривается Метагалактика, т есть видимая Вселенная, диаметр которой составляет порядка 6 500 Мпс, где оди мегапарсек составляет 31с двадцатью одним нулём метров. Для сравнения - рас стояние до скопления галактик в созвездии Волопаса составляет 650 Мпс, т.е. 2 двадцатью пятью нулями метров.

Из приведённого морфологического описания вытекает структурная соподчр

нённость звёздных систем, то есть существование иерархической структуры Вселенной. Распределения галактик имеют сгустки и разрежения во всех масштабах. Последнее соображение явилось основанием для качественного вывода о фрактальном пространственном распределении материи во Вселенной.

Предфрактальный граф, на котором базируется математическая модель крупномасштабной кластеризации материи во Вселенной, строится следующим образом. Множество затравок Н состоит из п, -вершинных звёзд-затравок, / = 1,2,..., Г. Значения параметров п, определяются статистическими данными о количестве галактик в скоплениях, скоплений в сверхскоплениях и так далее. В частности, элементом множества Я может быть 2-верщинная затравка, то есть ребро. Пусть Ь - ранг моделируемой Метагалактики. Предполагаемая для неё математическая модель строится в виде последовательности текущих графов траектории С, =(У1,Е/), /=1,2,...,£, где / = 1,2,..., Ь - этапы процесса порождения предфрактального графа В этой последовательности текущий граф С, представляет собой определённую затравку Нс <= Н. Затравка Н, представляет собой п, -вершинную звезду, где п, -количество сверхскоплений, то есть скоплений, уровень которых предшествует уровню моделируемой Метагалактики. Центру звезды-затравки Н, ставится во взаимно однозначное соответствие гравитационный центр этой Метагалактики. Висячим вершинам затравки Н, по взаимно однозначным соответствиям ставятся вышеуказанные сверхскопления. Каждому ребру этой затравки приписывается длина, величина которой соответствует расстоянию между гравитационными центрами смежных скоплений. Если сверхскопления материи представляют собой одну галактику, то в этом случае соответствующая вершина затравки блокируется, то есть эта вершина не замещается затравкой при построении траектории.

Теоретико-графовая модель Вселенной характеризуется следующим:

1 Ь - ранг предфрактального графа модели, который определяет собой (¿ + 1) иерархический уровень-образование;

2 п1 - число вершин в затравке типа /;

3 /7 - коэффициент масштабирования для оценки отношения длин рёбер соседних рангов;

4 аг,Ьг - интервал значений длин рёбер г-го ранга;

5 [ак,Рк] - интервал значений диаметров Вк иерархических образований к-го уровня, к = 1,4.

При построении траектории предфрактального графа С7 используется множество затравок Н = {Н,}, где затравка Н, является граф-звездой. Поэтому во втором разделе диссертации проведено специальное исследование метрических характеристик предфрактального графа, порождённого затравкой-звездой. Получены такие оценки для некоторых характеристик:

• нижняя и верхняя оценки радиуса предфрактального графа С;, где 1 = 1,2,..., I, выражается неравенством:

1<г(а,)<% (в)

• нижняя и верхняя оценки диаметра предфрактального графа С,, где / = 1,2,..., Ь, выражается неравенством:

2-/<Й?(С?/)<3/-1. (7)

В третьем разделе «Алгоритмы поиска центров предфрактальных графов» предложены алгоритмы поиска центров предфрактального графа. Каждый из алгоритмов оптимизирует один или несколько критериев многокритериальной задачи, по другим критериям даны гарантированные оценки.

Для многокритериальной задачи размещения /»-центра предфрактального графа разработаны и исследованы следующие полиномиальные алгоритмы:

* алгоритм а1 поиска внешнего центра предфрактального графа, смежност «старых» рёбер которого сохраняется;

■ алгоритм аг поиска внутреннего центра предфрактального графа, смежност «старых» рёбер которого сохраняется;

■ алгоритм аъ поиска внешне-внутреннего центра предфрактального граф; смежность «старых» рёбер которого сохраняется;

■ алгоритм о-4 поиска центра предфрактального графа, смежность «старых рёбер которого сохраняется;

■ алгоритм /?, поиска р-центра предфрактального графа, смежность «старых рёбер которого сохраняется, алгоритм позволяет построить /»-цент предфрактального графа для р = п1л вершин, он основан на алгоритме выделени центра на графе;

■ алгоритм р2 поиска р-центра предфрактального графа, смежность «стары* рёбер которого сохраняется, алгоритм позволяет построить р-центр для р = п1' вершин, он работает только на блоках второго ранга;

" алгоритм ¡5 поиска р-центра предфрактального графа, смежность «стары* рёбер которого сохраняется, алгоритм является обобщением алгоритма /Ь работает только на блоках первого ранга предфрактального графа.

Теорема 3 Вычислительная сложность алгоритма ог4 на предфрактально

графе 0^=(Уь,Ес), порождённом затравкой И = (IV,О), где \У,\ = N и \Щ = >

равна 0(4п2 ■ N).

Теорема 4 Алгоритм а4 выделяет центр х. на предфрактальном гpaq = оптимальный по третьему Г3(х4) и четвёртому /\,(х4) критерия,

в!' — 1 в1 —1 оцениваемый по первому и второму критериям: а——— < ^(х4)< Ь(п-1) ———

0 — 1 и — 1

_ 1 _ 1

а--- < Е2(х4 ) < Ь{п-1)--.

в-\ 2 0-1

На рис. 2 представлен пример поиска центра предфрактального 1рафа б Предфрактальный граф взвешен в соответствие с правилом взвешивания рёбер, него начальный отрезок [а;6] = [9;18], а весовой коэффициент в = 1/3. Алгорш поиска центра начинает свою работу с подграф-затравок третьего ранга. Таким о

разом, центром предфрактального графа G3 является вершина х®, для которой число разделения минимальное: х* = х®. Радиус предфрактального графа С3 равен числу разделения вершины х*: р = s(x*) = 20,5.

Рисунок 2 - Поиск центра предфрактального графа . Пример, рассмотренный на рис. 2, даёт следующие значения критериев ^ (х4) и ^С**): ^,(х4)= Г2(х4) = р = я(х*) = 20,5. Вычислив оценки этих критериев по формулам из теоремы 3, получаем:

Оценка критериев верна: ^(х4) = ^(х4) = 20,5<52, ^(х4) = ^2(Х4) = 20,5>13.

В третьем разделе также исследованы центрированные предфрактальные графы, порождённые затравкой-звездой.

Пусть - предфрактальный граф, порождённый затравкой-звездой

Н = (И7,0). Если при порождении предфрактального графа замещение вершин проводится по следующему принципу: вершины предфрактального ориентированного графа являются центрами подграф-затравок предфрактального графа для всех 1 = 2, 3, ..., то предфрактальный граф будем называть «центрированным».

Следствие 3.1 Центром всякого центрированного предфрактального гра$ С, является центр графа С,. Л

Следствие 3.2 Центром всякого центрированного предфрактального гра4

0 ¡является центр графа б, для всех I =2, 3,..., Ь.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

В результате выполнения работы в диссертационном исследовательском пр< екте построена новая математическая модель задачи размещения кратного центра I частности, р-центра) на предфрактальном графе:

1 На основе классических моделей размещения центра графа показано ЫР полное решение задачи размещения р-центра в обыкновенных графах и на этой 01 нове сформулированы основные требования к математическому построению модел размещения центра в предфрактальных графах с полиномиальными оценками;

2 Построена и исследована математическая модель задачи размещения кратног центра (в частности, р-центра) на предфрактальном графе;

3 Сформулирована и интерпретирована задача размещения р-центра на взв( шенных предфрактальных графах как многокритериальная, обоснована практич( екая необходимость многокритериальной постановки задачи, обоснованы предлс женные критерии. Очерчен круг многих задач, сводимых к задаче о нахождении; центра на предфрактальных графах;

4 Описаны, обоснованы и построены полиномиальные алгоритмы, которые т ходят решение многокритериальной задачи математического моделирования разм< щения р-центра на предфрактальных графах. Каждый алгоритм оптимизирует оди или несколько критериев задачи. Даны гарантированные оценки по критериям, г которым оптимум не достигается. Для некоторых алгоритмов выделения р-цент]: выявлено их превосходство по вычислительной сложности над известными алп ритмами поиска р-центра в обыкновенных графах;

5 Исследованы топологические свойства и найдены метрические характерисп ки предфрактальных графов, порождённых затравкой-звездой;

6 Подсчитана временная вычислительная сложность или характеристика тру; норешаемости алгоритмов, выделяющих неоптимальные решения. Проверенная в всех случаях их вычислительная трудоёмкость подтвердила то положение, что } предфрактальных графах многие алгоритмы решаемы полиномиально;

7 Построена модель крупномасштабной кластеризации материи во Вселенно! что помогает решению задач по оптимизации размещения спутников-наблюдателе с минимумом расстояний от Земли и между спутниками;

8 Построен комплекс программ в целях реализации системы поддержки прин; тия решений, программный комплекс вариативно перестраивает свою структуру зависимости от набора решаемых задач.

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ

Публикации в ведущих рецензируемых журналах и изданиях, определённых ВАК:

1 Узденов A.A., Кочкаров P.A. Алгоритм поиска центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Вестник СевероКавказского государственного технического университета. - 2011. - № 1. 0.35 п.л., в т.ч. автора 0.3 п.л.;

2 Узденов A.A. Алгоритм поиска внешнего центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Доклады Адыгской (Черкесской) Международной академии наук. - 2010. - Том 12. - № 2. 0.29 п.л.;

3 Узденов A.A., Кочкаров P.A. Алгоритм поиска внешне-внутреннего центра предфрактального графа с сохранением смежности «старых» рёбер // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. - 2010. -№3 (101). - С. 145-149. 0.65 пл., в т.ч. автора 0.6 пл.;

4 Узденов A.A., Букка Е.С., Кочкаров P.A. Алгоритм поиска внешнего центра предфрактального графа // Известия Кабардино-Балкарского научного центра РАН. - 2010. - № 5 (37). Часть И. - С. 31-36. 0.47 пл., в т.ч. автора 0.4 пл.;

Публикации в других изданиях:

5 Узденов A.A., Кочкаров P.A., Урусова Г.З. Оценка сложности алгоритма выделения центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Сборник материалов VI-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011». - Таганрог: Таганрогский технологический институт Южного федерального университета, 2011. - С. 283-286. 0.25 пл., в т.ч. автора 0.2 пл.;

6 Узденов A.A., Салпагарова Л.У. Гарантированные оценки р-медианы на пред-фрактальном графе с затравкой регулярной степени // Сборник материалов III-ей Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 247-248. 0.4 пл., в т.ч. автора 0.3 пл.;

7 Узденов A.A., Салпагарова Л.У. Параллельный алгоритм поиска /»-центра на предфрактальном графе // Сборник материалов Ш-ей Всероссийской научно. практической конференции «Перспективные системы и задачи управления». -

Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 235-236. 0.4 пл., в т.ч. автора 0.3 пл.;

8 Узд снов A.A. Эффективный алгоритм построения р-центра предфрактального графа с затравкой регулярной степени // Материалы Региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-технических проблем региона». - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2008. Часть I. 0.05 пл.;

1 Узденов A.A., Павлов Д.А. Разработка и исследование задачи распознавания предфрактального графа с затравкой - «простая цепь» // Материалы Н-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологическо-

го института Южного федерального университета, 2007. - С. 191-193. 0. пл., в т.ч. автора 0.1 п.л.;

Узденов A.A., Эльканова Л.М. Двухпараметрическая шестикритериальная з дача о р-центрах // Материалы И-ой Всероссийской научно-пракгическс конференции «Перспективные системы и задачи управления». - Таганрог: И дательство Таганрогского технологического института Южного федерально! университета, 2007. - С. 188-190. 0.12 пл., в т.ч. автора 0.1 пл.; Узденов A.A., Павлов Д.А. Об одной многокритериальной задаче о р-медиан; на предфрактальных графах К Электронный журнал «Исследовано в России http://zhumal.ape.relam.ru/artic)es/2007/166.pdf. - 2007. - № 10. - С. 1958-196 0.29 пл., в т.ч. автора 0.25 пл.;

Узденов A.A., Кочкаров A.M. Эффективный алгоритм построения р-центров иерархических системах // Известия Таганрогского государственного ради* технического университета. Тематический выпуск трудов 1-ой Всероссийско научно-практической конференции «Перспективные системы и задачи ynpai ления». - Таганрог: Издательство ТРТУ, 2006. - № 3. - С. 290-296. 0.17 п л т.ч. автора 0.15 пл.;

Узденов A.A., Кочкаров P.A. Об одной многокритериальной задаче выделени р-центров на предфрактальном графе // Труды Ш-ей Международной конф( ренции «Нелокальные краевые задачи и родственные проблемы матемг тической биологии, информатики и физики». - Нальчик: Издательство НИ1 ПМиА КБНЦ РАН, 2006. - С. 286-288.0.17 пл., в т.ч. автора 0.15 пл.; Узденов A.A., Кочкаров P.A. Алгоритм выделения р-центров на предфрактал1 ном графе // Вестник Северо-Кавказского государственного техиическог университета. - 2006. - № 5 (9). - С. 44-46. 0.35 пл., в т.ч. автора 0.3 пл.; Узденов A.A., Кочкаров P.A. Задача выделения р-центра с гарантированным оценками на предфрактальном графе с затравкой - «полный л-вершинны граф» // Известия Таганрогского государственного радиотехнического универ ситета. Специальный выпуск № 8. - Таганрог: Издательство ТРТУ, 2004. С. 305-306.0.1 пл., в т.ч. автора 0.05 пл.;

Павлов Д.А., Кочкаров A.A., Узденов A.A. Об одной многокритериальной зада че выделения наибольших максимальных цепей на предфрактальных графах / Препринт Специальной астрофизической обсерватории (CAO) РАН № 198 -Нижний Архыз: Издательство CAO РАН, 2004. - 15 с. 0.76 пл., в т.ч. автор; 0.70 пл.;

Узденов A.A., Павлов ДА. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой - «полным я-вершинным графом» // Препринт Специальной астрофизической обсерватории (CAO) РАН №201 -Нижний Архыз: Издательство CAO РАН, 2004. - 8 с. 0.53 пл., в т ч "автора 0.45 пл.;

Узденов A.A. Гарантированные оценки р-медиан на предфрактальном графе с затравкой - «полным я-вершинным графом», «ребром», «я-вершинной звездой» // Препринт Специальной астрофизической обсерватории (CAO) РАН № 202. - Нижний Архыз: Издательство CAO РАН, 2004. - 10 с. 0.65 пл.; Узденов A.A. Задача выделения р-центра с гарантированными оценками // Ма-

териалы VI-го Всероссийского симпозиума «Математическое моделирование и компьютерные технологии». - Кисловодск: Издательский центр Кисловод-ского института экономики и права, 2004. - С. 11. 0.12 пл.;

) Уздгнов A.A. Задача выделения р-центра с гарантированными оценками на предфрактальном графе с затравкой - «двудольный граф» // Материалы Российской конференции «Дискретный анализ и исследование операций». - Новосибирск: Издательство Института математики имени СЛ. Соболева СО РАН, 2004.-С. 116.0.11 п.л.;

I Узденов A.A. Гарантированные оценки р-медиан на предфрактальном графе с затравкой - «полный л-вершинкый граф» // Материалы XVII-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-17)». - Кострома: Издательство Костромского государственного технического университета, 2004. Том 1.-С. 180-181. 0.17 п.л.;

I Узденов A.A., Салпагаров С.И. Задача об абсолютном р-центре на предфрак-тальных графах // Материалы Всероссийской научно-практической конференции «Инвестиционная привлекательность туристических фирм и мест рекреации регионов». - Нижний Архыз: Издательство Ростовского государственного экономического университета «РИНХ», CAO РАН, 2004. - С. 84-86. 0.18 п.л., в т.ч. автора 0.15 п.л.;

3 Коркмазова З.О., Узденов A.A. /»¿-медиана предфрактального графа с затравкой - «лес» // Материалы Международного Российско-Узбекского симпозиума «Уравнения смешанного типа и родственные проблемы анализа и информатики». - Нальчик: Издательство НИИ ПМиА КБНЦ РАН, 2003. - С. 157-158. 0.06 п.л., в т.ч. автора 0.05 пл.;

4 Узденов A.A. Алгоритм определения абсолютных р-центров на предфракталь-ных графах // - Черкесск: Карачаево-Черкесская государств, технологическая академия. Депонировано в ВИНИТИ, № 1975-В2003. - 2003. - С. 2-9. 0.33 пл.;

5 Узденов A.A. Гарантированные оценки р-медиан на предфрактальных графах // - Черкесск: Карачаево-Черкесская государственная технологическая академия. Депонировано в ВИНИТИ, № 1976-В2003. - 2003. - С. 2-7. 0.33 пл.;

6 Узденов A.A. Полиномиальный алгоритм решения многокритериальной задачи о р-медианах на предфрактальных графах // Материалы XVI-ой Международной научной конферен. «Математические методы в технике и технологиях (ММТТ-16)». - СПб: Издательство Санкт-Петербургского государственного технического ин-та (технического ун-та), 2003. - Том 1. - С. 187-190. 0.18 пл.;

7 Узденов A.A. Математическая модель задач размещения на предфрактальных и фрактальных графах // - Черкесск: Карачаево-Черкесская госуд. технологическая акад. Депонировано в ВИНИТИ, № 767-В2002. - 2002. - С. 2-11. 0.65 пл.;

:8 Узденов A.A. Полиномиальный алгоритм решения двухкритериальной задачи о р-медианах // Материалы V-ro Всероссийского симпозиума «Математическое моделирование и компьютерные технологии». - Кисловодск: Издательский центр Кисловодского института экономики и права, 2002. - С. 39. 0.12 пл.;

19 Узденов A.A. Многокритериальная задача размещения на предфрактальных и фрактальных графах // Сборник трудов lV-ой научно-практической конференции «Решение научно-технических и социально-экономических проблем со-

п

временности». - Черкесск: Издательство Карачаево-Черкесского государс венного технологического института, 2002. Часть II. - С. 46. 0.12 пл.;

30 Узденов A.A., Кочкаров A.M. Задача о /»-медиане на предфрактальных графах Материалы 11-ой Международной конференции «Нелокальные краевые зада1 и родственные проблемы математической биологии, информатики и физики - Нальчик: Издательство НИИ ПМиА КБНЦ РАН, 2001. - С. 163-164.0.06 п.: в т.ч. автора 0.05 п.л.;

31 Узденов A.A., Кочкаров A.M. Математическая модель прогнозирования свойс крупномасштабной кластеризации материи во Вселенной да предфрактальнь графах // Труды IV-ой научной конфер. «Региональная экономика, управлен! и право». - Черкесск: Издательство Карачаево-Черкесского государственно технологического института, 2001. - С. 25-27. 0.12 п.л., в,т.ч. автора0.1 п.л.;

32 Узденов A.A. Определение гравитационных центров L-ых уровней // Матери лы VI-ой Международной конференции «Экология и здоровье человека. Эк логическое образование. Математические модели и информационные техн логии». - Краснодар: Издательство Кубанского государственного аграрно университета, 2001.0.17 п.л.;

Свидетельство о государственной регистрации программ для ЭВМ:

33 Узденов A.A. Кочкаров P.A. Нахождение центральных вершин фрактально графа. Заявка № 2011616665 от 5 сентября 2011 г. Федеральная служба по и теллектуальной собственности, патентам и товарным знакам. Зарегистриров

• но в Реестре программ для ЭВМ 31 октября 2011 г., свидетельство . 2011618548. - 9 с. 0.63 п.л., в т.ч. автора 0.5 п.л.

Подписано в печать 13.12.2011 г. Формат 60x84/16. Бумага типографская № 1.

Гарнитура Times .New Roman. Условно-печатных листов 1.0. Тираж 100 экз. Заказ 289. Типография издательства ООО «Магик». 357700, г. Кисловодск, ул. Азербайджанская, 17. Тел. 8(87937) 7-18-77

61 12-1/365

На правах рукописи

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СЕВЕРО-КАВКАЗСКАЯ ГОСУДАРСТВЕННАЯ ГУМАНИТАРНО-ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ

УЗДЕНОВ АХМАТ АБДУЛЛАХОВИЧ

МНОГОКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАЗМЕЩЕНИЯ Р-ЦЕНТРА НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, профессор КОЧКАРОВ A.M.

Черкесск - 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.................................................................................4

1 МОДЕЛИ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ГРАФАХ.................17

1.1 Задачи размещения центров и медиан на графах......................17

1.2 Классическая постановка задачи размещения центров

в графах и сетях.................................................................18

1.3 Задача размещения /7-центра и алгоритм её решения................26

1.4 Выводы.............................................................................33

2 МНОГОКРИТЕРИАЛЬНАЯ МОДЕЛЬ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ...................34

2.1 Фрактальные и предфрактальные графы. Определение фрактального и предфрактального графов.............................34

2.2 Многокритериальная модель размещения р-центра

на предфрактальных графах................................................42

2.3 Математическая модель крупномасштабной кластеризации материи во Вселенной..........................................................43

2.4 Метрические характеристики предфрактальных графов, порождённых затравкой-звездой...........................................51

2.5 Выводы.............................................................................57

3 АЛГОРИТМЫ ПОИСКА ЦЕНТРОВ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ И ИХ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ...................58

3.1 Алгоритм щ поиска внешнего центра предфрактального

графа................................................................................58

3.2 Алгоритм а2 поиска внутреннего центра предфрактального графа, смежность «старых» рёбер которого сохраняется...........80

3.3 Алгоритм а3 поиска внешне-внутреннего центра предфрактального графа, смежность «старых» рёбер

которого сохраняется..........................................................90

3.4 Алгоритм а4 поиска центра предфрактального графа,

смежность «старых» рёбер которого сохраняется.....................99

3.5 Алгоритм р, поиска /?-центра (р = п1' ') предфрактального

графа, смежность «старых» рёбер которого сохраняется.........105

» 2

3.6 Алгоритм р2 поиска р-центра (р = п ' ) предфрактального графа, смежность «старых» рёбер которого сохраняется.........117

3.7 Алгоритм р поиска /7-центра предфрактального графа, смежность «старых» рёбер которого сохраняется....................122

3.8 Описание программного комплекса и результаты расчётов.....124

3.9 Выводы...........................................................................126

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В

ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ...................................127

БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННЫХ

МАТЕРИАЛОВ.........................................................................129

ПРИЛОЖЕНИЕ. ПРОГРАММНЫЙ КОМПЛЕКС «НАХОЖДЕНИЕ

ЦЕНТРАЛЬНЫХ ВЕРШИН ФРАКТАЛЬНОГО ГРАФА».

ТЕКСТ ПРОГРАММ С КОММЕНТАРИЯМИ.................................148

ВВЕДЕНИЕ

В современном мире всё чаще приходится проектировать, строить, обслуживать системы, состоящие из большого количества элементов, соединённых многими связями друг с другом, так называемые «сложные системы». При этом связи (бинарные отношения) между элементами с навешиваемыми на них скалярными характеристиками могут изменяться во времени. Порождение и исследование процессов изменения связей между элементами системы или способов изменения инцидентора графа (сети) и других структурных преобразований в системе относят к новой математической дисциплине, называемой «структурной динамикой». К таким практическим системам в первую очередь следует отнести современные коммуникационные и информационные сети, объём и масштаб которых в процессе роста, развития и эксплуатации может претерпевать значительные топологические, пространственные и количественные метрические изменения, при этом системы остаются структурно инвариантными.

В таких сетях хорошо известная в дискретной математике задача о назначениях, в частности, о размещении центров, приобретает новый смысл. Для решения современных задач структурной динамики становится где-то сложно, а где-то невозможно использовать классическую теорию графов, поскольку необходимо приходится моделировать динамические структуры с большим количеством элементов и ещё большим количеством отношений (связей) между ними. Связи между элементами перестают быть тривиальными бинарными отношениями, они часто приобретают фрактальную природу. Для успешного математического моделирования подобных новых систем приходится пользоваться и достаточно новыми математическими объектами - «фрактальными и предфракталъными графами».

В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования или средств обслуживания в сетях или на графах. В частности, если граф представляет сеть дорог, а вершины графа соот-

ветствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, полицейских участков, пожарных частей и многих других крайне необходимых предприятий и служб. В таких случаях критерий оптимальности может состоять в минимизации суммарного расстояния, максимального расстояния, стоимости или времени проезда и т.д. от пункта обслуживания до самой удалённой вершины графа, т.е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить не один, а несколько таких пунктов обслуживания. При этом самая отдалённая вершина графа должна находиться на минимально возможном расстоянии по крайней мере от одного пункта обслуживания. К таким задачам прежде всего относят задачи размещения аварийных служб, поэтому объективным требованием в них является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. По очевидным причинам задачи такого типа называются «минимаксными задачами размещения». Полученные при решении этих задач места размещения пунктов обслуживания называются «центрами» графа.

В некоторых задачах размещения лучше всего было бы минимизировать сумму всех расстояний от вершин графа до центра графа (центра обслуживания), если предполагать, что ищется место для размещения только одного такого пункта обслуживания. Такой критерий является наиболее подходящим, например, в задаче о размещении склада в сети дорог, где вершины сети представляют потребителей, обслуживаемых этим складом, или в задаче размещения телефонных станций в телефонной сети, где вершины сети представляют собой абонентов. Задачи такого типа вообще относятся к «мини-суммным задачам размещения», хотя целевая функция является часто не просто суммой расстояний, а суммой различных функций от расстояний. Места размещения пунктов обслуживания, полученные в результате решения минисуммной задачи, называются «медианами» графа.

В более общих и более сложных практических задачах появляется воз-

можность рассматривать и строить не один центр в одной вершине, а множество из/ьточек, которые и образуют «кратный центр» или «р-центр».

В классической теории графов перечень работ и список исследователей, которые решали задачу размещения центров, огромен. Достаточно сослаться на работы Н. Кристофидеса, C.J1. Хакими, Д. Дейкстра, С. Сингера, К. Бержа, A.A. Зыкова, Ф. Харари, Г. Фрэнка, И. Фриша, О. Ope, Р. Басакера, Т. Саати, Г.М. Адельсон-Вельского, Е.А. Диница, A.B. Карзанова, Р. Уилсо-на, J1. Форда, Д. Фалкерсона, В.А. Евстигнеева, Р.В. Флойда.

Исследования в области структурной динамики сложных систем с привлечением фрактальных и предфрактальных графовых структур ведутся в России в научных школах Института проблем управления имени В.А. Трапезникова РАН, Института прикладной математики имени М.В. Келдыша РАН, Вычислительного центра имени A.A. Дородницына РАН.

Благодаря исследованиям, проводимым в научной школе профессора A.M. Кочкарова в Северо-Кавказской государственной гуманитарно-технологической академии, фрактальные (предфрактальные) графы получили распространение как инструмент моделирования «сложных динамических систем». Это происходит из-за нарастающей потребности построения многокритериальных моделей и решения оптимизационных задач в сложных системах, обогащенных и отягощенных быстрым изменением во времени нестационарных переменных современных конъюнктур.

В диссертационной работе проводится математическое моделирование, исследование процесса размещения и решение задач «многокрил1ериального размещения р-центра на предфрактальных графах», их алгоритмической и программной реализации.

«Моделирование» - инструментальное средство для понимания сути исследуемых процессов и явлений. «Математическая модель» представляет собой формальное отражение исследуемого явления или процесса и является основным математическим инструментом для многих дисциплин прикладной

математики. Если раньше моделирование было исключительно прерогативой специалистов технических и инженерных направлений науки, то теперь оно как инструмент познания окружающего мира используется во многих отраслях современного знания [19, 29, 31].

Любая целенаправленная деятельность требует планирования и прогнозирования. Каждая из составляющих этой деятельности невозможна без понимания сути процесса в той области, где она осуществляется. Достичь удовлетворительного понимания можно с помощью адекватно построенной математической модели. На основе имеющейся математической модели возможно оптимизировать решение задачи, что позволяет делать прогнозы и планировать дальнейшие действия. Задачи автоматического управления, оптимального и адаптивного, автоматизации проектирования, эколого-экономического планирования, принятия решений, компромисса в условиях неполной информации, математического программирования и т.п. находятся в сфере деятельности специалистов по исследованию операций. Предметом их исследований становятся «сложные системы» [52, 74, 91].

Основной целью задач исследования операций с оптимизацией является оценка эффективности различных вариантов решений и выбор среди них более эффективных. В формулировке задач планирования и проектирования содержатся требования к критериям оптимальной конструкции или искомого плана. Зачастую эти требования и сами критерии являются противоречащими друг другу. Всё это приводит к «многокритериальной постановке оптимизационной задачи». В общем случае она выглядит следующим образом:

¥(х) = (Fl(x),F2(x),...,Fi(x),...,Fn(x)),

Fj (х) —» extr(max/ min), i = l,n,

где F(x) - векторно-целевая функция (ВЦФ) с критериями Fj(x), i-\,n, оптимизирующимися на множестве допустимых решений (МДР) X = {х}.

В исследовании всякой многокритериальной задачи можно выделить

три последовательных этапа.

Первый этап - построение МДР. Построение множества допустимых решений всегда связанно со спецификой той области, в которой проводится оптимизация. Построение МДР часто оказывается нетривиальной задачей. Существует ряд методов, в том числе и хорошо автоматизируемых, которые позволяют выделять МДР. При этом не только формулируется полная постановка многокритериальной задачи, но и задачи, включающей кроме МДР также векторно-целевую функцию.

На втором этапе из множества допустимых решений выделяются решения, оптимальные по Парето. Наименование указанного понятия связанно с именем итальянского ученого В. Парето (1848-1923), который одним из первых начал его использовать при математических исследованиях процесса рыночного обмена товаров. В отечественной научной литературе наиболее полное и систематическое изложение проблем, посвященных Парето-оптимальным решениям, можно найти в [14]. Это паретовское множество (ПМ) или множество эффективных решений. Решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счёт ухудшения значений других критериев. Такие решения называют векторно-несравнимыми [14].

Третий этап - принятие окончательного решения или выбора. На этом этапе из паретовского множества необходимо выбрать решение, которое будет реализовано с учётом сущности задачи и особенностей области приложения. Выбор может быть осуществлен «лицом, принимающим решение» (ЛПР) в соответствии с его личным опытом деятельности или же автоматизировано с использованием методов и подходов теории принятия решений при многих критериях [15, 35, 82].

Каждый из этапов исследования многокритериальной задачи является отдельной самодостаточной задачей. Настоящую работу следует отнести к исследованиям, связанным со вторым этапом.

Одной из широко используемых и хорошо развитых областей дискретной математики является теория графов. Методы теории графов нашли приложение во многих областях современной науки: в технике, в экономике, в биологии и химии, в исследовании надёжности, стойкости и живучести систем, в моделировании динамических систем и в управлении ими и т.д. Нередко использование методов теории графов в перечисленных областях исходило из постановки оптимизационных задач. Напомним, что появление самих графов произошло при решении Л. Эйлером по сути оптимизационной задачи о кёнигсбергских мостах. Поиск решений оптимизационных задач на графах осуществляется специализированными алгоритмами. Время решения задачи алгоритмом оценивается его вычислительной трудоёмкостью или вычислительной сложностью [3, 13, 21, 30, 69].

Вычислительная сложность определяется общим числом всех элементарных операций, произведенных алгоритмом за время его работы. В общем виде вычислительная сложность оказывается функцией /(п), которая ставит в соответствие размерность п задачи с количеством производимых алгоритмом элементарных операций. Будем считать, что /{п) есть 0^(п)), если

существует константа с, такая, что \/(п)\ < с\0^(п))\ для всех значений

п > 0. Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называют алгоритм, у которого временная сложность равна 0{р{п)), где р(п) - некоторая полиномиальная функция. Алгоритмы, которые не поддаются подобной оценке, называются экспоненциальными или ЫР-полными. С ростом размерности задачи предпочтительность полиномиальных алгоритмов перед экспоненциальными вполне очевидна. Поэтому первые называются также эффективными, а вторые - неэффективными. Задача называется труднорешаемой, если для её решения не существует полиномиального алгоритма. Таким образом, обоснованный полиномиальный алгоритм решения графовой оптимизационной задачи является одним из наи-

более полезных результатов проводимого исследования.

В диссертационной работе проводится построение математической модели, математическое моделирование размещения р-центра на предфрак-тальных графах и исследование решения этой задачи как многокритериальной, поэтому цели и задачи диссертационного исследования можно определить следующим образом. Целью диссертационного исследования является разработка, построение и исследование математической модели размещения кратных или /^центров на предфрактальных графах как на структурных образах самоподобных сетевых систем.

Реализация цели диссертационного исследования потребовала решения следующих задач:

1 Обозрение классических подходов к построению математических моделей и к решению задач размещения центра и кратных центров на обыкновенных графах и сетях.

2 Формулировка многокритериальной задачи размещения р-центра на предфрактальном графе с интерпретацией предложенных критериев.

3 Построение и исследование математической модели размещения кратного центра или /7-центра на предфрактальном графе.

4 Исследование свойств отдельного класса предложенных математических моделей - предфрактальных графов, порождённых затравкой-звездой.

5 Получение аналитических формул и построение алгоритмов нахождения оптимальных решений сформулированной задачи с подсчётом гарантированных оценок для алгоритмов, выделяющих неоптимальные решения.

6 Полезное использование того важного свойства предфрактальных структур, по которому вычислимость алгоритмов на этих структурах полиномиальна, ибо базируется на трудоёмкости анализа только его затравок.

7 Разработка вариативной архитектуры программного комплекса, алгоритмов и самих программ, допускающих реализацию на персональных компьютерах применительно ко всем этапам предложенной методологии.

Методы исследования. В диссертационной работе использовались новые математические методы моделирования объектов, методы многокритериальной оптимизации, синергетики, теории фракталов и теории хаоса, теории графов и сетей, теории алгоритмов, кластерный анализ. Вычислительная трудоёмкость или труднорешаемость алгоритмов оценивалась согласно теории сложности алгоритмов.

Достоверность и обо