Теория сетей Петри и моделирование систем. Алгебраическое описание сетей Петри

РТУ МИРЭА Дизайн Дизайн И. И. Гайдель Гайдель 2007 2007 Теория сетей Петри и моделирование систем Лекция 4 Дизайн И. Гайдель 2007 Способы описания сетей Петри = (0,0). Существует несколько подходов к описанию СП: - матричное описание; - алгебраическое описание; - описание на основе базовых фрагментов; - графическое описание. Дизайн И. Гайдель 2007 Способы описания сетей Петри = (0,0). Алгебраическое описание сетей Петри Алфавит языка: буквы: N,T,Q; специальные знаки: ";",":",",","$","+","*","-",">",".","#', "(", ")", "g", "h", "^"; цифры: 0,1,2,3,4,5,6,7,8,9; пробел Дизайн И. Гайдель 2007 Способы описания сетей Петри = (0,0). Грамматика язы ка Алгебраическое описание сетей Петри < иерархическая сеть >:: = < идентификатор сети > : < описание сети># < описание сети > :: = < выражение > < список ИПР > | < выражение > | < список ИПР > < список ИПР > :: = < список ИПР > | < ИПР > < ИПР > :: = < идентификатор ИПР> : < описание сети > < выражение > :: = < терм > < операция > < выражение > | < операция > < выражение > | < терм > < терм > :: = ( < выражение > ) | < идентификатор сети > | < идентификатор ИПР > | < идентификатор перехода > < операция > :: = <число > > | , | ; | $ | + | * | - | ^ | <число>q | <число>h < идентификатор сети > :: = N < число > < идентификатор ИПР> :: = Q < число > < идентификатор перехода > :: = T < указатель перехода > < указатель перехода > :: = < число > | N < число> . < число > | Q < число > . < число > < число > :: = < цифра > < число > | < цифра > < цифра > :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Дизайн И. Гайдель 2007 Способы описания сетей Петри = (0,0). Описание сетей Петри на основе базовы х фрагментов Определение 3. Базовой вершиной-переходом vt СП N , где t  T, назовем фрагмент СП, включающий переход t и все позиции, для которых I(p,t) >=1 и O(p,t)>=1 . Определение 4. Базовой вершиной-позицией vp СП N , где p  P, назовем фрагмент СП, включающий позицию p и все переходы, для которых I(p,t) >=1 и O(p,t) >=1 . Вершину-переход (vt) и вершину-позицию (vp) в дальнейшем будем называть базовыми фрагментами. Рассмотрим следующую теорему. Теорема. СП N = (P, T, I, O,  0) считается заданной, если заданы множества P, T и отображение Г, которое может быть определено: - либо множествами входных элементов для каждой вершины Г={pre(bi)}, где bi  P  T и i = 1,| P |  |T |; - либо множествами выходных элементов для каждой вершины Г={post(bi)}, где bi  P  T и i = 1,| P |  | T |. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Задачи анализа Одним из важнейших свойств СП, моделирующей реальное устройство, является безопасность. Известно, что если позиция безопасна, то число меток в ней равно 0 или 1. Безопасность - это частный случай более общего свойства ограниченности. Другим важным свойством СП является наличие или отсутствие тупиковых ситуаций. Тупики в реальных системах возникают при распределении ресурсов между взаимодействующими процессами и служат предметом многих исследований в области сложных систем. В СП-модели аналогом тупиковых ситуаций являются тупиковые разметки. Большинство задач, к которым мы до сих пор обращались, касается достижимости разметки. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Задачи анализа Задача достижимости формулируется следующим образом: для СП N с начальной разметкой 0 и разметкой ' определить   ' . Задача достижимости является основной задачей анализа СП. Многие другие задачи анализа можно сформулировать в терминах задачи достижимости. В настоящее время наиболее широко используются два метода анализа СП, которые позволяют решить некоторые из перечисленных задач: 1 - построение дерева достижимых разметок, 2 - метод основанный на решении матричных уравнений. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Анализ сетей Петри на основе дерева достижимости Множество достижимых разметок R(N) в СП N можно представить в виде дерева достижимости. Данное дерево представляет собой ориентированный граф, множество вершин которого образовано множеством R(N), причем из вершины  в вершину  ' ведет дуга, помеченная символом перехода t, если и только если  t   ' . В общем случае для любой СП с бесконечным множеством достижимых разметок соответствующее дерево также должно быть бесконечным. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. Для этого необходимо найти средства, которые ограничивают введение новых разметок, называемых граничными. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Анализ сетей Петри на основе дерева достижимости Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Алгоритм построения дерева достижимости Каждая вершина i дерева связывается с расширенной разметкой i . В расширенной разметке число меток в позиции может быть либо неотрицательным целым, либо  . Каждая вершина классифицируется или как граничная, терминальная, дублирующая вершина, или как внутренняя. Граничными являются вершины, которые еще не обработаны алгоритмом. После обработки граничные вершины становятся либо терминальными, либо дублирующими, либо внутренними. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Алгоритм построения дерева достижимости Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Матричны е методы анализа Показано, что если СП живая и ограниченная, то она должна быть последовательной и инвариантной. Данные свойства недостаточны для утверждения живости и ограниченности СП. Однако их полезно проверить исходя из матриц инцидентности, так как если одно из этих свойств не подтверждается, то можно заключить, что описываемая система содержит некоторые недоработки. Дизайн И. Гайдель 2007 Методы анализа сетей Петри = (0,0). Матричны е методы анализа Инвариантные и последовательные сети Петри . Введем в рассмотрение матрицу С, которая получается следующим образом: C=O-I . Пусть размерность С равна n  m , где m и n мощности множеств P и T . Рассмотрим матричные уравнения : C  x=0; (1) y  C=0, (2) где x и y - векторы, размерность которых равна n и m соответственно. Вектор у, удовлетворяющий решению уравнения (1) и все элементы которого положительны, называется р-цепью; р-цепь, все элементы которой больше нуля, называется полной р-цепью. Анaлогично на основе уравнения (2) определяются понятия t-цепи и полной t-цепи. СП, для которой существует полная р-цепь, называется инвариантной. СП, для которой существует полная t-цепь, называется последовательной . Дизайн И. Гайдель 2007 Методы анализа сетей Петри Матричны е методы анализа. Исследование сети Петри на живость и безопасность. Дизайн И. Гайдель 2007 Методы анализа сетей Петри Матричны е методы анализа. Исследование сети Петри на живость и безопасность. Дизайн И. Гайдель 2007 Спасибо за внимание!