textbook, страница 6

Начальной маркировке соответствует корневая вершина. Если из вершины µ' в вершину µ" ведет дуга, то она взвешена переходом,переводящим сеть Петри из маркировки µ' в µ". Тупиковым маркировкамсоответствуют висячие вершины. Необходимо отметить, что в таком определении дерево достижимости в общем случае является бесконечным, поскольку даже сеть с конечным множеством достижимости (рис. 2.13, а) может иметь бесконечное дерево достижимости (рис. 2.13, б).P1(1, 0)t2(0, 1)t2t1t1(1, 0)t2P2абРис. 2.13. Сеть с конечным множеством достижимости (а)и бесконечным деревом достижимости (б)38Для анализируемой сети (см. рис. 2.12) дерево достижимости представлено на рис. 2.14.Всякий путь от корня в дереве соответствует допустимой последовательности переходов.

Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера, т.е.найти средства, которые ограничивают введение новых маркировок на каждом шаге построения. В этом смысле выделяют пассивные (терминальные),дублирующие вершины и вершины с расширенной маркировкой.(1, 0, 0)t1(1, 3, 0)t1t1t2(1, 1, 0)(0, 1, 1)t1t2t3(1, 2, 0)(0, 2, 1)(0, 0, 1)t2t3(0, 3, 1)(0, 1, 1)ДублирующаяПассивная(тупик)(1, ω, 0)РасширеннаяРис. 2.14.

Дерево достижимостиПассивная (или терминальная) вершина – это маркировка, в которойнет разрешенных переходов. Для анализируемого примера сети это маркировка (0, 0, 1) (см. рис. 2.12). Дублирующая вершина – это вершина с маркировкой, которая уже ранее встречалась в этом дереве достижимости. Припоявлении дублирующей вершины нет необходимости производить из неедальнейшие построения, поскольку это приведет к появлению поддерева,полученного из места первого появления дублирующей вершины. В рассматриваемом примере маркировка (0, 1, 1), получившаяся после выполнения t1, t2, t3 не будет порождать какие-либо новые вершины, поскольку она39ранее была получена в дереве после выполнения t2 из начальной маркировки.Расширенная маркировка вводится, исходя из следующих соображений.Пусть существует последовательность запуска переходов σ, переводящаямаркировку µ в µ', причем маркировка µ' совпадает с µ за исключением того,что имеет дополнительные метки в некоторых позициях, т.е.µ' = µ + (µ' – µ) и µ' – µ > 0.Поскольку на запуск переходов лишние метки повлиять не могут, топоследовательность σ можно запустить еще раз из µ' и получить µ", причемµ'' = µ' + (µ' – µ) = µ + 2(µ' – µ).В общем случае можно запустить последовательность переходов σ n рази получитьµ''' = µ' + n(µ' – µ).Поскольку число n можно выбрать сколь угодно большим, в некоторыхпозициях сети разметка будет неограниченно возрастать.

При построениидерева достижимости этот фрагмент дерева можно ограничить, вводя символ ω, который означает «бесконечность» в соответствующей позиции разметки. Для рассматриваемого примера (см. рис. 2.14) последовательное срабатывание t1 приводит к нарастанию разметки в позиции р2, что приводит квведению расширенной маркировки (1, ω, 0).Кроме того, различают граничные вершины и внутренние. Граничнымивершинами называют вершины дерева достижимости, которые еще не обработаны алгоритмом построения дерева достижимости. В результате реализации алгоритма построения дерева достижимости граничные вершины превращаются в терминальные, дублирующие или внутренние.Наличие свойств безопасности и ограниченности легко проверяется издерева достижимости.

Сеть Петри ограничена тогда и только тогда, когдасимвол ω отсутствует в дереве достижимости. Если символа ω нет, то можно определить границу числа меток в позициях путем перебора вершин де40рева достижимости. Если в дереве достижимости присутствует символ ω, тодля того, чтобы сеть была сохраняющей по отношению к некоторому вектору взвешивания, необходимо, чтобы вес ωi позиции рi , имеющей в некоторой маркировке ω, был нулевым.2.5.2. Метод матричных уравненийЭтот подход основан на матричном представлении сетей Петри. Входная и выходная функции представляются матрицами D– и D+ соответственно. Элементы матриц определяются следующим образом:D– [i, j] = # (pi, I(tj));D+ [i, j] = # (pi, O(tj));i = 1, n;j = 1, m.Матричная форма представления сети C = 〈P, T, D–, D+〉 эквивалентнастандартной, но позволяет дать определения в терминах векторов и матриц.Пусть е[j] – m-вектор-столбец, содержащий все нули, за исключением jй позиции.

