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

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

<

Батчаев Ильяс Заурович

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

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

Таганрог-2004

Работа выполнена на кафедре Математики Карачаево-Черкесской государственной технологической академии.

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

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

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

профессор Наталуха Игорь Анатольевич

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

доцент Лепский Александр Евгеньевич

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

Защита состоится 30 сентября 2004 года в 14 часов на заседании диссертационного совета ДР 212.259.09 Таганрогского государственного радиотехнического университета.

С диссертацией можно ознакомиться в библиотеке ТРТУ.

Автореферат разослан 2004 года.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 347928, Ростовская область, г.Таганрог, пер. Некрасовский, 44, Таганрогский государственный радиотехнический университет. Ученый секретарь специализированного совета д.т.н., профессор -г* ^ Л.К. Бабенко

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

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

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

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

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

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

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

- исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки критериев (АЛСК);

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

- разработка нового способа задания произвольного предфрактального графа, способного адекватно отражать структуру графов этого типа;

- построение и исследование полиномиальных алгоритмов решения многокритериальной задачи покрытия предфрактальных графов звездами ранговых типов;

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

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

Работа выполнена в соответствии с пунктами 22 - «Разработка и анализ моделей информационных процессов и структур», 3.3 - «Разработка и исследование моделей данных и новых принципов их проектирования», 9.1

— «Разработка новых интернет-технологий, включая средства поиска, анализа и фильтрации информации», 10.3 - «Разработка основ ... теории графов», 14 - «Разработка теоретических основ создания программных систем для новых информационных технологий» паспорта специальности 05.13.17

- «Теоретические основы информатики».

Методологическая основа диссертации. При решении поставленных задач в работе использовались: методы теории графов; теории предфрактальных и фрактальных графов; элементы комбинаторики; методы математического программирования и многокритериальной оптимизации.

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

1. Исследование возможности решения 2-х и 3-х критериальных задач построения покрытий предфрактальных графов звездами ранговых типов с помощью АЛСК.

2. Построение новых математических моделей, сводимых к построению покрытий предфрактальных графов звездами ранговых типов.

3. Разработка и обоснование полиномиальных алгоритмов отыскания некоторых парето-оптимальных решений изучаемой оптимизационной задачи.

4. Построение эвристического алгоритма построения покрытий с указанием оценок параметров их критериального пространства.

5. Разработка и исследование методов построения предфрактальных графов с заданными свойствами.

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

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

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

Апробация работы. Научные и практические результаты, полученные в диссертации, опубликованы в 12 печатных работах и докладывались на: II Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (г. Нальчик, 2001), V Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г. Кисловодск, 2002), IV научно-практической конференции «Решение научно-практических и социально-экономических проблем современности» (г. Черкесск, 2002), Международном Российско-Узбекском симпозиуме «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Эльбрус, 2003), VI

б

Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г. Кисловодск, 2004), научных семинарах, проводимых в НИИ Прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН (г. Нальчик, 200-2003), научных семинарах профессорско-преподавательского состава КЧГТА (г. Черкесск, 20002004).

Структура диссертации. Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников из 92 наименований. Работа изложена на 118 страницах и содержит 1 страницу рисунков, 1 страницу приложения, 10 страниц списка использованных источников.

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

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

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

