Диссертация (1152223), страница 73
Текст из файла (страница 73)
Каждый элемент принимает значение 1, если переход может сработать приданной маркировке, или 0, если переход не активен, формула (5.8)u1Uu 2 , где:(5.8)u3uj=1 означает, что переход j готов к срабатыванию,uj=0 переход j не готов к срабатыванию.Примем во внимание, что i строка матрицы инцидентности A отображает изменение маркировки СП в результате срабатывания i-перехода. Теперь, если известно текущее состояниесети Mk , можно вычислить её следующее состояние сети Mk+1 путём умножения матрицы инцидентности на вектор срабатывания, формула (5.9).Mk+1 = Mk + ATU(5.9)Рассмотрим пример СП, содержащей три перехода и четыре позиции, изображённый нарисунке 5.13:p1t1t3p2t2p4p3Рисунок 5.13 - Пример СПИсточник: составлено автором.Для данной СП вычислим матрицу инцидентности, показанную на рисунке 5.14:Переход T1 T2 T3ПозицияP1-1 0+1P2+1 -1 0P3+1 -1 0P40+1 -1Рисунок 5.14 - Матрица инцидентностиИсточник: составлено автором.285Примем во внимание, что в текущей маркировке M0 позиция P1 содержит один маркер,остальные позиции пустые, следовательно, готов к срабатыванию переход T1, остальные заблокированы.
После срабатывания перехода T1 позиция P1 потеряет маркер, а позиции P2 и P3 получат по маркеру. Мы можем записать уравнение (5.10):M11101011001100011100011(5.10)0Отметим недостатки матричного метода. Во-первых, матрица инцидентности не позволяет правильно оценить ситуацию, когда переходы имеют входы и выходы из одной позиции(т.н. петли). Во-вторых, вектор запуска не содержит информации о последовательности срабатывания переходов. В-третьих, наличие решения фундаментального уравнения является необходимым условием для достижимости маркировки, но является достаточным.Проверка достижимости с помощью фундаментального уравненияПусть есть маркировка M2, достижимая из некоторой маркировки M1. Это означает, чтосуществует некоторая последовательность срабатываний переходов δ = {U1, U2, , Ud}.
Мы можем записать уравнение (5.11):dM2M1ATUiM1AT S(5.11)i 0Где вектор S есть вектор числа срабатываний, его каждый элемент указывает, сколько разсработает конкретный переход на пути от маркировки M1 к маркировке M2. Обратим внимание,это вектор не указывает порядка срабатывания переходов, только число срабатываний.P-Инвариант сети ПетриP-Инвариантом называют вектор x размера n*1, который удовлетворяет следующемуусловию (5.12):xT A = 0(5.12)Если воспользоваться фундаментальным уравнением СП и умножить обе его части на xT,то получим уравнение (5.13):xTM2 = xTM1 + xT A(5.13)поскольку xT A = 0 , мы получим:xTM2 = xTM1 , иными словами это условие сохранения числа маркеров в сети.
Можно сделать вывод, если для СП существует P-инвариант, то эта сеть является сохраняющей.Фундаментальной системой решений системы линейных однородных уравнений (5.14)286xT A = 0(5.14)называют такую их совокупность, через которую линейно выражаются все остальные решения. Если ранг матрицы А равен числу неизвестных (r = n), то уравнение (5.15) имеет тольконулевое решение.xT A = 0(5.15)Если r < n, то система (5.7) помимо нулевого имеет бесконечное множество других решений, причём фундаментальная система состоит из (n — r) векторов Х. Ранг n m — матрицы А= ‖ aij‖ равен наивысшему порядку отличного от нуля определителя, полученного вычёркиванием n — r столбцов и m — r строк из матрицы А.Таким образом, все инварианты Х для маркирований сети можно получить из n — r базисных решений. Объединив записанные в виде векторов-строк решения фундаментальной системы, получим матрицу инвариантов или базисных решений В.
Тогда для любого достижимогомаркирования имеем, формула (5.16):BM = BM0 = K0 .(5.16)Если все компоненты Р-инварианта неотрицательны, его называют Р-цепью. Полная Рцепь — это Р-инвариант, все компоненты которого положительны. Сеть Петри инвариантна,если для неё существует полная Р-цепь.
Полная Р-цепь включает в себя все позиции сети.Инвариантная сеть Петри является ограниченной. Докажем это. Пусть Х — полная Рцепь. Тогда X*M=K0, т. е. взвешенная сумма меток по всем позициямxi miK 0 - ограни-iченная. А поскольку xi положительные и вся сумма ограничена, то и маркирования всех позиций сети ограничены.T-Инвариант сети ПетриT-Инвариантом называют вектор y размера m*1, который удовлетворяет следующемуусловию, формула (5.17):Ay = 0(5.17)Если воспользоваться фундаментальным уравнением СП и умножим обе его части на y, тополучим уравнение (5.18):M2y = M1y + Ay(5.18)поскольку Ay = 0 , мы получим уравнение (5.19):M2y = M1y или M2 = M1 ,(5.19)Таким образом, после некоторой последовательности срабатываний сеть возвращается висходную маркировку.
Можно сделать вывод, если для СП существует T-инвариант, то эта сетьявляется реверсивной.287Полная T-цепь — это T-инвариант, все компоненты которого положительны. Полная Tцепь включает в себя все переходы сети. Если сеть имеет полную T-цепь, то она жива при любом начальном маркировании, поскольку в цепи маркирований от M0 до М= M0 срабатываютвсе переходы. Таким образом, по устойчивости процессов и значению T-инварианта можноопределить живость сети: если сеть жива и ограничена, то она инвариантна и устойчива.Поведенческие и структурные свойства сетей ПетриРазличают поведенческие и структурные свойства СП [304]. Свойство называют поведенческим, если оно справедливо при определённой начальной маркировки сети.
Одноименноесвойство называют структурным, если оно справедливо для любой допустимой маркировки сети. Поведенческие и структурные свойства различаются способом доказательства. Первые доказываются путём построения дерева достижимости СП, представляющего из себя граф, вершинами которого являются все допустимые маркировки сети.
Алгоритмы построения графа достижимости известны, однако трудоёмкость их построения растёт экспоненциально относительно числа позиций сети. Структурные свойства проверяются путём решения фундаментального уравнения СП [304], решение имеет полиномиальную сложность.В большинстве работ по анализу модели бизнес-процесса используют анализ поведенческих свойств модели, например, свойства живости и безопасности [299, 201, 300, 217] [301],[207], [302], [223].
Это накладывает на способы отображения исходного процесса в СП требование поведенческой эквивалентности. В работе [223] анализируются сложности, возникающиепри таком отображении. К сожалению, таким образом, удаётся отобразить в СП только наборэлементов, соответствующий предыдущей версии BPMN 1.0.Вместе с тем, возникает вопрос о целесообразности поведенческого моделирования процесса в нотации BPMN с помощью СП. Во-первых, СП не моделирует данные, так что нельзяопределить направление, по которому логический оператор маршрутизирует поток управления[307].
Это не позволяет анализировать поведение отдельного экземпляра процесса. Во-вторых,системы СУБП позволяют проводить динамический анализ процесса непосредственно в средемоделирования.Вместе с тем, доказав структурное свойство моделируемого процесса, мы сможем утверждать, что оно выполняется при любых сочетаниях данных процесса. Отказавшись от необходимости обеспечить поведенческую эквивалентность СП и бизнес-процесса, мы существенноупростим отображение модели процесса в СП.
Мы сосредоточимся на анализе структурныхсвойств модели бизнес-процесса.288Классификация СПАвтоматной (state machine) называют сеть Петри, у которой любой переход имеет не болееодного входа и не более одного выхода (формула 5.20), как показано на рисунке 5.15. Автоматныесети Петри позволяют описать последовательный процесс, в котором присутствует только ЛО«ИЛИ», но отсутствуют ЛО «И».|•t| = |t•| = 1 для ∀ t ∈ T(5.20)Источник: составлено автором по материалам [306]Рисунок 5.15 - Автоматная сеть ПетриМаркированной (market graph) называют СП, показанную на рисунке 5.16, у которых каждая позиция имеет не более одного входа и не более одного выхода (формула 5.21), они позволяют моделировать последовательно–параллельные процессы.|•p| = |p•| = 1 для ∀ p ∈ P(5.21)Рисунок 5.16.
Маркированный графИсточник: составлено автором по материалам [306]Сетью свободного выбора (free choice nets) — называется сеть, в которой каждая дуга,выходящая из позиции, является либо единственным выходом из неё, либо единственным входом в последующий переход, как показано на рисунке 5.17. Если p1 и р2 есть две позиции некоторой СП свободного выбора, тогда справедливо условие (5.22):p1• ⋂ р2• ≠ Ø ⇒ |p1•| = |р2•| для ∀ p1, р2 ∈ P(5.22)Рисунок 5.17 - Сеть свободного выбораИсточник: составлено автором по материалам [305]Методы анализа сетей свободного выбора хорошо исследованы, разработан механизм выявления ловушек и тупиков.Расширенной сетью свободного выбора (extended free choice nets) — называется подкласс сетей Петри, в котором у любых двух переходов: либо пересечение множеств их входных289вершин является пустым множеством, в противном случае множества их входных вершин эквивалентны.
Если p1 и р2 есть две позиции некоторой расширенной СП свободного выбора p1•,р2• ∈ P, тогда, справедлива формула (5.23):p1• ⋂ р2• ≠ Ø ⇒ |p1•| = |р2•| = 1 для ∀ p1, р2 ∈ P(5.23)Рисунок 5.18 - Расширенная сеть свободного выбораИсточник: составлено автором по материалам [305].Сетью ассиметричного выбора (asymmetric choice nets) — называется подкласс сетейПетри, изображённый на рисунке 5.19, у которых дуга, выходящая из какой-либо позиции, может не быть единственной исходящей, а у перехода, для которого она является входной, небыть единственной входящей. При этом, вторая дуга, входящая в этот же переход, приходит извторой позиции, для которой она является единственной исходящей. Если p1 и р2 есть две позиции некоторой СП ассиметричного выбора, тогда справедлива формула (5.24):p1• ⋂ р2• ≠ Ø ⇒ p1• ⊆ р2• или р2• ⊆ p1• для ∀ p1, р2 ∈ P(5.24)Рисунок 5.19 - Сеть асимметричного выбораИсточник: составлено автором по материалам [305]В узком смысле такую сеть называют сетью с позицией ассиметричного выбора [308].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
