Задача 3. Анализ сетей Петри

Сеть Петри задана графически (рис.23…30). В табл.1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.

Выполнить следующие действия:

Описать сеть аналитическим и матричным способами.

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

Построить дерево достижимости заданной сети.

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

Таблица 1

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p₁, p₂, p₃, p₄, p₅} и переходы T = {t₁, t₂, t₃ , t₄ }.

Начальная маркировка сети обозначается вектором μ₀ [μ₁,μ₂,μ₃,μ₄,μ₅], μ₀ [1 3 0 1 2]. Отсюда получим:

При аналитическом способе задания сеть Петри задается как C = (P,T,F,H,μ₀), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции.

Через F (t _j ) обозначается множество входных позиций, а через H (t _j ) - множество выходных позиций перехода t _j; μ ₀ - начальная маркировка сети.

F (t₁) = {p₅},H (t₁) = {p₁, p₂ },

F (t₂) = {p₁},H (t₂) = {p₃, p₄},

F (t₃) = {p₃, p₄}H (t₃) = {p₁ },

F ( t ₄ ) = { p ₂ , p ₃ , p ₄ } H ( t ₄ ) = { p ₅ }.

μ₀ [1 3 0 1 2]

Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = ( P , T , D ^- , D ⁺ ,μ⁰). Здесь D ^- и D ⁺ - матрицы входных и выходных инциденций соответственно размером m × n, где m - число переходов и n - число позиций.

Элемент d_ij ^- матрицы D ^- равен кратности дуг, входящих в i-й переход из j-й позиции.

Элемент d_ij ⁺ матрицы D ⁺ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.

Для рассматриваемой сети Петри

Матрица D = D ⁺ - D ^- называется матрицей инцидентности сети Петри,

2. При начальной маркировке μ₀ [1 3 0 1 2] сети Петри разрешенными являются переходы t ₁ и t ₂.

Условия срабатывания для перехода t ₃ и t ₄ не выполняется.

Переход t ₁

[μ₀] ≥ [1000]* D ^- = [1000] · ; [1 3 0 1 2] ≥ [00001] –

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t ₁ равна:

.

Переход t ₂

[μ₀] ≥ [0100]* D ^- = [0100] ·;[1 3 0 1 2] ≥ [10000] –

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t ₂ равна:

.

Переход t ₃

[μ₀] ≥ [0010]* D ^- = [0010] ·;[1 3 0 1 2] ≥ [00110] - условие не

выполняется, переход запрещен.

Переход t ₄

[μ₀] ≥ [0001]* D ^- = [0001] ·;[1 3 0 1 2] ≥ [01110] –

условие не выполняется, переход запрещен.

Построим дерево достижимости заданной сети.

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

Уравнение  принимает вид

Перенесем  в левую часть и выполним умножение, тогда

.

Приравняем составляющие векторов

Система имеет решение x ₁ = 1; x ₂ = 2; x ₃ = 0; x ₄ = 2.

Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t ₁ срабатывает один раз, переходы t ₂ и t ₄ - по два раза, переход t ₃ не срабатывает.