Методы линейной алгебры для решения уравнений смены состояний сети

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

Целочисленный вектор X = {Xi}, i=1,2,…n, являющийся решением линейной системы

AX = 0 (8)

называется Р-инвариантом или Р-циклом.

Рассмотрим уравнение (6), обе части которого умножим на X*:

X*M = X*M₀+ X*A*S (9)

Известно, что AX = X*A*, поэтому из выражения (9) с учётом (8) получим:

X*M = X*M₀ (10)

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

Если обозначить X*M₀ = K₀, где K₀ - постоянная величина, то свойство инвариантности сети представимо в виде отношения-равенства:

X*M = K₀ = const (11)

Вектор Х называют Р-инвариантом, поскольку он определяет некоторое из свойств распределения меток по позициям P_i.

Фундаментальной системой решений системы линейных однородных уравнений (8) называют такую их совокупность, через которую линейно выражаются все остальные решения. Если ранг матрицы А равен числу неизвестных (r = n), то система (8) имеет только нулевое решение.

Если r < n, то система (8) помимо нулевого имеет бесконечное множество других решений, причём фундаментальная система состоит из (n - r) векторов Х. Ранг n*m - матрицы А = || a_ij || равен наивысшему порядку отличного от нуля определителя, полученного вычёркиванием n - r столбцов и m - r строк из матрицы А.

Таким образом, все инварианты Х для маркирований сети можно получить из n - r базисных решений. Объединив записанные в виде векторов-строк решения фундаментальной системы, получим матрицу инвариантов или базисных решений В. Тогда для любого достижимого маркирования аналогично равенству (11).

BM = BM₀ = K₀ эквив. X*M = X*M₀ = K₀ (12)

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

Инвариантная сеть Петри является ограниченной. Докажем это. Пусть Х – полная Р-цепь. Тогда X*M=K₀, т. е. взвешенная сумма меток по всем позициям ∑_j x_jm_j = K₀ - ограниченная. А поскольку x_j положительные и вся сумма ограничена, то и маркирования всех позиций сети ограниченны.

Характеристики сети Петри на основе t-инварианта.

Рассмотрим следующую группу характеристик, получение которых основывается на вычислении t-инвариантов (или t-циклов).

Целочисленный вектор У называется t-инвариантом, если он является решением линейной системы.

A*Y = 0 (13)

Если значение t-инварианта подставить в уравнение (6) вместо вектора счёта срабатываний S, то окажется, что

M = M₀ + A*Y = M₀

Отсюда следует, что если Y≠0, то сеть устойчива, т. е. после ряда переключений она возвращается в исходное состояние M₀. Устойчивость процессов связана с их циклической повторяемостью, начиная с состояния M₀. заметим, что среди решений системы (13) могут быть такие векторы У, компоненты y_i которых отрицательны.

Полная t-цепь – это t-цикл, все компоненты которого положительны. Полная t-цепь включает в себя все переходы сети. Если сеть имеет полную t-цепь, то она жива при любом начальном маркировании, поскольку в цепи маркирований от M₀ до М= M₀ срабатывают все переходы.

Таким образом, по устойчивости процессов и значению t-инварианта можно определить живость сети: если сеть жива и ограничена, то она инвариантна и устойчива.