Теория вычислительных процессов Анализ сетей Петри Преподаватель: Веретельникова Евгения Леонидовна 1. - презентация

1 Теория вычислительных процессов Анализ сетей Петри Преподаватель: Веретельникова Евгения Леонидовна 1

2 Задачи анализа сетей Петри Безопасность Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, – безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1. Сеть Петри безопасна, если безопасны все позиции сети. Если позиция не является кратной входной или кратной выходной для перехода, ее можно сделать безопасной. К позиции p i, которую необходимо сделать безопасной, добавляется новая позиция p' i. Переходы, в которых p i используется в качестве входной или выходной, модифицируются следующим образом: 2

3 Задачи анализа сетей Петри Безопасность Если p i I(t j ) и p i О(t j ), тогда добавить p' i к О(t j ). Если p i О(t j ) и p i I(t j ), тогда добавить p' i к I(t j ). Простая сеть Петри на рис.1 преобразована в безопасную на рис. 2. Небезопасная сеть Петри. Безопасная сеть Петри 3

4 Задачи анализа сетей Петри Ограниченность Безопасность – это частный случай более общего свойства ограниченности. Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k. 1-безопасная позиция называется просто безопасной. Заметим, что граница k' по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p 1 может быть 3-безопасной, тогда как позиция р 2 – 8-безопасной). Однако, если позиция p i k - безопасна, то она также и k'-безопасна для всех k' k. Поскольку число позиций конечно, можно выбрать k, рав- ное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k- безопасна. Иногда нас будет интересовать только то, является число фишек в позиции ограниченным или нет, а не конкретное значение границы. Позиция называется ограниченной, если она k-безопасна для некоторого k; сеть Петри ограниченна, если все ее позиции ограниченны. 4

5 Задачи анализа сетей Петри Ограниченность Иногда нас будет интересовать только то, является число фишек в позиции ограниченным или нет, а не конкретное значение границы. Позиция называется ограниченной, если она k-безопасна для некоторого k; сеть Петри ограниченна, если все ее позиции ограниченны. 5

6 Задачи анализа сетей Петри Сохранение Определение 3. Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ' R(C, μ ). Строгое сохранение – это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, |I(t j )| = |О(t j )|. Если бы это было не так, запуск перехода изменил бы число фишек в сети. 6

7 Задачи анализа сетей Петри Сохранение Однако для более общего представления о свойстве сохранения рассмотрим рис. 3. Изображенная на нем сеть Петри не является строго сохраняющей, поскольку запуск перехода t 1 или t 2 уменьшит число фишек на 1, а запуск перехода t 3 или t 4 добавит фишку к маркировке. Мы можем тем не менее преобразовать эту сеть Петри в сеть на рис. 4, являющуюся строго сохраняющей. 7

8 Задачи анализа сетей Петри Сохранение В общем можно определить взвешивание фишек. Взвешенная сумма для всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0; другим фишкам можно присвоить веса 1, 2, 3 или любое другое целое. Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания w = (w 1, w 2,..., w n ) определяет вес w i для каждой позиции p i P. 8

9 Задачи анализа сетей Петри Сохранение Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется сохраняющей по отношению к вектору взвешивания w, w = (w 1, w 2,..., w n ), n = |Р|, w i 0, если для всех μ' R(C, μ ). Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1,..., 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0,..., 0). Поэтому сеть Петри будем назы- вать сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому вектору взвеши- вания w >0 (с положительными ненулевыми весами, w i > 0). Так сеть Петри с рис. 3 является поэтому сохраняющей, поскольку она сохраняющая по отношению к (1, 1, 2, 2, 1). 9

10 Задачи анализа сетей Петри Активность Тупик в сети Петри – это переход (или множество переходов), которые не могут быть запущены. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход t j сети Петри С называется потенциально запустимым в маркировке μ, если существует маркировка μ' R(C, μ), в которой t j разрешен. Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(C, μ). Следовательно, если переход активен, то всегда возможно перевести сети Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным. 10

