Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

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

МНОГОКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ

МОДЕЛЬ РАЗМЕЩЕНИЯ PЦЕНТРА

НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ

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

численные методы иакомплексыапрограмм

АВТОРЕФЕРАТ

диссертации на соискание учёной степени

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

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

Работа выполнена на кафедре математики в ФГБОУ ВПО

Северо-Кавказская государственная

гуманитарно-технологическая академия

(Карачаево-Черкесская Республика, г. Черкесск)

Научный руководитель: доктор физико-математических наук,

профессор

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

Официальные оппоненты:  доктор физико-математических наук,

доцент

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

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

главный научный сотрудник

Броневич Андрей Георгиевич

Ведущая организация: Кубанский государственный университет

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

355009, г. Ставрополь, ул. Пушкина, 1, корп. 1, ауд. 214.

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

Ставропольского государственного университета

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

Учёный секретарь совета Д212.256.08

по защите докторских и кандидатских

диссертаций, кандидат физико-

математических наук, доцент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цели и задачи диссертационного исследования

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

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

  1. Обозрение классических подходов к построению математических моделей и к решению задач размещения центра и кратных центров на графах и сетях;
  2. Формулировка многокритериальной задачи размещения р-центра на предфрактальном графе с интерпретацией предложенных критериев;
  3. Построение и исследование математической модели размещения кратного центра или р-центра на предфрактальном графе;
  4. Исследование свойств отдельного класса предложенных математических моделей - предфрактальных графов, порождённых затравкой-звездой;
  5. Получение аналитических формул и построение алгоритмов нахождения оптимальных решений сформулированной задачи с подсчётом гарантированных временных оценок для алгоритмов, выделяющих неоптимальные решения;
  6. Полезное использование того важного свойства предфрактальных структур, по которому вычислимость алгоритмов на этих структурах полиномиальна, ибо базируется на трудоёмкости анализа только его затравок;
  7. Разработка вариативной архитектуры программного комплекса, алгоритмов и самих программ, допускающих реализацию на персональных компьютерах применительно ко всем этапам предложенной методологии.

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

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

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

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

Научная новизна диссертационного исследования:

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие основные положения:

  1. Показано, что задачи на предфрактальных графах принципиально отличаются от задач на обычных графах и сетях, они позволяют все алгоритмические построения выполнять за полиномиальное время при невысокой степени полиномов, что открывает возможности их применения в больших сетях, вплоть до глобальных; 
  2. Математические модели размещения р-центра удаётся построить на предфрактальном графе. Проведено исследование метрических характеристик новых модельных объектов - предфрактальных графов, порождённых затравкой-звездой;
  3. На теоретической основе математической модели размещения р-центра предложена модель крупномасштабной кластеризации материи во Вселенной;
  4. Обоснована практическая необходимость многокритериальности постановки задач математического моделирования сетей принципиально нового типа. Сформулирована многокритериальная задача размещения р-центра на взвешенных предфрактальных графах. Очерчен круг задач, сводимых к задаче о р-центре на графах;
  5. Предложены, обоснованы и исследованы полиномиальные алгоритмы поиска решений многокритериальной задачи размещения р-центра на предфрактальных графах. Каждый из алгоритмов оптимизирует один или несколько критериев сформулированной многокритериальной задачи. Даны гарантированные оценки по критериям, где оптимум не достигается. Для некоторых алгоритмов выделения р-центра выявлена меньшая вычислительная сложность по сравнению с известными алгоритмами поиска центров графа или сети;
  6. Модели и теоретические положения реализованы с помощью программного комплекса, структура которого инвариантна от задачи к задаче, а реализованные алгоритмы покрывают все решаемые задачи исследования.

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

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

  • 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 источников.

ОСНОВНОЕ содержание ДИССЕРТАЦИОННОЙ работы

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

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

Теоремаа1 Вычислительная сложность алгоритма Флойда на графе , где - множество вершин, Ц  множество рёбер, равна , где .

Теоремаа2 Вычислительная сложность метода взвешенных расстояний на графе равна , где .

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

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

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

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

