Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Батчаев, Ильяс Заурович

• Батчаев, Ильяс Заурович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Батчаев, Ильяс Заурович

ВВЕДЕНИЕ.

ГЛАВА 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. Впервые исследована обратная задача к рассматриваемой многокритериальной задаче: необходимо построить предфрактальный граф, для которого существует точное решение со значениями критериев равными заданным числам. Предложены полиномиальные алгоритмы ее решения.

Список литературы диссертационного исследования кандидат физико-математических наук Батчаев, Ильяс Заурович, 2004 год

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.