11 Задачи анализа сетей Петри Активность Существуют другие, связанные с активностью понятия, которые рассматривались при изучении тупиков. Их можно разбить на категории по уровню активности и определить для сети Петри С с маркировкой μ следу- ющим образом: Уровень 0: Переход t j обладает активностью уровня 0, если он никогда не может быть запущен. Уровень 1: Переход t j обладает активностью уровня 1, если он потенциально запустим, т.е. если существует такая t j μ' R(C, μ), что t j разрешен в μ. 11

12 Задачи анализа сетей Петри Активность Уровень 2: Переход t j обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой t j присутствует по крайней мере n раз. Уровень 3: Переход t j обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой t j присутствует неограниченно часто. Уровень 4: Переход t j обладает активностью уровня 4, если для всякой μ' R(C, μ) существует такая после- довательность запусков σ, что t j разрешен в δ(μ', σ). 12

13 Задачи анализа сетей Петри Активность Переход, обладающий активностью уровня 0, называется пассивным. Переход, обладающий активностью уровня 4, называется активным. Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i. В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 5. Переход t 0 не может быть запущен никогда; он пассивен. Переход t 1 можно запустить точно один раз; он обладает активностью уровня 1. Переход t 2 может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t 3. Если мы хотим запустить t 2 пять раз, мы запускаем пять раз t 3, затем t 1 и после этого пять раз t 2. 13

14 Задачи анализа сетей Петри Активность Однако, как только запустится t 1 (t 1 должен быть запущен до того, как будет как будет запу- щен t 2 ), число возможных запу- сков t 2 станет фиксированным. Следовательно, t 2 обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t 3 можно запускать бесконечное число раз, и поэтому он обладает актив- ностью уровня 3, но не уровня 4, поскольку, как только запу- стится t 1, t 3 больше запустить будет нельзя. 14

15 Задачи анализа сетей Петри Достижимость и покрываемость Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок. Задача достижимости является, по-видимому, наиболее простой (для формулировки). Определение 4.5. Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ' определить: μ' R(C, μ) ? Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости. Например, для сети Петри с рис.5 тупик может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0). 15

16 Задачи анализа сетей Петри Достижимость и покрываемость Задача покрываемости аналогична достижимости, но несколько отличается от нее. Маркировка μ" покрывает маркировку μ', если μ" μ'. Определение 4.6. Задача покрываемости. Для данной сети Петри С с начальной маркировкой μ и маркировки μ' определить, существует ли такая достижимая маркировка μ" R(C, μ), что μ" μ'. 16

17 Методы анализа сетей Петри Дерево достижимости Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 6. Начальная маркировка ее – (1, 0, 0). В этой начальной маркировке разрешены два перехода: t 1 и t 2. Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достижимости для (достижи- мых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 7). 17

18 Методы анализа сетей Петри Дерево достижимости Корневой (начальной) является вершина, соответ- ствующая начальной маркировке. Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки. 18 Рис. 6. Маркированная сеть ПетриРис. 7. Первый шаг построения дерева достижимости

19 Методы анализа сетей Петри Дерево достижимости Теперь необходимо рассмотреть все маркировки, достижи- мые из новых маркировок. Из маркировки (1, 1,0) можно снова запустить t 1 ( получая (1, 2, 0)) и t 2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t 3 (получая (0, 0, 1)). Это порождает дерево, изображенное на рис Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рис Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1, 1), порождаемая запуском t 3 в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском t 2. 19

20 Методы анализа сетей Петри Дерево достижимости Рис. 8. Второй шаг построения дерева 20

21 Методы анализа сетей Петри Дерево достижимости 21 Рис. 9. Третий шаг построения дерева

22 Методы анализа сетей Петри Дерево достижимости Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся дерево достижимости может оказаться бесконечным. Будет порождена каждая маркировка из множества достижимости, поэтому для любой сети Петри с бесконечным множеством достижимости соответствующее дерево также должно быть бесконеч- ным. Даже сеть Петри с конечным множеством дости- жимости может иметь бесконечное дерево (рис. 10). Дерево представляет все возможные последова- тельности запусков переходов. 22

23 Методы анализа сетей Петри Дерево достижимости 23

24 Методы анализа сетей Петри Дерево достижимости Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. (Заметим, что если какое-то представление бесконечного множества конечно, то бесконечное множество маркировок должно отображаться в такое представление. В общем случае это приведет к потере информации и, возможно, к тому, что некоторые свойств сетей Петри определить будет нельзя, но все зависит от того, как представление было получено.) 24