Рёбра предфрактального графа , появившиеся на -ом этапе порождения, будем называть рёбрами ранга l. Новыми рёбрами предфрактального графа назовем рёбра ранга , а все остальные рёбра предфрактального графа назовем старыми.

При удалении из предфрактального графа всех рёбер рангов получим множество , блоков r-го ранга, где - порядковый номер блока. Термином подграф-затравка будем называть блок Bl,s(1), s = 1..nl-1 первого ранга предфрактального графа Gl, l = 1..L, из порождающей траектории. Мощность множества , , всех подграф-затравок из траектории графа равна .

На рис.а1. изображена траектория предфрактального графа , порождённого затравкой - 4-вершинным графом. Самыми жирными линиями нарисованы рёбра подграф-затравки . Линиями средней жирности нарисованы рёбра подграф-затравок , , и . И, наконец, тонкими линиями нарисованы новые рёбра предфрактального графа , которые образуют подграф-затравки , .

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

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

Будем говорить, что предфрактальный граф вершинно взвешен, если каждой вершине приписано действительное число , где .

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

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

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

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

Всевозможные подмножества предфрактального графа образуют множество допустимых решений (МДР) .

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

,                                         (1)

,                                                       (2)

где - число разделения;

,                                                       (3)

где - радиус отдельного центра;

,                                                               (4)

где - количество типов центров;

,                                                                 (5)

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

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

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

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

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

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

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

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

  1. L - ранг предфрактального графа модели, который определяет собой иерархический уровень-образование;
  2. - число вершин в затравке типа ;
  3. - коэффициент масштабирования для оценки отношения длин рёбер соседних рангов;
  4. - интервал значений длин рёнбер rго  ранга;
  5. - интервал значений диаметров иерархических образований -го уровня, .

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

  • нижняя и верхняя оценки радиуса предфрактального графа , где , выражается неравенством:

;  (6)

  • нижняя и верхняя оценки диаметра предфрактального графа , где , выражается неравенством:

.         (7)

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

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

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

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

Теоремаа4 Алгоритм выделяет центр на предфрактальном графе , оптимальный по третьему и четвёртому критериям, оцениваемый по первому и второму критериям: ,  .

На рис.а2 представлен пример поиска центра предфрактального графа . Предфрактальный граф взвешен в соответствие с правилом взвешивания рёбер, у него начальный отрезок , а весовой коэффициент . Алгоритм поиска центра начинает свою работу с подграф-затравок третьего ранга. Таким образом, центром предфрактального графа является вершина , для  которой число разделения минимальное: . Радиус предфрактального графа равен числу разделения вершины : .

Пример, рассмотренный на рис.а2, даёт следующие значения критериев и : . Вычислив оценки этих критериев по формулам из теоремыа3, получаем:

,

.

Оценка критериев верна:

,

.

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

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

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

Следствиеа3.2 Центром всякого центрированного предфрактального графа является центр графа для всех , 3, Е, L.

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

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

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

  1. На основе классических моделей размещения центра графа показано NP-полное решение задачи размещения р-центра в обыкновенных графах и на этой основе сформулированы основные требования к математическому построению модели размещения центра в предфрактальных графах с полиномиальными оценками;
  2. Построена и исследована математическая модель задачи размещения кратного центра (в частности, р-центра) на предфрактальном графе;
  3. Сформулирована и интерпретирована задача размещения р-центра на взвешенных предфрактальных графах как многокритериальная, обоснована практическая необходимость многокритериальной постановки задачи, обоснованы предложенные критерии. Очерчен круг многих задач, сводимых к задаче о нахождении р-центра на предфрактальных графах;
  4. Описаны, обоснованы и построены полиномиальные алгоритмы, которые находят решение многокритериальной задачи математического моделирования размещения р-центра на предфрактальных графах. Каждый алгоритм оптимизирует один или несколько критериев задачи. Даны гарантированные оценки по критериям, по которым оптимум не достигается. Для некоторых алгоритмов выделения р-центра выявлено их превосходство по вычислительной сложности над известными алгоритмами поиска р-центра в обыкновенных графах;
  5. Исследованы топологические свойства и найдены метрические характеристики предфрактальных графов, порождённых затравкой-звездой;
  6. Подсчитана временная вычислительная сложность или характеристика труднорешаемости алгоритмов, выделяющих неоптимальные решения. Проверенная во всех случаях их вычислительная трудоёмкость подтвердила то положение, что на предфрактальных графах многие алгоритмы решаемы полиномиально;
  7. Построена модель крупномасштабной кластеризации материи во Вселенной, что помогает решению задач по оптимизации размещения спутников-наблюдателей с минимумом расстояний от Земли и между спутниками;
  8. Построен комплекс программ в целях реализации системы поддержки принятия решений, программный комплекс вариативно перестраивает свою структуру в зависимости от набора решаемых задач.

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

