Сети Петри

Содержание

    Введение

    1  Постановка задачи 

    2  Теоретические сведения 

    3  Расчёты  и полученные результаты 

    4  Вывод 

    Заключение 

    Литература 

     Приложение А

 

Введение

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

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

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

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

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

1 Постановка задачи

     Для заданной сети Петри, описывающей распределение  ресурсов, сделать следующее:

     выписать  матричное уравнение смены маркировок;

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

     Входные данные

     На  вход в программу поступают данные, необходимые для формирования некоторой  сети Петри, а именно:

     - общее количество условий (позиций)  сети;

     - общее количество переходов сети;

     - начальная разметка меток по  вершинам сети;

     - связи между условиями и переходами  в сети Петри. 

       
 
 
 
 
 
 

     Выходные  данные

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

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

 

     

     2 Теоретические сведения

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

     Определение. Сетью Петри называется четвёрка элементов 

                                                    C = (P, T, I ,O),                                     (3.2.1)

     где  

                                              P = { p₁, p₂,…,p_n }, n > 0                             (3.2.2) 

     множество позиций (конечное), 

                                             T = { t₁, t₂,…,t_m }, m > 0                                (3.2.3) 

     множество переходов (конечное), 

                                                    I: T → P                                                 (3.2.4) 

     функция входов (отображение множества переходов  во входные позиции),

                                             O: T → P                                                 (3.2.5)

 

     функция выходов (отображение множества  переходов в выходные позиции). 

     Если  p_i I (t_j) , то  p_i – входная позиция j - го перехода, если  p_i I (t_j) , то  p_i – выходная позиция j - го перехода.

     Для наглядного представления сетей  Петри используются графы.

     Граф  сети Петри есть двудольный ориентированный  мультиграф 

                                               G = (V, ),                                                 (3.2.6) 

     где V = P U T , причём  P ∩ T = Ø.

     Исходя  из графического представления сети Петри, её можно определить и так: 

                                            C = (P, T, A),                                                 (3.2.7) 

     где А – матрица инцидентности графа сети.

     Определим понятие маркированной сети Петри  – оно является ключевым для любой  сети.

     Маркировка  μ сети Петри C = (P, T, I, O)  есть функция: 

                                         N = μ(P),  N N,                                             (3.2.8) 

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

                                           μ = {μ₁, μ₂,…, μ_n} ,                                         (3.2.9) 

где  n = │P │, а μ_i N.  Между этими определениями есть связь: 

                                               μ_i = μ (p_i)                                                    (3.2.10) 

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

     Таким образом, маркированная сеть Петри  представляет собой пятёрку элементов:

                                       M = (P, T, I, O, μ).                                              (3.2.11) 

 

     

    3  Расчёты и полученные результаты

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

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

     Исходная  сеть в виде графа:

      
 
 
 
 
 

     Для матричного анализа сети найдём её матрицу изменений. 
 
 

    Матрицу изменений найдём как разность между 

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

                                              μ₀ = (1010)                                           (3.3.4) 
 
 
 
 
 
 

     Составим  дерево покрываемости маркировок сети.

     (1010)

    

    (1001) 

     (1110) 

     (1000)          (1101) 

                        (1210) 

                         (1100)        (1201) 

                                           (1310) 
 
 

    Вывод

 

    Заключение

 

    Список  литературы

1. Котов  В.Е. Сети Петри. – М.: Наука, 1984.

2. Питерсон  Дж. Теория сетей Петри и моделирование систем. – М.: Мир, 1984.

3. Майника  Э. Алгоритмы оптимизации на  сетях и графах /Под ред. Е.К. Масловского – М.: Мир, 1981. – 322 с.