Часть 2. Тема «Основные понятия сетей Петри. Анализ сетей Петри»

Часть 2. Тема

«Основные понятия сетей Петри. Анализ сетей Петри»

Задание

Для предлагаемой сети Петри, заданной в виде двудольного ориентированного мультиграфа, выполнить следующее:

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

Решение

Определить сеть Петри в виде .

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

В нашем случае эта четверка будет выглядеть следующим образом:

P = {p1, p2, p3, p4};

T = {t1, t2, t3, t4, t5, t6};

I(t1) = {p1}                                        O(t1) = {p2}

I(t2) = {p1}                                        O(t2) = {p2, p3}

I(t3) = {p1}                                        O(t3) = {p3, p3}

I(t4) = {p2}                                        O(t4) = {p3}

I(t5) = {p3, p3}                                O(t5) = {p4}

I(t6) = {p4}                                        O(t6) = {p1}

Определить расширенные входную и выходную функции.

Для нашей сети Петри расширенные входная и выходная функции будут выглядеть так:

I(p1) = {t6}                                        O(p1) = {t1, t2, t3}

I(p2) = {t1, t2}                                O(p2) = {t4}

I(p3) = {t2, t3, t3,t4}                                O(p3) = {t5, t5}

I(p4) = {t5}                                        O(p4) = {t6}

Определить мультиграф в виде .

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

V = {p1, p2, p3, p4,t1, t2, t3, t4, t5, t6};

A = {(p1,t1), (p1,t2), (p1,t3), (t1,p2), (t2,p2), (t2,p3), (t3,p3), (t3,p3), (p2,t4), (t4,p3), (p3,t5),

(p3,t5), (t5,p4), (p4,t6), (t6,p1)}.

Нарисовать граф инверсной сети Петри и описать ее как .

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

Множества переходов и позиций будут те же, что и в исходной сети, а входная и выходная функции, соответственно, примут вид:

I(t1) = {p2}                                        O(t1) = {p1}

I(t2) = {p2, p3}                                O(t2) = {p1}

I(t3) = {p3, p3}                                O(t3) = {p1}

I(t4) = {p3}                                        O(t4) = {p2}

I(t5) = {p4}                                        O(t5) = {p3, p3}

I(t6) = {p1}                                        O(t6) = {p4}

Нарисовать граф двойственной сети Петри и описать ее .

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

Множество переходов, множество позиций, входная и выходная функции:

P = {p1, p2, p3, p4, p5, p6};

T = {t1, t2, t3, t4};

I(t1) = {p6}                                        O(t1) = {p1, p2, p3}

I(t2) = {p1, p2}                                O(t2) = {p4}

I(t3) = {p2, p3, p3, p4}                        O(t3) = {p5, p5}

I(t4) = {p5}                                        O(t4) = {p6}

Выполнить сеть Петри, записав последовательность переходов и последовательность маркировок .

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

Определим следующую последовательность переходов:

у = t20, t41, t52, t63, t34, t55, t66, t17, t48.

       Ниже приведена последовательность маркировок.

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

Мы видим, что именно такая ситуация сложилась на последней маркировке. Для запуска перехода t5 необходимо во входной позиции p3 иметь две фишки, а у нас только одна.

Построить дерево достижимости и определить тип всех его вершин.

Строим дерево достижимости.

Далее определим типы его вершин.

С самого начала маркировка сети у нас (1, 0, 0, 0). В такой маркировке у нас может произойти запуск переходов t1, t2 или t3. То есть от корня дерева у нас пойдет три ветви. А сам корень будет являться внутренней вершиной.

Рассмотрим левую ветвь. После запуска перехода t1 у нас получится маркировка (0, 1, 0, 0). В такой маркировке может произойти только запуск перехода t4 с последующим получением маркировки (0, 0, 1, 0). Вершина (0, 1, 0, 0) становится внутренней вершиной. А вершина (0, 0, 1, 0) является, как было показано в предыдущем пункте, терминальной. Теперь перейдем к центральной ветви дерева.

После запуска перехода t2 получаем маркировку (0, 1, 1, 0). Теперь фишки у нас находятся в позициях p2 и p3. Переход t5 не может быть запущен из-за нехватки фишек, остается переход t4. После его запуска получаем маркировку (0, 0, 2, 0), а вершина (0, 1, 1, 0) становится внутренней. Здесь возможен запуск только одного перехода t5. После его запуска получаем маркировку (0, 0, 0, 1), а предыдущая вершина также становится внутренней. Опять получаем ситуацию запуском единственно возможного перехода, на этот раз t6. После его запуска получаем маркировку (1, 0, 0, 0), которая есть ни что иное как вершина, дублирующая корень дерева. То есть с этой ветвью мы тоже справились.

Теперь правая ветвь дерева достижимости. После запуска перехода t3 получаем маркировку (0, 0, 2, 0). Но такая вершина уже присутствует в центральной ветви, то есть она является дублирующей.

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

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

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

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

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

Переход tj обладает активностью уровня 0, если он никогда не может быть запущен. Из дерева достижимости видно, что таких переходов у нас нет. Переход tj обладает активностью уровня 1, если он потенциально запустим, то есть существует такая маркировка, что tj разрешен в этой маркировке. Из дерева достижимости видно, что все наши переходы обладают по крайней мере активностью уровня 1. Переход tj обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой tj присутствует по крайней мере n раз. Из дерева достижимости видно, что этому условию не удовлетворяет переход t1 – он запускается из начальной маркировки и приводит к тупику. Из этого делаем вывод, что наша сеть Петри обладает активностью уровня 1.

Для матричного представления сети Петри определить матрицы и вектор запусков последовательности для из п.6. Вычислить .

Матрица представляет собой входную функцию, а матрица – выходную. Они имеют количество строк по количеству переходов в сети и количество столбцов по числу позиций. То есть в нашем случае это будут матрицы размерностью [6 x 4]. Матрица   – это составная матрица изменений. Последовательность из пункта 6 будет представлена вектором запусков переходов .

Матрицы и в нашем случае имеют вид:

,

,

а матрица :

.

Последовательность у = t2 t4 t5 t6 t3 t5 t6 t1 t4 представляется вектором запусков f(у) = (1, 1, 1, 2, 2, 2). Получим маркировку м’:

То есть получили маркировку м9 из пункта 6, что и требовалось.