СЛЕДУЮЩИЕ РАБОТЫ

Публикации в ведущих рецензируемых журналах и изданиях,

определённых ВАК:

  1. Узденов А.А., Кочкаров Р.А. Алгоритм поиска центра предфрактального графа, смежность старых рёбер которого сохраняется // Вестник Северо-Кавказского государственного технического университета. - 2011. - № 1. 0.35 п.л., в т.ч. автора 0.3 п.л.;
  2. Узденов А.А. Алгоритм поиска внешнего центра предфрактального графа, смежность старых рёбер которого сохраняется // Доклады Адыгской (Черкесской) Международной академии наук. - 2010. - Том 12. - № 2. 0.29 п.л.;
  3. Узденов А.А., Кочкаров Р.А. Алгоритм поиска внешне-внутреннего центра предфрактального графа с сохранением смежности старых рёбер // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. - 2010. - № 3 (101). - С. 145-149. 0.65 п.л., в т.ч. автора 0.6 п.л.;
  4. Узденов А.А., Букка Е.С., Кочкаров Р.А. Алгоритм поиска внешнего центра предфрактального графа // Известия Кабардино-Балкарского научного центра РАН. - 2010. - № 5 (37). Часть II. - С. 31-36. 0.47 п.л., в т.ч. автора 0.4 п.л.;

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

  1. Узденов А.А., Кочкаров Р.А., Урусова Г.З. Оценка сложности алгоритма выделения центра предфрактального графа, смежность старых рёбер которого сохраняется // Сборник материалов VI-ой Всероссийской научно-практичес- кой конференции Перспективные системы и задачи управления и III-ей Молодёжной школы-семинара Управление и обработка информации в технических системах - Управление 2011. - Таганрог: Таганрогский технологический институт Южного федерального университета, 2011. - С. 283-286. 0.25 п.л., в т.ч. автора 0.2 п.л.;
  2. Узденов А.А., Салпагарова Л.У. Гарантированные оценки р-медианы на предфрактальном графе с затравкой регулярной степени // Сборник материалов III-ей Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 247-248. 0.4 п.л., в т.ч. автора 0.3 п.л.;
  3. Узденов А.А., Салпагарова Л.У. Параллельный алгоритм поиска р-центра на предфрактальном графе // Сборник материалов III-ей Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 235-236. 0.4 п.л., в т.ч. автора 0.3 п.л.;
  4. Узденов А.А. Эффективный алгоритм построения р-центра предфрактального графа с затравкой регулярной степени // Материалы Региональной научно-практической конференции Рациональные пути решения социально-экономических и научно-технических проблем региона. - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2008. Часть I. 0.05 п.л.;
  5. Узденов А.А., Павлов Д.А. Разработка и исследование задачи распознавания предфрактального графа с затравкой - простая цепь // Материалы II-ой Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2007. - С.а191-193. 0.15 п.л., в т.ч. автора 0.1 п.л.;
  6. Узденов А.А., Эльканова Л.М. Двухпараметрическая шестикритериальная задача о р-центрах // Материалы II-ой Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2007. - С. 188-190. 0.12 п.л., в т.ч. автора 0.1 п.л.;
  7. Узденов А.А., Павлов Д.А. Об одной многокритериальной задаче о р-медианах на предфрактальных графах // Электронный журнал Исследовано в России, . - 2007. - № 10. - С. 1958-1961. 0.29 п.л., в т.ч. автора 0.25 п.л.;
  8. Узденов А.А., Кочкаров А.М. Эффективный алгоритм построения р-центров в иерархических системах // Известия Таганрогского государственного радиотехнического университета. Тематический выпуск трудов I-ой Всероссийской научно-практической конференции Перспективные системы и задачи управления. - Таганрог: Издательство ТРТУ, 2006. - №а3. - С.а290-296. 0.17 п.л., в т.ч. автора 0.15 п.л.;
  9. Узденов А.А., Кочкаров Р.А. Об одной многокритериальной задаче выделения р-центров на предфрактальном графе // Труды III-ей Международной конференции Нелокальные краевые задачи и родственные проблемы матемантической биологии, информатики и физики. - Нальчик: Издательство НИИ ПМиА КБН - РАН, 2006. - С. 286-288. 0.17 п.л., в т.ч. автора 0.15 п.л.;
  10. Узденов А.А., Кочкаров Р.А. Алгоритм выделения р-центров на предфрактальном графе // Вестник Северо-Кавказского государственного технического университета. - 2006. - №а5 (9). - С. 44-46. 0.35 п.л., в т.ч. автора 0.3 п.л.;
  11. Узденов А.А., Кочкаров Р.А. Задача выделения р-центра с гарантированными оценками на предфрактальном графе с затравкой - полный n-вершинный граф // Известия Таганрогского государственного радиотехнического университета. Специальный выпуск № 8. - Таганрог: Издательство ТРТУ, 2004. - С.а305-306. 0.1 п.л., в т.ч. автора 0.05 п.л.;
  12. Павлов Д.А., Кочкаров А.А., Узденов А.А. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах // Препринт Специальной астрофизической обсерватории (САО) РАН №а198. - Нижний Архыз: Издательство САО РАН, 2004. - 15ас. 0.76 п.л., в т.ч. автора 0.70 п.л.;
  13. Узденов А.А., Павлов Д.А. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой - полным n-вершинным графом // Препринт Специальнойаастрофизической обсерватории (САО) РАН №а201. - Нижний Архыз: Издательство САО РАН, 2004. - 8ас. 0.53 п.л., в т.ч. автора 0.45 п.л.;
  14. Узденов А.А. Гарантированные оценки р-медиан на предфрактальном графе с затравкой - полным n-вершинным графом, ребром, n-вершинной звездой // Препринт Специальнойаастрофизической обсерватории (САО) РАН №а202. - Нижний Архыз: Издательство САО РАН, 2004. - 10ас. 0.65 п.л.;
  15. Узденов А.А.  Задача выделения р-центра с гарантированными оценками // Материалы VI-гоаВсероссийского симпозиума Математическое моделирование и компьютерные технологии. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2004. - С.а11. 0.12 п.л.;
  16. Узденов А.А.  Задача выделения р-центра с гарантированными оценками на предфрактальном графе с затравкой - двудольный граф // Материалы Российской конференции Дискретный анализ и исследование операций. - Новосибирск: Издательство Института математики имени С.Л. Соболева СО РАН, 2004. - С.а116. 0.11 п.л.;
  17. Узденов А.А. Гарантированные оценки р-медиан на предфрактальном графе с затравкой - полный n-вершинный граф // Материалы XVII-ой Международной научной конференции Математические методы в технике и технологиях (ММТТ-17). - Кострома: Издательство Костромского государственного технического университета, 2004. Тома1. - С.а180181. 0.17 п.л.;
  18. Узденов А.А., Салпагаров С.И. Задача об абсолютном р-центре на предфрактальных графах // Материалы Всероссийской научно-практической конференции Инвестиционная привлекательность туристических фирм и мест рекреации регионов. - Нижний Архыз: Издательство Ростовского государственного экономического университета РИНХ, САО РАН, 2004. - С.а8486. 0.18 п.л., в т.ч. автора 0.15 п.л.;
  19. КоркмазовааЗ.О., УзденоваА.А. PL-медиана предфрактального графа с затравкой - леса// Материалы Международного Российско-Узбекского симпозиума Уравнения смешанного типа и родственные проблемы анализа и информатики. - Нальчик: Издательство НИИ ПМиА КБН - РАН, 2003. - С.а157-158. 0.06 п.л., в т.ч. автора 0.05 п.л.;
  20. Узденов А.А. Алгоритм определения абсолютных р-центров на предфрактальных графах // - Черкесск: Карачаево-Черкесская государств. технологическая академия. Депонировано в ВИНИТИ, №а1975-В2003. - 2003. - С.а29. 0.33 п.л.;
  21. Узденов А.А. Гарантированные оценки р-медиан на предфрактальных графах // - Черкесск: Карачаево-Черкесская государственная технологическая академия. Депонировано в ВИНИТИ, № 1976-В2003. - 2003. - С.а27. 0.33 п.л.;
  22. Узденов А.А. Полиномиальный алгоритм решения многокритериальной задачи о р-медианах на предфрактальных графах // Материалы XVI-ой Международной научной конферен. Математические методы в технике и технологиях (ММТТ-16). - СПб: Издательство Санкт-Петербургского государственного технического ин-та (технического ун-та), 2003. - Тома1. - С.а187190. 0.18 п.л.;
  23. Узденов А.А. Математическая модель задач размещения на предфрактальных и фрактальных графах // - Черкесск: Карачаево-Черкесская госуд. технологическая акад. Депонировано в ВИНИТИ, №а767-В2002. - 2002. - С.а211. 0.65 п.л.;
  24. Узденов А.А. Полиномиальный алгоритм решения двухкритериальной задачи о р-медианах // Материалы V-гоаВсероссийского симпозиума Математическое моделирование и компьютерные технологии. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2002. - С. 39. 0.12 п.л.;
  25. Узденов А.А. Многокритериальная задача размещения на предфрактальных и фрактальных графах // Сборник трудов IV-ой научно-практической конференции Решение научно-технических и социально-экономических проблем современности. - Черкесск: Издательство Карачаево-Черкесского государственного технологического института, 2002. Часть II. - С.а46. 0.12 п.л.;
  26. Узденов А.А., Кочкаров А.М. Задача о р-медиане на предфрактальных графах // Материалы II-ой Международной конференции Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. - Нальчик: Издательство НИИ ПМиА КБН - РАН, 2001. - С.а163164. 0.06 п.л., в т.ч. автора 0.05 п.л.;
  27. Узденов А.А., Кочкаров А.М. Математическая модель прогнозирования свойств крупномасштабной кластеризации материи во Вселенной на предфрактальных графах // Труды IV-ой научной конфер. Региональная экономика, управление и право. - Черкесск: Издательство Карачаево-Черкесского государственного технологического института, 2001. - С.а2527. 0.12 п.л., в т.ч. автора 0.1 п.л.;
  28. Узденов А.А. Определение гравитационных центров L-ых уровней // Материалы VI-ой Международной конференции Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии. - Краснодар: Издательство Кубанского государственного аграрного университета, 2001. 0.17 п.л.;

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

  1. Узденов А.А. Кочкаров Р.А. Нахождение центральных вершин фрактального графа. Заявка № 2011616665 от 5 сентября 2011 г. Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Зарегистрировано в Реестре программ для ЭВМ 31 октября 2011 г., свидетельство № 2011618548. - 9 с. 0.63 п.л., в т.ч. автора 0.5 п.л.

Подписано в печать 13.12.2011 г.

Формат 60х84/16. Бумага типографская № 1.

Гарнитура Times New Roman.

Условно-печатных листов 1.0. Тираж 100 экз.

Заказ 289. Типография издательства ООО Магик.

357700, г. Кисловодск, ул. Азербайджанская, 17.

Тел. 8 (87937) 7-18-77

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям