Презентация на тему: Сети Петри Глава. 6. Фундаментальное уравнение сети Петри. Инварианты

Реклама. Продолжение ниже
Сети Петри Глава. 6. Фундаментальное уравнение сети Петри. Инварианты.
Оглавление :
Графовая форма математического представления сетей Петри.
Графовая форма математического представления сетей Петри.
Подстановочная форма математического представления сетей Петри
Подстановочная форма математического представления сетей Петри
Характеристический вектор последовательности
Матрица инциденций
Фундаментальное уравнение сети Петри
Фундаментальное уравнение сети Петри
Фундаментальное уравнение сети Петри
Фундаментальное уравнение сети Петри
Фундаментальное уравнение сети Петри
Инварианты сети Петри
Инварианты сети Петри
t- инварианты сети Петри
p- инварианты сети Петри
p- инварианты сети Петри
p- инварианты сети Петри
p- инварианты сети Петри
Алгоритм поиска p - инвариантов
Алгоритм поиска p - инвариантов
Алгоритм поиска p - инвариантов. Пример
Алгоритм поиска p - инвариантов. Пример
Литература
1/25
Средняя оценка: 4.7/5 (всего оценок: 97)
Код скопирован в буфер обмена
Скачать (525 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Сети Петри Глава. 6. Фундаментальное уравнение сети Петри. Инварианты

Aurelia Prepelita Conf., dr., USM Chisinau, 2010

Изображение слайда
1/1
2

Слайд 2: Оглавление :

Глава. 6. Фундаментальное уравнение сети Петри. Инварианты. Формы математического представления сетей Петри Графовая Матричная Подстановочная Допустимая последовательность срабатываний Фундаментальное уравнение сети Петри Характеристический вектор последовательности Матрица инциденций Инварианты сети Петри p - инварианты t – инварианты Алгоритм поиска p - инвариантов. Примеры

Изображение слайда
1/1
3

Слайд 3: Графовая форма математического представления сетей Петри

Определение : Сетью Петри называется набор из двух множеств ( 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/1
4

Слайд 4: Графовая форма математического представления сетей Петри

Рис. 1. Три представления сети Петри. а) графовое ; b) матричное ; с) подстановочное. а) б) с)

Изображение слайда
1/1
5

Слайд 5: Подстановочная форма математического представления сетей Петри

Подстановочное представление сети Петри – это множество выражений вида :  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)

Изображение слайда
1/1
6

Слайд 6: Подстановочная форма математического представления сетей Петри

Подстановка, соответствующая переходу 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

Изображение слайда
1/1
7

Слайд 7: Характеристический вектор последовательности

