ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

Алгоритмическое и программное обеспечение для нахождения параметризованных инвариантов сетей Петри

Статья опубликована в выпуске журнала № 2 за 2005 год.[ 24.06.2005 ]
Аннотация:
Abstract:
Авторы: Демидов Н.Е. () - , ,
Ключевое слово:
Ключевое слово:
Количество просмотров: 7447
Версия для печати
Выпуск в формате PDF (1.97Мб)

Размер шрифта:       Шрифт:

Сети Петри (СП) – одно из современных и наиболее эффективных средств графического и математического моделирования систем самых различных классов [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.

 


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=527
Версия для печати
Выпуск в формате PDF (1.97Мб)
Статья опубликована в выпуске журнала № 2 за 2005 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: