41279

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

Лекция

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

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

Русский

2013-10-23

176.5 KB

9 чел.

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


 

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

66493. МЕЖБАНКОВСКИЙ КЛИРИНГ 556.5 KB
  В соответствии с утвержденными планами модернизации платежной системы Республики Беларусь РБ в ближайшее время намечено внедрить пусковой комплекс нового проекта межбанковских расчетов в составе: системы расчетов по срочным и крупным платежам на валовой основе...
66494. ОСОБЕННОСТИ РАЗВИТИЯ ВНИМАНИЯ У ДЕТЕЙ ДОШКОЛЬНОГО ВОЗРАСТА 315.5 KB
  Внимание среди познавательных процессов занимает особенное место, поскольку оно не имеет собственного содержания, а обслуживает другие психические процессы. Внимание во многом определяет успешность их функционирования. От уровня развития свойств внимания (устойчивости, концентрации, объёма, распределения, переключения)
66497. Механизмы сетевого взаимодействия 39.5 KB
  Цель работы – изучить программный интерфейс сетевых сокетов, получить навыки организации взаимодействия программ при помощи протоколов Internet и разработки прикладных сетевых сервисов.
66499. Автоматическое управление в функции времени. Реле времени 248.5 KB
  Наряду с автоматизацией технологических процессов реле времени широко применяют для автоматизации процесса пуска мощных электродвигателей посредством пусковых реостатов в металлорежущих станках бытовых машинах и пр.
66501. Программирование и использование программных модулей 83 KB
  Разработать программный модуль (ПМ), в котором содержится не менее 4 подпрограмм (таблица 1) Задание 2 Составить Паскаль-программу, в которой используется не менее 4 подпрограмм программного модуля, разработанного в задании 1. Отчет должен содержать: -название лабораторной работы и номер варианта...