Из правил срабатывания переходов следует что достижимые маркировки могут вычисляться путем применения матрично- Векторных операций. Пусть, например, в сети PN=<P,T, B,F > маркировка М ’ получается из М в результате срабатывания последовательности переходов = t i1,..., t ik, т.е. М [  >M’. Рекурсивно для всех t ij получим : М ’=M - B  ’ + F  ’, (5) где  ’ = ( 1, …,  n ) - вектор-столбец длины n=|T| (T в Качестве вехнего индекса обозначает транспонирование ), в котором  i равно количеству вхождений t i в последователь- ность . Вектор  ’ называется характеристическим вектором последовательности .

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Матрица инциденций

Существует более компактная запись выражения (5) : M’=M+C  ’, (6) где С= F-B. (7) Выражение (6) можно применять для определения достижимой маркировки М ’, если известна допустимая последовательность срабатываний . Матрица С называется матрицей инциденций сети Петри, а уравнение (6)- фундаментальным уравнением.

Изображение слайда
1/1
9

Слайд 9: Фундаментальное уравнение сети Петри

Фундаментальное уравнение сети Петри играет большую роль в структурной теории сетей Петри. Однако при анализе функционирования сети Петри при заданной маркировке М0 применять матрицу С следует осторожно, поскольку в общем случае она не является представлением сети Петри – при вычислении с ij = f ij - b ij теряется информация о значениях кратности дуг ( p i, t j ) и ( t j,p i ), если обе эти дуги существуют. Иными словами, по матрице С определить матрицу В однозначно невозможно, и, следовательно, невозможно выразить условие возбуждения для перехода t j.

Изображение слайда
1/1
10

Слайд 10: Фундаментальное уравнение сети Петри

Например, одна и та же матрица инциденций соответствует сети на рис. 1 и на рис. 3. -1 -1 2 1 0 0 0 1 -1 С= Рис. 1 Рис. 3

Изображение слайда
Изображение для работы со слайдом
1/2
11

Слайд 11: Фундаментальное уравнение сети Петри

Роль фундаментального уравнения состоит в том, что оно дает формальную возможность исследовать соотношения между последовательностями срабатываний и изменениями маркировок, которые определяются структурными характеристиками сети и не зависят от начальных маркировок :  М  = M’ – M = C  ’. (8) Если  М – вектор с неотрицательными компонентами, то M’ ≥ M и согласно условию срабатывания переходов, все переходы, возбужденные при М, возбуждены также при M’.

Изображение слайда
1/1
12

Слайд 12: Фундаментальное уравнение сети Петри

Отсюда непосредственно вытекает следующее Утверждение. Все последовательности срабатываний, допустимые в сети <N, M 0 >, допустимы также в сети <N, M’ 0 >, если M’ 0 ≥ M. Это утверждение называется принципом монотонности. Поскольку показывает что увеличение вектора маркировки влечет за собой увеличение числа допустимых последовательностей срабатываний.

Изображение слайда
1/1
13

Слайд 13: Фундаментальное уравнение сети Петри

-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.

Изображение слайда
1/1
14

Слайд 14: Инварианты сети Петри

Определение. Повторяющаяся последовательность срабатываний  называется стационарно повторяющейся, если она приводит к той же маркировке, из которой началась, т.е. С  ’ =0. (9)

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: Инварианты сети Петри

Например, в сети на рис. 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 С=

Изображение слайда
1/1
16

Слайд 16: t- инварианты сети Петри

Определение. t -инвариантом сети Петри N= <P, T, C> называется целочисленный неотрицательный вектор-столбец g удовлетворяющий условию C g =0. (10) Очевидно, что каждый t -инвариант равен характеристическому вектору стационарно повторяющейся последовательности срабатываний. t -инварианты определяют стационарно повторяющиеся последовательности срабатываний (с точностью до характеристических векторов).

Изображение слайда
1/1
17

Слайд 17: p- инварианты сети Петри

Определение. Скалярное произведение положительного целочисленного вектора f=(f 1,..., f m ), m=|P|, на вектор маркировки fM= f i M(p i ), i=1,..., m (11) называется взвешенной суммой маркеров. Вектор f называется весовым, а каждая его компонента f i – весом маркеров в позиции p i.

Изображение слайда
1/1
18

Слайд 18: p- инварианты сети Петри

Приращение взвешенной суммы маркеров при функционировании сети получается умножением (8) на f  М  = f * М  = f * M’ – f *M = f * C  ’. Существенно то, что  М  не зависит от начальной маркировки, т.е. является структурной характеристикой сети.  

Изображение слайда
1/1
19

Слайд 19: p- инварианты сети Петри

Определение. p- инвариантом сети Петри N= <P, T, C> называется целочисленный неотрицательный вектор-столбец f=(f 1,..., f m ) удовлетворяющий условию f * C =0. (10) Очевидно, что каждый p -инвариант определяет весовый вектор для подмножества позиций, в котором взвешенная сумма маркеров при функционировании сети остается постоянной. Поиск таких подмножеств можно выполнить, решив уравнение (10). 

Изображение слайда
1/1
20

Слайд 20: p- инварианты сети Петри

Можно убедиться на примере рис. 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). 

Изображение слайда
1/1
21

Слайд 21: Алгоритм поиска p - инвариантов

Исходные данные : матрица С размерности 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,-)

Изображение слайда
1/1
22

Слайд 22: Алгоритм поиска p - инвариантов

Шаг 3 3.1. Исключаются из С и B строки с индексами i IJ. 3.2. Исключается из С первый столбец. Конец алгоритма. Множество строк матрицы B есть минимальное порождающее семейство инвариантов.

Изображение слайда
1/1
23

Слайд 23: Алгоритм поиска p - инвариантов. Пример

-1 1 1 3 -3 -1 1 -1 -1 1 -2 6 1 -6 Рис. 5. Сеть Петри и ее матрица инциденций

Изображение слайда
1/1
24

Слайд 24: Алгоритм поиска p - инвариантов. Пример

Исходную информацию для алгоритма представим в виде 2 матриц : -1 1 1 3 -3 -1 1 -1 -1 1 -2 6 1 -6 1 1 1 1 1

Изображение слайда
1/1
25

Последний слайд презентации: Сети Петри Глава. 6. Фундаментальное уравнение сети Петри. Инварианты: Литература

Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. - Новосибирск: Наука. Сибирское отделение, 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.

Изображение слайда
1/1