Сети Петри. Анализ дискретных систем с помощью сетей Петри

Лекция №8. Сети Петри

1. ОПРЕДЕЛЕНИЕ СЕТЕЙ ПЕТРИ

1.1. Структура и граф сети Петри

Сеть Петри — это асинхронная сеть, связывающая между собой условия и события. Реализация событий выполняется отдельными действиями. Последовательность действий образует моделируемый процесс. Формально структура сети Петри задается четверкой:

S = < T, P, I, O >,

где T — множество переходов;

P — множество позиций;

I — входная функция инцидентности;

O — выходная функция инцидентности.

При описании сети пользуются обобщением понятия множества — комплектом. В отличие от множества, в котором каждый элемент множества входит в него только один раз, в комплекте один и тот же элемент может входить несколько раз. Рассмотрим пример, показывающий отличие понятия комплекта от понятия множества. Пусть имеется множество, состоящее из трех элементов: A1 = {a, b,c}. Пусть также имеются три комплекта, состоящие из тех же элементов:

A = {a, a, a, b}; B = {a, a, b, b, c}; C = {a}.

Основной операцией на комплекте является операция определениячисла экземпляров в комплекте. Она обозначается знаком #. Данная операция указывает, сколько раз встречается элемент в комплекте. Для нашего примера: # (a,A) = 3 (элемент a встречается в комплекте A три раза); # (c,A) = 0; #(b, B) = 2.

Входная и выходная функции сети (I, O) могут определяться через эту операцию. Они  связывают позиции с переходами и определяют входные и выходные позиции для перехода: p_i Î I (t_j) — входные позиции перехода t_j; p_i Î O (t_j) — выходные позиции перехода t_j.Граф сети представляет собой ориентированный двудольный мультиграф. На рис. 1.1. приведен пример графа сети Петри.

Рис. 1.1. Пример графа сети Петри: p₁, p₂ — позиции (места); t₁, t₂ — переходы

Граф называется двудольным, если в нем имеются два типа вершин и существуют только связи между вершинами разных типов. Для сети Петри имеются два типа вершин: позиции и переходы (p иt). Позиции связаны только с переходами. Переходы связаны только с позициями (см. рис. 1.1).

Граф называется мультиграфом (гиперграфом), если между двумя вершинами допускается дуга кратностью больше единицы. Так, для рассмотренного примера сети Петри существуют дуги кратностью большей единицы. Позиция p₁ с переходом t₁ связана двумя дугами. Переход t₂ с позицией p₁ связан четырьмя дугами.

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

I (t₁) = {p₁, p₁} — входные позиции для t₁;

I (t₂) = {p₂} — входные позиции для t₂;

O (t₁) = {p₂} — выходные позиции для t₁;

O (t₂) = {p₁, p₁, p₁, p₁} — выходные позиции для t₂.

Можем определить для данных комплектов значения функции числа экземпляров в комплекте, например: # (p₁, O (t₂)) = 4.

В сетях Петри связывают с действиями переходы, а с условиями — позиции. Входные позиции для перехода называются предусловиями, а выходные — постусловиями. Таким образом, с помощью сети Петри задают причинно-следственные связи между отдельными событиями.

1.2. Динамика сетей Петри

Присвоение позициям сети фишек — неотрицательных чисел — называется ее маркировкой. Маркировкой также называется вектор

M = (m₁, …, m_n),

где n — число позиций, m_i Î N È {0}.

Сеть Петри, заданная структурой и маркировкой, называется маркированной сетью Петри:

MS = < T, P, I, O, M >.

Фишки сети Петри иногда называются транзактами. На графе сети Петри фишки обозначаются кружочками. Так, на рис. 1.2 двум позициям p₁, p₂ присвоены неотрицательные числа 3и 1 соответственно.

Для рассматриваемого примера маркировка описывается вектором М = (3, 1).

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

Переход разрешен, если m (p_i) ³  # (p_i,I (t_j)). Одновременно срабатывает только один из разрешенных переходов.

Рис. 1.2. Пример размеченного графа сети Петри

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

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

2. Переход t_j срабатывает (запускается) только в том случае, если количество фишек входной позиции перехода m_i не меньше числа дуг, связывающих эту позицию и переход, то есть не меньше числа экземпляров комплекта, определяемого входной функцией этого перехода # (p_i, I (t_j)):

m_i ³ # (p_i, I (t_j)).

Для примера, приведенного на рис. 1.2, оба перехода t₁, t₂ являются разрешенными: 3 > 2, значит переход t₁ разрешенный, 1 ³ 1, переход t₂ также является разрешенным.

Можно для двух рассмотренных правил формально записать общее правило функционирования сети Петри:

m_i^’ = m_i – # (p_i, I (t_j)) + # (p_i, О (t_j)).