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


 

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

12064. НАПРАВЛЕНИЯ СОВЕРШЕНСТВОВАНИЯ ДЕЯТЕЛЬНОСТИ ОАО «СБЕРЕГАТЕЛЬНОГО БАНКА» НА ВАЛЮТНОМ РЫНКЕ 450 KB
  Сделки покупки-продажи иностранной валюты Наличные сделки покупки-продажи today omorrow spot Срочные сделки покупки-продажи forward futures option swap Сделки с разрывами даты валютирования Чистая балансовая позиция Открытая валютна...
12065. ОБЩАЯ ХАРАКТЕРИСТИКА ДЕЯТЕЛЬНОСТИ ЛЕНИНСКОГО ОТДЕЛЕНИЯ № 4158 АК СБ РФ 127.5 KB
  Введение Расчетнокассовый центр одно из центральных звеньев банковской системы. Развитие их деятельности необходимое условие реального создания банковского механизма. Процесс экономических преобразований начался с реформирования банковс...
12066. Основные направления совершенствования денежно-кредитной политики в Российской Федерации 173 KB
  Введение Денежнокредитная политика одно из четырех направлений единой финансовой политики государства обеспечивающих устойчивость экономики и достижение экономического роста. Именно она контролирует инфляцию и рост денежной массы. Наличие в Российской Федерац
12067. Совершенствование системы финансового анализа банковской деятельности 1.49 MB
  Введение Актуальность темы. Банки неотъемлемая составляющая современного денежного хозяйства их деятельность тесно связана с потребностями производства. Банки создают основу рыночного механизма с помощью которого функционирует экономика
12068. Платежный баланс страны (на примере Казахстана) 478.5 KB
  Платежный баланс страны на примере Казахстана Содержание Введение 1 Платежный баланс страны его роль и значение 1.1 Сущность и структура платежного баланса ...
12069. Анализ потребительского кредитования на примере ОАО «Русский Банк Развития» 417 KB
  Введение Актуальность темы дипломного исследования определяется тем что в условиях перехода к рыночной экономике в России существенно изменились состав и структура денежных доходов населения. В частности увеличился временной интервал необходимый для накопления оп
12070. Совершенствование системы управления человеческими ресурсами ОАО АИКБ «Татфондбанк» 379.5 KB
  Введение На рубеже XXI века в экономически развитых странах родилась характерная для новой эпохи постиндустриального развития новая стратегия управления предприятиями краеугольным камнем которой является решающая роль человека в их деятельности. Трудовые ресурсы а...
12071. Проектирование решения по оптимизации кадрового состава АКБ «АЛТАЙ - БАНК» 256 KB
  Введение Актуальность изучения разработки управленческих решений по оптимизации кадрового состава банка состоит в том что одна из основных и наиболее ответственных функций выполняемых руководителем в процессе управления принятие решений. Целью написания наст
12072. Удосконалення формування розподілу прибутку підприємства при зовнішньоекономічній діяльності (за матеріалами ТОВ «Банк Ренесанс Капітал») 481.5 KB
  ДИПЛОМНА РОБОТА на тему: Удосконалення формування розподілу прибутку підприємства при зовнішньоекономічній діяльності за матеріалами ТОВ Банк Ренесанс Капітал ВСТУП Проблематика трансформаційних процесів вимагає наукового розвязання сучасних екон