Лекция 21

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

Сеть Петри определяется четверкой объектов

где – конечные множества позиций (мест) и переходов, соответственно; и –отображения переходов во множество позиций (входная и выходная функции, соответственно).

Входная функция I отображает переход во множество позиций называемых входными позициями перехода, а выходная функция O – во множество позиций называемых выходными позициями перехода.

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

Дуги мультиграфа соединяют переходы только с позициями, а позиции – только с переходами, поэтому мультиграф является двудольным. Совокупность переходов, позиций и дуг позволяет описать статику сети Петри.

Представление динамики сети Петри опирается на понятия: события, услов­ия, которые эти события определяют, и причинно-следственные отношения, устанавливаемые на множестве «события-условия». Появление события определяет состояние системы, которое описывается множеством условий. Усло­вие – это описание состояния системы. В сетях Петри условия моделируются позициями, а события – переходами.

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

Маркировка сети Петри представляет собой функцию m, отображающую множество позиций P во множество неотрицательных целых чисел N, т.е. Маркировка сети может быть определена как вектор m = (m ₁, …, m_i, …, m_n), где

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

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