Моделирование процессов

Основные понятия

• Часть 1
• | 2
• | 3

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

Популярность сетей Петри вызвана  удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделированию. Прекрасное изложение теории сетей Петри можно найти на русском языке в [1] и [2]. Формальное определение сетей Петри будет приведено ниже. Здесь же дать простое представление об этом математическом инструменте.

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

Либо начало дуги совпадает с позицией и тогда конец этой дуги совпадает с переходом, либо наоборот.

На рис.1 приведены примеры, соответствующие этому ограничению, на рис.2 - недопустимые примеры.

Оригинальным понятием теории сетей Петри является понятие “фишка”. Фишки изображаются точками, расположенными внутри позиций. Таким образом, каждой позиции сети ставится в соответствие натуральное число, указывающее количество фишек в данной позиция. Это число называют разметкой позиции, а совокупность таких чисел для всех позиций сети называют разметкой сети. Замечу, что позиция может и не содержать фишек, т.е. иметь нулевую разметку.

Пример сети с разметкой приведен на рис.3.

Другое оригинальное понятие сети Петри - “срабатывание” переходов.

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