Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 19
Текст из файла (страница 19)
Альтернативнызг по отношению к определению сети Петри в виде (Р, Т, /, 0) является определение двух матриц Р и Р+, представляющих входную и выходную функции. (Они эквивалентны функциям г' и В определения Хэка сетей Петри, см. равд. 2.6.) Каждая матрица имеет т строк (по одной на переход) и п столбцов (по одному на позицию). Определим Р [г, г[ = = Щрп Ц1т)), а Р+ [г, г[ = $ф(рг, 0 (11)). Р определяет входы в переходы, Р' — выходы. Матричная форма определения сети Петри (Р, Т, Р, Р+) эквивалентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть еЦ— т-вектор, содержащий нули везде, за исключением гчй компоненты. Переход 11 представляется т-вектором е[Дэг.
Теперь переход 11 в маркировке р разрешен, если р ~ еИ ° Р, а результат запуска перехода 11 в маркировке [г записывается как В(р, уг) р — е [г) Р +еЦ. Р'= = [г+ е [1[ ° ( — Р + Р') = р+ е Щ Р, где Р = Р+ — Р— составная матрица изменений. П Па отношению к аяясзяяаму в этам раздаче алгоритму. — ПРим. перев. з> э[1[ — веятар-сгракз. — "Прим. перев. Анализ сетей Петри ют Тогда для последовательности запусков переходов а = 1л11, ...
имеем В (р, о) = В (р, 11„1,,, ..., 1;,) = = р + е[1,[ . Р+ е [1е[ . Р+ - . + е [1н) . Р = = р, + (е [1г[+ е [[е[+ ° + е [1д[) 0 = [г+ [(о) Р. Вектор 1(о) = е[Я+ еЯ+ ... + е[1х] называется вектором запусков последовательности 1ь1;,...11,. г-й элемент вектора 1(о), 1(о) г — это число зйлуской перехода 1г в последовательности 1Ь11,... ... 1е„.
Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами. (Вектор 1(о) — это отображение Парпха последовательности [2291.) Для того чтобы показать полезность такого матричного подхода к сетям Петри, рассмотрим, например, задачу сохранения: является ли данная маркированная сеть Петри сохраняющей? Для того чтобы показать сохранение, необходимо найти (ненулевой) вектор взвешивания, для которого взвешенная сумма по всем достижимым маркировкам постоянна. Пусть га — и х 1 — вектор-столбец. Тгн да, если р — начальная маркировка, а р' — произвольная достижимая маркировка, необходимо, чтобы р ш = р.' ° га. Теперь, поскольку р' достижима, существует последовательность запусков переходов о, которая переводит сеть из р в р'. Поэтому р' = е (р, о) = р + Да) ° Р.
Следовательно, гг ° и = р' . ш = (р + 1(о) ° Р) ° га = р. га + + 1'(о) - Р ° гв, поэтому 1(о) ° Р ° га =- О. Поскольку это должно быть верно для всех 1(о), имеем Р. га =О. Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный вектор и,, что Р ° пг = О. Это обеспечивает простой алгоритм проверки сохранения, а также позволяет получать вектор взвешивания га. Развитая матричная теория сетей Петри является инструментом для решения проблемы достижимостн.
Предположим, что марию- ровна р' достижима из маркировки р. Тогда существует последовательность (возможно, пустая) запусков переходов о, которая приводит из р к р'. Это означает, что 1(о) является неотрицательным целым решением следующего матричного уравнения для х: р' = р+ х . Р. (4-[) Следовательно, если рт достижима из р„тогда уравнение (4-1) имеет решение в неотрицательных целых; если уравнение (4-Ц не имеет решения, тогда р' недостижима из р.
Глава 4 108 Рассмотрим, например, маркированную сеть Петри на рис. 4.26. Матрицы О н О+ имеют вид: 0 О ! 0 1 0 0 0 О 2 1 0 О 0 0 1 а матрица О: Π— 1 — 1 0 0 +2 +1 — 1 О 0 — 1 +1 В начальной маркировке р = (1, О, 1, 0) переход ! разрешен и приводит к маркировке 1г', где 0 — 1 — 1 0 О +2 +1 — 1 0 0 — 1 +1 р' = (1, О, 1, О) + (О, О, 1) . = (1, О, 1, О) + (1, 2, 2) .
Π— 1 — 1 О 0+2 +1 — 1 0 0 — 1 +1 = (1„0, 1, О)+ (О, З, — 1, О) = (1, З, О, О). Рг Рг Рис. 4.х6. Сеть Петри, иллюстрирующая метод анализа, основанный на мат- ричных уравнениях. = (1, О, 1, 0) + (О, О, — 1, + 1) = (1, О, О, 1). Последовательность о = 1 !х(а!хтг представляется вектором запусков 1(о) = (1, 2, 2) и получает маркировку р'.
Анализ сетей Петри 109 Для определетшя того, является ли маркировка (1, 8, О, 1) достижимой из маркировки (!, О, 1, О), имеем уравнение 0 — 1 — 1 0 0+2+1 — 1 0 0 — 1 +! (1, 8, О, 1) =(1, О, 1, 0)+х. 0 — 1 — 1 0 0 +2 +1 — 1 О 0 — 1 +1 (О, 8, — 1, 1)=х. которое имеет решение х = (О, 4, 5). Это соответствует последовательности о = ! !з(з!з!з!з!з!зтз. Далее мы можем показать, что маркировка (1, 7, О, 1) недостижима нз маркировки (1, 0„1, 0), поскольку матричное уравнение 0 — 1 — 1 0 (1, 7, О, 1)=(1, О, 1, О) + х - О + 2 -! 1 — 1 0 0 — ! +1 0 — 1 — 1 0 0 +2 +1 — 1 0 Π— 1 +1 (О, 7, — 1, 1) =- х . не имеет решения.
Матричный подход к анализу сетей Петри очень перспективен, но имеет и некоторые трудности. Заметим прежде всего, что матрица О сама по себе не полностью отражает структуру сети Петри. Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц В и 11, но затем нзанмно уничтожаются в матрице В =- Р е — О . Это отражено в предыдущем примере позицией р, и переходом !о Другая проблема — это отсутствие информации о последовательности в векторе запуска. Рассмотрим сеть Петри на рис. 4.27. Предположим, мы хатим определить, является ли маркировка (О, О, О, О, 1) достижимой из (1, О, О, О, 0). Тогда имеем уравнение Это уравнение не имеет однозначного решения, но сводится к множеству решений (оЩо) = (1, х„хе — 1, 2хз, х,— 1, хе)). Оно (О, О, О, О, 1)=(1, 0 О, О, 0) + х .
— 1 0 0 0 0 0 2 1 0 0 0 0 0 О 0 1 0 0 — 1 0 ! 0 2 0 0 — 1 0 — 1 — 2 1 Глава 4 Рис. 4.27. Другая сеть Петри, служащая длн иллюстрации матричного анализа. определяет взаимосвязь между запусками переходов. Если положим ха = 1 и х, = 1, то 1(о) = (1, 1, 0,2, О, 1), но этому вектору запуска соответствуют как последовательность 1,~1 141а, так и последовательность 1ггага141а.
Следовательно, хотя и известно число запусков переходов, порядок их запуска неизвестен. Еще одна трудность заключается в том, что решение уравнения (4-1) является необходимым для достижимости, но недостаточным. Рассмотрим простую сеть Петри, приведенную на рис. 4.28. Если мы хотим определить, является ли (О, О, О, 1) достижимым из (1, О, О, 0), необходимо решить уравнение™ Г вЂ” 1 +1 — 1 О! (О, О, О, 1) = (1, О, О, 0) + ) (о) - ~ Ра Рис. 4.28. Сеть Петри, показывающая, что решение матричного уравнення— необходимое. но недостаточное условие для решения задачи достижимосги. Анализ сетей Пензе Зто уравнение имеет решение Яо) = (1, 1), соответствующее двум последовательностям: Глг, и 1,1г Но ни одна из этих двух последовательностей переходов невозможна, поскольку в (1, О, О, 0) ни 1н ни 1, не разрешены.
Таким образом, решения уравнения (4-1) недостаточно для доказательства достнжимости. Возможность недействительных решений уравнения (4-1) (решений, которые не соответствуют возможным последовательностям переходов) стала причиной только ограниченного исследования матричного представления сетей Петри.
Лучшее исследование этого подхода проведено Муратой [206, 208, 209]. 4.3. Замечания н литературе В публикациях Хольта н др. [128] и Хольта и Коммонера [127] определены некоторые из первых задач анализа сетей Петри— активность и безопасность, которые продолжают считаться основными задачами анализа. Актнвнсхть изучалась Коммонером [53], Лаутенбахом [167] и Льеном [173]. Келлер [150] вместе с другими задачами рассматривал также и активность. Льен [173] определил задачу сохранения. Карп и Миллер [128] впервые описали построение дерева достижимостп и доказали его конечность. Задачи покрываемости и достижимости были определены ими как если бы это были задачи эквивалентности и включения.
Последние задачи явились предметом изучения в [26]. В [213] дана краткая формулировка задачи достижимости. Хэк [111] рассмотрел большинство этих задач вместе и показал„как дерево достижимостн можно использовать для решения некоторых из них. Матричный подход рассматривался Питерсоном [236], но, как оказалось, возможности его ограничены. Мурата, имеющий ббльшую квалификацию в линейной алгебре, достиг чуть большего В этом подходе в [210, 206, 212, 208, 209].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
