Aurelia Prepelita Conf., dr., USM Chisinau, 2010
Глава. 6. Фундаментальное уравнение сети Петри. Инварианты. Формы математического представления сетей Петри Графовая Матричная Подстановочная Допустимая последовательность срабатываний Фундаментальное уравнение сети Петри Характеристический вектор последовательности Матрица инциденций Инварианты сети Петри p - инварианты t – инварианты Алгоритм поиска p - инвариантов. Примеры
Определение : Сетью Петри называется набор из двух множеств ( P и T ) и двух функций ( B и F ): PN=<P,T, B,F > (1) Здесь : Р={ p 1, p 2,..., p m } – множество позиций, соответствующее множеству условий в системе; Т={ t 1, t 2,..., t n } – множество переходов соответствующее множеству событий; функции предшествования B и следования F ставят в соответствие каждой паре ( p i, t j ) и ( p k, t l ) целые неотрицательные числа b ij или f kl, соответственно.
Рис. 1. Три представления сети Петри. а) графовое ; b) матричное ; с) подстановочное. а) б) с)
Подстановочное представление сети Петри – это множество выражений вида : j : S’ j S’’ j, j=1,2,...,|T|. (2) Каждая подстановка j выражает входные и выходные условия перехода следующим образом : S’j = {(x i ≥b ij, p i ): p i t j) }; (3) S’’j = {(x i -b ij, p i ): p i t j) }{ (y i +f ij, p’ i ): p i t j ) }; (4)
Подстановка, соответствующая переходу t (рис. 2) имеет вид : : {(x 1 ≥3, p1),(x2≥2, p2)} {(x 1 - 3, p1),(x2-2, p2), (x3+1,p3), (x4+2, p4), (x5+1, p5)} Рис. 2
Из правил срабатывания переходов следует что достижимые маркировки могут вычисляться путем применения матрично- Векторных операций. Пусть, например, в сети PN=<P,T, B,F > маркировка М ’ получается из М в результате срабатывания последовательности переходов = t i1,..., t ik, т.е. М [ >M’. Рекурсивно для всех t ij получим : М ’=M - B ’ + F ’, (5) где ’ = ( 1, …, n ) - вектор-столбец длины n=|T| (T в Качестве вехнего индекса обозначает транспонирование ), в котором i равно количеству вхождений t i в последователь- ность . Вектор ’ называется характеристическим вектором последовательности .
Существует более компактная запись выражения (5) : M’=M+C ’, (6) где С= F-B. (7) Выражение (6) можно применять для определения достижимой маркировки М ’, если известна допустимая последовательность срабатываний . Матрица С называется матрицей инциденций сети Петри, а уравнение (6)- фундаментальным уравнением.
Фундаментальное уравнение сети Петри играет большую роль в структурной теории сетей Петри. Однако при анализе функционирования сети Петри при заданной маркировке М0 применять матрицу С следует осторожно, поскольку в общем случае она не является представлением сети Петри – при вычислении с ij = f ij - b ij теряется информация о значениях кратности дуг ( p i, t j ) и ( t j,p i ), если обе эти дуги существуют. Иными словами, по матрице С определить матрицу В однозначно невозможно, и, следовательно, невозможно выразить условие возбуждения для перехода t j.
Например, одна и та же матрица инциденций соответствует сети на рис. 1 и на рис. 3. -1 -1 2 1 0 0 0 1 -1 С= Рис. 1 Рис. 3
Роль фундаментального уравнения состоит в том, что оно дает формальную возможность исследовать соотношения между последовательностями срабатываний и изменениями маркировок, которые определяются структурными характеристиками сети и не зависят от начальных маркировок : М = M’ – M = C ’. (8) Если М – вектор с неотрицательными компонентами, то M’ ≥ M и согласно условию срабатывания переходов, все переходы, возбужденные при М, возбуждены также при M’.
Отсюда непосредственно вытекает следующее Утверждение. Все последовательности срабатываний, допустимые в сети <N, M 0 >, допустимы также в сети <N, M’ 0 >, если M’ 0 ≥ M. Это утверждение называется принципом монотонности. Поскольку показывает что увеличение вектора маркировки влечет за собой увеличение числа допустимых последовательностей срабатываний.
-1 -1 2 1 0 0 0 1 -1 Например, в сети на рис. 3 <N, M 0 >, М 0 =(2,0,0) допустимая последовательность = t1, t 2, t3, t2, t3, которая приведет к маркировке M’ =(2,0,0) + =(2,0,0) + (1,1,0)=(3,1,0) 1 2 2 Легко провенить, что при M’ допустимы все последовательности срабатывания, которые допустимы при М 0.
Определение. Повторяющаяся последовательность срабатываний называется стационарно повторяющейся, если она приводит к той же маркировке, из которой началась, т.е. С ’ =0. (9)
Например, в сети на рис. 4 Последовательность срабатываний =( t1, t 2, t2, t3, t3, t4) стационарно повторяющаяся. Рис. 4 2 -1 0 0 -2 1 0 0 0 0 -1 2 0 0 1 -2 0 -1 1 0 0 1 -1 0 С=
Определение. t -инвариантом сети Петри N= <P, T, C> называется целочисленный неотрицательный вектор-столбец g удовлетворяющий условию C g =0. (10) Очевидно, что каждый t -инвариант равен характеристическому вектору стационарно повторяющейся последовательности срабатываний. t -инварианты определяют стационарно повторяющиеся последовательности срабатываний (с точностью до характеристических векторов).
Определение. Скалярное произведение положительного целочисленного вектора f=(f 1,..., f m ), m=|P|, на вектор маркировки fM= f i M(p i ), i=1,..., m (11) называется взвешенной суммой маркеров. Вектор f называется весовым, а каждая его компонента f i – весом маркеров в позиции p i.
Приращение взвешенной суммы маркеров при функционировании сети получается умножением (8) на f М = f * М = f * M’ – f *M = f * C ’. Существенно то, что М не зависит от начальной маркировки, т.е. является структурной характеристикой сети.
Определение. p- инвариантом сети Петри N= <P, T, C> называется целочисленный неотрицательный вектор-столбец f=(f 1,..., f m ) удовлетворяющий условию f * C =0. (10) Очевидно, что каждый p -инвариант определяет весовый вектор для подмножества позиций, в котором взвешенная сумма маркеров при функционировании сети остается постоянной. Поиск таких подмножеств можно выполнить, решив уравнение (10).
Можно убедиться на примере рис. 4, что f1=(1,1,0,0,0,0), f2=(0,0,1,1,0,0) и f3=(0,0,0,0,1,1)- минимальное порождающее семейство p- инвариантов. Вектор f 4 =( 1,1,1,1, 1,1) тоже p- инвариант, но получается как линейная комбинация векторов f4=f1+f2+f3. Минимальное порождающее семейство t - инвариантов для этой сети содержит только один вектор g=(1,2,2,1).
Исходные данные : матрица С размерности mxn. Начальная установка : формируемая матрица B=E mxm. Основной цикл. Выполняется, пока матрица С имеет хотя бы один столбец. Шаг 1 : Формируются множества I и J такие, что I={i: ci1>0}, J={j: cj1>0}. Шаг 2 : Для каждой пары (i,j) IxJ выполняется следующее. 2.1. Приписывается к С строка, равная вектору c i1* C (j,-) - c j1* C (i,-) 2.2. Приписывается к В строка, равная вектору c i1* B (j,-) - c j1* B (i,-)
Шаг 3 3.1. Исключаются из С и B строки с индексами i IJ. 3.2. Исключается из С первый столбец. Конец алгоритма. Множество строк матрицы B есть минимальное порождающее семейство инвариантов.
-1 1 1 3 -3 -1 1 -1 -1 1 -2 6 1 -6 Рис. 5. Сеть Петри и ее матрица инциденций
Исходную информацию для алгоритма представим в виде 2 матриц : -1 1 1 3 -3 -1 1 -1 -1 1 -2 6 1 -6 1 1 1 1 1
Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. - Новосибирск: Наука. Сибирское отделение, 1990. Gu ţuleac E. Modelarea şi evaluarea performanţelor sistemelor de calcul prin Reţele Petri: Departamentul Editorial-Poligrafic al U.T.M. Chişinău, 1998.
Slide-Share