Переход tj, таким образом, может быть представлен векторомe[j].Переход tj в маркировке µ разрешен, если µ ≥ D –e[j], а результат запуска перехода tj в маркировке µ равенσ(µ, tj) = µ'= µ – D–e[j] + D+e[j] = µ + (D+ – D–)·e[j],где (D+ – D–) = D – составная матрица изменений, элементы которой могутбыть отрицательными.Тогда для последовательности запусков переходов σ = tj1, tj2, ..., tjk имеемδ(µ, σ) = µ + De[j1] + De[j2] + ... + De[jk] == µ + D﴾e[j1] + e[j2] + ... + e[jk]﴿ = µ + D·ƒ(σ),где ƒ(σ) = ﴾e[j1] + e[j2] + ... + e[jk]﴿ – вектор запусков последовательности σ,каждый элемент которого показывает число запусков соответствующего пе-41рехода.

Все элементы этого вектора неотрицательны.Для того чтобы показать сохранение сети, необходимо найти (ненулевой) вектор взвешивания ω, размерностью (1 × n), для которого взвешеннаясумма по всем маркировкам постоянна, т.е. ωµ = ωµ'.Поскольку маркировка µ' достижима, существует последовательностьзапусков переходов σ, которая переводит сеть из µ в µ':µ' = µ + Df(σ).Следовательно,ωµ = ωµ' = ω﴾µ + Df(σ)﴿ = ωµ + ωDf(σ).Отсюда следует, что ωDf(σ) = 0.

Поскольку это должно быть справедливо для всех f(σ), то ωD = 0.Таким образом, сеть Петри является сохраняющей тогда и только тогда,когда сущeствует такой вектор ω, что ωD = 0. Если ω = (1, 1, ..., 1), то этоусловие формулируется следующим образом: сумма элементов каждогостолбца матрицы D должна быть нулевой.Матричная теория сетей Петри является инструментом для решенияпроблемы достижимости.

Предположим, что маркировка µ' достижима измаркировки µ. Тогда существует последовательность запусков переходов σ,которая приводит из µ к µ'. Это означает, что f(σ) является неотрицательнымцелым решением следующего матричного уравнения для х:µ' = µ+Dx.(2.1)Если µ' достижима из µ, тогда уравнение имеет решение в неотрицательных целых, если уравнение не имеет решения, то µ' недостижима из µ.Наличие решения уравнения (2.1) является необходимым, но не достаточным для достижимости.

