Расчёты и полученные результаты

3.3 Расчёты и полученные результаты

Исходная сеть в виде графа:

p₁ p₆

▪ ▪

t₁ ▪ p₄ t₄

 

p₂ p₇

t₂ ▪ p₅ t₅

 

p₃ p₈

t₃ t₆

Рисунок 3.3.1 – Исходная сеть Петри

Для матричного анализа сети найдём её матрицу изменений.

 (3.3.1)

 (3.3.2)

Матрицу изменений найдём как разность между (3.3.2) и (3.3.1):

(3.3.3)

Таким образом, получив матрицу изменений, можно записать матричное уравнение смены маркировок вида (3.2.19). Вектор начальной маркировки определим так:

μ₀ = (10011100) (3.3.4)

Составим дерево покрываемости маркировок сети.

(10011100) ‘Новая’

t₁ t₄

‘Новая’ ‘Новая’

(01001100)  (10010010)

t₂ t₄ t₁ t₅

(00100100) (01000010) (01000010) (10000001)

‘Новая’ ‘Тупик’ ‘Тупик’ ‘Новая’

t₃ t₆

 

(10011100) ‘Старая’ (10011100) ‘Старая’

Рисунок 3.3.1 – Дерево покрываемости маркировок

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

Граф покрываемости сети выглядит следующим образом:

μ₀

t₃ t₆

10011100

00100100 t₁ t₄ 10000001

t₂ t₅

01001100 10010010

t₄ t₁

01000010

Рисунок 3.3.2 – Граф покрываемости маркировок сети Петри

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

Вопрос достижимости какой- либо маркировки легче всего решается, глядя на граф покрываемости. Действительно, возьмём для примера две маркировки: μ₁ = (01000010) и μ₂ = (00100010). Первая из них достижима, и возможны два пути прихода к ней: t₁ , t₄ или t₄ , t₁ . Однако они не единственны, перед вторым запуском перехода возможно бесконечное число раз запустить для первого случая последовательность t₂ , t₃ , для второго случая – t₅ , t₆ . Вторая маркировка явно недостижима, так как её нет на графе.

С помощью матриц этот вопрос решается следующим образом. Составляем уравнение вида (3.2.19), в котором вместо σ ставим неизвестный вектор x той же размерности, а вместо μ – интересующую нас маркировку μ₁. В итоге получаем систему из 8 уравнений относительно 6 неизвестных компонент вектора x.

(3.3.5)

Проанализировав данную систему, видим, что пятое уравнение является следствием из третьего и шестого, шестое – из седьмого и восьмого, первое – из второго и третьего. Из (1) и (4) следует, что x₅ = 0, x₆ = 0, из (7) следует, что x₄ = 1. Первые три уравнения в (3.3.5) являются линейно зависимыми, поэтому за свободное неизвестное примем x₁. Тогда получаем решение в виде x₁ = {y y-1 y-1 1 0 0}, где y – любое целое число. Полученное решение говорит о достижимости маркировки μ₁ и указывает, какие из переходов и сколько раз должны быть для этого запущены.

Сравнив оба способа решения, сразу можно увидеть недостатки второго. Во- первых, решение (3.3.5) не указывает, в какой именно последовательности должны быть запущены указанные переходы. Во- вторых, глядя на матрицу изменений, мы не можем судить о наличии в сети петель. Кроме того, полученное матричное решение не даёт, вообще говоря, гарантий своей реализуемости – оно является лишь необходимым условием достижимости. Однако, не получив решения, можно говорить о недостижимости маркировки.

Действительно, записав (3.2.19) для μ₂, получаем систему:

 (3.3.6)

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

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

Данная сеть является активной – в ней каждый переход может сработать хотя бы один раз. Проанализируем уровни активности отдельных переходов. Переходы t₁ и t₄ являются L1- активными, так как они в худшем случае (то есть при получения тупиковой маркировки) могут сработать хотя бы один раз. Переходы t₂, t₃, t₅ и t₆ являются L2- активными, так как они могут сработать любое наперёд заданное число раз и даже больше.

Отсюда можно сделать вывод о том, что данная сеть не является бесконфликтной – у неё есть тупиковое состояние.

Можно также сказать, что сеть является обратимой. Этот вывод можно получить и матричным путём – решив уравнение

x·D = 0 (3.3.7)

Получаем систему

 (3.3.8)

Данная система имеет 2 решения: {y y y 0 0 0} и {0 0 0 y y y}, где y – любое. Действительно, запуская любое число раз последовательности t₁ t₂ t₃ или t₄ t₅ t₆ , каждый раз мы возвращаемся к исходной маркировке.

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

Можно сказать, что данная сеть не является устойчивой. У неё есть тупик, и, кроме того, непосредственно перед переходом в тупиковое состояние всегда существуют два разрешённых перехода. Запуская ‘неправильный’ переход, мы запрещаем оба – и оказываемся в тупике. Такое свойство сети говорит о наличии потенциально возможных конфликтов.

Па основании графа (3.3.2) можно выписать множество достижимых из μ₀ маркировок:

 (3.3.9)

Для моделирования сети была написана программа на языке Turbo Pascal. Она отображает состояние сети и разрешённые в каждый момент переходы. Для выбора запускаемого перехода используется мышь.