моделирование СМО ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

Простые сети Петри

Сеть Петри из трех элементов: множество мест , множество переходов и отношение инцидентности.

Простая сеть Петри - это такой набор N = (S,T,F), где

- множество мест;
- множество переходов таких, что .
- отношение инцидентности такое, что
(а) ;
(б)

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

Входное и выходное мультимножества мест и переходов - находится из следующих условий:
Пусть задана сеть .

Если для некоторого перехода имеем , то будем обозначать ;
.

Будем говорить, что - входные, а - выходные места перехода . Таким образом, согласно определению, справедливо . Далее будем говорить, что место инцидентно переходу если или .

Расширим функции и на мультимножества переходов. Пусть есть мультимножество переходов такое, что . Тогда положим

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

Пример. Пример сети

В качестве простого примера расссмотрим сеть , где

1. ;

2. ;

В графической форме сеть представлена на Рис.1. Сеть имеет четыре места и три перехода. Отношение задает дуги сети. Так, например, элемент задает четыре дуги: из в и из в с кратностями 2, из в и из в с единичными кратностями. Для перехода справедливо и . Для места можно вычислить и .

Рис. 1: Пример графа сети Петри

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

Маркированная сеть Петри - это набор

, где

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

Пример. Пример маркированной сети.

На Рис.2 приведен пример маркированной сети. В начальной маркировке место

имеет две метки (токена), место

- одну метку, а места

- ни одной метки, т.е.

Рис. 2: Пример маркированной сети Петри

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

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

Правило срабатывания переходов - это следующий алгоритм
Пусть

маркированная сеть.

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

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

Рис. 3: Новая сеть с маркировкой .

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

T-точка доступа - это точка, определяемая следующими условиями
Пусть задана сеть и некоторый алфавит

. Т-точкой доступа называется набор

, где

- имя (идентификатор) t-точки доступа;
- некоторый алфавит;
- пометочная функция, где . Запись обозначает множество всех конечных и непустых мультимножеств, определённых на множестве .

S-точка доступа - это точка, определяемая следующими условиями
Пусть задана сеть . Тогда s-точкой доступа сети N называется набор

, где

- имя (идентификатор) s-точки доступа;
- множество такое, что .

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

1. Операция слияния переходов - позволяет порождать и описывать синхронизацию параллельных процессов (tmerge);

2. Операция слияния мест - позволяет применять к сетям операции последовательной композиции, выбора, итерации и другие (smerge).

Рис. 4: Пример операции слияния переходов

Рис. 5: Пример операции слияния мест

Приведённые операции имеют следующий смысл:

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

При слиянии переходов – определяется алфавит событий, видимых из t-точки доступа. Каждый переход в сети помечается либо невидимым событием, либо комбинацией событий из алфавита точки доступа. Слияние по переходам производится так, что если при срабатывании одной сети возникает некоторая комбинация событий, то эта же комбинация событий происходит во второй сети.

моделирование СМО ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

Знаете ли Вы, что вакроэкономическая модель - это экономико-математическая модель, в которой не выделяются переменные, описывающие отдельных хозяйствующих субъектов (предприятия, отрасли), составляющих моделируемую хозяйственную систему, и которая отражает только связи, присущие этой системе как целому.

НОВОСТИ ФОРУМА

Рыцари теории эфира