Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 18
Текст из файла (страница 18)
Если маркировка имеет м в качестве маркировки позиции рь тогда для того, чтобы сеть была сохранякхцей, вес этой пгвиции должен быть равным О. Напомним, что символ е» представляет бесконечное множество значений. Так как все веса неотрнцательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важна), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различакицихся в своей ы-компоненте.
Следовательно, еслн какая-либо маркировка с ненулевым весом равна ге, сеть — несохраняющая. Этн рассуждения относятся к сохранению по отношению к определенному взвешиванию. Сеть Петри является сохраняющей, если она сохраняющая по отношению к некоторому вектору га, га, ) О. Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов ге (если он существует). Заметим прежде всего, что для того, П Точнее, не превышает Ы вЂ” Прая. нерее. Анаеиэ сетей Петри чтобы сеть Петри была сохраняющей по отношению к положительному вектору весов, она должна быть ограниченной.
Как было указано выше„неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. (Если мы хотим допустить нулевые компоненты, нужно просто установить веса всех неограниченных позиций равными нулю и рассматривать после этого только оставшиеся компоненты.) Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее з, н вектор весов ш = (во гр„..., и„).
Для каждой маркировки р[х) дерева достижнмости имеем га, ° р [х), + а~е ° и [х)е + .. + ш„° и [х)„= з. Это равенство определяет для А вершин дерева достижимости совокупность из я линейных уравнений с п + 1 неизвестными. Добавим к ним ограничения: пу~ .'- О, 1 = 1, ..., п, в результате чего определим ограничения для вектора весов. Решение этой системы линейных уравнений — хорошо известная задача, имеющая множество алгоритмов решения.
Можно рассматривать ее как задачу линейного программирования или просто как систему линейных уравнений. В любом случае, если решение : существует, оно будет вычислено. (Решения, получаемые этими методами, будут, как правило, рациональными, не целыми, но веса можно умножить на общее кратноедля получения целого решения.) Если ограничения, накладываемые на веса, являются чрезмерно жесткими и, следовательно, вектора взвешиваний не существует, это будет определено. В любом случае можно определить, является или нет сеть Петри сохраняющей, и если это так, получить вектор весов.
4Л.1.3. Пэирмввемчсть Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемости мы хотим для данной маркировки р' определить„достижима ли маркировка р" ъ р'. Данная задача решается проверкой дерева достижимасти. Строим для начальной маркировки 1е дерево достижимостя. Затем ищем любую вершину х с р[х1 ~ р.'. Если такой вершины не существует, маркировка р' не покрывается никакой достижимой маркировкой; если она найдена, р[х1 дает достижимую аркнровку, покрывакхцую р'. Путь от корня к покрывающей маркировке определяет последовательность переходов, которые приводят из начальной маркировки к покрывающей маркировке, а маркировка, связанная с этой ршиной, определяет покрывающую маркировку. Символ в вновь жен рассматриваться как обозначение бесконечного множества ачений.
Если компонента покрывакицей маркировки — ь, то в от корня к покрывающей маркировке имеется «цикл». Для Глава 4 увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточяое число раз повторить этот цикл. Ре Рпс. 4.18. Сеть Петри. Заметим, что, если несколько компонент покрывакицей маркировки равны со, между изменениями маркировки, получающимися в результате прохождения циклов, возмшкиа взаимосвязь.
Рассмотрим сеть Петри на рис. 4.18 н ее дерево достижимости, показанное на рис. 4.19. Согласно проведенному анализу, маркировки (О, 14, 1, 7) покрывается в множестве достижимости. Путь, порождаияций покрывающую маркировку, состоит из некоторого числа переходов 1„ за которыми следует переход 1„после которого уже следует некоторое число переходов гв. Задача заключается в определении того, сколько раз нужно запустить переходы Г, и ге.
Так как мы хотим иметь в позиции ре 14 фишек, а 4~ намешает в р, одну фишку„попытаемся !0,0, 1,01 ,О,О1 <О,ь,1,О1 10,м, 1,ы) !" 10. св, 1, и1 Рис. 4.19. Дерево достыиимости дап сети Петри, приведенной иа рис. 4.18. Аиаеиа сетей Петри 102 в ыполнить 14 рь Однако нам необходимо выполнить 71„а каждый запуск 1а удаляет из ра фишку, поэтому в действительности необходимо выполнить ие менее 211„затем 1, и после этого не менее 71а (выполнить 1а такое число раз, чтобы в позиции рв осталось не менее 14 фишек).
Карп и Миллер 11481 предложили алгоритм, определяющий минимальное число запусков переходов, необходимых для покрытия данной маркировки. 4.2.4Л. Осраничеинос ь дерева нос иж мое и Как видим, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемостя. К сожалению, в общем случае его нельзя использовать Рис. 4.20. Сеть Петри, дерево досгижимости которой представлено на рис. 4.22. Рь Рис. 4.21. Втораи сеть Петри, дерево достижимости которой представлено на рис.
4.22. Сеть Петри, изображенная на рис. 4.20„имеет в иоаниии Рь ько*четиое число фишек, тогда как ага сеть Петри допускает дли рь произвольную маркировку. 104 Глава 4 для решения задач достижимости и активности, а также для определения возможной пгследовательности запусков. Решение этих задач ограничено существованием символа ы. Символ гв означает потерю информации; конкретные количества фишек отбрасываются, учитывается только существование их большого числа. П,О. 1,О1 !" П,о.о,11 П., 1,о1 11,«,О,О> 11...о, П 1" Рис. 4.22. Дерево дастимимосги дли сетей Петри.
приведенных не рис. 4.20 и 4.21. 11,ы, 1,О1 Рассмотрим, например, сети Петри на рис. 4.20 и 4.2!, дерево достижимости которых изображено на рис. 4.22. Одно дерево достижимости представляет эти две схожие (но различные) сети Петри.
Множества же достижимости их не совпадают. В сети Петри на рис. 4.Ю число фишек в пгпиции р, всегда четио (пока ие будет запущен переход вг), тогда как в сети Петри на рис. 4.21 оно может быть произвольным целым. Символ се не позволяет обнаруживать информацию такого рода, препятствуя использованию дерева достижимости для решения задачи достнжимости. Аналогичная трудность существует и шпя задачи активности На рис.
4.23 и 4.24 приведены две сети Петри, дерево достижимости которых изсбражено на рис. 4.25. Однако сеть иа рис. 4.23 может иметь тупик (иапример, в результате последовательности Гщ ), а сеть Петри с рнс. 4.24 — иет. Дерево дгстижимости же вновь ие может передать различие этих двух случаев. Заметим, что хотя дерево достижимости не обязательно содержит достаточную информацию для решения задач досгижимости и активио-"ии, тем не менее в некоторых случаях это бывает возможно.
Сеть, дерево достижимости которой содержит терминальную вершину (вершину, не имекдцую исходящих дуг), не активна (поскольку некоторая достижимая маркировка не имеет последующих маркировок). Аналогично маркировка р' в задаче достижимости может встретиться в дереве достижимости, и если зто так, то она достижима. Кроме того, если маркировка ие покрывается некого- | рой вершиной дерева достижимостя, то она недостижима.
Аналиэ сетей /уведи Рис. 4.23. Сеть Петри с воаможным тупиком. Рт Рнс. 4.24. Сеть Петри, в которой тупик неаоаможен. Зта сеть активна, коти ее дерево достижнмости (рис. 4.25) идентично дереву достижимостн неактивной сети Петри„приведенной на рис. 4.23. Рис. 4.25. Дерево достижнмостн сетей Петри, изображенных на рис. 4.23 и 4.24. (О.
1. ы) (1„ О,се) 1Об Глава 4 Эти условия достаточны для решения некоторых задач достижнмостн и активности, но они не решают эти задачи в общем. Следовательно, для решения этих двух задач необходимы другие подходы. Уяражяеяяя 1. Постройте деревья Ластнжямастя для маркированных сетей, представленных яз ряс. 4.1 я 4.2. 2. Нзяяшяте программу дяя ЭВМ, осуществляющую аастраеяяе дерева дастяжямаггя яа апясяяяю сети Петра я яачзльяай маркировке.
3. Большинство формулировок алгоритма яастраеяяя дерева дастяжямастя позволяет клзгсвфяцяравагь вершяяу яяк дублирующую только в там случае, если идентичная вершина встретилась яэ пути ат корня к этой вершине. Следавзтельяа, похабные вершины, приязллежзщяэ разным палзереяьям и представляющие одну маркировку, будут продолжать обрабатываться злгаритмам. Зтз мсдяфякзцяяг> увэличяяэег размер поддерева, яа алгоритм закончит рабату, даже если дублярующяе маркировки находятся в там же поддереве, чта и первая маркировка. Дакзжятз, чта разрешение дублярующям маркировкам быть в равных поддеревьях яе вызовет в дереве потерю какойляба мзряяравкя. 4.2.2. Матричные уравнения Второй подход к анализу сетей Петри основан иа матричном представлении сетей Петри.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
