Дослідження матричного подання сітки Петрі

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

Виходячи з умови збудження та правила спрацьовування переходів, динаміку сітки в просторі станів (маркувань) можна описати рекурентним рівнянням – рівнянням стану сітки:

M_k = M_{k –1} + A • U_k; k = 1, 2,..., (3.3)

де M_k – стан, у який перейде сітка зі стану m _{k -1} у результаті k -го впливу U_k (спрацьовування переходу);

U_k = [ U_jk ] – керуючий вектор, компонента якого U_jk = 1, якщо в k -й момент асинхронного часу виникає спрацьовування переходу t_j, або U_jk = 0, якщо спрацьовування не відбувається;

A = [ A_ij ] – матриця інциденцій позицій та переходів, елементи якої визначаються наступним чином: A_іj = l, якщо перехід t_j має l вихідних дуг до позиції p_і, A_іj = - l, якщо перехід t_j має l вхідних дуг з позиції p_і, A_іj = 0, якщо перехід t_j немає зв’язку з позицією p_і.

Матрицю А можна розрахувати на підставі операції над матрицями F = [ F_ij ] і H = [ H_ij ], які задають кількість дуг, що виходять відповідно з позицій і переходів:

A = H – F,

тобто елементи F_іj задають кількість маркерів, які потрібно забрати з позиції p_і при спрацьовуванні переходу t_j, а елементи H_іj визначають кількість маркерів, які направляються у позицію p_і при спрацьовуванні переходу t_j.

Очевидно, що в будь-якому стані компоненти вектора маркування не можуть бути від’ємними. Вони можуть набувати лише нульових або додатних цілочисельних значень. Ця умова у матричному записі має вигляд: M_k ³ 0 для всіх k. Враховуючи останнє, з рівняння станів одержуємо M_{k –1} + A • U_k ³ 0, а послідовність маркувань (3.3) можна замінити єдиним виразом через початкове маркування M ₀ і вектор підрахунку спрацьовувань переходів сітки:

. (3.4)

Елемент s_j вказує, яку кількість разів спрацьовує перехід t_j в послідовності маркувань, яка йде від M ₀ до M_k. Враховуючи рівняння (3.4), з (3.3) одержимо:

M_k = M ₀ + A • S, (3.5)

або якщо додати вектор зміни маркірування

dM = M_k – M ₀,

з рівняння (3.5) одержимо рівняння:

A • S = dM. (3.6)

Всі можливі рішення даного рівняння можна отримати за допомогою одного з методів розв’язку задач цілочисельного програмування.

Розглянемо використання методів лінійної алгебри у розв’язанні рекурентних рівнянь зміни станів моделі сітки. Вони дозволяють на основі математичного дослідження структури біграфа сітки і початкового маркування M ₀оцінити такі якісні характеристики сітки, як обмеженість, живучість.

Цілочисельний вектор , який є розв’язком лінійної системи

A^T • X = 0 (3.7)

називається р - інваріантом.

Розглянемо рівняння (3.3), обидві частини якого помножимо на транспонований вектор X^T:

X^T • M = X^T • M ₀ + X^T • A • S. (3.8)

Враховуючи (3.7) i те, що A^T • X = Х^T • А, з виразу (3.8) одержимо:

X^T • M = X^T • M ₀, (3.9)

тобто будь-який p -iнварiант характеризує всi досяжнi маркування сітки з точки зору збереження деяких властивостей процесiв, що моделюються сіткою.

Якщо позначити

X^T • M = К ₀,

де К ₀ – константа,

то iнварiантнiсть досяжних маркувань сітки представимо у виглядi спiввiдношення:

X^T • M = К ₀ = const. (3.10)

Вектор X тому називають p -інваріантом, що він визначає властивості структури сітки у розподілі маркерів за позиціями p_і незалежно від будь-якого досяжного маркування.

Враховуючи, що система (3.7) може мати нескінченну кількість рішень, фундаментальною системою розв’язків системи лінійних однорідних рівнянь називають таку сукупність розв’язків, за допомогою якої виражаються всі інші розв’язки.

