1. Определение метаграфа
Метаграфы - обобщение концепций графических структур. В метаграфе есть и элементы и орграфов, и гипеграфов, сам метаграф процесса выстраивается на основе иерархического графа. Формально, метаграф - множество <V,MV, E, ME>, где V - множество вершин, MV - множество метавершин, E - множество ребер, ME - множество метаребер [1].
Порождающее множество X для метаграфа - множество элементов , представляющее собой совокупность объектов рассматриваемой предметной области.
Метаребро е в метаграфе - пара , состоящая из входной метавершины и выходной , которые могут содержать произвольное количество объектов [1].
Простой путь h(x, y) от элемента х к элементу у - совокупность ребер , таких что:
В метаграфе метапуть М (В, С) от источника в есть множество ребер таких, что[1]:
Метаграф может быть задан матрицами смежности, инцидентности, матрицей весов [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] алгоритм поиск метапути наименьшего веса в метаграфе, являющийся модификацией алгоритма Дейкстры с применением элементов идемпотентной математики:
Для полученной матрицы применяем алгоритм Дейкстры для поиска пути наименьшего веса в орграфе.
В приложении к 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. Метаграфы и экономико-математические методы
Метаграфы могут применяться и в таких традиционных для графов задачах, как транспортная задача и сетевое планирование. Нами ведутся исследования в этой области.
Таким образом, в статье дана краткая теоретическая справка о метаграфах, определены основные математические характеристики структуры, приведены примеры. Обсуждаются отдельные сферы применения метаграфов, как уже тщательно проработанные (представление бизнес-процессов, оптимизация производственного процесса), так и области прикладной математики для потенциального использования метаграфов.
СПИСОК ЛИТЕРАТУРЫ