Software & Systems

Сети Петри (СП) – одно из современных и наиболее эффективных средств графического и математического моделирования систем самых различных классов [1]. СП – мощный инструмент для описания систем, использующих параллелизм, синхронизацию и разделяемые ресурсы, и в том числе промышленных производств, с целями координации процессов и принятия оперативных решений по управлению ими. Алгоритмы исследования свойств СП подразделяют на  предназначенные для построения множества достижимых маркировок, декомпозиции СП на подсети и поиска инвариантов СП. S- и T-инварианты СП широко используются для функционального диагностирования, уравнивания (балансировки) химических реакций и во многих других приложе- ниях [1,2]. Нахождение S-инвариантов СП формально заключается в вычислении m-k целочисленных линейнонезависимых решений уравнения Ax=0, в котором целочисленная матрица (ЦМ) A размеров n´m (n

Общее решение уравнения Ax=0 определяется зависимостью x=(I-A+A)y, в котором I – единичная матрица; A+ – обобщенная обратная матрица (ООМ), соответствующая условию AA+A=A; y – любой произвольный вектор [2]. Если A – ЦМ, то вектор x будет целочисленным при любом целочисленном векторе y, только если B=I-A+A – ЦМ. Основные вычислительные проблемы нахождения S-инвариантов связаны с определением ЦМ B, поскольку обычно в качестве таких инвариантов используются m-k линейнонезависимых столбцов этой ЦМ. В [2] показано, что при этом матрица A+ не обязательно должна быть ЦМ, однако она должна обладать определенными целочисленными свойствами.

При решении реальных задач, особенно большого размера, представляется целесообразным вычисление S-инвариантов с использованием развитого алгоритмического и программного обеспечения, предназначенного для нахождения нецелочисленных ООМ [3].

Проблема нахождения целочисленных S-инвариантов была решена с использованием ранее обоснованного автором параметризованного представления нецелочисленной ООМ [3] и его модификации для ЦМ.

Специальное разложение ЦМ A, называемое диагональной редукцией [2], имеет следующий вид:

где подматрица A11 имеет полный ранг k (что при необходимости достигается предварительной перестановкой строк и столбцов A), а подматрицы S11, S21 и Q12 отличаются от ЦМ скалярным сомножителем 1/r, причем r – целое и r³1.

Параметризованные ООМ AP+ и ортогональные проекции-матрицы AP+A и BP имеют вид:

При P21=0 m-k линейнонезависимых (базовых) S-инвариантов СП формируются из столбцов подматриц Q12 и Im-k матрицы Q и приводятся к целочисленному представлению умножением на r, при этом отметим, что существуют линейные комбинации исходных нецелочисленных базовых инвариантов, дающие целочисленные решения. Для их получения в линейных комбинациях целочисленных базовых инвариантов должны использоваться сомножители, кратные 1/r.

По известной матрице B, рассчитанной для нецелочисленной ООМ A+, подматрицу Q12 можно найти с использованием соотношения Q12=B12B22-1 (с предварительным выполнением необходимых перестановок столбцов и строк в B).

Возможности и особенности предлагаемого подхода рассматриваются на примере из [4] с ЦМ A размером 6 ´ 10 и строчным рангом, равным 5:

.

Нецелочисленная ООМ по Муру-Пенроузу A+ [3], являющаяся единственной для матрицы A:

.

Матрица B и рассчитанное по ней множество X целочисленных линейнонезависимых инвариантов для данного примера:

При решении реальных задач, особенно большого размера, представляется целесообразным вычисление и использование единого параметризованного S-инварианта СП с получением конкретных инвариантов путем задания целочисленных значений параметров и базового инварианта в случае задания всех нулевых значений параметров.

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

Поставленная проблема была решена с использованием ранее предложенного автором параметризованного представления обобщенных обратных матриц [3] и расширением его для целочисленных матриц.

Для формирования параметризованного S-инварианта xP с минимальным числом параметров, определяемым рангом к=5, в качестве P12 использована диагональная матрица с параметрами – элементами главной диагонали a, b, c, d/2 и –e, а также последний столбец ЦМ Q-1.

Окончательные результаты (инвариант xP и множество X из пяти полученных из xP при значениях параметров 0 или 1 обычных S-инвариантов, в том числе и базового инварианта) имеют следующий вид:

Комплекс программных модулей, решающих задачи нахождения S- и T-инвариантов СП с использованием параметризованных ООМ, оформлен в виде M-файлов системы для математических расчетов MATLAB, обладающей достаточными базовыми средствами для вычисления ООМ. Для нахождения решения рассмотренного примера использованы матричные функции линейной алгебры MATLAB pinv, rank и rats.

Список литературы

1. Питерсон Д. Теория сетей Петри и моделирование систем. – М.: Мир, 1984.  – 264 с.

2. Грегори Р., Кришнамурти Е.М. Безошибочные вычисления: методы и приложения. - М.: Мир, 1988. – 208 с.

3. Демидов Н.Е. Параметризация обобщенных обратных матриц: алгоритмическое и программное обеспечение // Программные продукты и системы. - 1998. - №2. – С. 33 – 36.

4. Murthy V.K., Schroder H.S. Systolic arrays for parallel matrix g-inversion and finding Petri net invariants // Parallel computing. – 1989. – 11, №3. – P. 349 – 359.