TVPS_posobie_13_06_2013

Пример 18. Рассмотрим СП (Рис. 20). Маркировка данной сети Петри определяется как (p1)=1, (p2)=2, (p3)=0, (p4)=0,

(p5)=1.

Рис. 20. Маркированная сеть Петри
Удобно представлять маркировку как вектор =( 1,	2, …, n)
где n=|P|, i – целое неотрицательное число, равное	количеству

фишек (точек), принадлежащих позиции pi (t=1, 2, ..., n). Тогда для нашего примера маркировка имеет вид: (1, 2, 0, 0, 1).

Определение. Маркированной сетью Петри М=(Р, Т, I, О, )

называется сеть Петри С=(P, T, I, O) с маркировкой .

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

Пример сети Петри с очень большой маркировкой (Рис. 21). Число точек заменено числами.

Рис. 21. Сеть Петри с очень большой маркировкой

41

Иногда полезно несколько иное описание сети Петри (P, T, I, O).

Определение. Расширенная входная функция указанной сети – это отображение позиций в комплекты переходов на входе I : Р T ,

а расширенная выходная функция – это отображение позиций в комплекты переходов на выходе О : Р T , такие, что:

#(tj, I (pi))=#(pi, O(tj)), #(tj, O (pi))=#(pi, I(tj)).

2.4.Двойственная сеть Петри. Инверсная сеть Петри

Определение. Двойственной к сети Петри С=(P, T, I, O)

является сеть Петри С*=(T, P, I, O), которая получается из сети С в результате перестановки местами позиций и переходов.

При переходе к двойственной СП структура графа сохраняется, просто меняются местами позиции и переходы

Пример 19. На Рис. 22,а изображена СП, а на Рис. 22,б – двойственная ей сеть.

а

б

Рис. 22. а – сеть Петри С; б – двойственная ей сеть Петри С*

Определение. Инверсной к сети Петри С=(P, T, I, O) является

сеть Петри C , которая получается из С путем изменения ориентации каждой дуги на противоположную:

C =(P, T, O, I).

42

Пример 20. На Рис. 23 изображена сеть Петри, инверсная к сети Петри из примера 19.

Рис. 23. Сеть Петри C , инверсная к сети Петри С из примера 19

2.5.Граф сети Петри

Рассмотрим граф СП. Очевидно, что он является ориентированным и двудольным (вершины графа делятся на два непересекающихся множества позиции и переходы так, что каждая дуга направлена от элемента одного множества к элементу другого множества). Кроме того, он является мультиграфом, так как может иметь кратные дуги.

Граф сети Петри есть двудольный ориентированный мультиграф

G=(V, A),

где V={v1, v2, ... , vr} – множество вершин,

А={a1, a2, ..., as} – комплект дуг, ai=(vj, vk), vj, vk V, т.е. множество V является объединением двух непересекающихся подмножеств Р и T:

V=P T, P T= ,

причем если ai=(vj, vk), ai А, то либо vj Р и vk Т, либо vj Т и vk Р.

43

Пример 21. Рассмотрим сеть Петри, имеющую структуру

С=(P, T, I, O), где P={p1, p2, p3, p4, p5}, T={t1, t2, t3, t4},

I(t1)={p1}; O(t1)={p2, p3, p5}; I(t2)={p2, p3, p5}; O(t2)={p5}; I(t3)={p3}; O(t3)={p4}; I(t4)={p4}; O(t4)={p2, p3}.

Соответствующий граф изображен на Рис. 24.

Рис. 24. Граф СП

Его расширенными входной и выходной функциями являются:

I (p1)= ,		O (p1)={t1},
I (p2)={t1, t4},		O (p2)={t2},
I (p3)={t1, t4},		O (p3)={t2, t3},
I	(p4)={t3},	O	(p4)={t4},
I	(p5)={t1, t2},	O	(p5)={t2}.

44

2.6.Функционирование маркированной сети Петри

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

Переход может запускаться только в том случае, когда он

разрешен.
Определение. Переход tj Т	в	маркированной сети Петри
С=(P, T, I, O, ) разрешен, если для	рi	Р (pi) pi, I(tj) .

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

разрешен.

Например, если позиции p1 и p2 служат входами для перехода t4, тогда t4 разрешен, если p1 и p2 имеют хотя бы по одной фишке. Для перехода t7 с входным комплектом {р6, р6, р6} позиция р6 должна обладать по крайней мере тремя фишками, для того чтобы t7 был разрешен.

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

Запуск перехода в целом заменяет маркировку сети Петри на новую маркировку ' (Рис. 25).

Обозначим pi) маркировку позиции pi до запуска перехода tj, обозначим ' pi) маркировку позиции pi после запуска перехода tj.

