Сетевые модели (n-схемы). Моделирование процессов функционирования систем на базе n-схем.

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

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

Формально сеть Петри (N-схема) задается четверкой вида

N=<B,D,I,O>

где В — конечное множество символов, называемых позициями, В≠ ;

D — конечное множество символов, называемых переходами, D ≠ , B∩D В≠ ;

I / — входная функция -(прямая функция инцидентности), I: ВхD→{0, 1}; О — выходная функция (обратная функция инцидентности),

О: DхВ→{0,1}.

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

Для представления динамических свойств объекта вводится функция маркировки (разметки) М:В→{0, 1, 2,...}. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы,. причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин-позиций соответствующего числа точек (когда количество точек велико, ставят цифры).

Маркированная (размеченная) N-схема может быть описана в виде пятерки N_M= <B, D, I, О, М> и является совокупностью сети Петри и маркировки М.

Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как М₀: B→{0, 1, 2,,..}. Смена разметок происходит в результате срабатывания одного из переходов d_jЄD сети. Необходимым условием срабатывания перехода d_j является b_i Є (d_j) {M(b_j)≥ 1}, где M{ b_j } — разметка позиции b_j - Переход d_j, для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию иди как возбужденный переход.

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

Типовые N-схемы на основе обычных размеченных сетей Петри пригодны для описания в моделируемой системе S событий произ­вольной длительности. В этом случае модель, построенная с ис­пользованием таких N-схем, отражает только порядок наступления событий в исследуемой системе S. Для отражения временных параметров процесса функционирования моделируемой системы S на базе N-схемы используется расширение аппарата сетей Петри: временные сети, Е-сети, сети Мерлина.

Важной особенностью моделей процесса функционирования систем с использованием типовых N-схем является простота построения иерархических конструкций модели.

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