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


 

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

79751. Расчеты с контрагентами 65.5 KB
  Одним из существенных моментов является соблюдение порядка ведения журналов учета счетовфактур при расчетах по НДС. Счетфактура представляется поставщиком покупателю и дает право на зачет сумм НДС Д68К19. Второй экземпляр счета фактуры остается у поставщика для отражения в книге продаж и начисления НДС при реализации товаров Д46К68. В счетефактуры должны быть указаны: порядковый номер счетафактуры; наименование и регистрационный номер поставщика товаров ИНН; наименование и регистрационный номер получателя товара ИНН;...
79752. ВНУТРЕННЯЯ СТРУКТУРА ИННОВАЦИОННЫХ ПРОЦЕССОВ 122.5 KB
  Целевые качественные или количественные изменения в выборе и использовании материалов сырья информации оборудования информации работников и других ресурсов Целевые качественны или количественные изменения в результатах производственно хозяйственной деятельности..
79753. МИРОВОЙ ОПЫТ И СХЕМЫ ФИНАНСИРОВАНИЯ ИННОВАЦИЙ 236.5 KB
  Если правительство заинтересовано в реализации инновационного проекта оно может действовать в следующих направлениях: Национализация перспективного проекта когда сотрудники инновационной фирмы получают возможность на стабильных рабочих местах не опасаясь неожиданностей но под постоянным контролем; Поддержка проекта когда создается микроструктура в государственном аппарате управления призванная шефствовать над проектом. Фирма получает при этом помощь не теряя самостоятельности; Пособие государства когда выделяется единовременная...
79754. Финансирование инвестиций. Оценка потребности в финансировании 72 KB
  Оценка потребности в финансировании Исходным пунктом для организации финансирования является расчет потребности в средствах необходимых для реализации проекта. Он производится на основе графика выполнения работ что вопервых обеспечивает привязку ко времени а вовторых позволяет увязать объемы финансирования и направления расходования средств. Итогом работы является таблица в которой потребность в средствах расписывается по месяцам. В этом случае более удобна следующая форма представления расчета: Виды работ Месяцы выполнения...
79755. Разработка инвестиционных проектов. Этапы инвестиционного проектирования 472.5 KB
  Инвестиционный проект это план программа хозяйственного мероприятия или предпринимательского проекта реализация которых требует привлечения инвестиций. Структура затрат на реализацию проекта а также доходов получаемых в результате инвестиций традиционно отлична для каждой из выделенных стадий. Определение целей и класса инвестиций 1. Метод расчета рентабельности инвестиций 2.
79756. СУЩНОСТЬ ИННОВАЦИОННЫХ ПРОЦЕССОВ И КЛАССИФИКАЦИОННЫЕ ПОДХОДЫ К ИХ ГРУППИРОВКЕ 308 KB
  Изменения в организации производства и его материально-техническом обеспечении. Речь может идти также о качественных или количественных изменениях как с положительными так и с отрицательными социально-экономическими последствиями. Большинство западных авторов обычно подчеркивают необходимость практической реализации изменения. Это могут быть количественные или качественные изменения которые касаются той или иной сферы деятельности предприятия.
79757. ИНВЕСТИЦИОННЫЙ ПРОЦЕСС И МИССИЯ КОМПАНИИ 63.5 KB
  Среди обширного спектра факторов влияющих на выбор миссии компании есть чрезвычайно важный с точки зрения долгосрочной перспективы безкризисного существования фирмы это фактор адекватности инвестирования выдвинутым критериям. Акцент на исследовании этого вопроса делается по двум основным причинам: определяющей роли которая принадлежит инвестиционному процессу в выборе линии поведения фирмы особенно на долгосрочном горизонте ее роста и инноваций продукта. Принятие решений в этой области...
79758. ИНВЕСТИЦИИ: ПОНЯТИЕ, КЛАССИФИКАЦИЯ. РОЛЬ ИНВЕСТИЦИЙ 151.5 KB
  Одной из важнейших сфер деятельности любой фирмы являются инвестиционные операции. Оба типа инвестиций имеют большое значение для сохранения жизнеспособности фирмы и ее развития. Их целью является прежде всего создание условий для снижения затрат фирмы за счет замены оборудования обучения персонала или перемещения производственных мощностей в регионы с более выгодными условиями производства; инвестиции в расширение производства. Логика зависимости между типом инвестиций и уровнем их риска очевидна: она определяется степенью...
79759. Инновационная политика в организации и финансировании инноваций и инвестиций 187 KB
  Как и практически всякая иная политика она неодинакова в разных странах хотя и подчинена одной и той же цели: стимулированию инновационной активности и развитию научнотехнического потенциала. Место и роль инновационной политики в структуре государственного регулирования экономики определяются особенностями инновационного процесса как объекта управления. В практической направленности инновационной идеи и состоит ее притягательная сила для капиталистических компаний. Так к числу внутренних побудительных мотивов инновационной активности можно...