Расширенная сеть петри позволяет снять ограничения

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.

Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

• множество позиций P,
• множество переходов T,
• входная функция I,
• выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j) , называемых входными позициями перехода . Выходная функция O отображает переход p_i в множество позиций O(p_i) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p₂, . p_i, p_n> — конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом p_i , i=1, . n, а произвольный элемент T — символом t_j, j=1, . m.

Правила выполнения сетей Петри Править

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

Переход запускается удалением разрешающих фишек, из всех его входных позиций (количество удаленных фишек для каждой позиции соответствует числу дуг, идущих из этой позиции в переход), с последующим помещением фишек в каждую из его выходных позиций (количество помещаемых фишек в позицию соответствует количеству дуг входящих в данную позицию из перехода).

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $

Расширенная сеть петри позволяет снять ограничения

На этом шаге мы кратко опишем некоторые модификации сетей Петри .

Сети Петри могут быть использованы для моделирования самых различных систем, в том числе аппаратного и программного обеспечения ЭВМ. Очевидно, что сети Петри могут адекватно моделировать разные системы, однако могут существовать такие системы, которые нельзя должным образом моделировать сетями Петри, т. е. мощность моделирования сетей Петри имеет пределы.

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

Рис.1. Виды расширенных сетей Петри

Рассмотрим подробнее некоторые типы сетей Петри.

Ингибиторная сеть представляет собой сеть Петри, дополненную специальной функцией инцидентности I IN : Р х Т -> <0, 1>, которая вводит ингибиторные (запрещающие) дуги для тех пар (p, t) , для которых I IN (Р, Т) = 1 . Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчивающимися не стрелками, а маленькими кружочками.

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

Например, используя ингибиторную дугу, можно промоделировать оператор условного вычитания (если x i <>0 , то x i = x i — 1 ) и получить фрагмент ингибиторной сети (рисунок 2).

Рис.2. Фрагмент ингибиторной дуги

Ингибиторные сети используются для разработки диагностических моделей средств вычислительной техники.

В приоритетных сетях вводят приоритеты срабатывания переходов. Если несколько переходов являются разрешенными, то срабатывает тот из них, который имеет наивысший приоритет. Такие сети используются для моделирования систем на уровне задач.

В структурированных сетях некоторые из переходов являются сложными. При их срабатывании запускается сеть другого уровня иерархии (рисунок 3).

Рис.3. Структурированная сеть Петри

Срабатывание t 2 приводит к запуску сети другого уровня. Выполнение сложного перехода заключается в помещении во входную позицию по сети фишки. После выполнения сети фишка появляется в ее выходной позиции, затем формируются фишки в выходных позициях сложного перехода.

Преобразование сети к виду, имеющему один вход и один выход, всегда возможно. Такие сети используются для моделирования модульных вычислительных систем.

В цветных сетях вводится понятие цвета для фишек. В общем случае может быть n цветов. В вычислительной технике используются трехцветные сети ( n = 3 ). Такие сети используются для моделирования аппаратных средств.

В сетях с изменяемой структурой кратность ребер не является постоянной.

В самомодифицируемых сетях кратность ребра может задаваться либо натуральным числом N , либо определяться количеством фишек, находящихся во входных позициях некоторого перехода.

Качественными характеристиками могут быть: отсутствие зацикливаний в системе, достижение некоторого состояния системы (например, конечного).

Количественными характеристиками являются: время работы некоторого маршрута в программе, время прохождения сигнала в схеме и т. д.

Во временных сетях переходам ставится в соответствие их времена срабатывания, либо позициям ставится в соответствие времена нахождения фишек в позициях.

В стохастических сетях указанные характеристики являются вероятностными, т. е. вводится функция плотности вероятности времен срабатывания переходов или времен нахождения фишек в позициях.

Предикатные сети — это сети с логическим описанием состояния системы.

Со следующего шага мы начнем рассматривать созданное приложение «Редактор сетей Петри» для моделирования систем .

Presentation1.ppt — МОДЕЛИРОВАНИЕ.

This preview shows page 1 — 5 out of 21 pages.

You’ve reached the end of your free preview.

Want to read all 21 pages?

• TERM Spring ’19
• PROFESSOR Smirnov
• TAGS Simulation, сетей Петри, логистических систем, ФИРМЫ (ПРЕДПРИЯТИЯ

Share this link with a friend:

Students who viewed this also studied

• статья(повышение эффективности складских процессов).doc
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

статья(повышение эффективности складских процессов).doc

• Список связей описание связей между элементарными сетями а также экземплярами
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

• определенные моменты времени Множество самостоятельных агентов с определенными
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

• типа источника заявок стохастическая сеть может быть замкнутой и открытой В
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

• статья (Особенности методики сопровождения автоматизированных производственных логистических процесс
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

статья (Особенности методики сопровождения автоматизированных производственных логистических процесс

• Все эти параметры объединены блоком NET инициализациясети NET имясети телосети
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• IPOVS 1 — Spring 2019

Study on the go

Other Related Materials

• prefetching ещё до первого к нему обращения Многие архитектуры имеют для этого
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• MATH 100 — Spring 2010

• для своих практических целей Социологические понятия следовательно представляют
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• SOCIOLOGY 1 — Summer 2016

• Дарков. Шапошников. Строительная механика. 1986
• MOSCOW STATE TECHNOLOGICAL UNIVERSITY STANKIN
• MATERIALS 123 — Winter 2016

Дарков. Шапошников. Строительная механика. 1986

What students are saying

As a current student on this bumpy collegiate pathway, I stumbled upon Course Hero, where I can find study resources for nearly all my courses, get online help from tutors 24/7, and even share my old projects, papers, and lecture notes with other students.

Kiran Temple University Fox School of Business ‘17, Course Hero Intern

I cannot even describe how much Course Hero helped me this summer. It’s truly become something I can always rely on and help me. In the end, I was not only able to survive summer classes, but I was able to thrive thanks to Course Hero.

Dana University of Pennsylvania ‘17, Course Hero Intern

The ability to access any university’s resources through Course Hero proved invaluable in my case. I was behind on Tulane coursework and actually used UCLA’s materials to help me move forward and get everything together on time.

Jill Tulane University ‘16, Course Hero Intern