Якщо ранг матриці A дорівнює числу невідомих (r = n), то система (3.7) має тільки нульовий розв’язків. Якщо r < n, то система (3.7), крім нульового, має нескінченну множину інших розв’язків, причому фундаментальна (базисна) система складається з (n – r) векторів p -інваріант.

Ранг матриці A = [ a_ij ] розміром n ´ m дорівнює найвищому порядку відмінного від нуля визначника, одержаного викреслюванням (n – r) стовпців і (m – r) рядків з матриці A. Таким чином, всі інваріанти X для маркувань сітки можна отримати з (n – r) базисних рішень, тобто , де - коефіцієнт лінійної комбінації векторів базисних рішень . Об’єднавши записані у вигляді векторів-рядків розв’язки фундаментальної системи, одержимо матрицю інваріантів чи базисних розв’язків .

Тоді подібно до (3.9) для будь-якого досяжного маркування будемо мати:

B • M = B • M ₀ = K ₀. (3.11)

Якщо всі компоненти p -інваріанта невід’ємні, його називають p- ланцюгом.

Повний p -ланцюг – це p -інваріант, всі компоненти якого додатні, тобто повний p- ланцюг включає всі позиції сітки.

Сітка Петрі інваріантна, якщо для неї існує повний p-ланцюг. Повний p -ланцюг потрібно шукати серед усіх рішень фундаментальної системи В або їх лінійної комбінації.

Інваріантна сітка Петрі є обмеженою, але обмежена сітка може не бути інваріантною, тобто не мати повного ланцюга. Це випливає з того, що якщо X – повний p -ланцюг і X^T • M = K ₀, то зважена сума маркерів за всіма позиціями є обмеженою. А оскільки x_і – додатні і вся сума обмежена, то і маркування m _і всіх позицій сітки обмежені. Необхідно зауважити, що якщо повний p -ланцюг є одиничним вектором, то сітка є безпечною.

Розглянемо наступну характеристику сітки – живучість, визначення якої базується на обчисленні t -інваріантів.

Цілочислений вектор називається t - інваріантом, якщо він є розв’язком лінійної однорідної системи:

A • Y = 0. (3.12)

Якщо значення t -інваріанта підставити в рівняння (3.5) замість вектора підрахунку спрацьовувань переходів S, то виявиться, що

M = M ₀ + A • Y = M ₀.

Звідси випливає, що якщо Y ¹ 0, то сітка стійка, тобто після деяких спрацьовувань переходів вона повертається в початковий стан M ₀. Стійкість сітки пов’язана з її циклічною повторюваністю, починаючи зі стану M ₀. Необхідно зазначити, що серед розв’язків системи (3.12) можуть бути і такі вектори Y, компоненти яких від’ємні.

Повний t -ланцюг – це t -інваріант, всі компоненти якого додатні. Повний t -ланцюг включає усі переходи сітки. Якщо сітка має повний t -ланцюг, то вона стійка, що є тільки необхідною умовою живучості при будь-якому початковому маркуванні, оскільки встановлено, що в послідовності маркувань від m₀ до m = m ₀ спрацьовують всі переходи, але не визначено чи існують тупикові маркування. Пошук повного t -ланцюга здійснюється подібно до пошуку повного p -ланцюга.

Тобто, якщо ранг матриці A дорівнює числу невідомих (r = m), то система (3.12) має тільки нульовий розв’язків. Якщо r < m, то система (3.12), крім нульового, має нескінченну множину інших розв’язків, причому фундаментальна (базисна) система складається з (m – r) векторів t -інваріант.

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

Тупик – це досяжний з початкового маркування стан, у якому не збуджений жоден з переходів сітки.

Запишемо умову збудження переходу t_j у наступному вигляді:

або

F • M ³ F • E,

де E – одиничний вектор.

Оскільки множина досягаємих маркувань R (N) повинна задовольняти умові (3.11), то відсутність збуджуваних переходів для m Î R (N) необхідно визначити з розв’язку системи

(3.13)

Якщо ця система має розв’язок M, то деяке її маркування є тупиковим, в іншому випадку сітка немає тупиків і є живою.