TVPS_posobie_13_06_2013

Замечания по применению матричного подхода

1) Матрица D сама по себе не полностью отражает структуру сети Петри. Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц Dи D+, но затем взаимно уничтожаются в матрице D=D+-D .

Фрагмент сети Петри, содержащий петлю, представлен на Рис. 68. Заметим, что в данном случае понятие петли отличается от соответствующего понятия теории графов.

p1	t1

Рис. 68. Пример петли

2) При вычислении матрицы D, если сеть Петри содержит петли, теряется информация о кратности дуг. В этом случае по матрице D однозначно определить матрицу D невозможно, следовательно, невозможно определить условия, при которых переход ti разрешен.

Фундаментальное уравнение

Пусть в сети Петри С=(P, T, D-, D+) с начальной маркировкой 0 =tj1tj2...tjk – допустимая последовательность запусков.

Пусть ( 0, )= ', ' можно вычислить, используя (5):

'= 0+е[j1]D+е[j2]D+…+е[jk]D= = 0+(е[j1]+е[j2]+…+е[jk])D.

Обозначим е[j1]+е[j2]+…+е[jk]=f( ), f( ) – вектор запусков,

характеризующий вектор	последовательности		. Получим
фундаментальное уравнение сетей Петри:
	'= 0+ f(	)D.	(5)
f( )=е[j1]+е[j2]+…+е[jk] –	вектор	запусков последовательности

=tj1tj2...tjk, в котором i-й элемент f( )i – это число запусков перехода ti в последовательности tj1tj2...tjk, вектор f( ) является отображением Париха.

101

Пример 43. Пусть =t1t3t3t1t1t5, |T|=6, f( )=(302010).

Роль фундаментального уравнения состоит в том, что оно дает формальную возможность исследовать соотношение между последовательностью запусков и изменениями маркировок, которые

описываются структурой СП и в определенной мере не зависят от	0.
'= +f( )D
'- =f( )D
= '- =f( )D	(6)

Если в векторе все элементы неотрицательные, то в соответствии с правилами запуска переходов все переходы, разрешенные в , разрешены и в '.

Утверждение 1. Для любой конечной последовательности запусков , состоящей из переходов СП существует маркировка такая, что это допустимая последовательность в маркированной сети (C, ).

Утверждение 2. Принцип коммутативности. Если	1 и	2
это две конечные последовательности запусков, допустимые из		и
имеющие одинаковые характеристические векторы f( 1)=f(	2), то обе
они, начавшись в , приведут к одной и той же маркировке.

Утверждение 2 называют принципом коммутативности, так как оно имеет следующую трактовку – никакие допустимые перестановки переходов в последовательности запусков не влияют на маркировку, к которой эта последовательность приведет.

102

Решение задачи достижимости с помощью матричного подхода

Для данной сети Петри С=(P, T, D-, D+) требуется определить, достижима ли маркировка ' из маркировки .

Если маркировка ' достижима из , то существует последовательность (возможно пустая) запусков переходов , которая приводит из к '. Следовательно, f( ) является целым неотрицательным решением следующего матричного уравнения относительно х:

'= +xD,			(7)
где x=f( )=(x1, x2, …, xm), m=|T|.
	3	1	0
Пример 44. Пусть =(0, 0, 2), '=(0, 1, 0), D	0	1	2 .
	3	0	2
Требуется определить, достижима ли маркировка			' из
маркировки .

Для решения данной задачи воспользуемся уравнением (7):

			3		1	0
(0, 1, 0)=(0, 0, 2)+(x1, x2, x3)			0		1	2
			3		0	2
3x1	3x3	0,	x1		x3 ,
x1 x	2 1,
			x		1	x .
				2
2x2	2x3	2				1
Пусть x1=x3=1, тогда x2=0. Таким образом,						для получения ' из

требуется запустить по одному разу переходы t1 и t3, если это возможно.

Замечание. Существование целого неотрицательного решения уравнения (7) является необходимым, но не достаточным условием для достижимости '.

Если уравнение (7) имеет только нецелочисленные решения и

103

решения с отрицательными компонентами, то ' недостижима из .

При этом если уравнение (7) имеет решение, которому соответствует последовательность запусков , то эта последовательность может оказаться недопустимой.

Важно отметить, что по вектору f( ) не удается однозначно определить , т.е. последовательность запусков.

Определение. В сети С последовательность запусков

называется повторяющейся, если при		, при которой она
допустима, допустима также *=	…
Теорема о повторяющейся последовательности. В сети Петри
С=(P, T, D-, D+) последовательность запусков		повторяется тогда и

только тогда, когда f( )D≥0.

Доказательство. Докажем сначала необходимость. Пусть повторяется, маркировка, из которой она допустима.

Воспользуемся фундаментальным уравнением для получения маркировки в результате однократного запуска последовательности

:

'= +f( )D.

Согласно принципу монотонности '≥ . Тогда f( )D≥0. Достаточность вытекает из принципа монотонности.

Следствие. Если повторяющаяся последовательность запусков, то существует маркировка 0, при которой в сети (С, 0) допустима последовательность *.

Доказательство. Так как конечна, то по утверждению 1 существует 0, при которой она допустима в сети (С, 0). Тогда при 0 допустима также * по определению повторяющейся последовательности.

Замечание. В сети Петри (С, 0) допустима бесконечная последовательность запусков * тогда и только тогда, когда из 0 достижима маркировка , из которой допустима повторяющаяся последовательность *.

104

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

Пример 45. Рассмотрим сеть Петри, в которой имеются стационарно повторяющиеся последовательности запусков (Рис. 69).

p1
			t2		t4
				p3
			t1

p2

t3

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

