Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2019-10-30 | 143 |
5.00
из
|
Заказать работу |
|
|
Раскрашенная сеть, как частный вариант нагруженных сетей, это объект, который характеризуется следующим множеством элементов:
CN = { N, C, F, C M0 }
где: N = { T, P, I, O } – биграф;
C = { X, R }, X = { λ, C1, C2, …, CL } = { Cr} – множество раскрашивающих цветов или других признаков, включающее элемент λ, обозначающий «отсутствие цвета»;
R - бинарное отношение на множестве цветов Х, (чаще всего это отношение эквивалентности или равенства цветов);
F: А à Х – отображение множества дуг биграфа N на множество цветов, дающее раскраску дуг: CijS - цвет S-ой дуги aijS биграфа, направленной из вершины i в вершину j;
С М0 – начальное цветное маркирования сети.
В сети также раскрашиваются метки. Если М – множество цветных меток, то цветное маркирование сети характеризуется парой отображений:
CM: { PèM; MèX }
первое из которых указывает на размещение меток по позициям, а второе на цвет этих меток. Факт размещения метки m в позиции Pi обозначим (m є Pi).
Условимся, что метка m, имеющая цвет c(m), может принять участие в возбуждении перехода tj, если пара (c(m),CijS) удовлетворяет заданному R-отношению на множестве цветов. Если R-отношение равенства, то метка (m є Pi) может участвовать в возбуждении tj при условии что c(m) = CijS (т. е. когда цвет метки равен цвету дуги aijS). Для возбуждения перехода tj необходимо, чтобы по всем входящим дугам могли пройти метки соответствующего цвета из позиций Pi, являющиеся предшественниками перехода tj.
Логическое уравнение, описывающее условие возбуждения перехода tj, имеет следующий вид:
∀ Pi є Pre(tj) ∃ m є Pi [ R(C(m), CijS) = 1] è U(tj) = 1,
иначе U(tj) = 0
Итак, если переход tj возбуждён (U(tj) = 1), то происходит его срабатывание и возбуждавшие метки из позиций Pre(tj) при этом изымаются, а позиции Post(tj) пополняются метками, цвет которых принимается равным цвету дуг, проходящих из tj в позиции Post(tj).
|
Для отображения цветного маркирования условимся представлять его в следующем виде:
CM = | m1 … mi … mn |,
где: * - операция транспонирования;
mi = | mi1 mi2 … miL |, причём mi2 - число меток r-го цвета в позиции Pi.
Динамика меток в раскрашенной сети характеризуется матрицей инцидентности Д, элементы которой dij представим в виде векторов-строк длиною L.
dij = | dij1 dij2 … dijL | (17)
где L - число раскрашивающих цветов.
Значения dij2 задаются следующим образом. Если метка цвета r потребляется переходом tj из позиции Pi при срабатывании tj, то dij2 = -1; Если метка цвета r поступает в Pi из tj, то dij2 = 1, и, наконец, в отсутствии этих действий dij2 = 0.
Эти же условия можно сформировать по другому. Если позиция Pi имеет исходящие дуги цвета r в переход tj, то dij2 = -1; если имеет входящие дуги цвета r, то dij2 = 1, и если не имеет инцидентных дуг цвета r, то dij2 = 0.
Динамику продвижения меток по раскрашенной сети можно описать уравнением состояния:
CMk = CMk-1 + D*Uk (18)
где CMk - состояние, в которое переходит раскрашенная сеть из CMk-1 под действием управляющего вектора Uk = | Ujk |, компоненты которого
1, если в К-ый момент срабатывает переход tj
Ujk=
0, иначе
Введём в рассмотрение инварианты раскрашенной сети, подобно тому как это сделано в сети Петри. Р-инвариант найдём из решения линейной системы.
DV = 0 (19)
где: V = | Vi | - целочисленный вектор-столбец, компоненты которого имеют вид:
Vi* = | Vi1 Vi2 …. ViL |
Учитывая уравнение (2), находим:
V*CM = V*CM0 (20)
|
Итак, подобно уравнению (10) для сети Петри, уравнение (20) для раскрашенной сети описывает инвариантность в её маркированиях.
Фундаментальная система решений однородной системы линейных уравнений имеет n – rl решений, где n - число позиций сети; r - ранг матрицы Д; l - мощность множества цветов Х. Объединив их в матрицу СВ, получим уравнение, аналогичное уравнению (12):
CB CM = CB CM0 = K0
Решение линейной системы
D*W = 0 (21)
Даёт t-инварианты W, где W = | Wj | - целочисленный вектор-столбец, в котором
Wj = | Wj1 Wj2… WjL |. Условие существования тупиков в раскрашенной сети находится из анализа системы:
CB CM = CB CM0
CO*CM ≤ COE’ – E (22)
подобно тому как это выполняется для сети Петри. Здесь CO* - матрица аналогичная O*, расширенная в пределах каждого элемента по принципу (17):
1, если существует дуга из tj в Pi, раскрашенная цветом r;
COij2 =
0, иначе
COij = | COij1, COij2, …, COijL |,
Е’ – единичный клеточный вектор, компоненты которого ej‘ представлены наборами из – единиц.
Итак, с математических позиций анализ раскрашенной сети и базовой сети Петри подобен. В случае раскрашенной сети, однако, действия выполняются на уровне клеточных матриц и векторов.
Рассмотрим простой пример для уяснения методики расчёта динамических свойств раскрашенных сетей.
рис A
В изображённой сети, описывающей взаимодействие двух процессов, обозначенных метками (□,○), протокол взаимодействия предусматривает порождение нового процесса (●), а затем возврат к исходным.
Каждому цвету из множества Х = (□,○,●) сопоставим числа r = 1, 2, 3. Тогда элементы матрицы Д = || dij ||, где i = 1, 2, 3, 4, j = 1, 2, 3, 4, 5, равны:
d11 = d22 = | -1 0 0 |; d23 = | 0 0 1 |;
d12 = d31 = | 1 0 0 |; d33 = | 0 0 -1|;
d35 = d44 = | 0 1 0 |; d24 = d45 = | 0 -1 0 |,
а другие dij = | 000 |.
Вектор начального маркирования СМ0 = | m0i | представлен компонентами:
m01 = | 100 |; m02 = m03 = m04 = | 000 |; m05 = | 010 |.
Уравнение состояния (18) здесь имеет вид:
m1 | m1 | d11 | d21 | d31 | d41 | U1 | ||||
m2 | m2 | d12 | d22 | d32 | d42 | U2 | ||||
m3 | = | m3 | + | d13 | d23 | d33 | d43 | * | U3 | |
m4 | m4 | d14 | d24 | d34 | d44 | U4 | ||||
m5 | k | m5 | k-1 | d15 | d25 | d35 | d45 | k |
|
Его рекуррентное решение позволяет моделировать динамику состояний сети.
Найдём Р-инвариант сети V* = | V1V2V3V4V5 |, где Vi* = | Vi1 Vi2 Vi3 |. Для этого нужно решить систему (19). Ранг матрицы Д равен 1, следовательно фундаментальная система имеет одно решение, так как n – rl = 1. Распишем систему уравнений (19) для данной сети:
V11 = V21 V42 = V52
V33 = V21 + V42 V33 = V11 + V52
В качестве инварианта можно взять клеточный вектор-столбец с компонентами V1* = V2* = |100|; V3*= |003|; V4* = V5* = |020|, удовлетворяющий приведённой однородной системе линейных уравнений. Затем вычисляем произведение:
V*CM0 = | V1* V2* V3* V4* V5*|| m1* m2* m3* m4* m5*|0 = 3
и условие инвариантности:
5
VCM = | Vi* || mi* |* = ∑ Vi* mi* = m11+ m21 +3m33 + 2m42 + 2m52 = 3
i=1
Верхний индекс здесь указывает цвет метки, а нижний – позицию. В рассматриваемом примере возможны следующие варианты распределения меток по позициям и их цветности:
m11+ 2m42 = 3; m11+ 2m52 = 3; m21 + m42 = 3;
m21 +m52 = 3; 3m33 = 3
Из условия инвариантности, содержащего в правой части константу 3, следует ограниченность сети. Решив систему (21), можно установить, что данная сеть живая и устойчивая. Элементы матрицы СО равны:
CO11 = CO22 = | 100 |; CO42 = CO54 = | 010 |; CO33 = | 001 |;
а другие COij= | 000 |. Система (22) здесь имеет вид:
m11+ m21 +3m33 + 2m42 + 2m52 = 3;
m11 ≤ 0; m21 + m42 ≤ 1; m33 ≤ 0; m52 ≤ 0.
Данная система не совместна, а, следовательно, исследуемая раскрашенная сеть не имеет тупиков.
Изменим раскраску на дуге (t3,p5) и примем новое начальное маркирование (рис Б):
На основе вычислений можно установить, что приведённая сеть – ограниченная, живая, однако тупиковая, поскольку система
m11+ m21 +3m33 + 2m42 + 2m51 + 2m52 = 3;
m11 ≤ 0; m21 + m42 ≤ 1; m33 ≤ 0; m52 ≤ 0.
совместна. Тупиковое маркирование описывается вектором СМ = | (000) (100) (000) (100) (000) |.
Рис Б.
«Обесцвечивание» сети, т. е. переход от раскрашенной сети к базовой сети Петри может привести к потере и искажению информации о протекании процессов в сетевой модели. Так, если выполнить «обесцвечивание» приведённой сети, то расчётами можно установить, что её инвариант станет равным m 1 + m 2 + 3 m 3 + 2 m 4 + 2 m 5 = 3, т. е. произошло как бы «обесцвечивание» инварианта сети, приведённой на (рис. а), а не на (рис. б). Но самое важное состоит в том, что «обесцвеченная» сеть – беступиковая, хотя исходная раскрашенная сеть имеет тупик. Искажение такого важного свойства при упрощении модели указывает, что для обеспечения достоверности проектного анализа при исследовании раскрашенных сетей недопустим переход к «обесцвеченной» сети.
|
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!