4.4.2 Формальное и графическое представление сетей Петри

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

В сетях Петри условия моделируются позициями, а события — переходами.

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

С = (Р, Т, Е), где

Р — непустое конечное множество позиций сети;

Т — непустое конечное множество переходов;

— отношение инцендентности позиций и переходов (множество дут сети) -логически обусловленные причинно-следственные связи между событиями и условиями.

Также могут быть заданы:

W: F  N — функция кратности дуг (каждой дуге ставится в соответствие n > 0 кратность дуг);

M: P  N -функция начальной разметки.

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

Графически ординарные сети Петри представляются двудольными орграфами:

С = (Р, Т, Е).

Множество вершин в таких орграфах состоит из непересекающихся подмножеств позиций

и переходов , а множество дуг Е разделяется на два подмножества и . Дуги ориентированы от позиций к переходам, а дуги — от переходов к позициям.

В изображении графов, представляющих ординарные сети Петри, позиции принято обозначать кружками, а переходы — барьерами (планками) следующим образом:

Рисунок 4.4.2 — Обозначения основных элементов сетей Петри

Для примера рассмотрим фрагмент сети Петри, моделирующей структуру процессов функционирования производственной системы, соответствующий примеру, приведенному в таблице 4.4.

Рисунок 4.4.3 — Фрагмент сети Петри

Реальный процесс может иметь более сложное ветвящееся графическое изображение (рис. 4.4.4).

Рисунок 4.4.4 — Фрагмент сети Петри

4.4.3 Динамика сетей Петри

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

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

Механизм маркировки позиций. Изменение состояния сети связано с механизмом изменения маркировок позиций. Начальное состояние сети Петри задается с помощью маркировки ее позиций. Маркировка сети (разметка позиции-места) заключается в присвоении позициям числовых значений (меток, маркеров, фишек). Метки представляют собой набор атрибутов (числа, переменные). Например, начальную разметку можно записать в виде вектора М₀(p) = (00000110100), где 1- соответствует условиям, которые должны быть выполнены.

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

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

Применяются следующие правила изменения маркировок:

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

• срабатывание перехода может наступить через любой конечный промежуток времени после его возбуждения;

• если в некотором состоянии сети возбужденным оказывается сразу несколько переходов, то всегда выполняется только какой-то один (любой) из них;

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

• выполнение перехода неделимый акт, изменение разметки входных и выходных позиций перехода при его выполнении осуществляется мгновенно.

Всякому возможному варианту выполнения сети будет отвечать определенная последовательность срабатываний переходов и последовательность получающих после каждого очередного срабатывания маркировок вида: М₀ > М₁ > М₂ > .... М_k.

Рисунок 4.4.5 — Реализация механизма маркировки в сетях Петри.

Сети Петри формализуют понятие абстрактной асинхронной системы динамической структуры из событий и условий. В сетях Петри не моделируется ход времени, события упорядочиваются по отношению "Выполняется после".