Необходимо проверить, существует ли разрешеннаяпоследовательность запуска переходов, соответствующая вектору разметкиµ'.Рассмотрим сеть, представленную на рис. 2.15.42P2t2P1P4t1t3P3Рис. 2.15. Пример для иллюстрации матричного представления сетейПетриМатрицы D–, D+, D для этой сети имеют следующий вид:⎡1⎢1−D =⎢⎢1⎢⎣00 0⎤⎡1⎥⎢00 0⎥ ; D+ = ⎢0 1⎥⎢0⎥⎢1 0⎦⎣00 0⎤00⎤⎡ 0⎥⎢−1 22 00⎥⎥; D=⎢⎥.1 0⎥1 − 1⎥⎢− 1⎥⎢⎥0 1⎦1⎦⎣ 0 −1В начальной маркировке µ = (1, 0, 1, 0)Т переход t3 разрешен и приводитк маркировке:00⎤⎡1 ⎤ ⎡ 0⎡1 ⎤ ⎡ 0 ⎤ ⎡1 ⎤⎡ 0⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ 0⎥ ⎢ − 1 2⎥000 ⎢ ⎥ 0⎥× 0 = ⎢ ⎥+ ⎢ ⎥ = ⎢ ⎥.µ' = ⎢ ⎥ + ⎢1 − 1⎥ ⎢ ⎥ ⎢1⎥ ⎢ − 1⎥ ⎢0⎥⎢1 ⎥ ⎢ − 1⎢ ⎥ ⎢⎥ ⎢⎣1⎥⎦ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥−0110⎣ ⎦ ⎣⎦⎣0⎦ ⎣ 1⎦ ⎣1⎦Последовательность σ = t3, t2, t3, t2, t1 представляется вектором запусковf(σ) = (1, 2, 2)T и приводит к маркировке4300⎤⎡1 ⎤ ⎡ 0⎡1 ⎤ ⎡ 0⎤ ⎡1 ⎤1⎤⎡⎢0⎥ ⎢ − 1 20⎥ ⎢ ⎥ ⎢0⎥ ⎢ 3⎥ ⎢3⎥⎢⎥⎢⎥× 2 = ⎢ ⎥+ ⎢ ⎥ = ⎢ ⎥.+µ' =1 − 1⎥ ⎢ ⎥ ⎢1⎥ ⎢ − 1⎥ ⎢0⎥⎢1 ⎥ ⎢ − 1⎢ ⎥ ⎢⎥ ⎢ 2⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥1⎦ ⎣ ⎦ ⎣0⎦ ⎣ 0⎦ ⎣0⎦⎣0⎦ ⎣ 0 − 1Для определения того, является ли маркировка µ' = (1, 8, 0, 1)T достижимой из маркировки µ = (1, 0, 1, 0), имеем линейные уравнения00⎤00⎤⎡ 0⎡ 0⎤⎡1⎤ ⎡1⎤ ⎡ 0⎢8⎥ ⎢0⎥ ⎢ − 1 2⎥⎢⎥⎢ 8⎥−1 200⎢ ⎥=⎢ ⎥+⎢⎥ ⋅ х, или ⎢⎥⋅х = ⎢ ⎥.1 − 1⎥1 − 1⎥⎢0⎥ ⎢1⎥ ⎢ − 1⎢− 1⎢ − 1⎥⎢ ⎥ ⎢ ⎥ ⎢⎥⎢⎥⎢ ⎥1⎦1⎦⎣1⎦ ⎣0⎦ ⎣ 0 − 1⎣ 0 −1⎣ 1⎦Система этих уравнений имеет решение хT = (0, 4, 5).

Это соответствуетразрешенной последовательностиσ = t3, t2, t3, t2, t3, t2, t3, t2, t3.Матричный подход к анализу сетей очень перспективен, но имеет и ряднедостатков. Матрица D сама по себе не полностью отражает структуру сети, так как встречные дуги между переходом и позицией (как, например,между р1 и t1 (см. рис. 2.15) взаимно уничтожаются в матрице D. Кроме того, в векторе запуска переходов f(σ) отсутствует информация о последовательности запуска переходов. Это приводит к тому, что одному и тому жерешению уравнения (2.1) можно поставить в соответствие несколько последовательностей запуска переходов.В качестве положительных свойств матричного метода анализа следуетотметить компактность представления информации и высокую степеньформализации, облегчающую применение средств вычислительной техники.442.6. Задание1.

Для указанного варианта построить модель ГПС сборочного типа в виде сети Петри. Получить матричное представление. Для описанияфункционирования использовать цветные маркеры.2. Произвести имитационное моделирование всей ГПС или ее части (поуказанию преподавателя) на ЭВМ.3. Построить дерево достижимости.4. Проанализировать свойства сети, доказать правильность реализации всети алгоритма функционирования моделируемого участка.Описание объекта моделированияОбъектом моделирования является участок ГПС сборочного типа, состоящий из сборочных центров, конвейеров для транспортировки кассет сосборочным материалом и спутников с объектами сборки, а также склада длякассет.

Общая структура участка ГПС показана на рис. 2.16.Спутниковый конвейерСЦ1СкладСЦ2СЦnКассетный конвейерРис. 2.16. Схема участка ГПС сборочного типаСборочные центры (СЦ) могут быть настроены на одну или несколькосборочных операций. По кассетному конвейеру транспортируются кассетыразличных типов, адресуемые определенным сборочным центром.Варианты заданий приведены в табл.