IV Международная студенческая научная конференция Студенческий научный форум - 2012

Работа поддержана РФФИ,  проект № 11-07-00580-а

1. Определение метаграфа

Метаграфы  - обобщение концепций графических  структур. В метаграфе  есть и элементы и орграфов, и гипеграфов, сам метаграф процесса выстраивается на основе иерархического графа. Формально,  метаграф - множество <V,MV, E, ME>, где V -  множество вершин, MV - множество метавершин, E - множество ребер, ME - множество метаребер  [1].

Порождающее множество X для метаграфа - множество элементов , представляющее собой совокупность объектов рассматриваемой предметной области.

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

Простой путь h(x, y) от элемента х к элементу у  - совокупность ребер , таких что:

• ;
• ;
• для всех .

В метаграфе  метапуть М (В, С) от источника в есть множество ребер таких, что[1]:

• ;
• ;
• .
• 2. Математическая основа метаграфа

Метаграф может быть задан матрицами смежности, инцидентности, матрицей весов [2].

Матрица смежности А для метаграфа S=<X, E> - квадратная матрица NxN, где N=|X|, такая что для всех

 где

Иными словами, элемент матрицы a  - есть тройка  , где Ie - входные вершины для ребра е, Ое- выходные.

Строки матрицы инцидентности I для метаграфа соответствуют каждому элементу порождающего множества, каждый столбец соответствует ребру, элементы матрицы определяются следующим соотношением:

Весом пути (либо метапути) назовем функцию, определенную как:

, где  - вес ребра .

Матрицей весов назоваем квадратную матрицу W, элементы которой задаются как:

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

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

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

Современные методологии представления бизнес-процессов (IDEF 0, IDEF 3, BPMN) не используют математическую основу для моделирования процессов, однако это может быть полезно в случае последующей оптимизации деятельности предприятия (см. раздел 4).

Формально, бизнес-процесс можно представить с помощью теоретико-множественных понятий как совокупность множеств <A, R, P, W>, где A -множество элементарных действий, R-множество отношений между ними (переходы), P - множество лиц, ответственных за выполнение работ, W-множество затрат для осуществления действий (временные, материальные, человеческие и прочие ресурсы). Рассматриваем ad-hoc бизнес-процессы, подвижные вследствие вариативности условий окружающей среды. Была разработана блок-схема  производственного процесса службы экспресс-почты региона [4], проведены ее модификации с использованием альтернативных средств моделирования. Был также проведен сравнительный анализ традиционных и потенциальных средств для моделирования бизнес-процессов, в результате чего самой оптимальной для такого рода процессов была признана модель с использованием метаграфов [2].  Более подробно с принципами построения метаграфа бизнес-процесса можно ознакомиться в [2].

Нами были получены метаграф процесса, его матрицы инцидентности, весов. Это позволило нам перейти к задаче оптимизации деятельности службы регионального представительства экспресс-почты Major Липецкой области.

4. Метаграфы в планировании и управлении организацией. Связь с идемпотентной математикой

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

В моделировании процессов с использованием метаграфов удобно применять принципы идемпотентной математики. Так, на основе [5,6] был разработан и программно реализован [7] алгоритм поиск  метапути наименьшего веса в метаграфе, являющийся модификацией алгоритма Дейкстры с применением элементов идемпотентной математики:

1. Определить матрицу весов орграфа, соответствующего метаграфу, иначе говоря, определить структуру унарных связей по правилу:
2. Определить матрицу весов гиперграфа, соответствующего метаграфу (структура межуровневых связей)
3. Структуру метаграфа определим как композицию указанных структур по правилу:

Для полученной матрицы применяем алгоритм Дейкстры для поиска пути наименьшего веса в орграфе.

В приложении к ad-hoc бизнес-процессам алгоритм позволяет не только смоделировать реальный процесс, но и найти наименее затратную стратегию поведения участников  при этом.  Может быть полезен в производственной деятельности предприятий малого и среднего бизнеса., а также применяться  в работе отделов крупных предприятий, где деятельность участников может несколько варьироваться из-за влияния среды. Так, был оптимизирован процесс ежедневной деятельности отдела по работе с проблемными активами отделения ОАО «Сбербанк».

5. Маршрутизация в IP-сетях с использованием метаграфов

Иерархия архитектуры сетей может быть отражена средствами метаграфов. Рассмотрим протокол внутреннего шлюза OSPF (Open Shortest Path First, , алгоритмы предложены Дейкстрой), который представляет собой протокол состояния маршрута (в качестве метрики используется - коэффициент качества обслуживания)[8]. Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Автономная система может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Пути с наименьшим суммарным значением метрики считаются наилучшими. Поиск наилучшего пути производится с использованием алгоритма Дейкстры[8].

При применении OSPF могут быть выделены области маршрутизации в пределах автономной системы. За счет представления сетей не в виде орграфа, а в виде метаграфа и использования переработанного алгоритма Дейкстры с улучшенной робастностью, предложенного в [9], можно более эффективно решить задачу маршрутизации пакетов в сети. Поставим задачу как поиск наилучшего пути  из множества  возможных метапутей и простых путей, где множество метавершин M - это области в пределах одной автономной системы, а простые вершины V- возможные пути от одной сети (или маршрутизатора) к другим. Правило «невидимости» топологии сети от соседей при этом выполнено, т.к. каждая сеть есть узел - простая вершина метаграфа.

Для рис. 4.2.11.2.2 , представленного в [8], имеем соответствующий метаграф (рис.3) при посылке пакета от ЭВМ-1 к ЭВМ-2:

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

6. Метаграфы и экономико-математические методы

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Basu A., Blanning R. Metagraphs and Their Applications // Amit Basu, Robert W. Blanning - Springer, 2010. - 173p.
2. Черных, О.О. Алгоритмы поиска пути наименьшего веса в метаграфе и их практическое применение / О.О. Черных, Д.И. Попова // 13 Региональная молодежная научная и инженерная выставка «Шаг в будущее, Центральная Россия». - Липецк: ЛГТУ, 2010. - 15 с.
3. Блюмин С.Л. Метаграфы: матричные представления, связи с оргафами и гиперграфами, с идемпотентной математикой. /С.Л.Блюмин.// Сборник трудов ИИТО. - Липецк: ЛГПУ, 2011. - 3 с.
4. Черных О.О. Применение теории гиперграфов в сфере бизнес- планирования / Черных О.О., Блюмин С.Л..// Сборник тезисов докладов научной конференции студентов и аспирантов ЛГТУ -Липецк: ЛГТУ, 2010. - с. 23-25.
5. Lossow M. A min-max version of Dijkstra´s algorithm with application to perturbed optimal control problems/ Marcus von Lossow. - Bayreuth : Mathematisches Institut, Universit¨at Bayreuth, 2007. - 12 с.
6. Huang L. Dynamic Programming Algorithms in Semiring and Hypergraph/ Liang Huang. -Harrisburgh: Frameworks Department of Computer and Information ScienceUniversity of Pennsylvania, 2006. - 21 с.
7. Блюмин С.Л., Попова Д.И., Черных О.О. Поиск наименьшего пути в метаграфе. - ФАП ВНТИЦ. Рег.№50201150337 от 22.03.2011
8. http://book.itep.ru/ - Семенов Ю.А. Телекоммуникационные технологии. [Электронный ресурс].
9. Кузнецов Н.А., Фетисов В.Н. Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях. «Автоматика и телемеханика», №2, 2008. - с. 80-85.

Код для цитирования: Скопировать