Анализ свойств раскрашенных сетей

 

Раскрашенная сеть характеризуется следующим множеством элементов:

 

CN = { N, C, F, C M₀ },

где: N = { T, P, I, O } – биграф;

C = { X, R }, X = { λ, с₁, с₂, …, с_L } = { с_r} – множество раскрашивающих цветов или других признаков, включающее элемент λ, обозначающий «отсутствие цвета»;

R - бинарное отношение на множестве цветов Х, (чаще всего это отношение эквивалентности или равенства цветов);

F: А à Х – отображение множества дуг биграфа N на множество цветов, дающее раскраску дуг: с_ij^S - цвет s-ой дуги a_ij^S биграфа, направленной из вершины i в вершину j;

С М₀ – начальное цветное маркирование сети.

В сети также раскрашиваются метки. Если – множество цветных меток, то цветное маркирование сети характеризуется парой отображений:

 

CM: { P ; Х },

 

первое из которых указывает на размещение меток по позициям, а второе - на цвет этих меток. Факт размещения метки m в позиции P_i обозначим (m P_i).

Условимся, что метка m, имеющая цвет c(m), может принять участие в возбуждении перехода t_j, если пара (c(m),с_ij^S) удовлетворяет заданному R-отношению на множестве цветов. Если R-отношение равенства, то метка (m P_i) может участвовать в возбуждении t_j при условии что c(m) = с_ij^S (т. е. когда цвет метки равен цвету дуги a_ij^S). Для возбуждения перехода t_j необходимо, чтобы по всем входящим дугам могли пройти метки соответствующего цвета из позиций P_i, являющиеся предшественниками перехода t_j.

Логическое уравнение, описывающее условие возбуждения перехода t_j, имеет следующий вид:

 

∀ P_i Pre(t_j) ∃ m P_i [ R(с(m), с_ij^S) = 1] u(t_j) = 1,

иначе u(t_j) = 0.

 

Итак, если переход t_j возбуждён (u(t_j) = 1), то происходит его срабатывание и возбуждавшие метки из позиций Pre(t_j) при этом изымаются, а позиции Post(t_j) пополняются метками, цвет которых принимается равным цвету дуг, проходящих из t_j в позиции Post(t_j).

Для отображения цветного маркирования условимся представлять его в следующем виде:

 

CM = | m₁ … m_i … m_n |*,

 

где: * - операция транспонирования;

m_i = | m_i¹ m_i² … … m_i^L |, причём m_i^r - число меток r-го цвета в позиции P_i.

Динамика меток в раскрашенной сети характеризуется матрицей инцидентности Д, элементы которой d_ij представим в виде векторов-строк длиною L:

 

d_ij = | d_ij¹ d_ij² … d_ij^L |, (5.16)

где L - число раскрашивающих цветов.

 

Значения d_ij^r задаются следующим образом. Если метка цвета r потребляется переходом t_j из позиции P_i при срабатывании t_j, то d_ij^r = -1; если метка цвета r поступает в P_i из t_j, то d_ij^r = 1, и, наконец, в отсутствии этих действий d_ij^r = 0.

Эти же условия можно сформировать по другому. Если позиция P_i имеет исходящие дуги цвета r в переход t_j, то d_ij^r = -1; если имеет входящие дуги цвета r, то d_ij^r = 1, и если не имеет инцидентных дуг цвета r, то d_ij^r = 0.

Динамику продвижения меток по раскрашенной сети можно описать уравнением состояния:

 

CM_k = CM_k-1 + D*U_k, (5.17)

где CM_k - состояние, в которое переходит раскрашенная сеть из CM_k-1 под действием управляющего вектора U_k = | u_jk |, компоненты которого

1, если в k-ый момент срабатывает переход t_j;

u_jk=

0, иначе.

 

Р-инварианты. Введём в рассмотрение инварианты раскрашенной сети, подобно тому как это сделано в сети Петри. Р-инвариант найдём из решения линейной системы:

 

DV = 0, (5.18)

где V = | V_i | - целочисленный вектор-столбец, компоненты которого имеют вид:

 

V_i* = | v_i¹ v_i² …. v_i^L |.

 

Учитывая уравнение (5.1), находим:

 

V*CM = V*CM₀. (5.19)

 

Итак, подобно уравнению (5.9) для сети Петри, уравнение (5.19) для раскрашенной сети описывает инвариантность в её маркированиях.

Фундаментальная система решений однородной системы линейных уравнений имеет n – rL решений, где n - число позиций сети; r - ранг матрицы Д; L - мощность множества цветов Х. Объединив их в матрицу СВ, получим уравнение, аналогичное уравнению (5.11):

 

CB CM = CB CM₀ = K₀.

 

T-инварианты. Решение линейной системы:

 

D*W = 0, (5.20)

 

даёт t-инварианты W, где W = | W_j | - целочисленный вектор-столбец, в котором

W_j = | W_j¹ W_j²… W_j^L |.

Условие существования тупиков в раскрашенной сети находится из анализа системы:

 

CB CM = CB CM₀;

CO*CM ≤ COE’ – E, (5.21)

 

подобно тому как это выполняется для сети Петри. Здесь CO* - матрица аналогичная O*, расширенная в пределах каждого элемента по принципу (5.16):

 

