Применение сетей Петри в задачах моделирования
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
- в каждый кружочек мы можем поместить точку (или несколько), которая будет отражать, грубо говоря, некоторый потенциал данной позиции. Например, промаркируем сеть рис. 1 следующим образом: (1, 0, 0, 2, 1). Здесь число, стоящее на i-й позиции в множестве обозначает количество точек в pi. Таким образом мы получаем рис. 3.
Рис. 3. Маркировка сети Петри
Следующий пункт - выполнение сети. Для этого надо разобрать исходное понятие - разрешённые переходы. Переход разрешён если каждая из его входных позиций имеет по крайней мере столько фишек, сколько дуг из этой позиции в данный переход. Запуск перехода - перенос фишек через разрешённые переходы из исходных позиций в новые (из исходных позиций фишки удаляются, в новые добавляются). Тогда выполнение сети - процесс запуска переходов. В результате выполнения сети мы получаем новую маркировку `.
Например, на рис. 3 разрешены переходы t1, t3, t4, а переход t2 запрещён. Переход t1 разрешён потому, что на входе у него позиция p1 с одной дугой и имеет одну фишку. Переход t2 запрещён, так как входящие в него позиции p2 и p3 не имеют фишек вообще. Переход t3 разрешён, так как в него входит посредством двух дуг позиция p4, имеющая 2 фишки. Переход t4 разрешён, так как имеет на входе он имеет позицию p5 с одной фишкой и одной дугой.
Рис. 4. Граф сети после запуска в сети рис.3 перехода t4
Рис. 5. Граф сети после запуска в сети рис.4 перехода t1
Можно заметить, что после последовательного выполнения переходов t4 и t1 переход t2 становится разрешённым.
Функция следующего состояния -
для сети Петри с маркировкой и переходом ti определена тогда и только тогда, когда переход ti разрешён и определяется выражением
где - новая маркировка, получаемая при выполнении перехода ti. Кроме того следует ввести понятие непосредственно достижимой маркировки. Маркировка непосредственно достижима из , если существует ti такой, что . Далее следует понятие множества достижимости. Множество достижимости R(C, ) для сети Петри с маркировкой есть наименьшее множестве маркировок, такое, что: а) , б) если и для некоторого tj , то Например, для сети на рис. 6. Множеством достижимости R(C, ) является множество: [2].
Рис. 6. Пример сети Петри для иллюстрации понятия множество достижимости
Так как все процессы моделирования усвоения знаний носят вероятностный характер по своей природе, то целесообразно определить стохастическую сеть Петри. Стохастической сетью Петри называется пара
где описывает структуру сети, а отображение
,
где присваивает каждой позиции вектор распределения вероятности наличия фишек [4]. То есть V - набор векторов, отражающих вероятность нахождения фишки в данной точке. При этом номер компоненты вектора отражает количество фишек, а значение компоненты равняется вероятности нахождения такого количества фишек в этой позиции. Проще говоря, V- двухмерный вектор, первая компонента соответствует номеру позиции, вторая компонента отражает вероятность того, что на данной позиции находится j-е количество фишек. Таким образом, размерность вектора количественно равна произведению количества позиций на максимальное число фишек. Соответственно переход ti в такой сети может быть разрешён тогда и только тогда, когда у вектора вероятностей каждой входной позиции этого перехода имеется компонента, не равная нулю с номером равным или большим числа дуг, соединяющих данную позицию с переходом [4]. Все функции, которые были определены выше для статической сети, теперь носят вероятностный характер. Для описания правил изменения маркировки применяется математический аппарат свёртки матриц Грама.
Пусть сеть имеет вид, представленный на рис. 7:
Рис. 7. Пример сети
И имеет начальную маркировку:
Рис. 8. Маркировка сети рис. 7
Переход t1 разрешён, так как
.
После срабатывания перехода t1 маркировка позиций p1 и p2 имеет вид:
Рис. 9. Маркировка сети после выполнения перехода t1
Определим вектор r:
Рис. 10. Вектор r
Найдём матрицу Грама для векторов и r:
Рис. 11. Матрица Грама
Таким образом, маркировка позиции p3 после перехода будет:
Рис. 12. Маркировка позиции p3 после выполнения перехода t1
Применение сетей Петри к задачам моделирования
По Питерсону [2], простое представление системы основано на основополагающих понятиях: событиях и условиях. События - это действия, которые имеют место быть в системе. Возникновение событий управляет состоянием системы. Состояние системы, в свою очередь, может быть описано множеством условий. В данном случае условия - это предикаты. Таким образом они могут принимать значения истина или ложь.
Так как события являются действиями, то они могут происходить. Чтобы оно произошло должно реализоваться предусловие. Возникновение событий может нарушать предусловия и может привести к выполнению других событий - постусловий.
Логичным примером построения простейшей системы с помощью сетей Петри может быть моделирование простого исполнителя, в данном случае - процессора компьютера. С достаточным уровнем абстракции он может быть описан в виде графа сети Петри на рис. 13.
Рис. 13. Моделирование простой вы