Сети Петри

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Природа систем, моделируемых сетями Петри

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

2. Подходы к проектированию систем с помощью сетей Петри

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

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

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

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

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

Определение 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). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример 2.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₃}.

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

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

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

сеть петри граф мультимножество

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

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

Пример 2.2. Граф сети Петри определённой в примере 2.1.

Определение 2.2. Граф сети Петри есть двудольный, ориентированный мультиграф G=(V, A), где V={v₁, v₂,…, v_k} - множество вершин, а А={a₁, a₂,…, a_r} - мультимножество направленных дуг, и множество V может быть разбито на два непересекающихся подмножества P и T, V=РИT, PЗT=Ж так, что для любой a_iОA и a_i=(v_j, v_s), (ГДЕ v_j, v_sОV) справедливо либо v_jОP иv_sОT, либо v_jОT и v_sОP.

Замечание 2.1. Согласно определению графа сети Петри в нём не возможны дуги между двумя позициями и между двумя переходами.

Замечание 2.2. Теоретико-множественное задание сети Петри N=(P, T, I, O) однозначно определяет граф сети Петри С=(V, A)

Пример 2.3. Построение графа сети Петри по её теоретико-множественному заданию.

N =(P, T, I, O), P={p₁, p₂, p₃, p₄}, T={t₁, t₂},

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

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

Размещено на Allbest.ru