Если начальная маркировка 0=(100), то стационарно повторяющимися последовательностями запусков будут:

1=(t1t3)*,

2=(t2t4)*, 3=(t1t3t2t4)*.

Решение задачи сохранения с помощью матричного подхода

Чтобы установить, что данная сеть Петри С с начальной маркировкой 0 является сохраняющей по отношению к вектору, необходимо найти положительный вектор взвешивания, для которого взвешенная сумма по всем достижимым маркировкам постоянна:

0W= 'W для ' R(C, 0),

(8)

где W=(w1, w2, ...,wn)T вектор-столбец.

Другими словами, взвешенная сумма фишек в сети остается постоянной.

105

Воспользуемся фундаментальным уравнением:

'= 0+f( )D.

(9)

Подставим (9) в (8):

0W=( 0+f( )D)W 0W= 0W+f( )DW f( )DW=0

Поскольку это условие выполняется для любого вектора , то

DW=0.

Данное условие является необходимым и достаточным для того, чтобы сеть была сохраняющей.

Таким образом, сеть Петри является сохраняющей тогда и

только тогда, когда существует такой положительный вектор W, что выполняется DW=0.

3 1 0

Пример 46. Дана сеть Петри. D= 0 1 2 . Определить,

3 0 2

является ли сеть сохраняющей по отношению к вектору. Решим систему уравнений DW=0.

3	1	0	w1		3w1	w2	0			1
									w			w ,
0	1	2	w2	=0,	w2	2w3	0	,	1	3		2
3	0	2	w3		3w1	2w3	0		w3	1		w2.
										2

Система имеет множество решений. Пусть w2=3, тогда w1=1, w3=3/2. Таким образом, сеть является сохраняющей по отношению к вектору взвешивания W=(1, 3, 3/2).

106

2.15.Классы сетей Петри

Расширенные и ограниченные модели сетей Петри

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

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

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

LB-эквивалентные преобразования сетей Петри

Сети Петри приходится преобразовывать по разным причинам. Возможные преобразования сетей будут описаны далее. Введем понятие LB-эквивалентного преобразования.

Определение. Преобразование сети (C, 0) в сеть (C', 0') называется LB-эквивалентным, если выполняются следующие условия:

1)сеть C' жива тогда и только тогда, когда жива сеть C;

2)сеть C' ограничена тогда и только тогда, когда ограничена сеть C.

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

107

Общие сети и общие сети без петель

В общих сетях не накладываются никакие ограничения на структуру сети Петри и кратность дуг. Сеть может быть представлена

двудольным	ориентированным	мультиграфом,	структурой
С=(P, T, I, O) или С=(P, T, D , D+).

Общая сеть без петель может быть представлена графом, структурой либо тройкой (P, T, D). Ограничение на отсутствие петель можно выразить следующим образом:

Если	#(pi, I(tj))>0,	то	#(pi, O(tj))=0;	если	#(pi,	O(tj))>0,	то
#(pi, I(tj))=0.
Если	D [j, i]>0,	то	D+[j, i]=0;	если	D+[j,	i]>0,	то
D [j, i]=0.

D [j, i] D+[j, i]=0.

Теорема. Для всякой сети Петри существует LB-эквивалентная ей сеть Петри без петель.

Рассмотрим алгоритм преобразования общей сети Петри (C, 0) в сеть Петри без петель (C', 0'):

1)переход tk, входящий в петлю, заменяется фрагментом, состоящим из двух переходов tk и tm+1 и новой позиции pn+1, после чего все переходы и позиции переобозначаются: tk', tm+1', pn+1' (Рис. 70).

tk		tk'
pl	pl'	pn+1'

tm+1'

Рис. 70. Исключение петли

2)матрицы D , D+ преобразуются в матрицы (D )', (D+)' следующим образом:

108

3)	0	'(p ')=	0	(p ), i	, n и	0	'(p	n+1	')=0.
		i		i

Из структуры преобразования видно, что исключение петли не влияет на свойства живости и ограниченности. Таким образом, теорема доказана.

Ординарные сети Петри. Преобразование Хэка

Определение. Ординарная	сеть Петри – это такая сеть
С=(P, T, I, O), что для рi Р, tj	Т: #(pi, I(tj)) , #(pi, О(tj)) .

Другими словами, в ординарных сетях запрещаются кратные дуги. Такие сети могут быть представлены обыкновенным двудольным ориентированным графом.

Если ординарная сеть	Петри	представлена	структурой
С=(P, T, I, O), то для описания входных и выходных				функций
используются не комплекты,	а множества (P, T,		I,	O) или
(P, T, D , D+), где элементы матриц D , D+		булевы.

Далее рассмотрен алгоритм преобразования произвольной сети Петри в ординарную. Оно носит название преобразование Хэка.

109

Преобразование Xэка

Для произвольной сети Петри М=(С, ) можно выполнить преобразование в ординарную сеть М'=(С', '), обладающую тем же набором свойств (живость, ограниченность, сохранение), что и сеть М, которое называют преобразованием Xэка.

Рассмотрим преобразование Хэка сначала на примере, а затем сформулируем определение.

Пример 47. Для сети Петри С=(P, T, I, O) (Рис. 71) выполнить преобразование Хэка.

Рис. 71. Исходная сеть Петри с кратными дугами

Для каждой позиции определяем максимальное число входящих/исходящих дуг. Пусть оно равно n(pi). Если n(pi)>1, то заменяем позицию pi на n(pi) позиций, а затем объединяем все эти позиции в кольцо с помощью новых переходов (Рис. 72). Входящие/исходящие дуги распределяем произвольно между n(pi) позиций, но таким образом, чтобы не было кратных дуг.

а

б

Рис. 72. Порядок проведения преобразования Хэка

110