1, если существует дуга из t_j в P_i, раскрашенная цветом r;

CO_ij^r =

0, иначе,

 

CO_ij = | CO_ij¹, CO_ij², …, CO_ij^r,…, CO_ij^L |,

 

Е’ – единичный клеточный вектор, компоненты которого e_j’ представлены наборами из L единиц.

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

 

Рассмотрим простой пример для уяснения методики расчёта динамических свойств раскрашенных сетей.

б)

a)

 

Рис.5.23. Примеры раскрашенных сетей

В изображённой на рис. 5.23а сети, описывающей взаимодействие двух процессов, обозначенных метками (□,○), протокол взаимодействия предусматривает порождение нового процесса (●), а затем возврат к исходным.

Каждому цвету из множества Х = (□,○,●) сопоставим числа r = 1, 2, 3. Тогда элементы матрицы Д = || d_ij ||, где i = 1, 2, 3, 4, j = 1, 2, 3, 4, 5, равны:

 

d₁₁ = d₂₂ = | -1 0 0 |; d₂₃ = | 0 0 1 |;

d₁₂ = d₃₁ = | 1 0 0 |; d₃₃ = | 0 0 -1|;

d₃₅ = d₄₄ = | 0 1 0 |; d₂₄ = d₄₅ = | 0 -1 0 |,

а другие d_ij = | 000 |.

 

Вектор начального маркирования СМ₀ = | m_0i | представлен компонентами:

 

m₀₁ = | 100 |; m₀₂ = m₀₃ = m₀₄ = | 000 |; m₀₅ = | 010 |.

 

Уравнение состояния (5.17) здесь имеет вид:

 

m1		m1		d11	d21	d31	d41		U1
m2		m2		d12	d22	d32	d42		U2
m3	=	m3	+	d13	d23	d33	d43	*	U3
m4		m4		d14	d24	d34	d44		U4
m5	k	m5	k-1	d15	d25	d35	d45			k

 

Рекуррентное решение данного уравнения позволяет моделировать динамику состояний сети.

Найдём Р-инвариант сети V* = | V₁V₂V₃V₄V₅ |, где V_i* = | v_i¹ v_i² v_i³ |. Для этого нужно решить систему (5.18). Ранг матрицы Д равен 1, следовательно фундаментальная система имеет одно решение, так как n – rL = 1. Распишем систему уравнений (5.18) для данной сети:

 

v₁¹ = v₂¹; v₃³ = v₁¹ + v₅²;

v₃³ = v₂¹ + v₄²; v₄² = v₅² .

В качестве инварианта можно взять клеточный вектор-столбец с компонентами V₁* = V₂* = |100|; V₃*= |003|; V₄* = V₅* = |020|, удовлетворяющий приведённой однородной системе линейных уравнений. Затем вычисляем произведение:

 

V*CM₀ = | V₁* V₂* V₃* V₄* V₅*|| m₁* m₂* m₃* m₄* m₅*|₀ = 3,

 

и условие инвариантности:

VCM = | V_i* || m_i* |* = ∑ V_i* m_i* = m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅² = 3.

i=1

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

 

m₁¹+ 2m₄² = 3; m₁¹+ 2m₅² = 3; m₂¹ + 2m₄² = 3;

m₂¹ +2m₅² = 3; 3m₃³ = 3.

 

Из условия инвариантности, содержащего в правой части константу 3, следует ограниченность сети.

Решив систему (5.20), можно установить, что данная сеть живая и устойчивая. Элементы матрицы СО равны:

 

CO₁₁ = CO₂₂ = | 100 |; CO₄₂ = CO₅₄ = | 010 |; CO₃₃ = | 001 |;

 

а другие CO_ij= | 000 |. Система (5.21) здесь имеет вид:

 

m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅² = 3;

m₁¹ ≤ 0; m₂¹ + m₄² ≤ 1; m₃³ ≤ 0; m₅² ≤ 0.

 

Данная система не совместна, а, следовательно, исследуемая раскрашенная сеть не имеет тупиков.

Изменим раскраску на дуге (t₃,p₅) и примем новое начальное маркирование как показано на рис. 5.23б.

На основе вычислений можно установить, что приведённая сеть – ограниченная, живая, однако тупиковая, поскольку система

m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅¹ + 2m₅² = 3;

m₁¹ ≤ 0; m₂¹ + m₄² ≤ 1; m₃³ ≤ 0; m₅² ≤ 0,

совместна. Тупиковое маркирование описывается вектором СМ = | (000) (100) (000) (100) (000) |.

«Обесцвечивание» сети, т. е. переход от раскрашенной сети к базовой сети Петри может привести к потере и искажению информации о протекании процессов в сетевой модели. Так, если выполнить «обесцвечивание» приведённой сети, то расчётами можно установить, что её инвариант станет равным m₁ + m₂ + 3m₃ + 2m₄ + 2 m₅ = 3, т. е. произошло как бы «обесцвечивание» инварианта сети, приведённой на (рис. а), а не на (рис. б). Но самое важное состоит в том, что «обесцвеченная» сеть – беступиковая, хотя исходная раскрашенная сеть имеет тупик. Искажение такого важного свойства при упрощении модели указывает, что для обеспечения достоверности проектного анализа при исследовании раскрашенных сетей недопустим переход к «обесцвеченной» сети.