41279

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

Лекция

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

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

Русский

2013-10-23

176.5 KB

14 чел.

Лекция 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


 

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

79166. Сциентистский дискурс философии техники. Техника классической, неклассической и постнеклассической науки. Технознание в концепции критического рационализма 16.66 KB
  Техника классической неклассической и постнеклассической науки. Сциентистский дискурс философии техники Научная техника означала на первых порах лишь применение к технике естествознания. Итак техника стала научной. Когда эту задачу начали выполнять сознательно и возникла новейшая научная техника.
79167. Научная и техническая теория в их соотношении: философско-методологические аспекты. Системно-интегративные тенденции современной технической теории 33.5 KB
  Системноинтегративные тенденции современной технической теории. В структуре развитой естественнонаучной теории наряду с концептуальным и математическим аппаратом важную роль играют теоретические схемы образующие своеобразный внутренний скелет теории. Теоретические схемы выражают особое видение мира под определенным углом зрения заданным в данной теории. Специфика технической теории состоит в том что она ориентирована на конструирование технических систем.
79169. Философско-методологические аспекты технической теории. Дисциплинарная организация технических наук. Философия техники и философия производства в их соотношении 28.5 KB
  Философскометодологические аспекты технической теории. В структуре развитой технической теории наряду с концептуальным и математическим аппаратом важную роль играют теоретические схемы образующие внутренний скелет теории. В технической теории графические изображения играют более существенную роль чем в физической теории. Именно в инженерной деятельности проверяется адекватность теоретических выводов технической теории и черпается новый эмпирический материал.
79170. Научная и техническая революция: общее и особенное. Социокультурные аспекты технической революции 36 KB
  Научная революция связана с перестройкой исследовательских стратегий задаваемых основаниями науки. Пока общие черты системной организации изучаемых объектов учтены в картине мира а методы освоения этих объектов соответствуют сложившимся идеалам и нормам исследования основания науки обеспечивают рост знания. В этой ситуации рост научного знания предполагает перестройку оснований науки. Научная революция может осуществляться: как революция связанная с трансформацией специальной картины мира без существенных изменений идеалов и норм...
79171. Междисциплинарные аспекты развития технознания. Роль техники в формализации и математизации научного знания, гуманитарные приложения технических наук 35.5 KB
  Роль техники в формализации и математизации научного знания гуманитарные приложения технических наук Технознание целостная система знаний о технике технологии и техносфере. В связи с возрастанием сложности проектируемых технических систем появлением новых прикладных дисциплин выработкой системных принципов исследования особое значение приобретает деятельность направленная на организацию и руководство такими видами деятельности как с одной стороны проектирование компонентов конструирование отладка разработка технологии а с другой...
79172. Философско-методологические аспекты соотношения научного и вненаучного. Наука, паранаука и мифология в их соотношении 36.5 KB
  Научное знание основано на принятой в данном обществе концепции рациональности которая находится в соответствии с др. Включает в себя учения или размышления трактаты о явлениях объяснения о которых не является убедительными Лженаучное знания домыслы и рассуждения Квазинаучное знания Осуществляется через методы насилия и принуждения отрицание кибернетики Лысенковчина Антинаучное знание Сознательное искажение действительности Псевдонаучное знание интеллектуальная активность специализирующееся на популярных исследованиях. IV...