Матричный метод анализа сетей Петри.

 

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

Итак, сеть Петри - это набор

N = (T,P,A), T Ç Р = Ø, где Т = {t₁, t₂,..., t_n} - подмножество вершин, называющихся переходами;
Р = {p₁, р₂,..., p_m} - подмножество вершин, называющихся местами; А Í (T×P) Ç (P×T) - множество ориентированных дуг.

По определению, дуга соединяет либо место с переходом, либо переход с местом.

Данный подход основан на матричном представлении сетей Петри. Входная и выходная функции представляются матрицами и соответственно. Элементы матриц определяются следующим образом:

[ i, j ] = (, I ()); (количество фишек уходящее из позиции , при срабатывании перехода ),

[ i, j ] = (, O ()); (количество фишек приходящее в позицию , при срабатывании перехода ), i= ; j= .

Матричная форма представления сети C = <P (множество позиций), T (множество переходов), , > эквивалентна стандартной, но позволяет дать определения в терминах векторов и матриц.

Пусть е [ j ] – m -вектор - столбец, содержащий все нули, за исключением j -й позиции. Переход , таким образом, может быть представлен вектором e [ j ].

Переход в маркировке μ разрешен, если μ ≥ e [ j ], а результат запуска перехода в маркировке μ равен

σ (μ, ) = μ' = μ – e [ j ] + e [ j ] = μ + ( – )· e [ j ],

где ( – ) = D – составная матрица изменений, элементы которой могут быть отрицательными.

Тогда для последовательности запусков переходов σ = , ,..., имеем

δ (μ, σ) = μ + De [ ] + De [ ] +... + De [ ] = μ + D ﴾ e [ ] + e [ ] +... + e [ ]﴿ = μ + D ·ƒ(σ),

,где ƒ(σ) = ﴾ e [ ] + e [ ] +... + e [ ]﴿ – вектор запусков последовательности σ, каждый элемент которого показывает число запусков соответствующего перехода. Все элементы этого вектора неотрицательны.

Для того чтобы показать сохранение сети, необходимо найти (ненулевой) вектор взвешивания ω, размерностью (1 × n), для которого взвешенная сумма по всем маркировкам постоянна, т.е. ωμ = ωμ'.

Поскольку маркировка μ' достижима, существует последовательность запусков переходов σ, которая переводит сеть из μ в μ':

μ' = μ + Df (σ).

Следовательно, ωμ = ωμ' = ω ﴾ μ + Df (σ)﴿= ωμ + ωDf (σ).

Отсюда следует, что ωDf (σ) = 0. Поскольку это должно быть справедливо для всех f (σ), то ωD = 0.

Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой вектор ω, что ωD = 0. Если ω = (1, 1,..., 1), то это условие формулируется следующим образом: сумма элементов каждого столбца матрицы D должна быть нулевой.

Матричная теория сетей Петри является инструментом для решения проблемы достижимости. Предположим, что маркировка μ' достижима из маркировки μ. Тогда существует последовательность запусков переходов σ, которая приводит из μ к μ'. Это означает, что f (σ) является неотрицательным целым решением следующего матричного уравнения для х: μ' = μ+Dx. (2.1)

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

Пример: Рассмотрим сеть, представленную на рис. 1.

Рис. 1. Пример для иллюстрации матричного представления сетей Петри

Матрицы , , для этой сети имеют следующий вид:

В начальной маркировке μ = переход разрешен и приводит к маркировке:

Последовательность σ = , , , , представляется вектором запусков f (σ) = и приводит к маркировке

Для определения того, является ли маркировка μ' = достижимой из маркировки μ = (1, 0, 1, 0), имеем линейные уравнения

Система этих уравнений имеет решение = (0,4,5). Это соответствует разрешенной последовательности σ = , , , , , , , , .

Матричный подход к анализу сетей очень перспективен, но имеет и ряд недостатков. Матрица D сама по себе не полностью отражает структуру сети, так как встречные дуги между переходом и позицией (как, например, между и (см. рис. 1) взаимно уничтожаются в матрице D. Кроме того, в векторе запуска переходов f (σ) отсутствует информация о последовательности запуска переходов. Это приводит к тому, что одному и тому же решению уравнения (2.1) можно поставить в соответствие несколько последовательностей запуска переходов.

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

 

 

12. Дерево достижимости и его свойства, алгоритм построения дерева, теорема оконечности дерева достижимости (без доказательства). Анализ сетей Петри с использованием дерева достижимости.

 

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

 

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

Пассивная (или терминальная) вершина – это маркировка, в которой нет разрешенных переходов ((0, 0, 1) для рис. 1).

Дублирующая вершина – это вершина с маркировкой, которая уже ранее встречалась в этом дереве достижимости. При появлении дублирующей вершины нет необходимости производить из нее дальнейшие построения, поскольку это приведет к появлению поддерева, полученного из места первого появления дублирующей вершины. В рассматриваемом примере маркировка (0, 1, 1), получившаяся после выполнения t1, t2, t3 не будет порождать какие-либо новые вершины, поскольку она ранее была получена в дереве после выполнения t2 из начальной маркировки.

Расширенная маркировка вводится в случае постепенного наращивания количества фишек в той или иной позиции достигаемых маркировок.

Для рассматриваемого примера (см. рис. 1) последовательное срабатывание t1 приводит к нарастанию разметки в позиции р2, что приводит к введению расширенной маркировки (1, ω, 0).

Кроме того, различают граничные вершины и внутренние. Граничными вершинами называют вершины дерева достижимости, которые еще не обработаны алгоритмом построения дерева достижимости. В результате реализации алгоритма построения дерева достижимости граничные вершины превращаются в терминальные, дублирующие или внутренние.

Алгоритм построения (конечного) дерева
Алгоритм начинает работу с начальной маркировки и работает до тех пор, пока в дереве есть граничные вершины.

Пусть x - граничная вершина, которую нужно обработать.

1) если в дереве есть другая вершина , то х – дублирующая.
2) если для маркировки ни один из переходов неразрешён, т.е. не определено для , то х – терминальная вершина.
3) для всякого перехода разрешённого в создать новую вершину z, маркировка которой определяется следующимм образом:
а) если , то .
б) если на пути от корневой вершины к х, существует вершина y с
и , то .
в) в противном случае .

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

Теорема о конечности дерева достижимости (без доказательства)

Существующий алгоритм построения ограниченного дерева достижимости применим для любой возможной сети Петри.

Или Для любой сети Петри можно с помощью приведенного алгоритма построить ограниченное дерево достижимости.