Главная | Обратная связь

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

 

 

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

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

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

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

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

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

 

Таблица 1

№ варианта

m1

m2

m3

m4

m5

№ рисунка

Рис. 23

Рис. 27

Рис. 28

Рис. 29

 

 

 

Решение:

1. Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p₁, p₂, p₃, p₄, p₅} и переходы T = {t₁, t₂, t₃, t₄, t₅}. Начальная маркировка сети обозначается вектором μ₀ [μ₁,μ₂,μ₃,μ₄,μ₅], μ₀ [1 3 1 0 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₄},

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

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

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

μ₀ [1 3 1 0 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 1 0 2] сети Петри.

 

 

Переход t₁

[μ₀] ≥ [10000]* D^– = [10000] · ; [1 3 1 0 2] ≥ [1 0 0 0 0] – условие выполняется, переход разрешен.

 

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

 

.

 

Переход t₂

[μ₀] ≥ [01000]* D^– = [01000] ; [1 3 1 0 2] ≥ [0 1 0 0 0] – условие выполняется, переход разрешен.

 

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

 

.

 

Переход t₃

[μ₀] ≥ [00100]* D^– = [00100] ; [1 3 1 0 2] ≥ [0 0 1 0 0] – условие выполняется, переход разрешен.

 

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

 

 

.

 

Переход t₄

[μ₀] ≥ [00010]* D^– = [00010] ; [1 3 1 0 2] ≥ [0 0 0 1 1] – условие не выполняется, переход запрещен.

 

Переход t₅

[μ₀] ≥ [00001]* D^– = [00001] ; [1 3 1 0 2] ≥ [0 0 0 1 1] – условие не выполняется, переход запрещен.

 

 

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

 

 

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

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

 

 

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

 

 

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

 

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

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