Основные определения. Сети Петри это инструмент для математического моделирования и исследования сложных систем

Введение в сети Петри

Сети Петри

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

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

В одном из подходов к проектированию и анализу систем сети Петри используются, как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху.

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

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

4.2.1. Теоретико-множественное определение сетей Петри

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

Сеть Петри N является четверкой N=(P,Т,I,O), где

P = {p ₁, p ₂,..., p _n } — конечное множество позиций, n ³ 0;

T = {t ₁, t ₂,..., t _m } — конечное множество переходов, m ³ 0;

I: T ® P* — входная функция, сопоставляющая переходу мультимножество его входных позиций;

О: T ® P* - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pÎP называется входом для перехода tÎT, если pÎI(t). Позиция pÎP называется выходом для перехода tÎT, если pÎO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример 4.1. Сеть Петри N =(P,T,I,O),

P={p ₁, p ₂, p ₃ },

T={t ₁, t ₂ },

I(t ₁)={ p ₁, p ₁, p ₂ }, O(t ₁)={p ₃ },

I(t ₂)={ p ₁, p ₂, p ₂ }, O(t ₂)={p ₃ }.

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

4.2.2. Графы сетей Петри.

Наиболее наглядным представлением сети Петри является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

Граф сети Петри обладает двумя типами узлов: кружок m, представляющий позицию сети Петри; и планка ¾, представляющая переход сети Петри. Ориентированные дуги этого графа (стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от входных позиций к переходу и от перехода к выходным позициям. Кратным входным и выходным позициям перехода соответствуют кратные входные и выходные дуги. Граф сети Петри примера 4.1.

Рисунок 4.1.

В графе сети Петри не возможны дуги между двумя позициями и между двумя переходами.

4.2.3. Маркировка сетей Петри.

Маркировка — это размещение по позициям сети Петри фишек, изображаемых на графе сети Петри точками. Фишки используются для определения выполнения сети Петри. Количество фишек в позиции при выполнении сети Петри может изменяться от 0 до бесконечности.

Маркировка m сети Петри N=(P,T,I,О) есть функция, отображающая множество позиций P во множество Nat неотрицательных целых чисел. Маркировка m, может быть также определена как n-вектор m=<m(p₁), m(p ₂),…, m(p _n)>, где n – число позиций в сети Петри и для каждого 1 £ i £ n m(p _i) Î Nat – количество фишек в позиции p _i.

Маркированная сеть Петри N=(P,Т,I,О,m) определяется совокупностью структуры сети Петри (P,T,I,О) и маркировки m. На рисунке 4.2 представлена маркированная сеть Петри m = <1,0,1>.

Рисунок 4.2.

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

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

Сеть Петри выполняется посредством запусков переходов. Запуск перехода управляется фишками в его входных позициях и сопровождается удалением фишек из этих позиций и добавлением новых фишек в его выходные позиции.

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

Пусть функция ^{^} #: P´T ® Nat для произвольных позиции pÎP и перехода tÎТ задает значение ^{^} #(p,t), которое совпадает с кратностью дуги, ведущей из p в t, если такая дуга существует, и с нулем, в противном случае.

Пусть функция # ^{^}: T´P ®Nat для произвольных и перехода tÎT позиции pÎP задает значение # ^{^} (t,p), которое совпадает с кратностью дуги, ведущей из t в p, если такая дуга существует, и с нулем, в противном случае.

Переход tÎT в маркированной сети Петри N=(P,T,1,О,m) разрешен, если для всех p Î I(t) справедливо m(p) ³  ^{^}#(p,t).

Запуск разрешённого перехода tÎT из своей входной позиции pÎI(t) удаляет ^{^} #(p,t) фишек, а в свою выходную позицию p’Î O(t) добавляет # ^{^} (t,p’) фишек.

Сеть Петри до запуска перехода t ₁ (рис. 4.3, а). Сеть Петри после запуска перехода t ₁ (рис. 4.3, б).

Рисунок 4.3. а б

Переход t в маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен и в результате этого запуска образуется новая маркировка m ', определяемая для всех pÎP следующим соотношением:

m'(p)= m(p) – ^{^} #(p,t) + # ^{^} (t,p).

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.

Если запуск произвольного перехода t преобразует маркировку m сети Петри в новую маркировку m', то будем говорить, что m' достижима из m посредством запуска перехода t и обозначать этот факт, как m ®^t m'. Это понятие очевидным образом обобщается для случая последовательности запусков разрешённых переходов. Через R(N,m) обозначим множество всех достижимых маркировок из начальной маркировки m в сети Петри N.

Преобразование маркировки сети Петри изображено на рисунке 4.3. Переход t ₁ преобразует маркировку m =<5,1> в маркировку m’=<2,3>.

Дата добавления: 2014-01-07