25 Методы анализа сетей Петри Дерево достижимости Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки – маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок – это маркировки, ранее встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами; 25

26 Методы анализа сетей Петри Дерево достижимости никакие последующие маркировки рассматривать нет нужды – все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 9 маркировка (0, 1, 1), получившаяся в результате выполнения последовательности t 1 t 2 t 3, не будет порождать какие- либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t 2 из начальной маркировки. 26

27 Методы анализа сетей Петри Дерево достижимости Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке μ и кончающуюся в маркировке μ', μ' > μ. Маркировка μ' совпадает с маркировкой μ, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, т. е. μ' = μ + (μ' – μ) > 0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная в μ', приходя к маркировке μ". 27

28 Методы анализа сетей Петри Дерево достижимости Так как действие последовательности переходов σ добавило μ' – μ фишек к маркировке μ, она добавит также μ' – μ фишек и к маркировке μ', поэтому μ'' = μ' + (μ' – μ) или μ'' = μ + 2(μ' – μ). В общем можно запустить последовательность σ n раз, получив в результате маркировку μ + n(μ' – μ). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 7, например, можно запустить переход t 1 столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р 2. 28

29 Методы анализа сетей Петри Дерево достижимости Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа ω, который обозначает «бесконечность». Для любого постоянного а определим ω + а = ω, а < ω, ω – а = ω, ω ω. Для построения дерева достижимости необходимы только эти операции над ω. 29

30 Методы анализа сетей Петри Дерево достижимости Теперь можно точно сформулировать действительный алгоритм построения дерева достижимости. Каждая вершина i дерева связывается с расширенной маркировкой μ [i]; в расширенноq маркировке число фишек в позиции может быть либо неотрицательным целым, либо ω. Каждая вершина классифицируется или как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Граничными являются вершины, которые еще не обработаны алгоритмом; алгоритм превратит их в терминальные, дублирующие или внутренние вершины. 30

31 Методы анализа сетей Петри Дерево достижимости Алгоритм начинает с определения начальной марки- ровки корнем дерева, т.е. граничной вершиной. До тех пор пока имеются граничные вершины, они обрабатыва- ются алгоритмом. Пусть х – граничная вершина, которую необходимо обработать. 1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана та же маркировка, μ[х] = μ[у]; то вершина х – дублирующая. 2. Если для маркировки μ[х] ни один из переходов не разрешен (т.е. δ(μ[х], t j ) не определено для всех t j Т), то х – терминальная вершина. 31

32 Методы анализа сетей Петри Дерево достижимости 3. Для всякого перехода t j Т, разрешенного в μ[х] (т.е. δ(μ[х], t j ) определено), создать новую вершину z дерева достижимости. Маркировка μ[z], связанная с этой вершиной, определяется для каждой позиции р i следующим образом: а) Если μ[х] i = ω, μ[z] i = ω. б) Если на пути от корневой вершины к х существует вершина y с μ[y] < δ(μ[х], t j ) и μ[y] i

33 Методы анализа сетей Петри Дерево достижимости Когда все вершины дерева – терминальные, дублиру- ющие или внутренние, алгоритм останавливается. 33

34 Методы анализа сетей Петри Дерево достижимости Сеть Петри и ее дерево достижимости 34

35 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Безопасность и ограниченность Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое k, что число фишек в любой позиции не может превысить k. Оба этих свойства можно проверить с помощью дерева достижимости. Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в ее дереве достижимости. Присутствие символа ω в дереве достижимости означает, что число фишек потенциально не ограничено; сущест- вует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая количество фишек до произвольно большого числа. 35

36 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Таким образом, если имеется символ ω, сеть неогра- ниченна. Кроме того, положение символа ω показывает, какие позиции неограниченны. Обратное утверждение также является верным, если сеть Петри неограниченна, то число достижимых мар- кировок бесконечно. Поскольку дерево достижимости конечно, бесконечное число достижимых маркировок отражает присутствие символа ω. Если сеть Петри огра- ниченна и символ ω отсутствует в дереве достижимости, то сеть Петри представляет систему конечных состояний. Дерево достижимости, по существу, является графом состояний и будет содержать вершину, соответствующую всякой достижимой маркировке. 36

