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

• Автор: Батчаев, Ильяс Заурович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Черкесск
• Количество страниц: 119 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ПЛАВА 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. Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Задача построения покрытия предфрактального графа звездами ранговых типов является частным случаем задачи о наименьшем покрытии (разбиении), которая формулируется следующим образом: пусть дано множество V = {м„и2и семейство 3 = {? Д. •»¦$„} множеств 5, с V. А,/€ {1,2,. Если под множеством К = {м,,ы2. К,? Здесь под звездой понимается полный двудольный граф, одна доля которого состоит из единственной вершины [2]. Существует несколько основных способов решения данной задачи. Некоторые из них описаны в [1]. К ним относится алгоритм, использующий дерево поиска - метод, заключающийся в сведении задачи о покрытии к задаче линейного программирования вида: пусть V = {ы,,ы2,-множество вершин графа (/, 3 = {АГК<1,АГ, %^. КХЯя | - семейство всех звезд допустимых типов. Л?,=1,/ = К2 ,. Здесь с}> 0 - стоимость звезды А', , . При этом, если стоимость равна единице для каждой звезды, то решение задачи линейного программирования определяет покрытие, состоящее из наименьшего числа звезд. В случае взвешенного графа О, стоимость может соответствовать весу звезды, т. В случае, когда минимизируется сразу несколько целевых функций вида (1), возникает необходимость решения многокритериальной задачи покрытия графа звездами. Следует подчеркнуть, что эта задача является МР-трудной, т. Так в [4] был осуществлен вероятностный анализ многокритериальной задачи покрытия графа звездами; в [5] построен эвристический алгоритм ес решения; в [6] обоснованы оценки эффективности векторной задачи покрытия графа звездами. Последние результаты в данной области, по всей видимости, можно отнести к работам В. А. Перепелицы: в [7] построен градиентный алгоритм для задачи покрытия графа звездами; условия полиномиальной разрешимости данной задачи разработаны в [8]; интервальная задача покрытия графа звездами, и исследование разрешимости ее в классе алгоритмов линейной свертки, рассматриваются в [9]; в [,] разработаны алгоритмы посгроения покрытий звездами и исследуется их практическое применение. На сегодняшний день в математике известно несколько способов решения многокритериальных задач. Охарактеризуем основные из них. Предположим, что необходимо решить многокритериальную задачу, в которой системой условий или каким-либо другим способом задается множество допустимых решений X = {*} (например, множество всевозможных покрытий звездами ранговых типов). Ft(x(i = 1,2,. Fk(x)-+ max всегда можно заменить на - Fk(x) -> min ). Наиболее предпочтительным является нахождение точных решений, т. Ft{x) min. F2(x) -> min Fm(x) -> min . В случае противоречивости критериев таких решений многокритериальной задачи не существует, т. ЛГ„(/ -1,2,. Х9 на каждом из которых значение /? В этом случае ВЦФ при т > 2 определяет паретовское множество X с X [-]. Решение хп е X называется парето-оптимапьным (по критериям /•;(*),(/ = 1,2,. Иными словами, парето-оптимальное решение является векторнонеулучшаемым - его нельзя улучшить ни по одному из критериев, нс ухудшив какой-либо другой. Множество /'(Х)= {р(х):х<= X}, где Р(х) = (рх(хР2(х. Ь'т(х)) называется множеством достижимости, а р(х) - паретовская граница множества достижимости Р(Х). Полным множеством альтернатив (ПМА) называется минимальное по мощности множество Х° с X такое, что /г(л,0)= /7(л') [-]. Как правило, «наилучшее» решение выбирается из ПМА. Опишем наиболее распространенные методы нахождения парето-оптимальных решений многокритериальной оптимизационной задачи [-]. Одним из них является нахождение лексикографического [,,] оптимума. Суть этого метода заключается в ранжировании критериев /•;(*¦)(#' = 1,2,. В этом случае особое значение представляет случай, когда найденное решение является парето-оптимальным. В данной работе этот метод применяется в большинстве алгоритмов, ибо позволяет разбить 3-х критериальную задачу на последовательность трех однокритериальных задач. S 4Л*М. Д = шах/*;(х), а, = min F(x). При использовании метода линейной свертки предполагается, что если на элементе х* е X целевая функция <г(х) достигает минимума, то х* € X, т. П^(х). Метод свертки имеет ряд достоинств: простота метода, возможность сведения противоречивой многокритериальной задачи к классической однокритериальной и т.