Составные сети Петри-Маркова на основе марковских процессов с пропозициональной логикой срабатывания логических переходов
Пусть СПМ состоит из нескольких подпроцессов (парциальных марковских процессов), при этом переход от одного подпроцесса к другому осуществляется только при выполнении определенных логических условий. Переход, срабатывающий при определенных логических условиях, далее называется логическим переходом.
Для того чтобы отделить подпроцессы, завершающиеся логическими условиями, от других подпроцессов, вводятся непримитивные переходы, срабатывающие при определенной логике наступления событий. СПМ с логическими переходами, соединяющими парциальные процессы, в [35] названы составными сетями Петри-Маркова (ССПМ). В отличие от классических СПМ, в которых переходы срабатывают, если для каждой входящей в переход дуги имеется не менее одного маркера, в данном случае для перехода может быть определена любая логика срабатывания.
Как и классические СПМ, составные СПМ представляются в виде графов. Пример графа ССПМ, построенной с использованием марковских процессов с логическими условиями, приведен.
Каждый участок графа соответствует одному из парциальных марковских процессов. При построении такого графа необходимо соблюдать следующие правила:
ССПМ должна начинаться с начальной позиции (или нескольких начальных позиций) и заканчиваться конечной позицией;
в ССПМ могут иметь место тупиковые позиции, в которых развитие процесса прекращается, для того чтобы показать, где может остановиться процесс, не достигнув конечной позиции;
должна быть установлена начальная разметка сети; в сети не может быть две подряд позиции или два подряд перехода; в сети могут применяться кратные дуги, но тогда, переходам, в которые входят кратные дуги, должны быть сопоставлены соответствующие правила срабатывания;
в ССПМ может иметь место разветвление процесса после переходов, то есть из перехода сети может исходить несколько дуг к разным позициям, при этом по всем таким дугам маркер (по каждому маркеру на дугу путем размножения одного маркера) перемещается в инцидентную позицию мгновенно с единичной вероятностью.
Далее для упрощения в данной работе на графе ССПМ переходы обозначаются номером с буквой z, а позиции просто нумеруются, в индексах функций и параметров первая буква означает номер состояния, из которого исходит дуга, а вторая - номер перехода, в который она входит, при двузначных цифрах применяется разделяющая запятая.
Расчет времени перемещения процесса оценивается по каждой траектории как сумма случайных времен перемещения из позиций в переходы.
При этом следует иметь в виду, что процесс из перехода в позицию ССПМ перемещается мгновенно, а из позиции в переход - за конечное в общем случае случайное время. Условия срабатывания логических переходов в ССПМ могут формально вводиться с использованием аппарата пропозициональной логики, с использованием операций с предикатами второго порядка или иными способами.
Основные логические условия и вероятности срабатывания переходов
Логическое условие Описание условия Вероятность срабатывания перехода АлВ («И»)
Логический переход срабатывает, если на его вход поступили все подпроцессы из совокупностей А и В зд)=Пад-Ш<'> іеА jsB АѵВ («ИЛИ»)
Логический переход срабатывает, если на его вход поступили или все подпроцессы из совокупности А, или все подпроцессы из совокупности В, или и те, и другие j*™,®=i- пи-^ wi- пв - ^ ®]=i- п каді іеА jeB і'еАхВ АѵВлС («ИЛИ-И»)
Логический переход срабатывает, если на его вход поступили все подпроцессы хотя бы одной из совокупностей А или В и все подпроцессы из совокупности С А® В (XOR или эксклюзивный вы- бор)
Логический переход срабатывает, если на его вход поступили или только все подпроцессы из совокупности А, или только все подпроцессы из совокупности В Р*оА0-| \І’,(І) \ |М ЩО] + іеА jeB +ПР--г;«)]-П-г;«) АлВС («И-НЕ»)
Логический переход срабатывает, если на его вход поступили подпроцессы из совокупности А (для двух подпроцессов), А и В (для трех подпроцессов) и не поступил ни один подпроцесс из совокупности С
Для двух совокупностей подпроцессов А л -С С wo=n w-ro-wi І€А j€<7
Для трех совокупностей подпроцессов іеА kzB JeC (АѵВ)л^С («ИЛИ-НЕ»)
Логический переход срабатывает, если на его вход поступили подпроцессы из совокупности А или из совокупности В и не поступил ни один подпроцесс из совокупности С 4»,.»(')={і- П г-«')][■ ПР-ад
Пусть между двумя логическими переходами по г -й траектории имеется У(' * позиций и дуг (рисунок 6.5), по каждой из которых процесс перемещается за конечное в общем случае случайное время т^\п = 1,N^ .
Траектория перемещения процесса по ССПМ между двумя логическими переходами
Тогда математическое ожидание времени перемещения процесса из позиции 0(г) (z) в переход N{r) (г) представляет собой сумму математических ожиданий независимых случайных величин и независимо от того, какие функции распределения имеют слагаемые времена, определяется из соотношения Nlr) ^ = (6-9) п= 1 где ТИ./)И - математическое ожидание времени перемещения процесса между позицией с номером п -1 в переход с номером п.
В [35] была показана возможность использования экспоненциального приближения для выходящего из логического перехода потока, а также условия, при которых такое приближение приемлемо для ориентировочных оценок.
Так как времена между событиями являются положительно определенными случайными величинами, то плотность распределения вероятности для них всегда может быть аппроксимирована гамма- распределением или при целочисленных значениях параметра формы - распределениями Эрланга:
т=- t"'-1 'Ц-D! f2(t) = — (6.10) 2(П2 ~1)! где tij и н, - параметры формы.
Следует отметить, что параметр формы в распределении Эрланга (потоки с таким распределением часто называют эрланговскими) в ССПМ соответствует количеству простых переходов между логическими переходами по рассматриваемой траектории.
Для эрланговских входящих потоков вероятность срабатывания перехода «И» (см. таблицу 6.1) удовлетворяет требованиям, предъявляемым к функциям распределения вероятностей случайных величин Ря(0) = 0,Ря( со) = 1. В связи с этим математическое ожидание времени срабатывания перехода рассчитывается по точным формулам, приведенным в таблице 6.2.
Вместе с тем, как показано в [35], что с достаточно высокой точностью для оценки математического ожидания времени срабатывания перехода с логикой «И» при небольших значениях параметра формы эрланговских входящих потоках можно использовать сравнительно простые формулы, приведенные также в таблице 6.2. Для сравнения в таблице 6.3 даны значения математического ожидания времени срабатывания логических переходов с логиками «И» и «ИЛИ», рассчитанные по точной и приближенной формулам.
Соотношения для расчета математического ожидания времени срабатывания переходов с логиками «И», «ИЛИ» и «И-ИЛИ»
Математическое ожидание времени срабатывания перехода
По точной формуле По приближенной формуле
Xй1 -е 4 X , „Л кГ 1 ** ІІ г, -(и, -1)! КТ2 J («!-!)! (г,-я,] + гх • я,-т2-п2 + (г2-и2] и, + г2 я2 ч-.я. К-1)1 - і-гМ «и- или» лЛ е г‘ Л1 • -0! U*2 Пі) u r\ 1-г J? J Xй' е ц L П ' Ci’h-if nr "И Г,-И, -Г2 -«2 (Т1 -Лі) -Т3 ,Л3 Tl-ni+T2-7I2 -У”? WV^'V”; |r2 -H2+T3-Я3| Т1 -Л1+T2 -Д2+T3'И3
Математические ожидания времени срабатывания логического перехода с логиками «И» и «ИЛИ», рассчитанные по точной и приближенной формулам
Параметры первого потока Параметры второго потока Результат расчета
гі «і г П2
По точной формуле По приближенной формуле Для перехода с логикой «И»
1 1 2 1 2.33 2.33 1 1 2 3 6.1 6.5 1 2 4 5 15 15.2 1 3 7 7 35 35.2 1 5 7 10 70 70,3 1 7 7 15 105 105,4
Для перехода с логикой «ИЛИ»
1 1 2 1 0.67 0.67 1 1 2 3 0.96 0.86 1 2 45 2 1.82 1 3 7 7 3 2.83 1 5 7 10 54.67 1 7 7 15 7 6.6
видно, что использование приближенной формулы вполне оправдано. Следует отметить, что с увеличением значений параметров формы закона Эрланга точность определения математического ожидания времени срабатывания логического перехода «И» возрастает. Однако это не всегда означает близость значений вероятностей срабатывания перехода.
Расчет самой вероятности проводится по формулам, приведенным, с использованием неполной ^-функции [92], y{a-t,n} 1 (и-і) і-І X п-1 exp (-х) dx (6.11)
Приведены для сравнения зависимости вероятностей срабатывания логического перехода с логикой «И», рассчитанные по формулам.
Соотношения для расчета вероятностей срабатывания переходов с логиками «И», «ИЛИ» и «И-ИЛИ»
Логика срабатывания перехода Вероятность срабатывания перехода По точной формуле По приближенной формуле
«И» р*(0=г(=>«і)-г(=>«2) Т1 Т2 P„(t) = l-exp /• . V
«ИЛИ» J II 1 1 £ р„л„(>) = 1-ехР t- ТИЛИ .
«И-ИЛИ» f II 1 1 > ^ II- -1 ри-,ш(<) = 1-ехР /• 7И-ИЛИ.
1 - г, = 1, т2 = 4, и, = 3,«2 = 3 2 - г, = 1, х2 = 15, и, = 3, я2 = 3
1 - г, = 1, г2 = 4, «j = 2, п, = 5 ; 2 - г, = 1, г2 = 10, и, = 2, = 5
1 - г, = 1, г2 = 4,пх = 2,пг = 10 ; 2 - г, = 1, г2 = 15,и, = 2,п2 =10
Зависимости от времени вероятности срабатывания логического перехода «И», рассчитанные по точной (сплошная линия) и приближенной (пунктирная линия) формулам
В частности, для пуассоновских входящих потоков с учетом только положительно определенных значений времени формула (6.12) преобразуется к виду Іи-нАу) = —еТ>+=1=Я(У), (6.13) ті+т2 тг + г, где j-j и т2 - средние значения случайных времен г, и т2; S(y) - дельта функция (функция Дирака).
Тогда усредненная вероятность того, что при каждой реализации будет выполняться неравенство у > 0, рассчитывается следующим образом: АД=^/(т+^)- (6.14)
Математическое ожидание времени и вероятность срабатывания перехода с логикой «И-НЕ» определяется по формулам, приведенным.
Соотношения для расчета вероятности и математического ожидания времени срабатывания перехода с логикой «И-НЕ» при эрланговских входящих потоках
Количество входящих потоков
Формулы для расчета математического ожидания времени срабатывания перехода
Формула для расчета вероятности срабатывания перехода
По точной формуле По приближенной формуле 2 с параметрами И] и п2
т{2) -т-п-1 И-НЕ — 41 п\ г, п, ) Ри-нЛ‘)=г[='п1 1 –г іб ри-ш (0 = 1 -ехр^-і/т^ні)
3 с параметрами пѵп2 и п3 J?) _ г(2) . ‘'И-НЕ 1 И-НЕ 1 +TtSL h-’h j ь) !-r(=’«3 j Рп-ш (0 = 1
Логический переход «ИЛИ-HE» имеет место применительно к не менее, чем трем входящим потокам, при этом он срабатывает, если или первый поток, или второй поток подойдет к переходу, а третий нет. Математическое ожидание времени срабатывания перехода рассчитывается с использованием того же подхода, что был использован для перехода с логикой «И-ЕЕ».
Формулы для расчета математического ожидания времени и вероятности срабатывания переходов с логикой «ИЛИ-HE» приведены соответственно в таблице 6.7. 27
Для пуассоновскиз ВХОДДЯЩИХ ПОТОКОВ = П2 = Пг = 1.
Соотношения для расчета вероятности и математического ожидания времени срабатывания перехода с логикой «ИЛИ-НЕ»
Количество входящих потоков
Формулы для расчета математического ожидания времени срабатывания перехода
Формула для расчета вероятности срабатывания перехода
По точной формуле По приближенной формуле 3 с параметрами п}, п2 и п3 ___ ( (1,2) ^ (и) . 1+ гж L ИЛИ-HE ‘‘ИЛИ — г„, ТУ ГІ ' П1 ' Г П2 ТШи — — Т\'П\ +Т2Ш П2 ^ ИЛИ-НЕ (0 j 'Нг 1-МНІННІ’ Рцші-ш (>) = 1 - ехР ( -<! hmu-HB
Вероятность того, что очередное событие первого потока поступит на переход при отсутствии события второго потока, рассчитывается по формуле: рѴОЕ (о=т [1 - р2 (о]+р2 (о • [1 ад] (6.15)
Переход срабатывает в том случае, когда время ti поступления первого потока меньше времени С поступления второго потока, то есть выполняется условие /j < t2.
Условная интенсивность поступления на переход первого потока, при условии того, что второй поток не поступил, определяется из соотношения:
М = = • j jfi(У + -fxiTi)• dr\dy . (6.16) Tl 0 0
Условная интенсивность поступления на переход второго потока, при условии того, что первый поток не поступил, определяется из аналогичного соотношения:
М2 оО 00 : = J J(у + г,) •/; (z2)-d z2dy
Для экспоненциального приближения:
= (Y71) {Гі/(т + Д )] = ^(д + Т2 ) (6.17) (6.18) fh=- г, “Ь
Поскольку переход срабатывает при поступлении любого из двух потоков, суммарная интенсивность такого срабатывания составляет величину:
Mxor = М\ + Иг =^/{г\ + гз) и ?хох ~ V Мхох ~(гі +гг)/і • (6-19)
Для двух пуассоновских входящих потоков вероятность срабатывания перехода рассчитывается по формуле:
Рхок(0 = [і -е~,/7' ] • е~,/7‘ + е~,/7' • [і - е~,/7- ], (6.20)
а для эрланговских входящих потоков - по формуле:
PjdiV) = К*/ T1 ,«і) {l - Л*І r2, n2)} + r(t/Г2, и2)) {l - y{t/Tj,«!)}. (6.21)
При этом в случае эрланговских потоков для расчета математического ожидания времени срабатывания перехода с логикой XOR может быть использовано приближенное соотношение:
Eim =(^"i ~*~72 • (6.22)
Примеры применения составных сетей Петри-Маркова на основе марковских процессов с логическими переходами с пропозициональной логикой срабатывания приведены.
