Сетевые модели (v-схемы)

В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов. Самым распространенным в настоящее время формализмом, описывающим структуру и взаимодействие параллельных систем и процессов, являются сети Петри (англ. Petri Nets), предложенные К. Петри [28, 30].

Основные соотношения.

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

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

где В — конечное множество символов, называемых позициями, В⁰; В — конечное множество символов, называемых переходами, ВФ0, В (1)Ф0 I — входная функция (прямая функция инцидентности), 1:ВхВ-+{0, 1}; О — выходная функция (обратная функция инцидентности), О: В х 2?-*{0, 1}. Таким образом, входная функция I отображает переход 4 в множество входных позиций 6, е/(4), а выходная функция О отображает переход 4 в множество выходных позиций 6, е/)(4). Для каждого перехода 4 ^е 7) можно определить множество входных позиций перехода 7(4) и выходных позиций перехода О (4) как.

Аналогично, для каждого перехода Ь₍еВ вводятся определения множества входных переходов позиции 1(Ь) и множества выходных переходов позиции 0(Ь)

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

Рис. 2.8. Графическое изображение N-cxeмы

Пример 2.7. Представим формально Н-схему, показанную в виде графа на рис. 2.7:

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

Маркированная (размеченная) N-схема может быть описана в виде пятерки #_м = <2?, Д, /, О, Л/) и является совокупностью сети Петри и маркировки М [28, 30].

Функционирование №схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как Л/₀: #-*{0, 1, 2, …}. Смена разметок происходит в результате срабатывания.

Рис. 2.9. Пример функционирования размеченной Н-схемы

одного из переходов⁶ О сети. Необходимым условием срабатывания перехода <1_Л является 6, е/Ц) {Л/(6 1}, где М{Ь) — разметка позиции Ь_{. Переход (1_Р для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.

Срабатывание перехода изменяет разметку сети А/(6) = =(А/(Л₁), Л/(6₂), А/(6″))² на разметку М' (Ь) по следующему правилу:

т. е. переход ^ изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций. Для изображения смены разметки М на ЛГ применяют обозначение м1м

Пример 2Л. Рассмотрим размеченную М-схему с начальной разметкой А/₀ = {1, О, 0, 0, 1, 0, 1}, которая приведена на рис. 2.9, а. При такой начальной разметке N-схемы единственным готовым к срабатыванию является переход </<sub>2, срабатывание которого ведет к смене разметки М₀ И М_и где М_х ~{0, 1, 1, 0, 1,0, 1} (рис. 2.9, б). При разметке М_х возможно срабатывание переходов </, и </<sub>5. В зависимости от того, какой переход сработал первым, получается одна из трех возможных новых маркировок (рис. 2.9, в, ъ, д). Функционирование X-схемы продолжается до тех пор, пока существует хотя бы один возможный переход.

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

Пример 2.9. Для некоторой заданной размеченной М-схемы (рис. 2.8) с начальной маркировкой А/₀" {1, 2, 0, 0, 1} (рас. 2.10, а) разрешенным является только переход, а остальные переходы <1₂, и — запрещенные. В результате выполнения этого перехода получим новую размеченную N-схему (рис.

2.10, б). Теперь разрешены переходы с1₂ и <1_Ъ в результате их запуска получим новую размеченную схему. Переходы с1₂ и </<sub>3 находятся в конфликте, так как запущен может быть только один из них. Например, при запуске <1_Ъ получим сеть, показанную на рис. 2.10, в. Теперь разрешен только переход с1_А и получим новую размеченную сеть (рис. 2.10, г). Теперь разрешено два перехода: а_а и (в конфликте). Запустим переход^ (рис. 2.10, д). Теперь ни один переход не может быть запущен и выполнение сети прекращается.

Важной особенностью моделей процесса функционирования систем с использованием типовых Л^-схем является простота построения иерархических конструкций модели. С одной стороны, каждая №схема может рассматриваться как макропереход или макропозиция модели более высокого уровня. С другой стороны, переход, или позиция #- схемы, может детализироваться в форме отдельной подсети для более углубленного исследования процессов в моделируемой системе 5. Отсюда вытекает возможность эффективного использования N-cxeм

Рис 2.10. Пример функционирования размеченной заданной Н-схемы

для моделирования параллельных и конкурирующих процессов в различных системах.

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