Введем понятие предфрактального (фрактального) графа. Пусть задано множество й = {#,,#,,...,W,,...} я, -вершинных непомеченных связных графов называемых затравками. Введем операцию замещение вершины графа затравкой, как обобщение хорошо известной операции расщепления вершины. Каждый элемент G„ (/ = 1,2.....L) последовательности графов где есть произвольная затравка множества с помеченными вершинами, а получается из GM = {У,.,.Е,_1) замещением каждой вершины последнего некоторой затравкой из й называется предфрактальным графом ранга I. При £->оо получаем граф, называемый фрактальным. Число называется рангом предфрактальяого графа. Множество EL\EL^ ребер ранга ¿называют «новыми»ребрами графа GL = (Vl,El), а все остальные - «старыми».

Обратим внимание на одну особенность предфрактального графа: если соединены новым ребром в и при переходе к предфрактальному графу ранга они замещаются затравками то ребро в графе преобразуется, и соединяет произвольные (или

выбранные по определенному правилу) две вершины, одна из которых принадлежит Я,, а вторая принадлежит Я,.

Пусть задан предфрактальный граф 01м={у1,Е1), порожденный одной или несколькими затравками множества П = {я„яа,...,я„...},

(Я, =(^,0^ = 1,2...../,...), т.е. на каждом этапе построения текущая вершина

может замещаться любым элементом из П . Граф взвешенный так, что каждому ребру ее Ес из С1 =(У1,Е1) приписывается число р{Щ>0. Здесь ребра ранга принимают соответственно веса где

- ранг ребра, - номер ребра - коэф-

фициент подобия или масштабирования.

Под звездой понимают полный двудольный граф, одна доля которого состоит из единственной вершины (центра звезды), а другая - из 5 вершин, называемых висячими. Иными словами, звезда - это совокупность ребер, инцидентных одной вершине. Число 5 назовем типом звезды. Для предфрактального («.¿)-графа ^ ранговым типом з, будем назы-

вать тип звезды все ребра которой имеют одинаковый ранг

¡, (/ = 1,2,...,£). Такую звезду будем обозначать К{, и назовем звездой рангового типа.

Остовный подграф х^{У1,Е1ж) не содержащий изолированных вершин назовем допустимым покрытием графа = {У^Е^ звездами ранговых типов, если каждая его связная компонента представляет собой звезду рангового типа.

Множество всевозможных допустимых покрытий (решений) х графа звездами ранговых типов К'и обозначим через X - {я}. На Хоп-

ределим критерии:

^¡М= N - число звезд покрытия х; (1)

= - число ранговых типов звезд покрытия х; (2)

2 - вес покрытия х. (3)

Задача покрытия предфрактальных графов звездами ранговых типов рассматривается в виде: для заданного взвешенного предфрактального порожденного связной затравкой

Я = (и'.С?) необходимо отыскать такое покрытие х из множества допустимых покрытий X, что значение каждого из критериев (1-3) (по возможности) Ъ(х) -> 1ШП, (/ = 1,2,3)1 хеХ

Решением многокритериальной (векторной) задачи с критериями (1)-(3) является паретовское множество.

Элемент дц,е X называется парето-оптимальным (или паретовским) решением (по критериям ^(»^^(х^Я^х)), если он удовлетворяет условию: не существует такого элемента уе X, чтобы среди неравенств ( = 1,2,3, было хотя бы одно строгое. При этом множество всех

парето-оптимальных решений называется паретовским и обозначается X.

Множество /г(Л,)={/г(лг):лге Х], где р{х) = (^{х\рг{х),р^х)) называется множеством достижимости, а /Г(Л") - паретовская граница множества достижимости /•"(ЛГ). Полным решением задачи или полным множеством альтернатив (ПМА) является минимальное по мощности множество Х° е X такое, что

Заметим, что в качестве приближенного решения можно рассматривать любое подмножество X' с X, для которого не имеет места включение /•"(л^с Относительное отклонение приближенного решения А* от ис-

комого полного решения оценивается вектором где

Такие приближенные решения назовем е-оптимальными покрытиями и обозначим X*. Для большей простоты вычислений вместо погрешности можно рассматривать ее верхнюю оценку где

Одним из самых популярных методов решения многокритериальных задач является АЛСК. В диссертационной работе построен предфракталь-ный (5,2)-граф, для которого с помощью АЛСК невозможно получить все элементы ПМА 2-х и 3-х критериальных задач покрытия предфрактальных графов звездами ранговых типов с критериями , Полученный

результат распространяется на случай предфрактального графа ранга два, порожденного п-вершинной затравкой, где п>4. После этого показывается существование предфрактальных графов произвольных рангов L>2, для которых многокритериальная задача неразрешима с помощью АЛСК. Таким образом, в общем случае имеют место теоремы.

Теорема 1. 2-х критериальная задача с критериями (1), (3) о покрытии произвольного предфрактального (п,Ъ)-графа (¿2 2,п ¿5) звездами ранговых типов неразрешима с помощью АЛСК

Теорема 2. 3-х критериальная задача с критериями (1)-(3) о покрытии произвольного предфрактального (П-Х^уграфа (¿2!2,лй5) звездами ранговых типов неразрешима с помощью АЛСК.

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

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

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

Рассмотрим Интернет как совокупность локальных сетей. Сопоставим каждой из них взвешенный граф, вершины которого соответствуют терминалам, ребра - сетевым соединениям, вес ребер - пропускной способности каналов. В результате получается взвешенный пред фрактальный граф в, =(у,,Е,) ранга ¿ = 5.

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

Интернете сводится к построению покрытия х предфрактального графа звездами ранговых типов. Определяются следующие критерии.

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

е " число ранговых типов звезд покрытия. Ранговый

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

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

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

дами ранговых типов, для которого значения критериев были бы

минимальными.

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

На первом этапе строим граф где под вершинами будем

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

щаются моделями республик, краев и областей, где вершины обозначают районы, получается граф С, =(Г,,£',). На четвертом этапе строим предфрак-тальный граф полученный заменой каждой вершины

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

зультате получен предфрактальный взвешенный граф <7, = (^..С,), порожденный затравками множества П = [Н1,Н1,...,Н,,...}, где каждая затравка = Д/= 1,2,...,/,...) представляет собой графовую модель отдельно взятых федеральных округов, республик, краев, областей, их районов, населенных пунктов и их микрорайонов.

Заметим, что центр МЧС вместе с обслуживаемой им территорией представляет собой звезду, центр которой определяет место расположения центра МЧС, а висячие вершины - обслуживаемые им пункты. Ребра звезды понимаются как дороги связывающие центр с потенциальными местами происшествий. Не эффективно допускать пересечения сфер деятельности отдельных центров, что на графовой модели соответствует непересечению звезд. Следует отметить, что МЧС имеет иерархию своих подразделений, т.е. на графовой модели каждая звезда должна состоять из ребер одного ранга и являться звездой рангового типа. Учитывая, что служба МЧС должна охватывать своей деятельностью всю территорию РФ, получаем, что сеть центров МЧС на графе С?} =(^,£5) соответствует покрытию х данного графа

звездами ранговых типов. Критерии являются значимыми:

- определяет число центров МЧС в РФ и с экономической точки зрения требует минимизации. - ранговый тип звезды определяет раз-

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

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

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

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

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

Теорема 3. Пусть дан предфрактальный {п,Ь)-граф Сс порож-

денный п-еершинной связной затравкой Н~{\У,0). Тогда процедура <р осуществляет разбиение графа на блоки £у',(/ = 1,2,.. Д;у = 1,2,....я"') за время х{<р) = о{ьы1), где N = - число вершин заданного предфракталъного графа.

Далее строится ряд новых алгоритмов решения многокритериальной задачи с критериями (1)-(3), имеющих полиномиальную трудоемкость.

Суть алгоритма заключается в лексикографическом упорядочении критериев, построении методом последовательного перебора альтернатив парето-оптимальных решении минимального веса с учетом упорядочения и распространении полученного результата на все затравки, состоящие из новых ребер. Учитывая, что такие затравки образуют разбиение вершин пред-фрактального графа, то объединение из покрытий звездами ранговых типов определит искомое решение, нахождение которого требует не более о(м2) шагов, где ^ = ¡^1 - число вершин предфрактального графа. Обоснованием

алгоритма является

Теорема 4. Пусть С1={у1,Е,) предфрактальный, взвешенный («,£.)-граф, аналогичным ребрам изоморфных 1-затравОК (/=2,3,...Д.) которого приписываются одинаковые веса. Тогда в случаев выполнения условия к алгоритм а, строит паретовские решения х, и х, оптимальные по третьему критерию и со следующими е-оценками по остальным критери-

Алгоритм определяет для каждой затравки, состоящей из новых ребер, возможность построения покрытия звездами одного рангового типа за действий. Для этого находятся всевозможные разбиения множества вершин затравки на равномощные подмножества и определяется возможность покрытия подграфов, порожденных этими подмножествами, одной звездой. Обоснованием алгоритма является

Теорема 5. Пусть С/А=(^,££) - предфрактальный, взвешенный (",/,)-граф, старые ребра которого не пересекаются, а аналогичным ребрам изоморфных ¡-затравок (/=2,3,...»¿) приписываются одинаковые веса Тогда

алгоритм а2 строит покрытие х звездами одного рангового типа s (если оно существует). При этом справедливы следующие оценки:

где А<1 — коэффициент пропорциональности, влияющий на изменение веса ребер.

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

Теорема 6. Пусть задан взвешенный предфрактальный (п£)-граф вь = аналогичные ребра изоморфных ¡-затравок (/=2,3,...,/.) которо-

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

В третьей главе предложен метод построения предфрактальных графов с наперед заданными характеристиками. Пусть даны натуральные числа а^а^а,, необходимо построить предфрактальный граф С1={У1,Е1) (если это возможно), для которого существует точное решение х многокритериальной задачи покрытия предфрактальных графов звездами ранговых типов со следующими значениями критериев: а,,/^*)® а1а^(х) = а,.

Для разрешения данной проблемы предложен ряд полиномиальных алгоритмов с трудоемкостью О^!^ обоснование которых дается в теоремах:

Теорема 7. Пусть заданы натуральные числа а,,аг, аг>1 и положительное рациональное число а,. Тогда алгоритм /?,, если возможно, строит взвешенный предфрактальный граф для которого существует покрытие х звездами ранговых типов удовлетворяющее условиям: и являющееся точным решением многокритериальной задачи с критериями (1.2-1.4).

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

Теорема 9. Пусть задано натуральное число а, и положительное рациональное число а,. Пусть а, является составным числом, представимым

в виде а, = «л1"', где S>1, П, L - натуральные числа, — = t - натуральное число большее двух. Тогда алгоритм строит предфрактальный граф

0L={yL,EL), для которого существует покрытие х звездами ранговых типов, являющееся точным решением многокритериальной задачи с критериями (1.2-1.4) и удовлетворяющее условиям: /•!(.*) = auF1[x) = llf^(jc) = а,. Трудоемкость алгоритма равна г{/?,)=

Теорема 10. Пусть задано натуральное число а, и положительное рациональное число aj. Тогда алгоритм fiA (по возможности) строит взвешенный предфрактальный граф Gt=(ft,£t), для которого существует точное решение х многокритериальной задачи с критериями (1.2-1.4) удовлетворяющее условиям: Fi(x)=al,F1{x) = 2,F3(x) = ai. Трудоемкость алгоритма равна г{А) = 0(^|).

Основные результаты работы заключаются в следующем.

1. Доказана неразрешимость 2-х и 3-х критериальных задач построения покрытий предфрактальных графов звездами ранговых типов с помощью АЛСК.

2. Впервые построены и исследованы фрактально-графовые модели системы контроля трафика в Интернете и сети центров МЧС РФ, сводимые к построению покрытий предфрактальных графов звездами ранговых типов.

3. Разработаны и обоснованы новые полиномиальные алгоритмы отыскания некоторых парето-оптимальных решений изучаемой оптимизационной задачи.

4. Построен «быстрый» алгоритм отыскания покрытий с указанием значений параметров критериального пространства.

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

Основные результаты работы изложены в следующих работах: 1.Батчаев И.З., Кочкаров A.M. Полиномиальные алгоритмы с оценками многокритериальной задачи на предфракталах //Вторая Международная конференция «Нелокальные краевые задачи и родственные проблемы мате-

матической биологии, информатики и физики. Тез. докл. Нальчик: НИИ ПМиА КБНЦ РАН, 2001. -С.13-14.

2.Батчаев ИЗ., Кочкаров A.M. Математическая модель задачи размещения центров технического обслуживания автомобильной компании //Вторая Международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. Тез. докл. Нальчик: НИИ ПМиА КБНЦ РАН, 2001. -С.14-16.

3.Батчаев И.З. Об одной многокритериальной задаче покрытия пред фрактальных графов звездами ранговых типов. Карачаевск, 2002, Деп. в ВИНИТИ, №724-В2002. -С.1-12.

4.Батчаев И.З. Кочкаров А.М. Об одной многокритериальной задаче покрытия минимального веса предфрактального графа звездами ранговых типов //V Всероссийский симпозиум «Математическое моделирование и компьютерные технологии» Тез.док. Кисловодск: КИЭП, 2002. -С.27-28.

5.Батчаев И.З., Кочкаров А.М. Задача покрытия предфрактального графа звездами одного рангового типа //Сб. трудов IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности». Черкесск: КЧТИ, 2002. -С.9-11.

6.Батчаев И.З. Об одной многокритериальной задаче покрытия предфрак-тальных графов звездами одного рангового типа //Известия Кабардино-Балкарского научного центра РАН, -Нальчик, №1 (8), 2002. -С.1-5.

7.Батчаев И.З. Оптимизация затравки и ранга предфрактального графа с наперед заданными ограничениями //Электронный журнал «Исследовано в России», 123,2003.-С. 1465-1472.

8.Батчаев ИЗ., Кочкаров A.M. Быстрый алгоритм на предфрактальных графах с оценками //Материалы Международной Российско-Узбекского симпозиума «Уравнения смешанного типа и родственные проблемы анализа и информатики». Нальчик-Эльбрус, 2003. -С. 108-110.

9.Батчаев И.З. Математическая модель сети центров МЧС РФ //VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004. -С.7-9.

Ю.Батчаев И.З. Математическая модель системы контроля Интернета // II Международная научно-практическая конференция «Материалы и технологии XXI века». Пенза, 2004. -С.107-110.

П.Батчаев И.З., Батчаев З.Ю. О некоторых способах задания предфрак-тального графа //Вестник Карачаево-Черкесского государственного университета. Карачаевск: КЧГУ, 2004. -С.278-285.

№14209

12.Батчаев И.З., Батчаев З.Ю. Алгоритмы построения предфрактальных графов с заданными свойствами //Вестник Карачаево-Черкесского государственного университета. Карачаевск: КЧГУ, №12,2004. -С.285-298.

В работах, опубликованных в соавторстве, лично Батчаеву И З. принадлежат следующие результаты: в [1] разработаны и описаны алгоритмы построения покрытий и вычислены оценки их трудоемкости; в [2] построена математическая модель размещения центров технического обслуживания автомобильной компании; в [5] разработан и описан полиномиальный алгоритм построения покрытий одного рангового типа; в [8] описан эвристический алгоритм построения покрытий и вычислены оценки параметров критериального пространства; в [11] разработана и описана процедура выделения блоков предфрактального графа; в [12] описана постановка задачи построения предфрактальных графов с заданными характеристиками и разработана общая идея методов ее решения.

Типография ТРТУ, ГСП 17А, Таганрог, ул. Энгельса, 1. Заказ. SsS~Q. Тираж 100 экз.

ВВЕДЕНИЕ.

ГЛАВА 1. Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов.

1.1. Необходимые обозначения и определения.

1.2. Постановка многокритериальной задачи о покрытии предфрактально-го графа звездами ранговых типов.

1.3. Исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки.

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

1.4.1. Математическая модель системы контроля трафика в Интернете.

1.4.2. Математическая модель сети центров МЧС РФ.

1.5. Выводы.

ГЛАВА 2. Полиномиальные алгоритмы построения покрытий предфрактальных графов звездами ранговых типов с оценками.

2.1. Способы задания предфрактальных графов.

2.2. Предварительные упрощения задачи.

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

2.3.1. Алгоритм построения покрытий минимального веса.

2.3.2. Алгоритм построения покрытий звездами одного рангового типа.

2.4. «Быстрый» алгоритм построения покрытия предфрактального графа звездами ранговых типов с оценками.ЛЬ

2.5. Выводы.

ГЛАВА 3. Построение предфрактальных графов с заданными характеристиками.

3.1. Формулировка проблемы и постановка задачи.

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

3.2.1. Алгоритм построения предфрактального графа, для которого число ранговых типов звезд точного покрытия больше двух.

3.2.2. Алгоритмы построения предфрактального графа, точное покрытие которого состоит из звезд одного рангового типа.

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

3.3. Выводы.

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

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

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

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

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

Перечислим некоторые из них:

- распознавание предфрактальных и фрактальных графов;

- способы их задание (представления в памяти ЭВМ);

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

- исследование разрешимости многокритериальных задач на предфрактальных графах с помощью алгоритма линейной свертки критериев;

-построение предфрактальных и фрактальных графов с заданными свойствами.

Задача построения покрытия предфрактального графа звездами ранговых типов является частным случаем задачи о наименьшем покрытии (разбиении), которая формулируется следующим образом: пусть дано множество v = {и,,и2,.,«/„} и семейство 3 = {Л',,^,---^™} множеств st с v. Необходимо отыскать подсемейство 3' = ^>h,sj2,.,s]t} семейства 3 наименьшей мощности, такое, что и^, = Y>SJt r>sjt =0, для любых Л,/е {1,2,.,*} [1].

Если под множеством v - {м,,и2,.,!/„} понимать вершины заданного графа G-{y,E), а в качестве элементов семейства 3 рассматривать всевозможные содержащиеся в нем звезды, то приходим к задаче покрытия графа звездами. Здесь под звездой понимается полный двудольный граф, одна доля которого состоит из единственной вершины [2].

Существует несколько основных способов решения данной задачи. Некоторые из них описаны в [1]. К ним относится алгоритм, использующий дерево поиска - метод, заключающийся в сведении задачи о покрытии к задаче линейного программирования вида: пусть v = ipix,u2,.,un} множество вершин графа G, 3 = \KhSi,K]S2,.,KUm\ - семейство всех звезд допустимых типов. Необходимо минимизировать функцию т = (1) при ограничениях: т

1, i = 1,2,.,и,

У = 1 где

1, если£, принадлежит покрытию х

0, если К^ Sj не принадлежит покрытию х'

1, если и, е Кх и =1

О, если и & К.

Здесь с} > 0 - стоимость звезды KX Sj. При этом, если стоимость равна единице для каждой звезды, то решение задачи линейного программирования определяет покрытие, состоящее из наименьшего числа звезд. В случае взвешенного графа G, стоимость может соответствовать весу звезды, т.е. будет отыскиваться покрытие минимального веса.

В случае, когда минимизируется сразу несколько целевых функций вида (1), возникает необходимость решения многокритериальной задачи покрытия графа звездами. Следует подчеркнуть, что эта задача является NP-трудной, т.е. не существует полиномиального алгоритма, способного дать точное решение для любого графа [2,3]. В связи с этим, пути ее исследования идут в трех направлениях: строятся вероятностные алгоритмы, отыскиваются полиномиально разрешимые классы графов, создаются эвристические алгоритмы с оценками. Так в [4] был осуществлен вероятностный анализ многокритериальной задачи покрытия графа звездами; в [5] построен эвристический алгоритм ее решения; в [6] обоснованы оценки эффективности векторной задачи покрытия графа звездами. Последние результаты в данной области, по всей видимости, можно отнести к работам В.А. Перепелицы: в [7] построен градиентный алгоритм для задачи покрытия графа звездами; условия полиномиальной разрешимости данной задачи разработаны в [8]; интервальная задача покрытия графа звездами, и исследование разрешимости ее в классе алгоритмов линейной свертки, рассматриваются в [9]; в [10,11] разработаны алгоритмы построения покрытий звездами и исследуется их практическое применение.

На сегодняшний день в математике известно несколько способов решения многокритериальных задач. Охарактеризуем основные из них.

Предположим, что необходимо решить многокритериальную задачу, в которой системой условий или каким-либо другим способом задается множество допустимых решений X = {*} (например, множество всевозможных покрытий звездами ранговых типов). На этом множестве определяется векторная целевая функция (ВЦФ)

F{x) = {F]{x\F2(x),.,Fm(x))^ где f;(*),(/ = i,2,.,m) требуют минимизации (Ft(x)->max всегда можно заменить на ~Fk(x)~+ min). Наиболее предпочтительным является нахождение точных решений, т.е. множества всех допустимых решений х е X с минимальными значениями критериев

F^x) —> min, F2(x) min,., Fm(x) —> min .

В случае противоречивости критериев таких решений многокритериальной задачи не существует, т.е. пересечение Qx, оказывается пустым, где X„(i -1,2,.,/и) множество допустимых покрытий хеХ, на каждом из которых значение 1\ (х) достигает минимума. В этом случае ВЦФ ^ при т > 2 определяет паретовское множество X с X [12-15].

Решение х0еХ называется парето-оптимальным (по критериям /•;(*),(/ = 1,2,.,/и)), если оно удовлетворяет следующему условию: не существует такого элемента у ^ X, чтобы среди неравенств у)<^(х0), i = 1,2,.,/я было хотя бы одно строгое. Иными словами, парето-оптимальное решение является векторнонеулучшаемым - его нельзя улучшить ни по одному из критериев, не ухудшив какой-либо другой.

Множество f(x)={f(x)хеХ], где f(x) = (f[(*),f2(x\.,fm(х)) называется множеством достижимости, a f(x) - паретовская граница множества достижимости f(x). Полным множеством альтернатив (ПМА) называется фь минимальное по мощности множество X" с X такое, что f(x°)= [12

15]. Как правило, «наилучшее» решение выбирается из ПМА.

Опишем наиболее распространенные методы нахождения парето-оптимальных решений многокритериальной оптимизационной задачи [1620].

Одним из них является нахождение лексикографического [18,20,21] оптимума. Суть этого метода заключается в ранжировании критериев F,(x\(i = 1,2,.,/и) по степени важности, т.е. осуществляется линейное упорядочение критериев так, что для любых двух из них можно однозначно указать, какой имеет приоритетное значение. В этом случае особое значение представляет случай, когда найденное решение является парето-оптимальным.

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

Один из наиболее простых и, в то же самое время, самый эффективный метод многокритериальной оптимизации, свертка [18,22,23], основан на идее замены критериев единственной целевой функцией представимой в виде: т

2>дА М,

1=1 где F^x) - нормированное значение критерия b\ (х), ht - коэффициент относительной важности г-й целевой функции, при этом ht> 0,J>=1. i=i

Нормирование функций F(x), необходимое для приведения их к одному измерению, осуществляется, например, согласно правилам:

М = —^W или = ai А~а, где Л = max F (х), а = min F(x). хеХ 14 ' ' хеХ

При использовании метода линейной свертки предполагается, что если на элементе х' е X целевая функция <т(х) достигает минимума, то х* е X, т.е. является парето-оптимальным решением.

Следует отметить, что в некоторых случаях свертку осуществляют в т виде произведения Р(х) = i=i

Метод свертки имеет ряд достоинств: простота метода, возможность сведения противоречивой многокритериальной задачи к классической од-нокритериальной и т.д. За счет этого на основе линейной свертки базируется большинство алгоритмов многокритериальной оптимизации [17,2429].

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

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

-проверить наличие начальных данных, при которых свертка не достигает минимума ни при каких допустимых значениях xel, что означает невозможность нахождения некоторых решений данным методом;

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

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

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

М= где 5>1.

Распространенным методом является введение метрики в пространстве целевых функций [18,30]. Если не удается найти точное решение многокритериальной задачи, то в качестве векторного оптимума х0 берется решение, для которого вектор F(x0) = (FXx0),F2(x0),.,Fm(x0)) наименее удален от вектора а = (a,,a2„.,am), где а, = rrnnF,{x\(i = l,2,.,m).

Иными словами, в пространстве целевых функций F,(x),(/ = 1,2,.,/и) определяется точка а, которую называют точкой «абсолютного минимума». При этом подразумевается, что расстояние от абсолютного минимума до всякой точки F(x) е Rm берется с учетом относительной важности целевых функций. Таким образом, получается функция, являющаяся улучшенным вариантом свертки

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

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

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

Предпосылкой возникновения предфрактальных и фрактальных графов стало введение и исследование понятия «фрактал». Это понятие было введено в 1975 году Б. Мандельбротом с целью создания математического аппарата, предназначенного для описания объектов природы, науки и техники (конечных и бесконечных), обладающих очень сложной структурой, процессов, характеризующихся хаотически изменяющимися условиями протекания [32,33].

С математической точки зрения фрактал - это, прежде всего, множество с дробной размерностью (под размерностью понимается размерность Хаусдорфа-Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая в последствии А.С. Безиковичем) [31,33-37]. Кроме этого, следует отметить одно основополагающее свойство присущее фракталам - это свойство самоподобия, т.е. любая, даже самая малая, часть фрактала, в какой-то степени, подобна целому и является как бы уменьшенной его копией. Это свойство отличает фракталы от объектов классической геометрии.

Дальнейшее изучение фракталов осуществлялось в рамках нового междисциплинарного подхода - синергетики [32,38-41], где одной из центральных задач являлось моделирование объектов и явлений, которым присущ хаос, т.е. непредсказуемость протекающих в них процессов, отсутствие пространственной регулярности, случайность, рассогласованность поведения составляющих элементов и т.д. [38,40-42] С развитием этого направления удалось выявить регулярные законы и закономерности возникновения, казалось бы, на первый взгляд, хаотичных систем, условия протекания непредсказуемых (или, по крайней мере, очень сложных) процессов и явлений, показать фрактальные структуры, лежащие в их основе. Более того, при дальнейшем изучении оказалось, что моделирование многих фрактальных объектов физики, химии, биологии и других дисциплин сводится к составлению автономных систем обыкновенных дифференциальных уравнений, зависящих от параметров [43].

Подчеркнем, что, при исследовании дискретных объектов [46,17,24,28,44-56], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [40,43]. Подобные объекты моделируются средствами теории графов [1,2,57,58]. При этом, получаемые модели, обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов.

Впервые термин «фрактальный граф» возник в работах [59,60] для отражения иерархии связей с учетом варьируемой разветвленности. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова A.M. и Перепелицы В.А. [31,35,37,61-63]. Разработка этой теории показала важность и широкие возможности применения предфрактальных и фрактальных графов. Справедливо утверждение: «В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф -это, в конечном счете, один из способов выявления некоторых качеств моделируемой системы. Причем по отношению ко всей исследуемой системе речь здесь идет о таких качествах, которые не выводимы прямо из свойств элементов системы и локальных взаимодействий этих элементов» [31].

На сегодняшний день, по всей видимости, наиболее серьезные результаты теории предфрактальных и фрактальных графов представлены в [31]. В этой работе предложены полиномиальные алгоритмы распознавания фрактальных графов, построены модели некоторых фрактальных объектов при помощи математического аппарата данной теории. Вычислены размерности Хаусдорфа-Безиковича для некоторых типов фрактальных графов. В [37,61] приведены некоторые результаты исследований свойств графов такого типа. Проблема построения остовного дерева фрактального графа рассмотрена в [62]. Некоторые результаты исследований задачи о кликах фрактального графа предложены в [63].

Немаловажное значение играют предфрактальные графы. В действительности не так много объектов, при моделировании которых получается фрактальный граф. Поэтому для решения конкретных задач математики и физики, экономики и биологии, химии и строительства, планирования и т.д. используются предфрактальные графы, ранг которых может выступать характеристикой степени приближения строящихся моделей к реальным объектам исследования, т.е. чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих экономических, биологических, социальных, технических и т.д. задач тесно связано с необходимостью моделирования очень сложных и изменчивых во времени структур, состоящих из большого числа элементов, применение классических методов математического моделирования [1,64-67] для решения подобных проблем не всегда представляется возможным в силу их неэффективности. Применение же теории предфрактальных и фрактальных графов помогает решать задачи там, где бессильны традиционные подходы.

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

- проблема задания предфрактальных и фрактальных графов;

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

- вопросы вычисления фрактальной размерности произвольного фрактального графа;

-задачи моделирования объектов с элементами структурного хаоса при помощи математического аппарата данной теории;

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

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

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

Основными задачами исследования, определяемыми поставленной целью, являются:

- исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки критериев;

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

- разработка нового способа задания произвольного предфрактального графа, способного адекватно отражать структуру графов этого типа;

- построение и исследование полиномиальных алгоритмов построения покрытий предфрактальных графов звездами ранговых типов;

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

Методы исследования основываются на использовании математического аппарата:

-теории графов;

- теории предфрактальных и фрактальных графов;

- комбинаторики;

- математического программирования;

- многокритериальной оптимизации.

Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.

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

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

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

В диссертационной работе получены следующие новые научные результаты:

- доказана неразрешимость 2-х и 3-х критериальных задач построения покрытий предфрактальных графов звездами ранговых типов с помощью алгоритма линейной свертки критериев;

- впервые построены и исследованы фрактально-графовые модели системы контроля трафика в Интернете и сети центров МЧС РФ, сводимые к построению покрытий предфрактальных графов звездами ранговых типов;

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

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

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

По теме диссертационной работы опубликовано 12 печатных работ.

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

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

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

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

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

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

-научных семинарах, проводимых в НИИ Прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН (г. Нальчик, 200-2003);

- научных семинарах профессорско-преподавательского состава КЧГТА (г. Черкесск, 2000-2004).

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

3.3. Выводы

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

ЗАКЛЮЧЕНИЕ

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

При этом получены следующие новые научные результаты:

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

2. Впервые построены математические фрактально-графовые модели системы контроля трафика в Интернете и сети центров МЧС в Российской Федерации. При этом новизна заключается в сведении этих моделей к многокритериальной задаче покрытия предфрактальных графов звездами ранговых типов.

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

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

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

1. Кристофидис Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978. -432с.

2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич

3. Р.И. Лекции по теории графов. -М.: Наука, 1990. 383с.

4. Перепелица В.А., Сергиенко В.А. Полиномиальные и NP-полные многокритериальные задачи перечисления альтернатив В сб. Теор. и прогр. реализ. мет. дискр. оптимиз. -Киев: ИК АН СССР, 1989. -С.58-69.

5. Кочкаров A.M., Шунгаров Х.Д. Вероятностный анализ одной многокритериальной задачи покрытия графа звездами. Республиканский семинар дискретной оптимизации //Тез. докл. 1985., Киев. -С.72-74.

6. Кочкаров A.M., Перепелица В.А., Шунгаров Х.Д. Исследование эффективности одного быстрого алгоритма решения двухкритери-альной задачи покрытия графа звездами //Известия АН БССР, серия физ.-мат. наук. 1986. -№5. -С.117-122.

7. Кочкаров А.М., Фоменко МЛ. Обоснование оценок эффективности одного алгоритма для векторной задачи покрытия графа звездами //Всероссийский симпозиум «Математическое моделирование эколого-экономических систем.» Тез. докл. Кисловодск: КИЭП, 1997. -С.64-66.

8. Перепелица В.А., Тебуева Ф.Б. Условия асимптотической точности градиентного алгоритма для задачи покрытия графа звездами //Препринт №142Т. Нижний Архыз: САО РАН. 2001. - 9с.

9. Перепелица В.А., Тебуева Ф.В. Об условиях полиномиальной разрешимости задач покрытия графа звездами и цепями

10. Математическое моделирование в образовании, науке и производстве. Материалы научно-практической конференции 27-30 июня2001 г. Тирасполь: РИО ПТУ, 201. - С. 110-113.

11. Перепелица В.А., Салпагаров С.И., Тебуева Ф.Б. Точные алгоритмы для задач покрытия графов звездами //Известия вузов. Северо-Кавказский регион. Естественные науки. 2002. -№1. - С.30-34.

12. Емеличев В.А., Кравцов М.К., Янушкевич О.А. Условия парето-оптимальности в одной дискретной векторной задаче на системе подмножеств//ЖВМиМФ, 1995. Т.35. -№11. -С.1641-1652.

13. Перепелица В.А., Мамедов А.А. Исследование сложности разрешимости векторных задач на графах. -Черкесск: КЧТИ, 1995. -45с.

14. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. -М.: Наука, 1982. -256с.

15. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах //ЖВМиМФ, 1989. -№2. -С.171-183.

16. Емеличев В.А., Перепелица В.А., Козырев В.А. Обзор некоторых проблем дискретной многокритериальной оптимизации //Труды сем. по дискретной математике и ее прилож. -М.: МГУ, 1989. -С.13-17.

17. Озерной В.М., Гафт М.Г. Методология решения дискретных многокритериальных задач. В кн.: Многокритериальные задачи принятия решений. Машиностроение, Москва, 1978. С. 14-47.

18. Перепелица В.А. Об одном классе многокритериальных задач на графах и гиперграфах //Кибернетика. -1984. -№4. -С.62-67.

19. Вентцель Е.С. Исследование операций: задачи, принципы, методология. -М.: Наука, 1980. 208с.

20. Червак Ю.Ю. Методы лексикографического поиска решений для дискретных задач выпуклого программирования. -Укр. матем. журнал, 1974, т. XXVI, вып. 2. С.269-272.

21. Гафт М.Г. Принятие решений при многих критериях. -М.: Знание, 1979.-64с.

22. Ларичев О.И. Наука и искусство принятия решения. -М.: Наука, 1979. -200с.

23. Кравцов M.K., Янушкевич О.А. О многокритериальных задачах, разрешимых с помощью алгоритмов линейной свертки // Препринт. -МН.: Ин-т техн. Кибернетика АН Беларуси, 1995. -№16. -16с.

24. Маламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном //Тез. докл. 9 Всероссийской конф. «Математическое программирование и приложения.» -Екатеринбург, 1995. -С.65.

25. Перепелица В.А., Сергеева J1.H. Исследование разрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач //Кибернетика и системный анализ. -1996.-№2. -С.71-77.

26. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач //Журн. выч. мат. и мат. физ. 1988. -Т28, №3. -С.400-419.

27. Emelichev V.A., Perepelitsa V.A. Complexity of vector optimization problems on graphs // Optimization, 1991. V.22 №6. -P.903-918.

28. Моисеев H.H. Математические задачи системного анализа. -М.: Наука, 1979, 494с.

29. Кочкаров A.M. Распознавание фрактальных графов: Алгоритмический подход. Нижний Архыз: Изд. центр «CYGNUS», 1998. -170с.

30. Малинецкий Г.Г., Попов А.Б. Нелинейность. Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур. -М.: Наука, 1996. -С.95-164.

31. Федер Е. Фракталы. -М.: Мир, 1991.

32. Вишек М.И. Фрактальная размерность множеств //Соросовский образовательный журнал. -1998. -№1. С. 122-127.

33. Кочкаров A.M., Перепелица В.А., Сергеева JI.H. Фрактальные графы и их размерность. Черкесск, 1996. Деп. в ВИНИТИ, №3284-В96. С.1-34.

34. Марголина А. Фрактальная размерность периметра роста. В сб. Фракталы в физике. -М.: Мир, 1988. -С.507-512.

35. Kochkarov А.М., Perepelitsa V.A. Fractal Graphs and Their Properties. ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters, p.347.

36. Гласс А., Мэки M. От часов к хаосу: Ритмы жизни. -М.: Мир, 1991.

37. Евин И.Л. Синергетика искусства. -М.: 1993.

38. Курдюмов С.П., Малинецкий P.P., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В кн. Новое в синергетике. Загадки мира неравновесных структур. -М.: Наука, 1996. -С.95-164.

39. На ken Н. Synergetics, Springer, 1997.

40. Chaoc Theory in Economics: Methods, Models and Evidnce. Edited by Dechert W.D., Edward Elgar, 1996.

41. Шустер Г. Детерминированный хаос. Введение. -М.: Мир, 1998.

42. Бакурова А.В., Перепелица В.А. Вероятностный анализ сложности и устойчивости для векторной задачи коммивояжера //Докл. АН Украины, Сер. А.-1993.-№11. С.80-84.

43. Бакурова А.В., Емеличев В.А., Перепелица В.А. Об устойчивости многокритериальных задач на системах подмножеств //Докл. АН Беларуси.-1995.Т.39, №2. С.33-35.

44. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач //Дискретная математики. -1994. Т.6 №1.с.з-зз.

45. Кочкаров A.M. Многокритериальная задача покрытия графа цепями заданной длины. В сб. Математические вопросы исследования операций. -Минск: НИИ ЭМП. 1982. -С.42-49.

46. Кочкаров А.М. Парето-оптимальные решения многокритериальной задачи покрытия графа цепями. Минск, 1983, деп. в Бел. НИ-ИНТИ, 02.06.83, №645 Бе-Д83. -С. 1-13.

47. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. Математические методы в исследовании операций //Тез. докл. Международной конференции НРБ, София, 1983. -С.42-43.

48. Кочкаров А.М., Перепелица В.А. Вероятностный анализ одной многокритериальной задачи теории графов //Всесоюзная конференция «Проблемы теоретической кибернетики.» -Иркутск: ИГУ, 1985. С.74-75.

49. Кочкаров A.M., Перепелица В.А. О покрытии графа лесами. Труды сем. по дискретной математике и ее приложения. -М.: МГУ, 1989. -С.282-283.

50. Майника Э. Алгоритмы оптимизации на сетях и графах. -М.: Мир, 1981.-323с.

51. Перепелица В.А. Об алгоритмах с оценками для многокритериальных задач на графах. Комбинаторно-алгебраические методы в дискретной оптимизации. Межвуз. сб. Науч. Трудов. Нижний. Новгород: Нижегородский гос. ун-т, 1991. -С.95-106.

52. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. -Киев: Наук, думка, 1988.

53. Burkard R.E., Keiding Н., Krarap J., Prnzan P.M. A relationship between optimality and efficiency in multicriteria 0-1 programming problems //Computers & Optuations Research, 1981. V.8. -№4. -P.241-247.

54. Kochkarov A.M., Perepelitsa V.A., Sergeeva L.N. Algorithm for covering of graph by forest of minimum weight. Computing in Civil and Building Engineering, Pahl & Wemer (eds), 1995, Balkema/Rotterdam/ Brookfield, pp.711-714.

55. Ope О. Теория графов. М.: Наука, 1968. -352с.

56. Харари Ф. Теория Графов. -М.: Мир, 1973.

57. Мелроуз Дж. Иерархические фрактальные графы и блуждания на них. В сб. Фракталы в физике. -М.: Мир, 1988. -С.519-523.

58. Солла С. Разрушение нагруженных фрактальных деревьев. В сб. Фракталы в физике. -М.:Мир, 1988. -С.256-259.

59. Кочка ров А.М., Перепелица В. А. О гамильтоновости фрактальных графов //Международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики.» Тез. докл. -Нальчик, НИИ ПмиА КБНЦ РАН, 1996. -С.52-53.

60. Кочкаров A.M., Перепелица В.А. Остовные деревья на фрактальном графе //Всероссийский симпозиум «Математическое моделирование эколого-экономических систем.» Тез. докл. Кисловодск: КИЭП, 1997. -С.67-69.

61. Кочка ров A.M. Задача о кликах на фрактальных графах //Республиканская конференция преподавателей и аспирантов КЧТИ. Черкесск: КЧТИ, 1997. -С.51-55.

62. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. -М.: Радио и связь, 1981.

63. Еленин Г.Г., Синько М.Г. Математическое моделирование явления на поверхности. -М.: Знание, 1988.

64. Моисеев Н.Н. Математика ставит эксперимент. -М.: Наука, 1979.

65. Михалевич В.С., Волкович B.JI. Вычислительные методы исследования и проектирования сложных систем. -М.: Наука, 1981. -287с.

66. Альбитц П., Ли К. DNS и BIND. -СПб.: Символ-Плюс, 2002. -696с.

67. Камер Дуглас Э., Стивене Дэвид Л. Сети TCP/IP. Т.З. Разработка приложений типа клиент/сервер для Linux/POSIX. -М.: Изд. дом «Вильяме», 2002. -592с.

68. Спортак Марк А. и др. Компьютерные сети. Книга 2: Networking essentials. Энциклопедия пользователя. К.: изд. «Диа Софт», 1999. -432с.

69. Хелеби С., Мак-Ферсон Д. Принципы маршрутизации в Internet. 2 изд. М.: изд. дом «Вильяме», 2001. -448с.

70. Цвики Э., Купер С., Чапмен Б. Создание защиты в Интернете. -СПб.: Символ-Плюс, 2002. -928с.

71. Батчаев И.З. Математическая модель системы контроля Интернета //II Международная научно-техническая конференция «Материалы и технологии XXI века». Пенза, 2004. С. 107-110.

72. Батчаев И.З. Об одной многокритериальной задаче покрытия предфрактальных графов звездами ранговых типов. Карачаевск, КЧГУ, 2002, Деп. в ВИНИТИ, №724-В2002. С. 1-12.

73. Батчаев И.З., Кочкаров А.М. Задача покрытия предфрактального графа звездами одного рангового типа //Сб. трудов IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности». Черкесск: КЧТИ,2002.-С.9-11.

74. Батчаев И.З. Об одной многокритериальной задаче покрытия предфрактальных графов звездами одного рангового типа //Известия Кабардино-Балкарского научного центра РАН, -Нальчик, №1 (8), 2002. С.1-5.

75. Батчаев И.З., Кочкаров A.M. Быстрый алгоритм на предфрактальных графах с оценками //Материалы Международной Российско-Узбекского симпозиума «Уравнения смешанного типа и родственные проблемы анализа и информатики». Нальчик-Эльбрус,2003. С.108-110.

76. Батчаев И.З. Математическая модель сети центров МЧС РФ //VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004. -С.7-9.

77. Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций //Дискр. анализ. -1974. -Вып.25. -№1. -С.7-11.

78. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.-478с.

79. Холл М. Комбинаторика. -М.: Мир, 1970. 424с.

80. Емеличев В.А., Перепелица В.А. К вычислительной сложности многокритериальных задач //Изв. АН СССР. Техн. Кибер. -1988. -№1. -С.85-87.

81. Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах //Кибернетика. -1975. №1. -С.1-8.

82. Емеличев В.А., Перепелица В.А. Многокритериальные задачи об остовах графа //ДАН СССР, 1988. Т.298. -№3. -С.544-547.

83. Черкасский Б.В. Новый алгоритм генерации остовных деревьев. //Кибернетика. -1987. -№1. -С.85-89.

84. Батчаев И.З. Оптимизация затравки и ранга предфрактального графа с наперед заданными ограничениями //Электронный журнал «Исследовано в России», 123, 2003. С.1465-1472.

85. Батчаев И.З., Батчаев З.Ю. Алгоритмы построения предфрак-тальных графов с заданными свойствами //Вестник Карачаево-Черкесского государственного университета. Карачаевск: КЧГУ, №12, 2004. С.285-298.