Лабораторная работа № 3

АНАЛИЗ СВОЙСТВ СЕТЕЙ ПЕТРИ

Цель работы - изучение форм представления сетей Петри и их анализ в среде системы компьютерной математики Mathcad.

Основные понятия и определения

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

;	;
;	;
;	;
;	.

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

Рис. 5. Граф сети Петри

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

Функции входов и выходов могут быть представлены матрицами инцидентности  соответственно. Каждая матрица имеет – строк и – столбцов. Элементы матрицы определяются следующим образом:

,   .

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

,

где  – составная матрица изменений маркировок. Для последовательности запусков переходов  вектор запусков определяется соотношением: . Элемент вектора  – число запусков перехода в последовательности . При этом смена маркировки определяется соотношением:

.

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

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

Сеть Петри консервативна, или S - инвариантна, если существует положительное целое число , связанное с каждой позицией , такое, что сумма маркеров постоянна для любой маркировки , достижимой из :

.

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

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

Лабораторное задание

1. Согласуйте с преподавателем вариант структуры и начальной маркировки сети Петри. Постройте граф сети в документе.

2. Определите входную и выходную функции сети Петри, матрицы инцидентности , вектор начальной маркировки .          

3. Постройте дерево достижимости сети Петри с использованием матричного способа описания.

4. Определите достижимость маркировки  из начальной маркировки  и последовательность запусков переходов .

5. Исследуйте структурные свойства сети Петри: ограниченность, консервативность, повторяемость и непротиворечивость.

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

Протокол формализованного задания и анализа сети Петри по всем пунктам лабораторного задания средствами системы MathCAD.

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

1. Какие используются способы аналитического и графического представления маркированных сетей Петри?

2. Каким образом выполняется смена маркировки и определяется пространство состояний сети Петри?

3. Каким образом осуществляется матричный способ описания выполнения маркированной сети Петри?

4. По каким правилам и в какой последовательности строится дерево достижимости маркированной сети Петри?

5. Какие структурные свойства сети Петри зависят только от топологии и не зависят от начальной маркировки?