Порядок выполнения работы. 1. Изучить правила функционирования сетей Петри

1. Изучить правила функционирования сетей Петри.

2. Из набора заданий к самостоятельной работе выбрать свою сеть Петри.

3. Представить сеть Петри в виде двудольного графа.

4. Описать связи , , , .

5. Построить матрицу R сети Петри.

6. Выбрать начальную маркировку М₀ и просчитать маркировку на 5 шагов М₁,…,М₅ с возможными равновероятными вариантами.

7. Построить дерево маркировок.

8. Выбрать маркировки и проверить их достижимость.

9. Проверить сохраняемость сети и определить веса.

10. Выполнить проверку.

11. Оформить отчет по самостоятельной работе.

Содержание работы и пример выполнения

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

Позиции обозначают окружностями, а переходы планками. Ниже приведен пример сети Петри:

Рис. 1. Графическое представление сети Петри

Рис. 2. Представление сети Петри в виде двудольного графа

Для данной сети Петри |P| = n = 4, |T| = m = 2.

I(t₁) = {p₁, p₃} I(t₂) = {p₂}

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

I(p₁) = Æ I(p₂) = {t₁} I(p₃) = {t₂} I(p₄) = {t₂}

O(p₁) = {t₁} O(p₂) = {t₂} O(p₃) = {t₁} O(p₄) = Æ

Матрица сети Петри размера m´n: ,

,

где

,

Отсюда

, ,

Пусть m(j) – m-мерный вектор из нулей с единицей на j-м месте, j = 1,…,m.

Условие разрешения перехода :

M ³ m(j)

Правило функционирования:

M₁ = M₀ + m(j)R

Рассмотрим маркировки

и

Необходимо определить разрешенность данных маркировок:

m(1)

т.к. , то условие ³ m(1) не выполняется:

m(2)

не выполняется; следовательно, такая сеть функционировать не будет и маркировка не разрешена.

В то же время

m(1) -

переход разрешен; маркировка разрешена. Функционирование сети с данной маркировкой на один шаг:

m(1)

m(2)

следовательно, сработать может любой переход.

Рис. 3. Дерево маркировок после первого шага

На втором шаге необходимо проверить все переходы для маркировок и и т.д.

Следующий этап – исследование достижимости некоторой маркировки M^~. Задача достижимости сводится к определению неотрицательного целочисленного вектора

m = m(j₁) + m(j₂) + m(j₃) +…+ m(j_k)

где k – количество шагов.

Необходимо решить уравнение:

mR = M² - M

Пусть

Имеем систему четырех уравнений с двумя неизвестными; m не может равняться –1 или 0.5; следовательно, маркировка M² не достижима.

Если

то

Следовательно, m₂ = 1, m₁ = 0, m = m(2) = . Это означает, что разрешен второй переход и метка M² достижима.

Для проверки сохраняемости и отыскания сохраняющих весов необходимо решить уравнение RW = 0, где

Для рассматриваемого примера:

Система имеет множество решений.

Пусть w₃ = a, w₄ = b; тогда w₂ = a + b, w₁ = b, W = (b, a + b, a, b). Например, если b = 0, a = 1, то W = (0, 1, 1, 0). Данная сеть Петри является сохраняющей. Проверка заключается в установлении равенства MW = M²W.

Содержание отчета

1. Титульный лист.

2. Задание, выданное преподавателем.

3. Результаты расчетов по всем пунктам раздела 3.

4. Выводы о сети Петри.

Контрольные вопросы

1. Чем описывается функционирование сетей Петри?

2. Назовите основные правила функционирования сетей Петри.

3. Опишите матричное представление сети Петри.

4. Какая маркировка M_k называется непосредственно достижимой из маркировки M_k-1?

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

6. Как определяется достижимость маркировки?

7. Какая сеть Петри является сохраняющей?

8. Как осуществляется проверка сохраняемости и отыскания сохраняющих весов?

9. Как строится дерево маркировок сети Петри?