Труды КНЦ вып.3 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.1 3/2010(3))

существует такой переход д’= 5(д , 0 . У е Т. при котором Можно распространить это понятие на множество достижимых из данной маркировок. Определим множество достижимых из д маркировок R(C, д) следующим образом: 1. (1 е R(C, д); 2. если д’ е R(C, д), д’= 5 (д , t;) и д” = 8 (д \ tA), то и ц ” е R(C, д). Вектором маркировки для сети Петри является вектор, в котором число элементов равно числу по­ зиций, а значением элемента является количество фишек в соответствующей позиции. Одной из ос­ новных аналитических задач сетей Петри является задача определения достижимости маркировки, ко­ гда для исходного вектора маркировки требуется установить существование последовательности пе­ реходов, выполнение которых обеспечивает дости­ жение заданного выходного вектора маркиров­ ки. Простейший способ анализа достижимости мар­ кировки состоит в следующем. Структура сети Пет­ ри представляется в виде двух матриц инциденций (D+ и D ) , с числом строк, равным числу переходов в сети, и числом столбцов, равным числу позиций. Матрицы D+ и D- содержат соответственно выход­ ные и входные функции переходов. При этом D+ на­ зывается матрицей входов и содержит 1 на пересече­ нии /-той строки и y-го столбца, если y-тая позиция является входной для /-того перехода (и 0 для других вариантов). D- называется матрицей выходов и со­ держит 1 на пересечении /-той строки иy-го столбца, если y-тая позиция является выходной для /-того перехода. Вектор x называется вектором запуска пе­ реходов. Число элементов в x равно числу переходов, а значение каждого элемента определяет количество запусков данного перехода в процессе выполнения. Если исходный вектор маркировки обозначить m0, а результирующую маркировку - через mi, то дости­ жимость маркировки mj равнозначна существованию вектора x с неотрицательными целыми элементами, который служит решением уравнения: mj = m0 + x*(D+ - D-) (1), где (D+ - D ) - матрица изменений. Пример. Рассмотрим фрагмент сети Петри, заданной матрицами: D+= Пусть исходная маркировка m0 = (1, 0, 1, 0). Необходимо определить достижимость маркировки m1 = (1, 0, 0, 0). Решение. Вектор запусков, являющийся решени­ ем уравнения (1) имеет вид: ( 3 2 ч1/ Из чего следует, что требуемая маркировка дос­ тижима в результате выполнения процессов с номе­ рами 1, 2, 3. Г1 о о 0^ Г1 1 1 0' 0 1 1 0 D~ = 0 0 0 1 о о 1 ,° 0 1 0 Рис. 4. Граф соответствующий заданным матрицам инциденций Литература 1. Википедия. - Режим доступа: http://ru/wikipedia. org 2. Сети Петри. - Режим доступа: http://www.iacp.dvo.ru 3. Сети Петри. - Режим доступа: http://book.itep.ru/10/ 4. О сетях Петри. - Режим доступа: http://www.textan.org 5. Использование сетей Петри в математическом моделировании. - Режим доступа: http://revolution.aUbest.ru/programming/ 6. Методы оценки деятельности предприятия. - Режим доступа: http://www.interface.ru/ 7. Котов, В.Е. Сети Петри / В.Е. Котов. - М.: Наука, 1984. -160 с. 8. Советов, Б.Я., Моделирование систем / Б.Я. Советов, С.А. Яковлев. - М.: Высшая школа, 2005. -344 с. 40