37 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых маркировок. Например, чтобы определить границу для заданной позиции, нужно построить дерево достижимости и найти наибольшее значение компо- ненты маркировки, соответствующей этой позиции. Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций не превышает 1, сеть безопасна. На рис. 13 демонстрируется использование дерева достижимости для определения ограниченности. 37

38 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Рис. 13. Определение ограниченности для сети Петри с помощью дерева достижимости. 38

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

40 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Свойство сохранения эффективно проверяется с помощью дерева достижимости. Так как дерево достижимости конечно, для каждой маркировки можно вычислить взвешенную сумму. Если сумма одинакова для каждой достижимой маркировки, сеть – сохраняю- щая по отношению к данному весу. Если суммы не равны сеть – несохраняющая. При оценке сохранения необходимо быть внимате- льным с символом ω. Если маркировка имеет ω в качестве маркировки позиции p i, тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. 40

41 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Напомним, что символ ω представляет бесконечное множество значений. Так как все веса неотрицательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важно), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различающихся в своей ω- компоненте. Следовательно, если какая-либо маркиров- ка с ненулевым весом равна ω, сеть несохраняющая. Эти рассуждения относятся к сохранению по отноше- нию к определенному взвешиванию. Сеть Петри являет- ся сохраняющей, если она сохраняющая по отношению к некоторому вектору w, w i > 0. 41

42 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов w (если он существует). Заметим прежде всего, что для того, чтобы сеть Петри была сохраняющей по отношению к положительному вектору весов, она должна быть ограниченной. Как было указано выше, неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. (Если мы хотим допустить нулевые компоненты, нужно просто установить веса всех неограниченных позиций равными нулю и рассматри- вать после этого только оставшиеся компоненты.) 42

43 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее s, и вектор весов w = (w 1, w 2,..., w n ). Для каждой маркировки μ[х] дерева достижимости имеем w 1 · μ[х] 1 + w 2 · μ[х] w n · μ[х] n = s. Это равенство определяет для k вершин дерева достижимости совокупность из k линейных уравнений с n + 1 неизвестными. Добавим к ним ограничения: w i > 0, i = 1,..., n, в результате чего определим ограничения для вектора весов. 43

44 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Решение этой системы линейных уравнений – хорошо известная задача, имеющая множество алгоритмов решения. Если ограничения, накладываемые на веса, являются чрезмерно жесткими и, следовательно, вектора взвешиваний не существует, это будет определено. В любом случае можно определить, является или нет сеть Петри сохраняющей, и если это так, получить вектор весов. 44

45 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Покрываемость Последняя задача, которую можно решить с помощью дерева достижимости, – задача покрываемости. В задаче покрываемости мы хотим для данной маркировки μ' определить, достижима ли маркировка μ" μ'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево достижимости. Затем ищем любую вершину х с μ[х] μ'. Если такой вершины не существует, маркировка μ' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую маркировку, покрывающую μ. 45

46 Использование дерева достижимости для решения некоторых задач анализа сетей Петри Путь от корня к покрывающей маркировке определяет последовательность переходов, которые приводят из начальной маркировки к покрывающей маркировке, а маркировка, связанная с этой вершиной, определяет покрывающую маркировку. Символ ω вновь должен рассматриваться как обозначение бесконечного множества значений. Если компонента покрывающей маркировки – ω, то в пути от корня к покрывающей маркировке имеется «цикл». Для увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточное число раз повторить этот цикл. 46

47 Матричные уравнения Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к определению сети Петри в виде (Р, Т, I, О) является определение двух матриц D – и D +, представляющих входную и выходную функции. Каждая матрица имеет m строк (по одной на переход) и n столбцов (по одному на позицию). Определим D – [j, i] = #(p i, I(t j )), a D + [j, i] = #(p i, O(t j )). D – определяет входы в переходы, D + – выходы. 47

48 Матричные уравнения Матричная форма определения сети Петри (Р, Т, D –, D + ) эквивалентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть e[j] – m-вектор, содержащий нули везде, за исключением j-й компоненты. Переход t j представляется m-вектором-строкой е[j]. Теперь переход t j в маркировке μ разрешен, если μ e[j] · D –, а результат запуска перехода t j в маркировке μ записывается как δ(μ, t j ) = μ – e[j] · D – + e[j] · D + = = μ + e[j] · (– D – + D + ) = μ + e[j] · D, где D = D + – D – – составная матрица изменений. 48

49 Матричные уравнения Тогда для последовательности запусков переходов σ = t j1 t j2... t jk имеем δ(μ, σ) = δ(μ, t j1 t j2... t jk ) = μ + e[j 1 ] · D + e[j 2 ] · D + … + e[j k ] · D = = μ + (e[j 1 ] · D + e[j 2 ] · D + … + e[j k ] ) · D = μ + f(σ) · D. Вектор f(σ) = e[j 1 ] · D + e[j 2 ] · D + … + e[j k ] называется вектором запусков последовательности t j1 t j2... t jk. Тогда i-й элемент вектора f(σ), f(σ) i – это число запусков перехода t i в последовательности t j1 t j2... t jk. Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами. (Вектор f(σ) – это отображение Пaрихa последовательности.) 49

50 Матричные уравнения Покажем полезность матричного подхода к сетям Петри решением задачи сохранения: является ли данная маркированная сеть Петри сохраняющей? Для того чтобы показать сохранение, необходимо найти (ненулевой) вектор взвешивания, для которого взвешенная сумма по всем достижимым маркировкам постоянна. Пусть w – n 1 – вектор-столбец. Тогда, если μ – начальная маркировка, а μ' – произвольная достижимая маркировка, необходимо, чтобы μ · w = μ' · w. Теперь, поскольку μ' достижима, существует последовательность запусков переходов σ, которая переводит сеть из μ в μ'. Поэтому μ' = δ(μ, σ) = μ + f(σ) · D. 50

51 Матричные уравнения Следовательно, μ · w = μ' · w = (μ + f(σ) · D) · w = μ · w + f(σ) · D · w, поэтому f(σ) · D · w = 0. Поскольку это должно быть верно для всех f(σ), имеем D · w = 0. Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный вектор w, что D · w = 0. Это обеспечивает простой алгоритм проверки сохранения, а также позволяет получать вектор взвешивания w. 51

52 Матричные уравнения С помощью матричного подхода можно решить и проблему достижимости. Предположим, что маркировка μ' достижима из маркировки μ. Тогда существует последовательность (возможно, пустая) запусков переходов σ, которая приводит из μ к μ'. Это означает, что f(σ) является неотрицательным целым решением следующего матричного уравнения для х: μ' = μ + x · D.(*) Следовательно, если μ' достижима из μ, тогда уравнение (*) имеет решение в неотрицательных целых; если уравнение (*) не имеет решения, тогда μ' недостижима из μ. 52

53 Матричные уравнения ПРИМЕР: Рассмотрим маркированную сеть Петри. Матрицы D –, D + и D имеют вид:,,. 53

54 Матричные уравнения В начальной маркировке μ = (1, 0, 1, 0) переход t 3 разрешен и приводит к маркировке μ', где μ' = (1, 0, 1, 0) + (0, 0, 1) · = (1, 0, 1, 0) + (0, 0, –1, 1) = (1, 0, 0, 1). Последовательность σ = t 3 t 2 t 3 t 2 t 1 представляется век- тором запусков f(σ) = (1, 2, 2) и получает маркировку μ': μ = (1, 0, 1, 0) + (1, 2, 2) · = = (1, 0, 1, 0) + (0, 3, –1, 0) = (1, 3, 0, 0). 54

55 Матричные уравнения Для определения того, является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0), имеем уравнение (1, 8, 0, 1) = (1,0, 1, 0) + х ·, (0, 8, –1, 1) = х ·, которое имеет решение х = (0, 4, 5). Это соответствует последовательности σ = t 3 t 2 t 3 t 2 t 3 t 2 t 3 t 2 t 1. 55

56 Матричные уравнения Можно показать, что маркировка (1, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0), поскольку матричное уравнение (1, 7, 0, 1) = (1,0, 1, 0) + х ·, (0, 7, –1, 1) = х · не имеет решения. 56