45

Рис. 25. Схема изменения маркировки позиции после запуска перехода

Переход tj в маркированной сети Петри (C, ) может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода tj образуется новая маркировка ', причем для

pi P:

' pi)= pi) – pi, I(tj) + pi, O(tj) .

(1)

Правила функционирования сети Петри:

1. Если переход tj разрешен, то он может быть запущен, в результате его запуска маркировка сети меняется с на ' в соответствии с формулой (1).

2.Если два или более переходов, не имеющих общих входных позиций, разрешены, то они могут быть запущены в любой последовательности или параллельно.

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

4.Запуск переходов продолжается до тех пор, пока в сети Петри не останется разрешенных переходов. Тогда сеть останавливается. Не исключено, что сеть Петри не останавливается.

46

Пример 22. Рассмотрим маркированную сеть Петри, изображенную на Рис. 26.

Рис. 26. Маркированная сеть Петри для иллюстрации правил запуска

При такой маркировке разрешены только три перехода: t1, t3 и t4. Переход t2 не разрешен, так как ни позиция р2, ни позиция р3, являющиеся входами перехода t2, не содержат ни одной фишки. Так как переходы t1, t3 и t4 разрешены, любой из них может быть запущен. Если запущен переход t4, то происходит удаление фишки из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из р5, одна фишка помещается в р3, а количество фишек в р4 увеличивается с двух до трех. Новая маркировка, полученная в результате запуска перехода t4, показана на Рис. 27.

Рис. 27. Маркировка, полученная в результате запуска перехода t4

47

В маркированной сети Петри, изображенной на Рис. 27, разрешены только переходы t1 и t3. При запуске перехода t1 осуществляется удаление фишки из р1 и помещение фишек в р2, р3 и р4 (в р4 – две фишки, так как эта позиция является кратным выходом перехода t1). Эта операция образует маркировку, приведенную на Рис. 28.

Рис. 28. Маркировка, полученная при запуске перехода t1

В такой маркированной сети Петри разрешены переходы t2 и t3. Запуск перехода t3 образует новую маркировку (Рис. 29).

Рис. 29. Маркировка, полученная при запуске перехода t3

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

48

2.7. Пространство состояний маркированной сети Петри. Функция следующего состояния

Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей n

позициями, есть множество всех маркировок, т. е. N 0n .

Изменение в состоянии , вызванное запуском перехода tj,

определяется функцией изменения		(	, tj): N0n Т		N0n,	которую мы
назовем функцией следующего состояния.
	не определена, если tj			не разрешен в		;
( , tj)=
	', если tj разрешен в .
Таким образом, функция (		,	tj)	определена,		если pi Р
(pi) pi, I(tj) .
Если функция	( , tj) определена, то			( , tj)=	', где
'(pi)=	(pi)-#(pi, I(tj))+#(pi, O(tj)) для				pi Р.

Пусть дана сеть Петри С=(P, T, I, O) с начальной маркировкой 0. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tj0 в начальной маркировке образует новую маркировку 1= ( 0, tj0). В этой новой маркировке можно запустить любой другой разрешенный переход, и этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть

закончено.

При	выполнении	сети	Петри	получаются		две
последовательности: последовательность маркировок (					0,	1, 2, ...)
и последовательность		переходов,	которые	были	запущены

=(tjo, tj1, tj2, ...). Эти две последовательности связаны следующим соотношением: ( k, tjk)= k+1 для k=0, 1, 2, ...

49

Имея начальную маркировку 0 и последовательность переходов , легко получить последовательность маркировок сети Петри.

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

Рис. 30. Пример сети Петри, в которой возникает неоднозначность при восстановлении последовательности запуска переходов

Неоднозначность восстановления последовательности запуска переходов по последовательности маркировок может получиться, в частности, если два различных перехода имеют одинаковые комплекты входных и выходных позиций (Рис. 30).

Например, если мы имеем последовательность маркировок ((1, 0, 0), (0, 2, 1)), то по ней мы не можем определить какой из переходов tj или tk был запущен, чтобы из маркировки (1, 0, 0) получить маркировку (0, 2, 1).

Таким образом, обе эти последовательности –

последовательность маркировок и последовательность запуска переходов – представляют описание выполнения сети Петри.

Определение.				Пусть	имеется маркированная сеть		Петри
С=(P, T, I, O,		0)	и последовательность переходов =(tjo, tj1,				tj2, ...).
( k, tjk)=	k+1	для k=0,1,2,... Расширенная функция следующего
состояния	это		(	0, )= (	0, tjo, tj1, tj2, ...). Она определена только в
том случае, когда каждый из переходов в						разрешен к моменту
запуска.
					50