Сети Петри

Сети Петри основаны на теории графов и являются их развитием для имитационного моделирования динамических систем.

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

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

В этой постановке задачи Эйлер впервые сопоставил реальной географической карте абстрактный граф, в котором берега представлялись точками графа, а ребра графа соответствовали мостам. Этот граф является графом общего вида.

Представленный на рис.1 граф G=(A,C) может быть записан с помощью двух неупорядоченных множеств:

множества вершин А={а1, а2, а3, а4}

и множества ребер С={с1, с2, с3, с4, с5, с6, с7},

где: с1={а1, а2}; с2={а2, а1}; с3={а1, а3}; с4={а2, а3}; с5={а2, а4}; с6={а4, а2}; с7={а3, а4}.

Этот же граф G=(A,C) может быть задан матрицей смежности вершин:

- без учета количества связей (валентности) вершины

- с указанием количества связей (валентности) вершины

Этот же граф может быть задан матрицей инцидентности ребер вершинам

а также матрицей смежности ребер:

- без конкретизации общих вершин

- с указанием общих вершин

Для моделирования других систем применяются другие типы графов.

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

Примером применения направленного графа является сетевой график. В сетевых графиках выделяются три типа вершин:

- начальная (исток), из которой выходят дуги, но ни одна не входит;

- промежуточные, в которые входят и из которых исходят дуги;

- конечная (сток), в которую дуги только входят.

Применяются различные формы представления (задания) графов:

- в форме рисунка, на котором вершины обозначаются кружками или точками, а ребра или дуги соединяют эти вершины линиями или стрелками;

- перечислением взаимосвязанных элементов двух типов множеств: множества вершин и множества ребер или дуг;

- в форме матриц смежности и матриц инциденций.

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

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

Элементами сети Петри являются вершины двудольного графа:

- позиции, изображаемые кружочками;

- переходы, изображаемые утолщенными черточками.

Входные и выходные функции представляются дугами графа, соединяющими вершины и направленными:

- для входных функций – от позиций к переходам;

- для выходных функций – от переходов к позициям.

Эти элементы сети Петри являются статическими объектами.

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

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

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

Правила срабатывания переходов можно представить следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие , где – число маркеров в i-той позиции, а –число дуг, идущих от i-той позиции к срабатывающему переходу; в результате срабатывания перехода число маркеров в i-той позиции уменьшается на , а в j-той выходной позиции увеличивается на , где – число дуг, связывающих сработавший переход с j-той выходной позицией.

На рисунках 2 и 3 проиллюстрировано распределение маркеров по позициям:

- на рис.2 – начальное распределение ,

- на рис.3 – распределение полученное

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

Рис. 2. Фрагмент сети Петри, заданный вершинами позиций и вершиной переходов с начальной маркировкой .

Рис. 3. Фрагмент сети Петри, заданный вершинами позиций и вершиной переходов после первого срабатывания перехода с изменившейся маркировкой .

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

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

Формально сеть Петри представляется как набор вида:

С=(P, T, F, W, μ₀), (1)

где P – множество позиций, под которыми будем понимать состояния объекта и системы эксплуатации, являющиеся условиями элементарных операций процесса подготовки составных частей РКН; Т – множество переходов (событий), т.е. элементарных операций процесса подготовки; - множество дуг (отношения инциндентности) такое, что любой элемент сети инциндентен хотя бы одному элементу другого типа; - функция кратности дуг; - начальная маркировка сети, соответствующая исходному состоянию объекта и системы эксплуатации.

Функция инцидентности F представляется реализацией двух функций: I – входов и O – выходов:

(2)

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

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

(3)

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

, (4)

т.е. в результате срабатывания из всех входных позиций перехода t изымается F(p,t) маркеров и в каждую выходную позицию добавляется W(t,p) маркеров. Это означает, что маркировка ' непосредственно до­стижима из маркировки и обозначается —> .

Графическим изображением сети Петри является двудольный ориен­тированный граф с двумя типами вершин принадлежащих множеству P и T, а дуги соответствуют функции инцидентности позиций и переходов. На рис. 3 (в автореферате) представлена сеть Петри для операции “Проверка давления транспортирования элементов ПГС РБ” в матричном (рис. 3а) и графическом (рис. 3б) виде.

Базовая имитационная модель процесса подготовки СЧ и РКН в целом на ТК и СК, представленная сетью Петри, дополняется статистической моделью безотказности объекта в процессе испытаний, что, используя аппарат временных и расширенных сетей Петри, позволяет перейти к модели процесса с учетом возникновения нештатных ситуаций, где вероятность появления НшС в системе эксплуатации:

(5)

где P_оз – вероятность появления отказа в изделии, P_i – вероятность ошибка расчета, P_j – вероятность ошибки в технологическом процессе.