ТЕМА 6. Сети Петри

ТЕМА 6. Лекция 7. Сети Петри

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

2. Конечные разметки сети

3. Ограниченности сети Петри

4. Моделирование с помощью сетей Петри

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

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

Рекомендуемые материалы

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

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

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

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

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

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

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

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

Например, на рис.3 для перехода P1 входная позиция V1- выходная -V3.

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

Например, переход P1 на рис.3 при срабатывании изымает из позиции V1 одну фишку и увеличивает количество фишек в позиции V3 на одну.

Переход P2 изымает одну фишку из позиции V1 и помещает в позицию V2 две фишки.

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

Например, на рис.3. переход P3 не может сработать, ибо в позиции V3 находится только одна фишка, а дуг, связывающих V3 и P3 - две.

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

В самом деле, на рис.3 изображена сеть, в которой переход P3 не может сработать. Но если сработает переход P1, то количество фишек в позиции V3 - увеличится. Теперь P3 - сработает.

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

Завершение процесса функционирования приводит сеть к разметке, называемой конечной.

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

2. Конечные разметки сети

Одна из основных проблем в теории сетей Петри - задача о конечности функционирования сети (о достижении тупиковой разметки, “смертельные объятия” и т.д.).

Суть проблемы состоит в ответе на вопрос для данной конкретной сети - существует ли такая последовательность срабатывания переходов, которая приводит сеть к тупиковой разметке (т.е. разметке, при которой ни один переход не может сработать)?

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

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

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

Например, утверждение: “ сеть на рис.3 всегда останавливается, когда все фишки собраны в позиции V2” - справедливо.

А похожее утверждение: “ сеть на рис.3 всегда останавливается, причем все фишки собраны в позиции V2” - не верно.

Свойство достижения конечной разметки присуще далеко не всем сетям. Например, на рис.4 приведен пример сети всегда приходящей к тупиковой разметке, на рис.5 - сеть никогда не “попадает в тупик”, на рис. 6 - сеть, которая может остановиться, а может и нет.

3. Ограниченность сети Петри

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

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

Если ни в одной позиции сети при любой последовательности срабатываний переходов количество фишек не превышает некоторого K, то такую сеть называют K-ограниченной.

Например, сеть на рис.7 является ограниченной - при любом срабатывании сети количество фишек в любой позиции не превысит 1. Заметим, что само функционирование этой сети - бесконечно. Т.е. у данной сети отсутствует тупиковая разметка.

Так же не достигается тупиковая разметка сети на рис.8. Однако эта сеть не является ограниченной - количество фишек в любой позиции может увеличиваться бесконечно.

4. Моделирование с помощью сетей Петри

В первой статье этого цикла говорилось о двух основных подходах к моделированию объектов графами - “географическом” (граф соответствует структуре моделируемого объекта) и “состоятельном” (граф соответствует процессам, т.е. изменению состояний объекта).

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

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

Рис.9

Например, на рис. 9 изображена сеть, моделирующая известный эксперимент по выработке условного рефлекса слюноотделения у собаки как реакции на электрический звонок.

Рассмотрим данную сеть подробнее. Здесь позиции именуются буквами латинского алфавита: переходы - буквой P с номером. Позиция A соответствует множеству порций пищи, используемой в эксперименте, причем каждая порция изображается одной фишкой, размещаемой в данной позиции. Позиция B соответствует экспериментатору, а фишка в этой позиции изображает его готовность приступить к эксперименту. Позиция C представляет электрический звонок, а фишка в этой позиции - способность звонка звонить.

Сразу же видно различие в стартовой разметке

,

Существуют системы, необходимые для поддержки набора взаимосвязанных процедур, составляющих сложные производственные процессы (бизнес-процессы). Их задача состоит в контроле за логикой потока работ целой организации, взаимодействием интегрируемых приложений [1], [2]. Для достижения эффективности реализации бизнес-процессов  были разработаны методы и инструментальные средства описания, проектирования, анализа и оценки бизнес-процессов, концепции и правила их реорганизации, а также информационные технологии поддержки. В качестве языка моделирования предлагается язык сетей Петри (разработки МГУ).

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

Рассмотрим моделирование сети Петри на примере процесса обработки жалобы.

В первую очередь, жалоба регистрируется (задача зарегистрировать). Затем параллельно необходимо послать анкету  на заполнение “ябеде” (задача послать_ анкету) и оценить заявление (оценить). Если в течение двух недель от “ябеды” приходит ответ, то он должен быть обработан (обработать_анкету). В противном случае, результат процесс должен быть завершен (время_истекло). В зависимости от результатов оценки жалоба либо обрабатывается, либо нет. Фактическая обработка жалобы (задача обработать_жалобу) откладывается до тех пор, когда будет проведен опрос (или  истечет время). Обработка жалобы проверяется задачей проверить. И завершается процесс (в любом случае, но с разными результатами) выполнением задачи архив.

Задачи зарегистрировать, послать_анкету, оценить, обработать_анкету, обработать_жалобу,  время_истекло,  проверить, архив изображены на рисунке переходами. Переходы OK и NOK добавлены для моделирования двух возможных исходов выполнения задачи  проверить. По тем же причинам добавляются переходы обработать требования и отказать. Для моделирования состояний между выполнением задач служат условия, представленные позициями.  Например, позиция c2 соответствует условию “готов оценивать жалобу”, а условие c5- верно (т.е. позиция c5 содержит фишку), когда обработана анкета или истекло время. Условия i и o соответственно начальное и конечное условия.

Сеть Петри, которая моделирует бизнес-процесс, называется сеть WorkFlow (WF-net). WF-net удовлетворяет двум условиям.

Во-первых, WF-net имеет одно начальное (i) и одно конечное место (o). Фишка в позиции i соответствует тому, что процесс необходимо выполнить. Фишка в позиции o значит, что процесс уже был выполнен.

Во-вторых, в сети не должно быть тупиковых задач или условий. Каждая задача (переход) и условие (позиция) должны участвовать в процессе. Т.е. любой переход t (позиция p) должен быть на пути от i к o. Если соединить o и i дополнительным переходом t’, то второе требование соответствует связанности сети.

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

Ещё посмотрите лекцию "23. Импульсная коррекция дискретных автоматических систем" по этой теме.

ЛИТЕРАТУРА

1. М. Балк. Первое знакомство с сетями Петри. © 1998 г. 

Котов В. Е. Сети Петри. - М.: Наука, 1984.

2. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984.

3. Майника Э. Алгоритмы оптимизации на сетях и графах /Под ред. Е.К.Масловского - М.: Мир,1981. - 322 c.