41279

Сетевые модели (N-схемы). Основные соотношения. Возможные приложения N-схем

Лекция

Математика и математический анализ

Сетевые модели Nсхемы. Сетевые модели Nсхемы Основные соотношения Для формального описания структуры и взаимодействия параллельных систем и процессов а также анализа причинноследственных связей в сложных системах используются сети Петри англ. Граф Nсхемы имеет два типа узлов: позиции и переходы изображаемые 0 и 1 соответственно. Граф Nсхемы является мультиграфом так как он допускает существование кратных дуг от одной вершины к другой.

Русский

2013-10-23

176.5 KB

17 чел.

Лекция 9. Сетевые модели (N-схемы). Основные соотношения. Возможные приложения N-схем

2.6. Сетевые модели (N-схемы)

Основные соотношения

Для формального описания структуры и взаимодействия параллельных систем и процессов, а также анализа причинно-следственных связей в сложных системах используются сети Петри (англ. Petri Nets), называемые N-схемами.

Формально N-схема задается четверкой вида

N = <B, D, I, O>,

где В – конечное множество символов, называемых позициями, B  O;
D
– конечное множество символов, называемых переходами  O,
  O; I – входная функция (прямая функция инцидентности)
I: B  D  0, 1; О – выходная функция (обратная функция инцидентности),
О: B  D  0, 1. Таким образом входная функция I отображает переход dj в множество входных позиций bj  I(dj), а выходная функция O отображает переход dj в множество выходных позиций bj  О(dj). Для каждого перехода
dj  D можно определить множество входных позиций перехода I(dj) и выходных позиций перехода O(dj) как

I(dj) = { bi  B  I(bi, dj) = 1 },

O(dj) = { bi  B  O(dj, bi) = 1 },

i = ;  j = ; n = | B |, m = | D |.

Аналогично для каждой позиции bi  B вводятся определения множеств входных переходов позиции I(bi) и выходных переходов
позиции
O(bi):

I(bi) = { dj  D  I(dj, bi,) = 1 },

O(bi) = { dj  D  O(bi, dj) = 1 }.

Графически N-схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 2.7). Граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.

Рис. 2.7. Графическое изображение N-схемы

Пример 2.2. Представим формально N-схему, показанную в виде графа на рис. 2.7:

N = <B, D, I, O>,

B = <b1, b2, b3, b4, b5>,

D = <d1, d2, d3, d4>.

Входные позиции перехода        Выходные позиции перехода

I(d1)={b1},    O(d1)={b2, b3, b5},

I(d2)={b2, b3, b5},   O(d2)={b5},

I(d3)={b3},    O(d3)={b4},

I(d4)={b4}.    O(d4)={b2, b3}.

Возможные приложения N-схем

Приведенное представление N-схемы может использоваться только как отражение статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) позиций М: В  {0, 1, 2, …}. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин позиций соответствующего числа точек (когда количество точек велико, ставят цифры).

Маркированная   (размеченная)  N-схема   может   быть  описана в виде NМ = <B, D, I, O, M>.

Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как М0: В  {0, 1, 2, …}.
Смена разметок происходит в результате срабатывания одного из переходов
dj  D сети. Необходимым условием срабатывания перехода dj
является
bi  I(dj), {M(bi)  1}, где M{bi} – позиции bi. Переход dj,
для которого выполняется указанное условие, определяется как
находящийся в состоянии готовности к срабатыванию или как возбужденный переход.

Срабатывание перехода dj изменяет разметку сети
M(b) = (M(b1), M(b2), …, M(bn))2 на разметку M(b) по следующему правилу:

M(b) = M(b) – I(dj) + O(dj),

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

Пример 2.3. Рассмотрим размеченную N-схему с начальной разметкой
M0 = {1, 0, 0, 0, 1, 0, 1}, которая приведена на рис. 2.8, а. При такой начальной разметке N-схемы единственным готовым к срабатыванию является переход d2, срабатывание которого ведет к смене разметки на M1, где M1 = {0, 1, 1, 0, 1, 0, 1} (рис. 2.8, б). При разметке M1 возможно срабатывание переходов d1 d3 и d5. В зависимости от того, какой переход сработал первым, получается одна из трех возможных новых маркировок (рис. 2.8, в, г, д). Функционирование N-схемы продолжается до тех пор, пока существует хотя бы один возможный переход.

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

а

Рис.2.8, а. Пример функционирования размеченной N-схемы

б

Рис.2.8, б. Пример функционирования размеченной N-схемы

в

Рис.2.8, в. Пример функционирования размеченной N-схемы

г

Рис.2.8, г. Пример функционирования размеченной N-схемы

д

Рис.2.8, д. Пример функционирования размеченной N-схемы

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. М. : Высш. шк., 2001. 343 с.

2. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. 2-е изд. М.: Высшая школа, 1998. 319 с.

3. Тарасик В.П. Математическое моделирование технических систем: учеб. для вузов / В.П. Тарасик. М.: Наука, 1997. 600 с.

4. Введение в математическое моделирование: учеб. пособие для вузов/ под ред. П.В.Тарасова. М.: Интермет Инжиниринг, 2000. 200 с.

5. Ивченко Г.И. Математическая статистика: учебное пособие для втузов / Г.И. Ивченко, Ю.И. Медведев. М.: Высш. шк., 1984. 248 с.

6. Альянах И.Н. Моделирование вычислительных систем / И.Н. Альянах. Л.: Машиностроение, 1988. 233 с.

7. Шеннон Р. Имитационное моделирование систем – искусство и наука / Р. Шеннон. М.: Мир, 1978. 308 с.

4

b1

b5

d2

d1

b2

b3

d4

d3

b4

b1

b2

b4

b5

b3

b7

b6

d4

d2

d1

d5

d6

d3

d4

d3

d6

d5

d1

d2

b6

b7

b3

b5

b4

b2

b1

d4

d3

d6

d5

d1

d2

b6

b7

b3

b5

b4

b2

b1

d4

d3

d6

d5

d1

d2

b6

b7

b3

b5

b4

b2

b1

d4

d3

d6

d5

d1

d2

b6

b7

b3

b5

b4

b2

b1


 

А также другие работы, которые могут Вас заинтересовать

74846. Екатерина II. «Всякая всячина». Н.И. Новиков, его литературные труды и сатирические журналы. Сатира на лица и на пороки 16.52 KB
  Новиков его литературные труды и сатирические журналы. Предполагают что свои материалы в журнал посылали Фонвизин князь Щербатов и даже Новиков. Новикова. В Трутне под подписью Правдолюбов Новиков упрекает Екатерину.
74847. Классицизм как литературное направление. А.Д. Кантемир, В.К. Тредьяковский, М.В. Ломоносов 15.87 KB
  Сын астраханского священника он подобно Ломоносову охваченный жаждой знаний ушел из родительского дома учился в Славяно-греколатинской академии а затем за границей в Сорбонне. Одновременно с Ломоносовым был удостоен звания профессора Академии наук. Как поэта его при жизни затмили Сумароков и Ломоносов.
74848. Творчество Д.И. Фонвизина. «Недоросль» 14.62 KB
  Фонвизина Недоросль создателя подлинно самобытной национальной комедии который заложил внутри этой системы основы критического реализма. В комедии сочетаются яркие и правдивые сцены из жизни поместного дворянства и страстная проповедь просветительских идей об обязанностях правительства прямого честного гражданина. Хотя в основе сюжета лежит любовный конфликт стремление героев жениться на богатой наследнице все же основной конфликт комедии намного глубже. Другая проблема комедии истинное и ложное воспитание.
74849. А.Н. Радищев. Путешествие из Петербурга в Москву 14.28 KB
  Наиболее известное произведение Александра Радищева. Опубликовано в Российской империи в мае 1790 года. Работа печаталась без указания автора в домашней типографии Радищева. Роман представляет собой собрание разрозненных фрагментов, связанных между собой названиями городов и деревень, мимо которых следует путешественник. Автор рисует картины современной ему России, уделяя основное внимание положению крепостных крестьян...
74850. Просветительство и сентиментализм конца ХVIII века. Н.М. Карамзин. Его проза и поэзия 14.72 KB
  Сентиментализм Карамзина оказал большое влияние на развитие русской литературы. Поэзия Карамзина развившаяся в русле европейского сентиментализма кардинально отличалась от традиционной поэзии его времени воспитанной на одах Ломоносова и Державина...
74851. И.А. Крылов – баснописец. Традиции сатирической литературы XVIII века. Своеобразие авторской позиции, проблема народности басен 15.46 KB
  Крылов баснописец. Сюжеты ряда басен Крылова восходят к басням Лафонтена который в свою очередь заимствовал их у Эзопа Федра и Бабрия хотя немало и оригинальных сюжетов. Многие выражения из басен Крылова стали крылатыми. Жанр басни под пером Крылова заметно изменился.
74852. Основные течения в романтизме. Элегический романтизм В.А. Жуковского и К.Н. Батюшкова 15.87 KB
  Романтики выдвигали принцип творчества, основанного на вдохновении, утверждали приоритет гения в искусстве. В романтическом искусстве больше всего ценилась свободная поэтическая индивидуальность. Романтизм – сложное историко-литературное явление: Жуковский понимал романтизм иначе, чем Рылеев. Отрицая жизнь в тех формах, в которых она существовала, романтики либо уходили в себя, творили в себе свой «антимир», мир мечты и поэзии (романтизм Жуковского);
74853. Заговоры (виды, композиция, особенности языка) 60.35 KB
  Мифологическая школа –Заговор первоначально молитвы, обращенные к божествам. С мифами их сближает отождествление природного и человеческого, обращение к мифологическим персонажам (природным стихиям, космическим объектам, мифическим существам). Заговоры испытали значительное влияние христианства: как обряда (крестное знамение, молитва), так и книжности (например, часто упоминаются христианские святые).
74854. Постоянный эпитет, сравнение, параллелизм 67.48 KB
  Параллелизм: не отождествление человеческой жизни с природною и не сравнение а сопоставление по признаку действия движения: дерево хилится девушка кланяется. Параллелизм основан на сопоставлении субъекта и объекта по категории движения. Неорганический недвижущийся мирвошел в лоно параллелизмов:он также жил.