Уравнения состояний стохастических временных сетей Петри с информационными связями
Розглянуто застосування мереж Петрі з часовими затримками для імітаційного моделювання систем. Отримано рівняння перетворень стану мережі Петрі та фундаментальні матричні рівняння стохастичної мережі Петрі з часовими затримками, багатоканальними та конфліктними переходами, інформаційними зв’язками....
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84151 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Уравнения состояний стохастических временных сетей Петри с информационными связями / И.В. Стеценко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 164-179. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859804634138279936 |
|---|---|
| author | Стеценко, И.В. |
| author_facet | Стеценко, И.В. |
| citation_txt | Уравнения состояний стохастических временных сетей Петри с информационными связями / И.В. Стеценко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 164-179. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто застосування мереж Петрі з часовими затримками для імітаційного моделювання систем. Отримано рівняння перетворень стану мережі Петрі та фундаментальні матричні рівняння стохастичної мережі Петрі з часовими затримками, багатоканальними та конфліктними переходами, інформаційними зв’язками.
The use of timed Petri nets in systems simulation is analyzed. The equations of timed Petri net state transformations and fundamental matrix equations of stochastic timed Petri net with conflict and multi-transitions, with information ties are obtained.
|
| first_indexed | 2025-12-07T15:15:08Z |
| format | Article |
| fulltext |
ÓÄÊ 519.876.5
È.Â. ÑÒÅÖÅÍÊÎ
ÓÐÀÂÍÅÍÈß ÑÎÑÒÎßÍÈÉ ÑÒÎÕÀÑÒÈ×ÅÑÊÈÕ ÂÐÅÌÅÍÍÛÕ
ÑÅÒÅÉ ÏÅÒÐÈ Ñ ÈÍÔÎÐÌÀÖÈÎÍÍÛÌÈ ÑÂßÇßÌÈ
Êëþ÷åâûå ñëîâà: âðåìåííàÿ ñåòü Ïåòðè, èìèòàöèîííîå ìîäåëèðîâàíèå,
ìàòðè÷íîå óðàâíåíèå.
ÂÂÅÄÅÍÈÅ
Ñåòè Ïåòðè — óíèâåðñàëüíîå ñðåäñòâî ôîðìàëèçàöèè ïðîöåññîâ, èìåþùèõ
ñîáûòèéíûé õàðàêòåð, èíòåíñèâíî èñïîëüçóþòñÿ â ðàçëè÷íûõ îáëàñòÿõ. Ýëå-
ìåíòàìè ñåòè Ïåòðè, ïîçâîëÿþùèìè îïèñûâàòü ïðîöåññû ôóíêöèîíèðîâàíèÿ
ñëîæíûõ ñèñòåì, ÿâëÿþòñÿ ïåðåõîäû ñ âðåìåííûìè ñòîõàñòè÷åñêèìè çàäåðæ-
êàìè [1], ìíîãîêàíàëüíûå è êîíôëèêòíûå ïåðåõîäû [2, 3], èíôîðìàöèîííûå
ñâÿçè. Ïîñëåäíèå ââåäåíû â [4] äëÿ îòîáðàæåíèÿ ñïåöèôè÷åñêèõ ïðîöåññîâ
óïðàâëåíèÿ è ïðèìåíÿëèñü â [5–7] äëÿ èìèòàöèîííîãî ìîäåëèðîâàíèÿ. Èíôîð-
ìàöèîííûå ñâÿçè, êàê è ìíîãîêàíàëüíûå ïåðåõîäû, íå ðàñøèðÿþò êëàññ ñåòåé
Ïåòðè, îäíàêî äåëàþò èõ áîëåå óäîáíûìè äëÿ ïðåäñòàâëåíèÿ ñëîæíûõ ñèñòåì.
 ðàáîòå [8] ïîêàçàíî, ÷òî èíãèáèòîðíûå ñåòè Ïåòðè ðàâíîìîùíû ïðèîðè-
òåòíûì ñåòÿì Ïåòðè è äîêàçàíî, ÷òî îáà âèäà ñåòåé ýêâèâàëåíòíû ìàøèíå Òüþ-
ðèíãà. Ïîñòðîåíèå ñåòè Ïåòðè, ýêâèâàëåíòíîé ìàøèíå Òüþðèíãà, ðàññìîòðåíî
â [9]. Âðåìåííûå ñåòè Ïåòðè ïðåäîñòàâëÿþò âîçìîæíîñòü îäíîâðåìåííîãî èññëå-
äîâàíèÿ êàê ñòðóêòóðíî-ôóíêöèîíàëüíûõ ñâîéñòâ ñèñòåìû, òàê è åå ýêñïëóàòà-
öèîííûõ õàðàêòåðèñòèê [10]. Ñòîõàñòè÷åñêèå ñåòè Ïåòðè ìîùíåå ìàðêîâñêèõ
ïðîöåññîâ [11], â òî æå âðåìÿ èõ ïðèìåíåíèå äëÿ èìèòàöèîííîãî ìîäåëèðîâàíèÿ
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
© È.Â. Ñòåöåíêî, 2012
îãðàíè÷åíî, î ÷åì ñâèäåòåëüñòâóåò òîò ôàêò, ÷òî â èçâåñòíîé ìîíîãðàôèè [12] íå
óïîìèíàåòñÿ î ñåòÿõ Ïåòðè.
Âûâîä óðàâíåíèé ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè ñ êîíôëèêòíûìè
è ìíîãîêàíàëüíûìè ïåðåõîäàìè, ñ èíôîðìàöèîííûìè ñâÿçÿìè îñíîâàí íà ðàáî-
òàõ [13, 14]. Â [13] îïèñàíû ôóíäàìåíòàëüíûå óðàâíåíèÿ áàçîâîé ñåòè Ïåòðè
è ïðåäëîæåíû ñïîñîáû àíàëèòè÷åñêîãî èññëåäîâàíèÿ åå ñâîéñòâ.  [14] ââåäåíû
ïîíÿòèÿ ñîñòîÿíèÿ âðåìåííîé ñåòè Ïåòðè è êîëè÷åñòâà âîçìîæíûõ çàïóñêîâ ïå-
ðåõîäà, íàéäåíî óðàâíåíèå ñîñòîÿíèé âðåìåííîé äåòåðìèíèðîâàííîé ñåòè Ïåòðè
ñ ïðîäâèæåíèåì âðåìåíè ïî òàêòàì.
Îñíîâíûì ïðåäíàçíà÷åíèåì ïîëó÷åííûõ â äàííîé ñòàòüå óðàâíåíèé ÿâëÿåò-
ñÿ ìàòåìàòè÷åñêîå îïèñàíèå ïðàâèë ôóíêöèîíèðîâàíèÿ âðåìåííîé ñåòè Ïåòðè,
ñ ïîìîùüþ êîòîðîãî ñòðîèòñÿ àëãîðèòì èìèòàöèè åå ìîäåëè. Ýòè óðàâíåíèÿ
ïðèâåäåíû ê ìàòðè÷íîìó âèäó è ïîêàçàíî, ÷òî ïðè íóëåâûõ âðåìåííûõ çàäåðæ-
êàõ îíè àíàëîãè÷íû óðàâíåíèÿì â [13], à ïðè äåòåðìèíèðîâàííûõ âðåìåííûõ çà-
äåðæêàõ — óðàâíåíèÿì â [14].
ÏÐÎÖÅÑÑÛ ÓÏÐÀÂËÅÍÈß È ÂÐÅÌÅÍÍÛÅ ÑÅÒÈ ÏÅÒÐÈ
Ñ ÈÍÔÎÐÌÀÖÈÎÍÍÛÌÈ ÑÂßÇßÌÈ
Èíôîðìàöèîííûå ñâÿçè ìåæäó ïîçèöèåé è ïåðåõîäîì ïîçâîëÿþò ìîäåëèðî-
âàòü ñâÿçè ìåæäó ïîäñèñòåìàìè óïðàâëåíèÿ è îáúåêòà óïðàâëåíèÿ, õàðàêòåðè-
çóþùèåñÿ ïåðåäà÷åé èíôîðìàöèè î ñîñòîÿíèè. Íàïðèìåð, íà ðèñ. 1 ïðåäñòàâ-
ëåíà ñåòü Ïåòðè, ìîäåëèðóþùàÿ ïåðåñå÷åíèå àâòîìîáèëåì ïåðåêðåñòêà íà çå-
ëåíûé ñèãíàë ñâåòîôîðà. Ïîêàçàíà èíôîðìàöèîííàÿ ñâÿçü (øòðèõîâàÿ ëèíèÿ),
êîòîðàÿ èñïîëüçóåòñÿ äëÿ ñîåäèíåíèÿ ïîçèöèè P4 (åñòü çåëåíûé ñâåò â íàïðàâ-
ëåíèè äâèæåíèÿ) è ïåðåõîäà T1 (ïåðåñå÷åíèå àâòîìîáèëåì ïåðåêðåñòêà). Ðå-
çóëüòàòîì ôóíêöèîíèðîâàíèÿ îáúåêòà óïðàâëåíèÿ ÿâëÿåòñÿ èçìåíåíèå ñî-
ñòîÿíèÿ îáúåêòà, íî íå ïîäñèñòåìû
óïðàâëåíèÿ. Åñëè ïîäñèñòåìà îáúåê-
òà óïðàâëåíèÿ «÷òî-òî çíàåò» î ïîä-
ñèñòåìå óïðàâëåíèÿ, òî ýòî ïðèâî-
äèò ê êîððåêòèðîâêå ïðàâèë ôóíê-
öèîíèðîâàíèÿ îáúåêòà óïðàâëåíèÿ,
íî íå èçìåíÿåò ñîñòîÿíèÿ ïîäñèñòå-
ìû óïðàâëåíèÿ. Èìåííî äëÿ âîñ-
ïðîèçâåäåíèÿ ñâÿçè âèäà «çíàåò, íî
íå èçìåíÿåò» ïðåäíàçíà÷åíû èí-
ôîðìàöèîííûå ñâÿçè.
Èíôîðìàöèîííàÿ ñâÿçü ìåæäó
ïîçèöèåé è ïåðåõîäîì îçíà÷àåò, ÷òî
íàëè÷èå ìàðêåðîâ â ïîçèöèè â êîëè-
÷åñòâå, ðàâíîì êðàòíîñòè ñâÿçè,
îïðåäåëÿåòñÿ ïðè ïðîâåðêå óñëîâèÿ
çàïóñêà ïåðåõîäà, îäíàêî âî âðåìÿ
ñàìîãî çàïóñêà ìàðêåðû íå óäàëÿþò-
ñÿ. Òàêèì îáðàçîì, ïðè îáû÷íîé
(ìàòåðèàëüíîé) ñâÿçè ìåæäó ïîçèöèåé è ïåðåõîäîì îñóùåñòâëÿåòñÿ ïåðåìåùå-
íèå ìàðêåðîâ âäîëü ýòîé ñâÿçè â ñëó÷àå âûïîëíåíèÿ óñëîâèÿ çàïóñêà ïåðåõîäà,
à ïðè èíôîðìàöèîííîé ñâÿçè òàêîãî ïåðåìåùåíèÿ ìàðêåðîâ íå ïðîèñõîäèò.
Àëãîðèòìè÷åñêàÿ ðåàëèçàöèÿ ñåòè Ïåòðè ñ èíôîðìàöèîííûìè ñâÿçÿìè îòëè÷àåò-
ñÿ îò ðåàëèçàöèè îáû÷íîé ñåòè Ïåòðè òîëüêî íåîáõîäèìîñòüþ ðàçäåëÿòü âõîä-
íûå ïîçèöèè ïåðåõîäà íà ñîåäèíåííûå ñ íèì îáû÷íîé è èíôîðìàöèîííîé
äóãàìè. Ïðè ïðîâåðêå óñëîâèÿ çàïóñêà èññëåäóåòñÿ ñîñòîÿíèå âñåõ âõîäíûõ ïîçè-
öèé ïåðåõîäà, à ïðè åãî çàïóñêå — òîëüêî ïîçèöèé, ñâÿçàííûõ ñ ïåðåõîäîì îáû÷-
íîé äóãîé. Ñðàâíèâàÿ èíôîðìàöèîííûå äóãè ñ øèðîêî èçâåñòíûìè èíãèáèòîðíû-
ìè äóãàìè, îòìåòèì, ÷òî, è îäíè è äðóãèå ïðèìåíÿþòñÿ òîëüêî äëÿ äóã, íàïðàâëåí-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 165
T0 T1
3
T2 T3
T4
P0
P1
P2
P3
P5
P4
P6 P7
P8
Ïîäñèñòåìà óïðàâëåíèÿ
Ïîäñèñòåìà îáúåêòà óïðàâëåíèÿ
1
1
1
Ðèñ. 1. Ñåòü Ïåòðè, ìîäåëèðóþùàÿ ïåðåñå÷åíèå
àâòîìîáèëåì ïåðåêðåñòêà íà çåëåíûé ñèãíàë
ñâåòîôîðà
íûõ îò ïîçèöèè ê ïåðåõîäó, à ïåðåõîä ñ èíôîðìàöèîííîé ñâÿçüþ äîëæåí èìåòü
åùå è îáû÷íóþ âõîäíóþ äóãó. Îäíàêî â îòëè÷èå îò èíãèáèòîðíûõ äóã èíôîðìà-
öèîííûå ïîçâîëÿþò ïðîâåðÿòü íàëè÷èå ëþáîãî çàäàííîãî íà äóãå êîëè÷åñòâà
ìàðêåðîâ â ïîçèöèè. Âû÷èñëèòåëüíàÿ ñëîæíîñòü ñåòè Ïåòðè ñ èíôîðìàöèîííû-
ìè ñâÿçÿìè íå îòëè÷àåòñÿ îò âû÷èñëèòåëüíîé ñëîæíîñòè îáû÷íîé ñåòè Ïåòðè,
â òî âðåìÿ êàê ðåàëèçàöèÿ èíãèáèòîðíîé ñåòè Ïåòðè òðåáóåò óñëîæíåíèÿ óñëî-
âèÿ çàïóñêà [8]. Òåõíîëîãèÿ ïîñòðîåíèÿ ìîäåëåé ñèñòåì ñòîõàñòè÷åñêîé âðåìåí-
íîé ñåòüþ Ïåòðè ñ èíôîðìàöèîííûìè ñâÿçÿìè èçëîæåíà â [15].
ÔÎÐÌÀËÜÍÎÅ ÎÏÈÑÀÍÈÅ ÑÒÎÕÀÑÒÈ×ÅÑÊÈÕ ÂÐÅÌÅÍÍÛÕ ÑÅÒÅÉ ÏÅÒÐÈ
Ñ ÈÍÔÎÐÌÀÖÈÎÍÍÛÌÈ ÑÂßÇßÌÈ
Ðàññìîòðèì ñåòü Ïåòðè ( , , , , , , )P T A W K I R , çàäàííóþ ìíîæåñòâàìè ïîçèöèé
P � { }P ; ïåðåõîäîâ T � { }T , P T� �� ; äóã A P T T P� � �( )� ; èíôîðìàöèîí-
íûõ äóã I P T� �( ) ; íàòóðàëüíûõ ÷èñåë W A I: � � N , çàäàþùèõ êðàòíîñòè äóã
(êîëè÷åñòâî ñâÿçåé); ïàð çíà÷åíèé K T� � �{ N( , ) | , ,c b T cT T T bT �[ ; ]0 1 }, çàäàþ-
ùèõ ïðèîðèòåò è âåðîÿòíîñòü çàïóñêà ïåðåõîäîâ; íåîòðèöàòåëüíûõ äåéñòâèòåëü-
íûõ çíà÷åíèé R T: � � , õàðàêòåðèçóþùèõ âðåìåííûå çàäåðæêè â ïåðåõîäàõ.
Îáîçíà÷èì ìíîæåñòâà âõîäíûõ è âûõîäíûõ ïîçèöèé ïåðåõîäà T , êàê â [13],
ñîîòâåòñòâåííî
T è T
, ìíîæåñòâà âõîäíûõ è âûõîäíûõ ïåðåõîäîâ ïîçèöèè P
ñîîòâåòñòâåííî
P è P
, à ìíîæåñòâî âûõîäíûõ ïåðåõîäîâ, ñâÿçàííûõ ñ ïîçèöè-
åé P èíôîðìàöèîííîé ñâÿçüþ, P P� �
.
Ðàññìîòðèì ôóíêöèîíèðîâàíèå ñåòè Ïåòðè âî âðåìåíè, ïðîäâèãàþùåìñÿ îò
îäíîãî ñîáûòèÿ, ñâÿçàííîãî ñ âûõîäîì ìàðêåðîâ èç ïåðåõîäà, äî áëèæàéøåãî
ñëåäóþùåãî. Îáîçíà÷èì t òåêóùèé ìîìåíò âðåìåíè, à �t ñëåäóþùèé ìîìåíò âðå-
ìåíè. Îòìåòèì, ÷òî â òå÷åíèå âðåìåíè �
t t â ñåòè Ïåòðè ñîáûòèé íå ïðîèñõîäèò.
Ñîñòîÿíèå ñåòè Ïåòðè â ìîìåíò âðåìåíè t îïèñûâàåòñÿ ñîñòîÿíèÿìè åå ïîçèöèé
M( )t è ïåðåõîäîâ E M E S( ) : ( ( ), ( )) ( )t t t t� . Ñîñòîÿíèå ïîçèöèé îäíîçíà÷íî îïðåäå-
ëÿåòñÿ ìàðêèðîâêîé ñåòè Ïåòðè â ìîìåíò âðåìåíè t : M( ) ( ) | ( ) ,t M t M tP P� �{ N 0
P �P }, ãäå N 0 — ìíîæåñòâî öåëûõ íåîòðèöàòåëüíûõ ÷èñåë. Ñîñòîÿíèå ïåðåõî-
äîâ îïðåäåëÿåòñÿ ìíîæåñòâîì E T( ) ( ) |t E t TT� �{ }, ãäå E tT ( ) — ìíîæåñòâî ìî-
ìåíòîâ âûõîäà ìàðêåðîâ èç êàíàëîâ ïåðåõîäà T , êîòîðûå â ìîìåíò âðåìåíè t çà-
íÿòû (àêòèâíû):
E t E t E t qT T q T q( ) [ ( )] | [ ( )] ,� �� � { N },
ãäå q — íîìåð êàíàëà ïåðåõîäà, q E tT�1 2, , ... , | ( ) | , | ( ) |E tT — êîëè÷åñòâî
àêòèâíûõ êàíàëîâ â ìîìåíò âðåìåíè t.
Åñëè âûõîäà ìàðêåðîâ èç ïåðåõîäà íå îæèäàåòñÿ, òî ìíîæåñòâî E tT ( ) ýòîãî
ïåðåõîäà ñîäåðæèò òîëüêî îäíî çíà÷åíèå: �, ò.å. E tT ( ) � �{ }.
Ìíîæåñòâî äîïóñòèìûõ ñîñòîÿíèé ñåòè Ïåòðè îïèñûâàåòñÿ ìíîæåñòâàìè íå-
îòðèöàòåëüíûõ çíà÷åíèé ìàðêèðîâîê åå ïîçèöèé è ìîìåíòîâ âûõîäà èç ïåðåõîäîâ
S S P T( ) ( ) | ( ( ) ) ([ ( )] , , ...,t t M t P E t T qP T q� � � � � � � � � �{ 0 0 1 | ( ) | )E tT }.
Ââåäåì ïåðåìåííóþ �T t( ) , îïðåäåëÿþùóþ íàèìåíüøèé èç âñåõ ìîìåíòîâ âû-
õîäîâ ìàðêåðîâ èç ïåðåõîäà T t E tT
q
T q: ( ) min [ ( )]� � . Òîãäà ìîìåíò áëèæàéøåãî ñî-
áûòèÿ ïðåäñòàâëÿåòñÿ ìèíèìóìîì âñåõ çíà÷åíèé � �T
T T
t t t( ) : min ( )� � , � �t t .
Ìíîæåñòâî êàíàëîâ ïåðåõîäà s tT ( ) , êîòîðûì ñîîòâåòñòâóåò íàèìåíüøèé èç
âñåõ ìîìåíòîâ âûõîäà ìàðêåðîâ èç ïåðåõîäà, îïðåäåëÿåòñÿ ìíîæåñòâîì ïîðÿä-
êîâûõ íîìåðîâ ýòèõ êàíàëîâ
s t q E t tT T q T( ) { | [ ( )] ( )}� � �N � . (1)
Ââåäåì ïðåäèêàò Y : { ; }T��� 0 1 íà ìíîæåñòâå ïåðåõîäîâ T �T è ìíîæåñò-
âå ìîìåíòîâ âðåìåíè � ��t òàêèì îáðàçîì, ÷òî
( ( ) ) ( , )�T t t Y T t� � � � �1, ( ( ) ) ( , )�T t t Y T t� � � � � 0 .
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Âûõîä ìàðêåðîâ èç ïåðåõîäà T Y T t| ( , )� �1 ïðîèñõîäèò çà äâà ýòàïà: èçìåíÿ-
åòñÿ ìàðêèðîâêà ñåòè Ïåòðè (ñîñòîÿíèå åå ïîçèöèé) è èçìåíÿåòñÿ ñîñòîÿíèå ïå-
ðåõîäîâ. Ïîñêîëüêó âûõîä ìàðêåðîâ ìîæåò îñóùåñòâëÿòüñÿ èç íåñêîëüêèõ ïåðå-
õîäîâ, ñëåäóåò ïðîñóììèðîâàòü äîáàâëÿþùèåñÿ èç ïåðåõîäîâ T P�
ìàðêåðû.
Èìååì ñëåäóþùèå óðàâíåíèÿ, îïðåäåëÿþùèå ñîñòîÿíèå ñåòè Ïåòðè, êîòîðîå ÿâ-
ëÿåòñÿ ðåçóëüòàòîì âûõîäà ìàðêåðîâ èç ïåðåõîäîâ â ìîìåíò âðåìåíè �t :
� � � � � �
�
�P M t M t Y T t W s t
P P
T P
T P TP ( ) ( ) ( , ) | ( ) |, , (2)
� � � �
� �
� � �
� � �
T Y T t
E t
s t E t
E tT
T T
T
T | ( , )
( )
{ } | ( ) | | ( ) |,
( )
1
E t E t q s t s t E tT T q T T T( ) \ {[ ( )] | ( )} | ( ) | | ( ) |,� � �
�
�
�
(3)
ãäå | |� — êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà (êàðäèíàëüíîå ÷èñëî).
Îáîçíà÷èì ïðåîáðàçîâàíèå ñîñòîÿíèÿ âðåìåííîé ñåòè Ïåòðè (2), (3), ñâÿçàí-
íîå ñ âûõîäîì ìàðêåðîâ èç ïåðåõîäîâ, D t t t t � � � � �: ( ) ( ) ( ) ( )E M E M èëè
S S( ) ( ( ))� � t D t .
Óòâåðæäåíèå 1. Ðåçóëüòàò ïðåîáðàçîâàíèÿ D t ( ( ))S åñòü âñåãäà äîïóñòèìîå
ñîñòîÿíèå ñåòè Ïåòðè.
Ïóñòü S( )t — äîïóñòèìîå ñîñòîÿíèå ñåòè Ïåòðè, òîãäà M tP ( ) � 0 � �P P è
[ ( )]E tT q � 0 � �T T, � �q E tT1, ..., | ( ) | . Èç óðàâíåíèÿ (2) ñëåäóåò, ÷òî
M t M t
P P
� � �( ) ( ) 0 � �P P. Èç îïðåäåëåíèÿ (1) âûòåêàåò, ÷òî | ( ) | | ( ) |s t E tT T� ,
ïîýòîìó 1� � � | ( ) | | ( ) |E t E t
T T . Èç óðàâíåíèÿ (3) èìååì, ÷òî � �T T
[ ( )] [ ( )]E t E t
T q T q
� � � 0 � � � q E t
T
1, ..., | ( ) | . Òîãäà � � � � S S S( ) : ( ) ( ( ))t t D t
M t
P
� �( ) 0 � �P P è [ ( )]E t
T q
� � 0 � �T T , � � � q E t
T
1, ..., | ( ) | , ÷òî è òðåáîâà-
ëîñü äîêàçàòü. �
Äëÿ íîâîé ìàðêèðîâêè M t
P
�( ) ïðîâåðÿþòñÿ óñëîâèÿ çàïóñêà äëÿ âñåõ ïåðå-
õîäîâ. Ââåäåì ïðåäèêàò Z T: ;��� { }0 1 íà ìíîæåñòâå ïåðåõîäîâ T �T è ìíî-
æåñòâå ìîìåíòîâ âðåìåíè � ��t òàêèì îáðàçîì, ÷òî
( ( ) ) ( , ),� � � � � � �
P T M t W Z T t
P P T 1,
( ( ) ) ( , ),� � � � � � �
P T M t W Z T t
P P T 0 .
Òîãäà ñëåäóþùåå ìíîæåñòâî ïðåäñòàâëÿåò ìíîæåñòâî âñåõ ïåðåõîäîâ, äëÿ êî-
òîðûõ âûïîëíåíî óñëîâèå çàïóñêà �( ) | ( , ) ,� � � � �t T Z T t T{ }1 T .
Ïóñòü �( )� ��t .  îáùåì ñëó÷àå � � �( )� �t T T� , ãäå T� è T� — ìíîæåñò-
âà êîíôëèêòíûõ è íåêîíôëèêòíûõ ïåðåõîäîâ ñîîòâåòñòâåííî. Ñðåäè êîíôëèêòíûõ
ïåðåõîäîâ ìíîæåñòâà T� �� ñëåäóåò ðàçðåøèòü êîíôëèêò, â ðåçóëüòàòå ÷åãî ìíî-
æåñòâî T� ïðåîáðàçóåòñÿ âî ìíîæåñòâî
~
T T� �� , íå ñîäåðæàùåå êîíôëèêòîâ.
Îïðåäåëåíèå. Êîíôëèêòíûìè ÿâëÿþòñÿ ïåðåõîäû, äëÿ êîòîðûõ âûïîëíåíî
óñëîâèå çàïóñêà â òåêóùèé ìîìåíò âðåìåíè, èìåþùèå õîòÿ áû îäíó îáùóþ
âõîäíóþ ïîçèöèþ
T� � �� � � � � � � �
{ }T t T t T P T T( ) | ( ( ) \ ), � .
Îïðåäåëèì ìíîæåñòâî êîíôëèêòíûõ ïîçèöèé êàê ìíîæåñòâî ïîçèöèé, ÿâëÿ-
þùèõñÿ âõîäíûìè äëÿ áîëåå ÷åì îäíîãî ïåðåõîäà èç ìíîæåñòâà �( )�t :
P� �� � � �
{ }P P t| | ( ) | 1 .
Âñÿêàÿ êîíôëèêòíàÿ ïîçèöèÿ îïðåäåëÿåò ïîäìíîæåñòâî êîíôëèêòíûõ ïåðå-
õîäîâ � P P�
� �P P� , ïðè÷åì �
P
P
�
�
P
T
�
�� . Ðàçðåøèòü êîíôëèêò îçíà÷àåò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 167
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
âûáðàòü íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà { }� P : �
P
P
�
��
~
P�
� ,
~
P P� �� , è â êàæ-
äîì èç íèõ âûáðàòü îäèí è òîëüêî îäèí ïåðåõîä, çàïóñê êîòîðîãî îñóùåñòâëÿåò-
ñÿ â òåêóùèé ìîìåíò âðåìåíè.
Ðàññìîòðèì ñëó÷àé �
P
P
�
��
~
P�
� , ò.å. êîíôëèêòíûå ïîçèöèè íå èìåþò
îáùèõ ïåðåõîäîâ. Òîãäà êîíôëèêò ðàçðåøàåòñÿ òîëüêî âíóòðè êàæäîãî ïîäìíî-
æåñòâà ïåðåõîäîâ � P ñëåäóþùèì îáðàçîì. Îñóùåñòâëÿåòñÿ âûáîð ïåðåõîäîâ èç
ïîäìíîæåñòâà � P , èìåþùèõ íàèáîëüøåå çíà÷åíèå ïðèîðèòåòà cT è íåíóëåâóþ
âåðîÿòíîñòü çàïóñêà bT : � � � � �
�
� �
�
P P T T
T
TT b c c
P
{ }| , max0 . Åñëè ïåðåõîäîâ âî
ìíîæåñòâå �� P íåñêîëüêî, | |� �� P 1, òî èç íåãî âûáèðàþòñÿ ïåðåõîäû, èìåþùèå
çíà÷åíèå âåðîÿòíîñòè çàïóñêà bT �1. Îáîçíà÷èì ýòî ìíîæåñòâî ��� P :
�� � � � �� �P P TT b{ }| 1 . Åñëè | |�� �� P 1, òî åäèíñòâåííûé ïåðåõîä, ïðèíàäëå-
æàùèé ìíîæåñòâó ��� P , ÿâëÿåòñÿ ðåçóëüòàòîì ðàçðåøåíèÿ êîíôëèêòà. Åñëè ìíî-
æåñòâî ��� P ñîäåðæèò íåñêîëüêî ïåðåõîäîâ, | |�� �� P 1, òî âûáèðàåòñÿ ñëó÷àéíûì
îáðàçîì îäèí èç íèõ ñ âåðîÿòíîñòüþ 1/ | |��� P , êîòîðûé è ÿâëÿåòñÿ ðåçóëüòàòîì
ðàçðåøåíèÿ êîíôëèêòà. Åñëè ìíîæåñòâî �� ��� P , òî âûáîð îäíîãî èç ïåðåõîäîâ
ìíîæåñòâà �� P îñóùåñòâëÿåòñÿ ñëó÷àéíûì îáðàçîì ïî çíà÷åíèÿì âåðîÿòíîñòåé
çàïóñêà bT , T P� �� , ïðè÷åì bT
T P�
� �
�'
1.
Òàêèì îáðàçîì, ðàçðåøàåòñÿ êîíôëèêò ïî âñåì ïîäìíîæåñòâàì � P . Ìíî-
æåñòâî
~
T� ñîäåðæèò ïî îäíîìó ïåðåõîäó îò êàæäîãî ïîäìíîæåñòâà � P , è â ýòîì
ñëó÷àå êîëè÷åñòâî ýòèõ ïåðåõîäîâ ðàâíî êîëè÷åñòâó êîíôëèêòíûõ ïîçèöèé. Ñëå-
äîâàòåëüíî, |
~
| | |T P� �� ïðè óñëîâèè �
P
P
�
��
~
P�
� .
Ðàññìîòðèì ñëó÷àé �
P
P
�
��
~
P�
� , ò.å. ñóùåñòâóþò êîíôëèêòíûå ïîçèöèè,
èìåþùèå îáùèå ïåðåõîäû. Îáîçíà÷èì �
P
P
�
�
~
~
P�
� �. Äëÿ âñåõ êîíôëèêòíûõ ïî-
çèöèé P �
P� \ ~� êîíôëèêò ðàçðåøàåòñÿ, êàê â ñëó÷àå �
P
P
�
��
~
P�
� . Ñôîðìèðó-
åì ïîäìíîæåñòâî ïîçèöèé P P P M P WP T
T P
~ ,| ~, ( )� �� � �
�
�
�
!
"
#
�
� . Äëÿ âñåõ ïîçè-
öèé P P$ ~
� êîíôëèêò ðàçðåøàåòñÿ, êàê â ñëó÷àå �
P
P
�
��
~
P�
� . Äëÿ ðàçðåøåíèÿ
êîíôëèêòà ïîçèöèé P P� ~
� ñôîðìèðóåì ìíîæåñòâî ïåðåõîäîâ
� ~ | || ~� � �� � �
{ }T T P� 1 . Äëÿ êàæäîãî ïåðåõîäà T � �� ñëó÷àéíûì îáðàçîì âû-
áèðàåòñÿ îäíà ïîçèöèÿ. Ïîñëå ýòîãî ðàçðåøàåòñÿ êîíôëèêò äëÿ ìíîæåñòâà � P
ýòîé ïîçèöèè îïèñàííûì âûøå ñïîñîáîì.
Ìíîæåñòâî ïåðåõîäîâ, âûáðàííûõ äëÿ çàïóñêà, ñîñòîèò èç ìíîæåñòâà íå-
êîíôëèêòíûõ ïåðåõîäîâ è ìíîæåñòâà ïåðåõîäîâ, âûáðàííûõ â ðåçóëüòàòå ðàçðå-
øåíèÿ êîíôëèêòîâ. Îáîçíà÷èì � � � %� � �( )
~
t T T , � � �� �( ) ( )t t . Ââåäåì ïðåäè-
êàò X : ;T��� { }0 1 íà ìíîæåñòâå ïåðåõîäîâ T �T è ìíîæåñòâå ìîìåíòîâ âðå-
ìåíè � ��t òàêèì îáðàçîì, ÷òî
T t X T t� � � � � �� ( ) ( , ) 1, T t X T t$ � � � � �� ( ) ( , ) 0 .
Ðåçóëüòàò âõîäà ìàðêåðîâ â ïåðåõîäû ïðåäñòàâëÿåòñÿ óðàâíåíèÿìè:
� �P P M t M t W X T tP P P T
T P P
( ) ( ) ( , ),
\
� � �
� �
�
�
�
, (4)
� � � �T X T tT | ( , ) 1 E t
t R
E t t R
T
T T
T T T
( )
,
( ) .
� �
� � � �
� % � � � �
�
�
�
{ }
{ }
�
�
(5)
Îáîçíà÷èì ïðåîáðàçîâàíèå ñîñòîÿíèÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè
Ïåòðè (4), (5), ñâÿçàííîå ñ âõîäîì ìàðêåðîâ â ïåðåõîäû, D t t
� � � �: ( ) ( )E M
� � � �E M( ) ( )t t èëè D t
�( ( ))S .
Óòâåðæäåíèå 2. Ðåçóëüòàò ïðåîáðàçîâàíèÿ D t
�( ( ))S åñòü âñåãäà äîïóñòè-
ìîå ñîñòîÿíèå ñåòè Ïåòðè.
Ïóñòü S( )�t — äîïóñòèìîå ñîñòîÿíèå ñåòè Ïåòðè, òîãäà M t
P
� �( ) 0 � �P P è
[ ( ' )]E tT q � 0 � �T T, � � �q E tT1, ..., | ( ) | . Èç (5) ñëåäóåò, ÷òî � � � �T TT | �
[ ( )] [ ( )]E t E tT q T q� � � � 0 � � � q E tT1,... , | ( ) | è [ ( )]E t t RT q T� � � � 0 � � �� q E tT| ( ) |
�1,... , | ( ) |E tT , � � � �T TT | � , [ ( )]E t t RT T� � � �1 0 .
Ïîêàæåì, ÷òî â ðåçóëüòàòå âû÷èñëåíèé (4) âûïîëíåíî � �P P M tP ( )� � 0 .
Åñëè X T t( , )� � 0 , òî óäàëåíèÿ WP T, â (4) äëÿ òàêîãî ïåðåõîäà íå ïðîèñõîäèò.
Ïóñòü òåïåðü X T t( , )� �1, ÷òî âîçìîæíî òîëüêî ïðè T t� � �� ( ) . Ïîñêîëüêó
T t� � �� ( ) , ïåðåõîä T íå èìååò îáùèõ ïîçèöèé ñ äðóãèìè ïåðåõîäàìè ìíîæåñòâà
� �� ( )t . Ïîýòîìó â (4) X T t( , )� �1 òîëüêî äëÿ îäíîãî èç ïåðåõîäîâ
� | � ( \ ) ( �, )T T P P X T t� � � �
� 1, ñëó÷àéíî âûáðàííîãî äëÿ çàïóñêà. Äëÿ äðóãèõ ïå-
ðåõîäîâ X T t( , )� � 0 . Èìååì
M t M t W X T t M t WP P P T
T P P
P P T( ) ( ) ( , ) ( ),
\
, �� � �
� � � �
�
�
�
�
0 ,
òàê êàê X T t Z T t( �, ) ( �, )� � � � �1 1. Ñëåäîâàòåëüíî, â (4) � �P P M tP ( )� � 0 .
Èìååì � � � � �
S S S( ) : ( ) ( ( ))t t D t M tP ( )� � 0 � �P P è [ ( )]E tT q� � 0 � �T T ,
� � �q E tT1, ..., | ( ) | , ÷òî è òðåáîâàëîñü äîêàçàòü. �
Ïðåîáðàçîâàíèå D t
�( ( ))S ïðåäñòàâëÿåò ðåçóëüòàò îäíîãî âõîäà ìàðêåðîâ
â ïåðåõîäû ñåòè Ïåòðè. Êîëè÷åñòâî ìàðêåðîâ âî âõîäíûõ ïîçèöèÿõ ìíîãîêà-
íàëüíîãî ïåðåõîäà ìîæåò óäîâëåòâîðÿòü óñëîâèþ çàïóñêà íå îäíîãî, à íåñêîëü-
êèõ êàíàëîâ ýòîãî ïåðåõîäà. Ïîýòîìó âõîä ìàðêåðîâ â ïåðåõîäû äîëæåí îñóùå-
ñòâëÿòüñÿ ìíîãîêðàòíî äî òåõ ïîð, ïîêà åùå åñòü õîòÿ áû îäèí ïåðåõîä, êîòîðûé
çàïóñêàåòñÿ.  ïðîòèâíîì ñëó÷àå ìîæåò âîçíèêíóòü ñèòóàöèÿ, êîãäà óñëîâèå çà-
ïóñêà ïåðåõîäà âûïîëíåíî, íî îí íå çàïóùåí â ìîìåíò �t è â ðåçóëüòàòå ïðîäâè-
æåíèÿ âðåìåíè åãî ìîæíî áóäåò çàïóñòèòü òîëüêî â ìîìåíò t t� �, ÷òî ïðîòèâîðå-
÷èò ïðàâèëàì ôóíêöèîíèðîâàíèÿ âðåìåííûõ ñåòåé Ïåòðè.
Ìàêñèìàëüíîå êîëè÷åñòâî çàïóñêîâ ïåðåõîäà â ìîìåíò âðåìåíè �t îïðåäåëÿ-
åòñÿ âåëè÷èíîé min
( )
,P T
P
P T
M t
W�
��
�
�
!
"
#
, ãäå èñïîëüçóåòñÿ îïåðàöèÿ äåëåíèÿ öåëûõ ÷è-
ñåë. Ôàêòè÷åñêîå êîëè÷åñòâî m âõîäîâ ìàðêåðîâ â ïåðåõîäû îáóñëîâëåíî òðåáî-
âàíèåì äîñòèæåíèÿ ìàðêèðîâêè ñåòè Ïåòðè, â êîòîðîé íè îäèí èç ïåðåõîäîâ íå
çàïóñêàåòñÿ:
m D t Z T tm
T
: ( ) ( ( )) : ( , )
� & � �S 0 , (6)
ãäå ( )D D D D Dm
� � � �� � — ðåçóëüòàò m -êðàòíîãî ïðèìåíåíèÿ ïðå-
îáðàçîâàíèÿ D
.
Ïóñòü X T t i( , )� , i m� '1, , , — çíà÷åíèå ïðåäèêàòà â i-ì âõîäå ìàðêåðîâ
â ïåðåõîä T â ìîìåíò �t . Âåêòîð u t X T tT i
i
m
( ) ( , )� � �
�
�
1
ïðåäñòàâëÿåò êîëè÷åñòâî
âõîäîâ ìàðêåðîâ â ïåðåõîä T â ñåðèè âõîäîâ ìàðêåðîâ â ïåðåõîäû ( )D m
, ñîîò-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 169
âåòñòâóþùåé ìîìåíòó âðåìåíè �t . Òàê êàê óäàëåíèå ìàðêåðîâ ìîæåò ïðîèñõî-
äèòü â ðåçóëüòàòå íåñêîëüêèõ âõîäîâ ìàðêåðîâ â ïåðåõîä, â óðàâíåíèè (4) ñëåäó-
åò ïðîñóììèðîâàòü óäàëåííûå èç ïîçèöèé ìàðêåðû ïî âñåì çàïóñêàì ïåðåõîäîâ
M t M t W u tP P P T T
T P P
( ) ( ) ( ),
\
� � �
� �
�
�
�
. (7)
Îòìåòèì, ÷òî ìíîæåñòâî çíà÷åíèé { }u tT ( )� â îáùåì ñëó÷àå çàâèñèò îò ñëó-
÷àéíîãî âûáîðà ïåðåõîäà èç ìíîæåñòâà çàïóñêàþùèõñÿ ïåðåõîäîâ. Ðåçóëüòàò
ýòîãî ñëó÷àéíîãî âûáîðà õàðàêòåðèçóåò çíà÷åíèå ïðåäèêàòà X T t i( , )� â i-ì âõîäå
ìàðêåðîâ â ïåðåõîä. Íàïðèìåð, íà ðèñ. 2 ïåðåõîäû T T T T1 2 3 4, , , ÿâëÿþòñÿ êîí-
ôëèêòíûìè è ïîäìíîæåñòâî � P T T T T
2 1 2 3 4� { }, , , . Êîíôëèêò ðàçðåøàåòñÿ ñëó-
÷àéíûì âûáîðîì îäíîãî ïåðåõîäà èç ïîäìíîæåñòâà � P2
. Â çàâèñèìîñòè îò
ðàçðåøåíèÿ êîíôëèêòà ìåæäó ïåðåõîäàìè ïîäìíîæåñòâà � P2
â ðåçóëüòàòå ñåðèè
âõîäîâ ìàðêåðîâ â ïåðåõîä âîçìîæíî âîçíèêíîâåíèå ñëåäóþùèõ çíà÷åíèé
(è òîëüêî èõ) êîëè÷åñòâà âõîäîâ ìàðêåðîâ â ïåðåõîäû { }u u u uT T T T1 2 3 4
, , , :
{ }
{ }
1 3 0 0
1 1 0 1
, , , ,
, , , ,
{ }
{ }
{ }
0 4 0 0
0 2 0 1
0 0 1 0
, , , ,
, , , ,
, , , .
Íà ðèñ. 3 ïîäìíîæåñòâà � P1
è � P2
ïåðåñåêàþòñÿ. Êîíôëèêò ðàçðåøàåòñÿ
ñëó÷àéíûì âûáîðîì îäíîãî èç ýòèõ ïîäìíîæåñòâ, è çàòåì âûáîðîì èç íåãî îäíî-
ãî ïåðåõîäà. Ìíîæåñòâî âñåõ âîçìîæíûõ çíà÷åíèé êîëè÷åñòâà âõîäîâ ìàðêåðîâ
â ïåðåõîäû { }u u u u uT T T T T1 2 3 4 5
, , , , ñîñòîèò èç ñëåäóþùèõ çíà÷åíèé:
{ }
{ }
{ }
{ }
1 3 0 0 0
1 1 0 1 0
0 3 0 0 1
0 1 0 1 1
, , , , ,
, , , , ,
, , , , ,
, , , , ,
{ }
{ }
{ }
0 4 0 0 0
0 2 0 1 0
0 0 1 0 0
, , , , ,
, , , , ,
, , , , .
Òàêèì îáðàçîì, ôàêòè÷åñêîå êîëè÷åñòâî âõîäîâ ìàðêåðîâ â ïåðåõîäû îãðà-
íè÷åíî íå òîëüêî ñâåðõó — ìàêñèìàëüíûì èõ êîëè÷åñòâîì, íî è ñíèçó — óñëî-
âèåì (6), êîòîðîå ñ ó÷åòîì (7) ìîæíî ïðåîáðàçîâàòü ñëåäóþùèì îáðàçîì:
� �T T � � � � ( � � �
� �
�
�P T M t W P T M t W u tP P T P P T
T P P
T: ( ) : ( ) (, ,
\ �
) ,� (WP T
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
2
T1
T2
T3
T4
P1
P2
4
4
1
Ðèñ. 2. Ðàçðåøåíèå êîíôëèêòíûõ ïåðåõîäîâ
â ñëó÷àå íåïåðåñåêàþùèõñÿ ìíîæåñòâ �P
�P2
T5
2
T1
T2
T3
T4
P1
P2
4
1
4
Ðèñ. 3. Ðàçðåøåíèå êîíôëèêòíûõ ïåðåõîäîâ
â ñëó÷àå ïåðåñåêàþùèõñÿ ìíîæåñòâ �P
�P2
�P1
( � � � � � �
(
�
�P T W u t M t WP T
T P P
T P P T: ( ) ( ),
\
,
�
( � � � � � �
� �
�P T W u t M t WP T
T P P
T
T P P
P P T: ( ) max ( ( ),
\ \
,
�
�
) .
Èìååì ñëåäóþùåå óñëîâèå äëÿ êîëè÷åñòâà âõîäîâ ìàðêåðîâ â ïåðåõîäû :
{ }u t u t
M t
W
T T
P T
P
P T
( ) : ( ) min
( )
,
� � �
��
�
�
!
"
#
)
*
+
++
,
�
-
.
..
�
� � � � � � �
� �
�P T W u t M t WP T
T P P
T
T P P
P P T: ( ) max ( ( ),
\ \
,
�
�
)
)
*
+
+
,
-
.
.
.
Âõîä ìàðêåðîâ â ïåðåõîäû T t� � �� ( ) îñóùåñòâëÿåòñÿ çà äâà ýòàïà: èçìåíÿåò-
ñÿ ñîñòîÿíèå âûõîäíûõ ïîçèöèé ïåðåõîäîâ è èçìåíÿåòñÿ ñîñòîÿíèå ïåðåõîäîâ.
Ñóììèðóÿ ìàðêåðû, óáûâàþùèå èç ïîçèöèè â ïåðåõîäû T P Ð�
\ � , ïîëó÷àåì
óðàâíåíèÿ, îïðåäåëÿþùèå ïðåîáðàçîâàíèå ( )D m
ñîñòîÿíèÿ ñåòè Ïåòðè â ìî-
ìåíò âðåìåíè �t :
� � � � �
� �
�
�P M t M t W u tP P P T T
T P P
P ( ) ( ) ( ),
\�
, (8)
� � � �
� � � �
T E t
t R t R
T
T T
u t
T
T
T ( )
(
( )
{ } { }�� �
� �
'
� t
E t t R t R
T T T
u t
T
T
) ,
( )
( )
� �
� � � � � �� �
� �
{ } { }
'
� ( ) .� � �
�
�
�
t
(9)
Êîìïîçèöèÿ ïðåîáðàçîâàíèé ( )D Dm
� ïðåäñòàâëÿåò ïðåîáðàçîâàíèå
ñåòè Ïåòðè, ñîîòâåòñòâóþùåå ìîìåíòó âðåìåíè �t . Ðàññìîòðèì ïîñëåäîâàòåëü-
íîñòü ìîìåíòîâ âðåìåíè tn , n �1 2, ,� . Òîãäà, ïîëàãàÿ â (4), (5) è (8), (9) t tn�
1
è � �t tn , ïîëó÷àåì ñëåäóþùóþ ñèñòåìó óðàâíåíèé, ïðåäñòàâëÿþùóþ ôîðìàëü-
íîå îïèñàíèå ôóíêöèîíèðîâàíèÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè ñ ìíîãî-
êàíàëüíûìè è êîíôëèêòíûìè ïåðåõîäàìè:
t E t t t
t D
n
T q
T n q n n
m
� )
*
+
,
-
. �
�
min min [ ( )] , ,
( ) ( ) (
1 1
0S S( )),
( ) ( ) ( ( ( )),
, , ... ,
t
t D D t
n
n
m
n
0
1
1 2
S S�
�
�
�
�
(10)
ãäå D îïèñûâàåòñÿ óðàâíåíèÿìè (4) è (5), à ( )D m
— óðàâíåíèÿìè (8) è (9),
m îïðåäåëÿåòñÿ óñëîâèåì (6).
Îòìåòèì, ÷òî ñèñòåìà óðàâíåíèé (10) îòëè÷àåòñÿ îò óðàâíåíèé ñåòè Ïåòðè
ñ äåòåðìèíèðîâàííûìè âðåìåííûìè çàäåðæêàìè íàëè÷èåì óðàâíåíèÿ, îäíîçíà÷-
íî îïðåäåëÿþùåãî ñëåäóþùèé ìîìåíò âðåìåíè ïî òåêóùåìó ñîñòîÿíèþ ïåðåõî-
äîâ, è òðåáîâàíèåì ê ôàêòè÷åñêîìó êîëè÷åñòâó âõîäîâ â ïåðåõîäû (6), îáåñïå÷è-
âàþùèì äîñòèæåíèå ñîñòîÿíèÿ ñåòè Ïåòðè, ïðè êîòîðîì äëÿ âñåõ åå ïåðåõîäîâ
íå âûïîëíÿåòñÿ óñëîâèå çàïóñêà.
ÀÍÀËÈÇ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÑËÎÆÍÎÑÒÈ ÓÐÀÂÍÅÍÈÉ ÑÎÑÒÎßÍÈÉ
ÑÒÎÕÀÑÒÈ×ÅÑÊÎÉ ÑÅÒÈ ÏÅÒÐÈ Ñ ÂÐÅÌÅÍÍÛÌÈ ÇÀÄÅÐÆÊÀÌÈ,
ÌÍÎÃÎÊÀÍÀËÜÍÛÌÈ ÏÅÐÅÕÎÄÀÌÈ È ÈÍÔÎÐÌÀÖÈÎÍÍÛÌÈ ÑÂßÇßÌÈ
Ñèñòåìà óðàâíåíèé (10) ÿâëÿåòñÿ ìàòåìàòè÷åñêèì îïèñàíèåì ñëåäóþùåãî àëãîðèòìà.
— Ôîðìèðîâàòü äàííûå î ñòðóêòóðå è íà÷àëüíîì ñîñòîÿíèè ñåòè Ïåòðè
(íà÷àëüíûé ìîìåíò âðåìåíè t0 ; ìíîæåñòâà ïîçèöèé P, ïåðåõîäîâ T, âõîäíûõ ñâÿ-
çåé
T, âûõîäíûõ ñâÿçåé T
; íà÷àëüíîå ñîñòîÿíèå ïîçèöèé è ïåðåõîäîâ
S M E( ) ( ( ), ( ))t t t0 0 0� ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 171
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
— Îñóùåñòâèòü íà÷àëüíûé çàïóñê ïåðåõîäîâ (ïðåîáðàçîâàíèå ( ) ( ( ))D tm
S 0 ).
— Ïîêà íå èñ÷åðïàíî âðåìÿ ìîäåëèðîâàíèÿ tn � timeMod , ïðîäâèíóòü âðå-
ìÿ â ìîìåíò áëèæàéøåãî ñîáûòèÿ t E tn
T q
T n q� )
*
+
,
-
.
min min [ ( )] ,1 îñóùåñòâèòü
ïðåîáðàçîâàíèå ñîñòîÿíèÿ ñåòè Ïåòðè ( ) ( ( ( ))D D tm
n
S 1 .
— Âûâåñòè ðåçóëüòàòû ìîäåëèðîâàíèÿ.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü ýòîãî àëãîðèòìà îïðåäåëÿåòñÿ êîëè÷åñòâîì øà-
ãîâ äî äîñòèæåíèÿ óñëîâèÿ tn � timeMod , ñëîæíîñòüþ ïîèñêà ñëåäóþùåãî ìî-
ìåíòà âðåìåíè, ñëîæíîñòüþ ïðåîáðàçîâàíèé ( )D m
è D ñîñòîÿíèÿ ñåòè Ïåòðè.
Êîëè÷åñòâî øàãîâ ðàâíî ñðåäíåìó êîëè÷åñòâó ñîáûòèé â åäèíèöó âðåìåíè,
óìíîæåííîìó íà timeMod . Îáîçíà÷èì �T ñðåäíåå êîëè÷åñòâî àêòèâíûõ êàíàëîâ
ïåðåõîäà T , V
T T
�
�
mean
T
� ñðåäíåå êîëè÷åñòâî àêòèâíûõ êàíàëîâ ïåðåõîäà T �T.
Òîãäà êîëè÷åñòâî øàãîâ îöåíèâàåòñÿ âåëè÷èíîé O V( | | )� �T timeMod . Ñëîæíîñòü
ïðåîáðàçîâàíèÿ D , êàê ñëåäóåò èç óðàâíåíèé (2), (3), îïðåäåëÿåòñÿ âåëè÷èíîé
| | | |T
T
� )
*
+ ,
-
.
�
mean
T
T V , ãäå mean
T
T
�
T
| | — ñðåäíåå êîëè÷åñòâî âûõîäíûõ ïîçèöèé
ïåðåõîäà. Ñëîæíîñòü ïðåîáðàçîâàíèÿ D
, êàê ñëåäóåò èç óðàâíåíèé (4), (5), îöåí-
íèâàåòñÿ âåëè÷èíîé O T V K
T
| | | |T
T
� )
*
+ ,
-
. )
*
+
,
-
.
�
mean 2 , ãäå mean
T
T
�
T
| | — ñðåäíåå
êîëè÷åñòâî âõîäíûõ ïîçèöèé ïåðåõîäà, K � mean | |T� — ñðåäíåå êîëè÷åñòâî
êîíôëèêòíûõ ïåðåõîäîâ. Òàê êàê ñðåäíåå êîëè÷åñòâî âõîäîâ â ïåðåõîäû ìåíüøå
ñðåäíåãî êîëè÷åñòâà àêòèâíûõ êàíàëîâ ïåðåõîäà, ñëîæíîñòü ïðåîáðàçîâàíèÿ
( )D m
ìîæíî îöåíèòü âåëè÷èíîé O V T V V K
T
� � )
*
+ ,
-
. � �)
*
+
,
-
.
�
| | | | | |T T
T
2 2mean .
Îòñþäà âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà îöåíèâàåòñÿ âåëè÷èíîé
O V T V V T
T T
| | | | | | | |T T
T T
2� � � )
*
+ � �
�
�
time Mod mean mean � � � ,
-
.
)
*
+
,
-
.V V K2 2| |T . Ñëå-
äîâàòåëüíî, âû÷èñëèòåëüíàÿ ñëîæíîñòü óðàâíåíèé (10) çàâèñèò ïðè çàäàííîì
âðåìåíè ìîäåëèðîâàíèÿ ïîëèíîìèàëüíî îò êîëè÷åñòâà ïåðåõîäîâ | |T , à çàäà÷à
ñîñòàâëåíèÿ óðàâíåíèé îòíîñèòñÿ ê Ð-êëàññó ñëîæíîñòè.
ÓÐÀÂÍÅÍÈß ÑÎÑÒÎßÍÈÉ ÑÒÎÕÀÑÒÈ×ÅÑÊÎÉ ÂÐÅÌÅÍÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
 ÌÀÒÐÈ×ÍÎÌ ÂÈÄÅ
Ðàññìîòðèì èçìåíåíèå ñîñòîÿíèÿ ñåòè Ïåòðè, îïèñàííîå ïðåîáðàçîâàíèåì
( )D Dm
� . Ìàðêèðîâêà ñåòè Ïåòðè â ìîìåíò tn èçìåíÿåòñÿ â ñîîòâåòñòâèè
ñ óðàâíåíèÿìè (2), (8). Ïîäñòàâëÿÿ (2) â (8), ïîëó÷àåì ñëåäóþùåå óðàâíåíèå:
� � � �
�
�P M t M t Y T t W s tP n P n n T P T n
T P
P ( ) ( ) ( , ) | ( ) |,1 1
� �
�
� Z T t W u tn P T T n
T P P
( , ) ( ),
\ �
. (11)
Ñîñòîÿíèå ïåðåõîäîâ ñåòè Ïåòðè â ìîìåíò tn èçìåíÿåòñÿ â ñîîòâåòñòâèè
ñ óðàâíåíèÿìè (3), (9), îáúåäèíÿÿ êîòîðûå, ïîëó÷àåì
� � �T Y T tnT | ( , ) 1 s t q E t tT n T n q T n( ) | [ ( )] ( )
� �1 1 1{ }� ;
E t
s t E t
E t E tT n
T n T n
T n T n
�
� � �
( )
| ( ) | | ( ) | ,
( ) \ [ (
{ }
{
1 1
1
� � �
�
�
� 1 1 1 1)] | ( ) | ( ) | | ( ) | ;q T n T n T nq s t s t E t}
(12)
� � � �
T Z T t E t
t R t R
n T n
n T n T
u tT n
T | ( , ) ( )
( )
1
{ } { }�� �
� �
� �� �
� �
� � �
�T n
T n n T n T
u t
t
E t t R t R
T n
( ) ,
( )
( )
{ } { }
� � �
�
�
�
�T nt( ) .
(13)
Êîëè÷åñòâî àêòèâíûõ êàíàëîâ àêòèâíîãî ïåðåõîäà ðàâíî ìîùíîñòè ìíîæåñòâà
| ( ) |E tT n , à íåàêòèâíîãî ïåðåõîäà — íóëþ. Ïóñòü �T t( ) — êîëè÷åñòâî àêòèâíûõ
êàíàëîâ ïåðåõîäà T â ìîìåíò t, òîãäà
�
�
�
T
T T
T
t
E t
( )
| ( ) | , ,
, .
�
� �
� �
�
�
�0
(14)
Èç óðàâíåíèé (12), (13) è îïðåäåëåíèÿ (14) ñëåäóåò, ÷òî èçìåíåíèå êîëè÷åñ-
òâà àêòèâíûõ êàíàëîâ ïðîèñõîäèò ñîãëàñíî óðàâíåíèþ
� �T T � �T n T n n T n n T nt t Y T t s t Z T t u t( ) ( ) ( , ) | ( ) | ( , ) ( )�
� �
1 1 . (15)
Óðàâíåíèå (15) èìååò î÷åâèäíûé ñìûñë: êîëè÷åñòâî àêòèâíûõ êàíàëîâ ïåðå-
õîäà â ìîìåíò tn ðàâíî êîëè÷åñòâó êàíàëîâ â ìîìåíò âðåìåíè tn
1 ïëþñ êîëè÷åñ-
òâî âõîäîâ â ïåðåõîä è ìèíóñ êîëè÷åñòâî âûõîäîâ èç íåãî.
Ïóñòü â íà÷àëüíûé ìîìåíò âðåìåíè t0 ñîñòîÿíèå ñåòè Ïåòðè
S M E( ) ( ( ), ( ))t t t0 0 0� . Ñîñòàâèì óðàâíåíèÿ (11), (15) äëÿ âñåõ ìîìåíòîâ t j ,
j n�1, ..., , è ïðîñóììèðóåì
� �P P M t M t W Y T t s tP n P T P
j
n
j T j
T P
( ) ( ) ( , ) | ( ) |,
� �
�
�
��
0
1
1
�
� �
� �W Z T t u tP T
T P P
j T j
j
n
,
\
( , ) ( )
� 1
, (16)
� �T T � �T n T j T j
j
n
j Tt t Y T t s t Z T t u( ) ( ) ( , ) | ( ) | ( , ) (
�
� �
�
�0 1
1
t j
j
n
).
�
�
1
(17)
Çàìåòèì, ÷òî Z T t u t tj T j
j
n
T n( , ) ( ) ( )� �
�
�
1
� îïèñûâàåò îáùåå êîëè÷åñòâî âõî-
äîâ â ïåðåõîä T çà âåñü èíòåðâàë âðåìåíè [ , ]t tn0 , à Y T t s tj T j
j
n
( , ) | ( ) |� �
�
� 1
1
� �T nt( ) îïèñûâàåò îáùåå êîëè÷åñòâî âûõîäîâ èç ïåðåõîäà T . Âûðàçèì êîëè÷åñò-
âî âûõîäîâ èç ïåðåõîäà T êîëè÷åñòâîì âõîäîâ â ïåðåõîä T èç óðàâíåíèÿ (17)
è ïîäñòàâèì â (16). Òîãäà óðàâíåíèÿ (16), (17) ïðèíèìàþò ñëåäóþùèé âèä:
� �P P M t W t M t W tP n T P T n
T P
P T P T
T P
( ) ( ) ( ) ( ), ,
)
*
+
+
,
� �
� �� �0 0
-
.
.
�
� �
�
� �
� �W t W tT P T n
T P
P T
T P P
T n, ,
\
( ) ( )� �
�
, (18)
� �T T � � � �T n T n T T nt t t t( ) ( ) ( ) ( )�
0 . (19)
Óðàâíåíèÿ (18), (19) èìåþò ñëåäóþùèé ñìûñë. Ïðè âõîäå ìàðêåðîâ â ïåðå-
õîä ìàðêåðû èç åãî âõîäíûõ ïîçèöèé óäàëÿþòñÿ è çàíèìàþò åãî êàíàëû (óâåëè-
÷èâàåòñÿ êîëè÷åñòâî àêòèâíûõ êàíàëîâ ïåðåõîäà). Ïðè âûõîäå èç ïåðåõîäà ìàð-
êåðû ïîêèäàþò åãî àêòèâíûå êàíàëû è äîáàâëÿþòñÿ â åãî âûõîäíûå ïîçèöèè.
Ñóììà M t W t
P T P T
T P
( ) ( ),
�
� � ïðåäñòàâëÿåò îáùåå êîëè÷åñòâî ìàðêåðîâ ïî-
çèöèè â ìîìåíò âðåìåíè t, êîòîðîå ñîñòîèò èç ìàðêåðîâ, íàõîäÿùèõñÿ â ïîçèöèè,
è ìàðêåðîâ, íàõîäÿùèõñÿ âî âõîäíûõ ïåðåõîäàõ ïîçèöèè (èõ ïîñòóïëåíèå â ïî-
çèöèþ ïëàíèðóåòñÿ â ñëåäóþùèå ìîìåíòû âðåìåíè). Òîãäà óðàâíåíèå (18) ïðè-
îáðåòàåò òàêîé ñìûñë: îáùåå êîëè÷åñòâî ìàðêåðîâ â ïîçèöèè â ëþáîé ìîìåíò
âðåìåíè ðàâíî îáùåìó êîëè÷åñòâó ìàðêåðîâ â ýòîé ïîçèöèè â íà÷àëüíûé ìîìåíò
âðåìåíè ïëþñ êîëè÷åñòâî ìàðêåðîâ, äîáàâëåííûõ â ïîçèöèþ â òå÷åíèå âñåãî èí-
òåðâàëà âðåìåíè [ , ]t tn0 , ìèíóñ êîëè÷åñòâî ìàðêåðîâ, óäàëåííûõ èç ïîçèöèè
â òå÷åíèå âñåãî èíòåðâàëà âðåìåíè [ , ]t tn0 .
Äëÿ òîãî ÷òîáû çàïèñàòü (18) â ìàòðè÷íîì âèäå, ââåäåì ñëåäóþùèå ìàòðèöû
è âåêòîðû:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 173
a
W T P
T P
P T
T P
,
, , ,
, ,
�
�
$
�
�
� 0
a
W T P P
T P P
P T
P T
,
, , \ ,
, \ .
�
�
$
�
�
�
�
�0
(20)
Îáúåäèíèâ óðàâíåíèÿ (19), (20), ïîëó÷èì ôóíäàìåíòàëüíûå óðàâíåíèÿ âðå-
ìåííîé ñåòè Ïåòðè â ìàòðè÷íîì âèäå
M a v M a v a a( ) ( ) ( ( ) ( )) ( ) ( )t t t t t tn n n n �
� � �
�
0 0 � � , (21)
� �( ) ( ) ( ) ( )t t t tn n n�
v v 0 , (22)
ãäå M( ) ( )t M tP� — âåêòîð ìàðêèðîâêè ïîçèöèé â ìîìåíò âðåìåíè t ;
v( ) ( )t tT� � — âåêòîð êîëè÷åñòâà àêòèâíûõ êàíàëîâ ïåðåõîäîâ; a � || ||
,
a
P T
—
ìàòðèöà âûõîäîâ; a
� || ||,aP T — ìàòðèöà âõîäîâ; �( ) || ( ) ||t tT� � — âåêòîð
êîëè÷åñòâà âõîäîâ â ïåðåõîäû çà ïåðèîä âðåìåíè [ , ]t t0 ; � ( ) || ( ) ||t tT� � —
âåêòîð êîëè÷åñòâà âûõîäîâ èç ïåðåõîäîâ çà ïåðèîä âðåìåíè [ , ]t t0 .
Óðàâíåíèå (21) ìîæíî ïðåîáðàçîâàòü ê âèäó
M M a v v a a( ) ( ) ( ( ) ( )) ( ) ( )t t t t tn n n
�
�
�
0 0 � . (23)
Èç (23) ñëåäóåò
/ /M a v a a � �
�
( ) ( )� t . (24)
Óðàâíåíèå (24) îïèñûâàåò èçìåíåíèå îáùåãî êîëè÷åñòâà ìàðêåðîâ ïîçèöèé
ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè ñ ìíîãîêàíàëüíûìè ïåðåõîäàìè, èç íåãî
ñëåäóåò, ÷òî îáùåå êîëè÷åñòâî ìàðêåðîâ ïîçèöèé ñåòè Ïåòðè îäíîçíà÷íî îïðå-
äåëÿåòñÿ ìàòðèöåé a a a�
è âåêòîðîì îáùåãî êîëè÷åñòâà âõîäîâ â ïåðåõî-
äû ñåòè Ïåòðè â òå÷åíèå èíòåðâàëà âðåìåíè [ , ]t t0 .
Ââåäåì îáîçíà÷åíèå � �
P P T P T
T P
t M t W t( ) ( ) ( ),�
�
� , èëè â âåêòîðíîì âèäå
�( ) ( ) ( )t M t t� � a v . Áóäåì íàçûâàòü �( )t ðàñøèðåííîé ìàðêèðîâêîé âðåìåí-
íîé ñåòè Ïåòðè. Òîãäà ìàòðè÷íûå óðàâíåíèÿ (21), (22) ïðèíèìàþò âèä
� � �( ) ( ) ( ) ( )t t tn n�
�
0 a a , (25)
� �( ) ( ) ( ) ( )t t t tn n n�
v v 0 . (26)
Óðàâíåíèå (25) èìååò âèä ôóíäàìåíòàëüíîãî óðàâíåíèÿ áàçîâîé ñåòè Ïåòðè,
ê êîòîðîìó ïðèìåíèìû èçâåñòíûå ìåòîäû èññëåäîâàíèÿ ôóíêöèîíàëüíûõ è
ñòðóêòóðíûõ ñâîéñòâ ñåòè Ïåòðè [1, 13]: äîñòèæèìîñòü, ñîõðàíÿåìîñòü, îãðàíè-
÷åííîñòü, àêòèâíîñòü, óïðàâëÿåìîñòü, ñòðóêòóðíàÿ àêòèâíîñòü è äð.
Çàìåòèì, ÷òî óðàâíåíèå (25) îòëè÷àåòñÿ îò èçâåñòíûõ ôóíäàìåíòàëüíûõ
óðàâíåíèé ñåòè Ïåòðè [13, 1] òåì, ÷òî â íåì âìåñòî îáû÷íîé ìàðêèðîâêè èñïîëü-
çóåòñÿ ïîíÿòèå ðàñøèðåííîé ìàðêèðîâêè, âêëþ÷àþùåé ìàðêåðû íå òîëüêî â ïî-
çèöèÿõ, íî è â ïåðåõîäàõ ñåòè Ïåòðè. Óðàâíåíèå (26) õàðàêòåðèçóåò êîëè÷åñòâî
âûõîäîâ èç ïåðåõîäîâ ñåòè Ïåòðè, ñîîòâåòñòâóþùåå ìàðêèðîâêå è êîëè÷åñòâó
âõîäîâ. Êîëè÷åñòâî çàâåðøåííûõ çàïóñêîâ ïåðåõîäà ðàâíî íàèìåíüøåìó èç çíà-
÷åíèé � T nt( ) è �T nt( ) : � � �T n T n T nt t t( ) min ( ), ( )� { }.
Åñëè êîëè÷åñòâî âõîäîâ â ïåðåõîäû ðàâíî êîëè÷åñòâó âûõîäîâ èç íèõ, òî
� �( ) ( ) ( )t t tn n n� � � . Êàê ñëåäóåò èç (26), ýòî óñëîâèå ýêâèâàëåíòíî óñëîâèþ
v v( ) ( )t tn � 0 . Òîãäà èç îïðåäåëåíèÿ ðàñøèðåííîé ìàðêèðîâêè èìååì
�
� � �
( ) ( ) ( ),
( ) ( ) ( ) ( ) (
t t t
t t t t
n n n
n
� �
� � �
M a v
M a v0 0 0 t t t
t t
n
n
0 0
0
) ( ) ( ) ,
( ) ( ).
�
� �
�
�
�
�
M M M
v v
/ /� (27)
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Óðàâíåíèå (25) ìîæíî çàïèñàòü â âèäå / � �� �a ( )tn , ãäå a a a�
. Òîã-
äà èç (27) è óñëîâèÿ � � �( ) ( ) ( )t t tn n n� � ñëåäóåò
/M a� � �( )tn . (28)
Óðàâíåíèå (28), ïîëó÷åííîå ïðè óñëîâèè, ÷òî êîëè÷åñòâî âõîäîâ â ïåðåõîäû
ðàâíî êîëè÷åñòâó âûõîäîâ èç íèõ â òå÷åíèå âðåìåíè [ , ]t t0 , àíàëîãè÷íî óðàâíå-
íèÿì, ïîëó÷åííûì â [13, 14]. Äåéñòâèòåëüíî, â ýòèõ ðàáîòàõ èñïîëüçóåòñÿ ïîíÿ-
òèå âåêòîðà êîëè÷åñòâà çàïóñêîâ ïåðåõîäîâ, ÷òî íå ïîçâîëÿåò ðàçëè÷àòü êîëè÷åñ-
òâî âõîäîâ â ïåðåõîäû è êîëè÷åñòâî âûõîäîâ èç íèõ.
Ïîêàæåì, ÷òî èç óðàâíåíèé (25), (26) ìîæíî ïîëó÷èòü óðàâíåíèÿ ñòîõàñòè-
÷åñêîé âðåìåííîé ñåòè Ïåòðè áåç èíôîðìàöèîííûõ ñâÿçåé, óðàâíåíèÿ áàçîâîé
ñåòè Ïåòðè [13], óðàâíåíèÿ âðåìåííîé ñåòè Ïåòðè ñ äåòåðìèíèðîâàííûìè âðå-
ìåííûìè çàäåðæêàìè [14].
Åñëè ñåòü Ïåòðè íå ñîäåðæèò èíôîðìàöèîííûõ ñâÿçåé, òî ìíîæåñòâî èíôîðìà-
öèîííûõ äóã I �� , îòêóäà ñëåäóåò, ÷òî â îïðåäåëåíèè ìàòðèöû âõîäîâ (20)
P � �� . Òàêèì îáðàçîì, óðàâíåíèÿ (25), (26) îïèñûâàþò ñòîõàñòè÷åñêóþ âðåìåí-
íóþ ñåòü Ïåòðè áåç èíôîðìàöèîííûõ ñâÿçåé ïðè P � �� .
Åñëè â óðàâíåíèÿõ (25), (26) ïðèíÿòü, ÷òî âñå âðåìåííûå çàäåðæêè ðàâíû
íóëþ, òî � �T T E tT ( ) � � . Ñëåäîâàòåëüíî, �T t( ) � 0 , à çíà÷èò, �( ) ( )t t� M è
� �( ) ( )t tn n� . Èìååì
M M a a( ) ( ) ( ) ( )t t tn n�
�
0 � , (29)
ãäå � � �( ) ( ) ( )t t tn n n� � — êîëè÷åñòâî çàïóñêîâ ïåðåõîäîâ.
Óðàâíåíèå (29) ñîâïàäåò ñ óðàâíåíèÿìè, îïèñàííûìè â [13], åñëè ïðèíÿòü îáîçíà-
÷åíèÿ M M( )t n n� , M M( )t0 0� , A a aT �
, �( )t n � x. Òîãäà M M A xn � �0
T ,
ãäå M0 è Mn — íà÷àëüíàÿ è òåêóùàÿ ìàðêèðîâêè ñåòè Ïåòðè ñîîòâåòñòâåííî,
A — ìàòðèöà èíöèäåíòíîñòè, x — âåêòîð êîëè÷åñòâà çàïóñêîâ ïåðåõîäîâ.
Åñëè ïðèíÿòü â óðàâíåíèÿõ (25), (26), ÷òî âñå âðåìåííûå çàäåðæêè äåòåðìè-
íèðîâàííûå, òî t t n tn �
�0 1( ) / , ãäå / t — ïðîäîëæèòåëüíîñòü îäíîãî òàêòà
âðåìåíè. Óðàâíåíèå (25) ñ ó÷åòîì îïðåäåëåíèÿ ðàñøèðåííîé ìàðêèðîâêè ïðåîá-
ðàçóåì ê âèäó
M M a a a v v( ) ( ) ( ) ( ) ( ( ) ( ))t t t t tn n n
�
�
�
0 0� .
Îòñþäà
M M a v v a( ) ( ) ( ( ) ( ) ( )) ( )t t t t t tn n n n
� �
�
0 0� � . (30)
Âåêòîð êîëè÷åñòâà âõîäîâ â ïåðåõîäû �( )tn â ðàáîòå [14] íàçûâàåòñÿ «âåêòî-
ðîì ñ÷åòà çàïóñêîâ ïåðåõîäîâ». Âåêòîð �( ) ( ) ( )t t tn n
v v 0 ðàâåí âåêòîðó êîëè-
÷åñòâà âûõîäîâ èç ïåðåõîäîâ � ( )tn , êàê ñëåäóåò èç óðàâíåíèÿ (26), è â ðàáîòå [14]
íàçûâàåòñÿ «âåêòîðîì ñ÷åòà çàâåðøåíèé ïåðåõîäîâ». Óðàâíåíèå (30) ïðèíèìàåò âèä
M M a a( ) ( ) ( ) ( )t t t tn n n
� �
�
0 � � . (31)
Îáîçíà÷èì ñîãëàñíî [14] M( )n ìàðêèðîâêó ñåòè Ïåòðè â òàêòå ñ íîìåðîì n,
M( )0 íà÷àëüíóþ ìàðêèðîâêó ñåòè Ïåòðè, �
� � ( )tn âåêòîð ñ÷åòà çàâåðøåíèé ïå-
ðåõîäîâ, �
� �( )tn âåêòîð ñ÷åòà çàïóñêà ïåðåõîäîâ, â ðåçóëüòàòå ÷åãî óðàâíå-
íèå (31) ïðèìåò âèä
M M a a( ) ( )n � � �
�
0 � � . (32)
Óðàâíåíèå (32) ñîâïàäàåò ñ ôóíäàìåíòàëüíûì óðàâíåíèåì äåòåðìèíèðîâàí-
íîé âðåìåííîé ñåòè Ïåòðè, ïîëó÷åííûì â [14].
Òàêèì îáðàçîì, óðàâíåíèÿ (25), (26) ïðåäñòàâëÿþò ôóíäàìåíòàëüíûå óðàâ-
íåíèÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè, âêëþ÷àþùèå, êàê ÷àñòíûé ñëó÷àé,
óðàâíåíèÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè áåç èíôîðìàöèîííûõ ñâÿçåé,
óðàâíåíèÿ áàçîâîé ñåòè Ïåòðè è äåòåðìèíèðîâàííîé âðåìåííîé ñåòè Ïåòðè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 175
Çàìåòèì, ÷òî ìàòðè÷íàÿ çàïèñü óðàâíåíèé ñîñòîÿíèé óäîáíà äëÿ èññëåäîâà-
íèÿ ñòðóêòóðíûõ è ôóíêöèîíàëüíûõ ñâîéñòâ ñåòè Ïåòðè. Àëãîðèòìè÷åñêàÿ ðåà-
ëèçàöèÿ ýòèõ óðàâíåíèé ïðèâîäèò ê âû÷èñëåíèÿì, ñëîæíîñòü êîòîðûõ
O( | | | | | | | | )P P T T � 2 ïðè óñëîâèè, ÷òî èçâåñòåí âåêòîð êîëè÷åñòâà âõîäîâ
â ïåðåõîäû �( )tn . Îäíàêî ïîèñê äîïóñòèìîãî âåêòîðà �( )tn ÿâëÿåòñÿ êîìáèíà-
òîðíîé çàäà÷åé è îòíîñèòñÿ ê NP-êëàññó ñëîæíîñòè. Ïîýòîìó äëÿ àëãîðèòìè÷åñ-
êîé ðåàëèçàöèè ðåêîìåíäóåòñÿ èñïîëüçîâàòü óðàâíåíèÿ ñîñòîÿíèé (10).
Åñëè det (( ) ( ))a a a a
�T 0, òî ìàòðè÷íûå óðàâíåíèÿ äîïóñêàþò ðå-
øåíèå îáðàòíîé çàäà÷è. Ïóñòü çàäàíû âåêòîðû M( )tn , M( )t0 , v( )tn , v( )t0 . Òîã-
äà âåêòîð �( )tn ìîæíî íàéòè ñëåäóþùèì îáðàçîì:
�( ) (( ) ( )) ( ) ( ( ) ( ) (t t tn n�
�
a a a a a a M M aT T1
0 v v( ) ( )))t tn
0 .
Åñëè êîìïîíåíòû �( )tn íåöåëûå èëè îòðèöàòåëüíûå, òî ñîñòîÿíèå M( )tn ,
v( )tn íåäîñòèæèìî. Åñëè êîìïîíåíòû �( )tn öåëûå è íåîòðèöàòåëüíûå, òî íåîáõî-
äèìî èññëåäîâàòü ñîîòâåòñòâóþùóþ ïîñëåäîâàòåëüíîñòü çàïóñêîâ ïåðåõîäîâ, ÷òî
â ñëó÷àå âðåìåííîé ñåòè Ïåòðè ÿâëÿåòñÿ NP-ñëîæíîé çàäà÷åé åùå è ïîòîìó, ÷òî íå
âñÿêàÿ ïîñëåäîâàòåëüíîñòü çàïóñêîâ ïåðåõîäîâ äîïóñêàåò ðåàëèçàöèþ âî âðåìåíè.
ÏÐÈÌÅÐ ÏÐÀÊÒÈ×ÅÑÊÎÃÎ ÏÐÈÌÅÍÅÍÈß ÑÒÎÕÀÑÒÈ×ÅÑÊÎÉ ÂÐÅÌÅÍÍÎÉ
ÑÅÒÈ ÏÅÒÐÈ
Ðàññìîòðèì çàäà÷ó äèíàìè÷åñêîãî ðàñïðåäåëåíèÿ âû÷èñëèòåëüíûõ ðåñóðñîâ
(ðèñ. 4). Ïîçèöèÿ P0 ïðåäñòàâëÿåò êîëè÷åñòâî äîñòóïíîãî ðåñóðñà, ïîçèöèè P1,
P2 , P3 — áóôåð çàäàíèé A B C, , ñîîòâå-
òñòâåííî. Ïðåäïîëàãàåòñÿ, ÷òî â áóôåðå
çàäàíèé âñåãäà åñòü çàäàíèÿ äëÿ âû÷èñ-
ëåíèé. Âðåìåííûå çàäåðæêè â ïåðåõî-
äàõ T0 , T1, T2 îïðåäåëÿþò âðåìÿ âûïîë-
íåíèÿ çàäàíèé A B C, , . Íåðàâíîìåðíîå
ïîòðåáëåíèå ðåñóðñîâ ïðèâîäèò ê òîìó,
÷òî ïðè îòñóòñòâèè ïðîöåññîâ óïðàâëå-
íèÿ çàäàíèÿ ñ ìåíüøåé ïîòðåáíîñòüþ
ðåñóðñà èñïîëüçóþò åãî â ïîëíîé ìåðå,
à çàäàíèÿ ñ áîëüøåé ïîòðåáíîñòüþ íà-
õîäÿòñÿ â ïîñòîÿííîì îæèäàíèè îñâî-
áîæäåíèÿ íåîáõîäèìîãî îáúåìà ðåñóðñà.
Óïðàâëåíèå ðàñïðåäåëåíèåì ðåñóðñîâ
îñóùåñòâëÿåòñÿ áëîêèðîâàíèåì âîçìîæ-
íîñòè çàõâàòà ðåñóðñîâ íà îñíîâàíèè èí-
ôîðìàöèè î êîëè÷åñòâå âûïîëíåííûõ çà-
äàíèé. Ïåðåõîä T5 ñðàâíèâàåò êîëè÷åñòâî
âûïîëíåííûõ çàäàíèé A B C, , ñ äðóãèìè
çàäàíèÿìè òàê, ÷òî èíôîðìàöèÿ î
min { , , }N N NA B C ñîäåðæèòñÿ â ïîçèöèè P9 , à èíôîðìàöèÿ î ðàçíîñòÿõ
N N N NA A B C
min { , , }, N N N NB A B C
min { , , }, N N N NC A B C
min { , , }
ñîäåðæèòñÿ â ïîçèöèÿõ P4 , P5 , P6 ñîîòâåòñòâåííî. Ïðè á�ëüøåì êîëè÷åñòâå âû-
ïîëíåííûõ çàäàíèé Â è Ñ ïðèíèìàåòñÿ ðåøåíèå î áëîêèðîâêå èõ âûïîëíåíèÿ
(ïåðåõîä T3), à ïðè á�ëüøåì êîëè÷åñòâå âûïîëíåííûõ çàäàíèé À — ðåøåíèå
î ñíÿòèè ýòîé áëîêèðîâêè (ïåðåõîä T4).
Ðàññìîòðèì ïîäñèñòåìó îáúåêòà óïðàâëåíèÿ (áåç ïîäñèñòåìû óïðàâëåíèÿ). Ñî-
îòâåòñòâóþùàÿ áàçîâàÿ ñåòü Ïåòðè îáëàäàåò èíâàðèàíòàìè ñîñòîÿíèÿ è ïîâåäåíèÿ, è
ïîñëåäîâàòåëüíîñòü çàïóñêîâ ïåðåõîäîâ, êîòîðàÿ ïðèâîäèò ê îäèíàêîâîìó êîëè÷åñ-
òâó âûïîëíåííûõ çàäàíèé, ÿâëÿåòñÿ äîïóñòèìîé. Â äåéñòâèòåëüíîñòè çàäàíèÿ ñî-
ïåðíè÷àþò çà çàõâàò ðåñóðñà íàñòîëüêî, ÷òî, íàïðèìåð, ïðè âðåìåííûõ çàäåðæêàõ
â ïåðåõîäàõ T0 , T1, T2 â ñðåäíåì 1, 0.157 è 0.333 ñîîòâåòñòâåííî çàäàíèÿ Â è Ñ,
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Ð1
Ïîäñèñòåìà îáúåêòà óïðàâëåíèÿ
Ïîäñèñòåìà óïðàâëåíèÿ
2
2
2
1
Ð0
1
1
Ð6Ð4
Ð7Ð8
Ð2
Ð3
Ð5
Ð9
1
Ò0
Ò1
Ò2
Ò4
Ò3
Ò5
Ð10
Ðèñ. 4. Ñåòü Ïåòðè, ìîäåëèðóþùàÿ óïðàâëåíèå
ðàñïåäåëåíèåì âû÷èñëèòåëüíûõ ðåñóðñîâ
îäíàæäû çàõâàòèâ ðåñóðñ è ïîî÷åðåäíî åãî îñâîáîæäàÿ, íå äàþò âîçìîæíîñòè çàäà-
íèÿì À çàíÿòü ðåñóðñ. Ýòîò ýôôåêò íåâîçìîæåí â áàçîâîé ñåòè Ïåòðè. Ñëåäîâàòåëü-
íî, áàçîâàÿ è âðåìåííàÿ ñåòè Ïåòðè ñóùåñòâåííî îòëè÷àþòñÿ.
Èññëåäîâàíèå ìîäåëè óïðàâëåíèÿ ðåñóðñàìè ñ ïîìîùüþ ìàòðè÷íûõ óðàâíå-
íèé (25), (26) ïîçâîëÿåò óñòàíîâèòü ñòðóêòóðíûå ñâîéñòâà ñåòè Ïåòðè, ïîäòâåð-
æäàþùèå ïðàâèëüíîñòü åå ïîñòðîåíèÿ. Íàïðèìåð, èç ìàòðè÷íûõ óðàâíåíèé (25)
ñëåäóåò, ÷òî äîñòèæèìûìè ÿâëÿþòñÿ ìàðêèðîâêè âèäà
M M a a a v v( ) ( ) ( ) ( ) ( ( ) ( ))t t t t tn n n�
�
�
�
0 0�
�
(2 2 1 1 1
1
0 1 2 0 1 2 0 5 0 1 5 1
2 5 2
� � � � � � � � � � � �
� � �
� � � � � �3 4 3 4 4 5 ) ,T
ãäå v( ) ( )tn � � � �0 1 2 0 0 0 T , �( ) ( )tn � � � � � � �0 1 2 3 4 5
T . Îòñþäà
2 2 00 1 2
�� � � , � 0 1� , �1 1� , � 2 1� , � � �0 5 0� , � � �1 5 1� ,
� � �2 5 2� , 0 13 4�
�� � . Ñëåäîâàòåëüíî, íåäîñòèæèìûìè ÿâëÿþòñÿ ìàð-
êèðîâêè, â êîòîðûõ êîëè÷åñòâî ìàðêåðîâ â ïîçèöèè P0 áîëüøå äâóõ, â ïîçè-
öèÿõ P1, P2 , P3 , P7 , P8 — áîëüøå îäíîãî, ÷òî ñîîòâåòñòâóåò ñìûñëó ìîäåëè.
Âðåìåííàÿ ñåòü Ïåòðè (ñì. ðèñ. 4) íå îáëàäàåò èíâàðèàíòàìè ïîâåäåíèÿ èëè
ñîñòîÿíèÿ ââèäó íàëè÷èÿ ïîçèöèé-ñ÷åò÷èêîâ P9 , P10 . Îäíàêî òàêèå ïîçè-
öèè-ñ÷åò÷èêè ïîçâîëÿþò ñäåëàòü óíèêàëüíûì ñîñòîÿíèå âðåìåííîé ñåòè Ïåòðè
â êàæäûé ìîìåíò âðåìåíè è, êàê ñëåäñòâèå, äîáèòüñÿ ñóùåñòâîâàíèÿ ìàòðèöû
(( ) ( ))a a a a
T 1. Ïóñòü öåëüþ óïðàâëåíèÿ ÿâëÿåòñÿ îáåñïå÷åíèå ïðèìåð-
íî îäèíàêîâîãî êîëè÷åñòâà âûïîëíåííûõ çàäàíèé âñåõ êëàññîâ. Ýòî òðåáîâàíèå ñî-
îòâåòñòâóåò òîìó, ÷òî ìàðêèðîâêà, äëÿ êîòîðîé êîëè÷åñòâî ìàðêåðîâ â ïîçèöèÿõ P4 ,
P5 , P6 áûëî íóëåâûì, äîñòèæèìà â ëþáîé ìîìåíò âðåìåíè. Íàïðèìåð, ñîñòîÿíèå
ñåòè Ïåòðè M( ) ( )tn � 2 0 1 1 0 0 0 0 1 50 6 T , v( ) ( )tn � 1 0 0 0 0 0 T äîñòèãà-
åòñÿ ïðè êîëè÷åñòâå âõîäîâ â ïåðåõîäû, ðàâíîì
�( ) (( ) ( )) ( ) ( ( ) ( ) (t t tn n�
a a a a a a M M a vT T1
0 ( ) ( )))t tn
�v 0
� ( )51 50 50 7 6 50 T .
Âñå êîìïîíåíòû íàéäåííîãî âåêòîðà öåëûå íåîòðèöàòåëüíûå ÷èñëà è âñå ïîñëå-
äîâàòåëüíîñòè çàïóñêîâ ïåðåõîäîâ ñ òî÷êè çðåíèÿ áàçîâîé ñåòè Ïåòðè äîïóñòèìû,
îäíàêî âåðîÿòíîñòü íàáëþäåíèÿ â ñòîõàñòè÷åñêîé ñåòè Ïåòðè ïîñëåäîâàòåëüíîñòè çà-
ïóñêîâ ïåðåõîäîâ ñ íàéäåííûì êîëè÷åñòâîì çàïóñêîâ ïåðåõîäîâ áëèçêà ê íóëþ.
Èññëåäîâàíèå ñ ïîìîùüþ èìèòàöèè ôóíêöèîíèðîâàíèÿ â ñîîòâåòñòâèè ñ
óðàâíåíèÿìè (10) ïîçâîëÿåò îöåíèòü ñðåäíåå êîëè÷åñòâî âûïîëíåííûõ çàäàíèé
è ñðåäíåå êîëè÷åñòâî ñâîáîäíûõ ðåñóðñîâ äëÿ çàäàííîãî âðåìåíè ìîäåëèðîâà-
íèÿ, à òàêæå îñóùåñòâèòü âûáîð ïàðàìåòðîâ óïðàâëåíèÿ, óäîâëåòâîðÿþùèõ
îïðåäåëåííîé öåëè. Íàïðèìåð, ïðè èìèòàöèè íà èíòåðâàëå âðåìåíè 500 ïðè âðå-
ìåííûõ çàäåðæêàõ â ïåðåõîäàõ T0 , T1, T2 , ðàâíûõ ýêñïîíåíöèàëüíî ðàñïðåäåëåí-
íûì ñëó÷àéíûì âåëè÷èíàì ñî ñðåäíèìè çíà÷åíèÿìè 1, 0.157 è 0.333 ñîîòâåò-
ñòâåííî, ñðåäíåå êîëè÷åñòâî âûïîëíåííûõ çàäàíèé â ïîçèöèè P9 ðàâíî 379.75,
ñðåäíåå êîëè÷åñòâî âûïîëíåííûõ çàäàíèé êëàññîâ — 433.5, 0.5, 0. Ââåäåì ïàðà-
ìåòðû óïðàâëåíèÿ, ñîîòâåòñòâóþùèå óñëîâèÿì, ïðè êîòîðûõ ïðèíèìàåòñÿ ðåøå-
íèå î áëîêèðîâêå a w w� �5 3 5 5, , , b w w� �6 3 6 5, , , c w w� � �4 4 4 5 1, , .
Ðåçóëüòàòû ýêñïåðèìåíòîâ ïðè ðàçëè÷íûõ çíà÷åíèÿõ ïàðàìåòðîâ ïðèâåäåíû
íà ðèñ. 5. Èç íèõ ñëåäóåò, ÷òî a �1, b � 2 — íàèëó÷øàÿ êîìáèíàöèÿ ñ òî÷êè çðåíèÿ
íàèáîëüøåãî îáùåãî êîëè÷åñòâà âûïîëíåííûõ çàäàíèé, a b� �2 1, — íàèëó÷øàÿ
êîìáèíàöèÿ ïàðàìåòðîâ ñ òî÷êè çðåíèÿ äîñòèæåíèÿ íàèìåíüøåãî ïðåèìóùåñòâà
â êîëè÷åñòâå âûïîëíåííûõ çàäàíèé ðàçëè÷íûõ êëàññîâ, à êîìáèíàöèÿ a b� �2 2, —
íàèëó÷øàÿ ñ òî÷êè çðåíèÿ íàèáîëüøåãî êîëè÷åñòâà ðåøåííûõ çàäà÷ êëàññà Ñ.
Ïðàêòè÷åñêîå ïðèìåíåíèå ñòîõàñòè÷åñêîé ñåòè Ïåòðè äëÿ ñèñòåìû óïðàâëå-
íèÿ ó÷åáíûì ïðîöåññîì âóçà îïèñàíî â [7].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 177
ÇÀÊËÞ×ÅÍÈÅ
 ðåçóëüòàòå íàó÷íîãî èññëåäîâàíèÿ ïîëó÷åíû ëîãèêî-àëãåáðàè÷åñêèå óðàâíåíèÿ
ïðåîáðàçîâàíèé âðåìåííîé ñåòè Ïåòðè, ñîîòâåòñòâóþùèõ âõîäàì è âûõîäàì ìàð-
êåðîâ èç ïåðåõîäîâ, âûâåäåíû îáû÷íûå è ìàòðè÷íûå óðàâíåíèÿ ñîñòîÿíèé ñòîõàñ-
òè÷åñêîé âðåìåííîé ñåòè Ïåòðè ñ ìíîãîêàíàëüíûìè è êîíôëèêòíûìè ïåðåõîäàìè,
èíôîðìàöèîííûìè ñâÿçÿìè. Ïîêàçàíî, ÷òî ôóíäàìåíòàëüíûå ìàòðè÷íûå óðàâíåíèÿ,
êîòîðûå ïîëó÷åíû äëÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè, ñîäåðæàò, êàê ÷àñ-
òíûé ñëó÷àé, óðàâíåíèÿ ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè áåç èíôîðìàöèîí-
íûõ ñâÿçåé, óðàâíåíèå äåòåðìèíèðîâàííîé âðåìåííîé ñåòè Ïåòðè è óðàâíåíèå áà-
çîâîé ñåòè Ïåòðè. Îòëè÷èÿ èçâåñòíûõ óðàâíåíèé ñîñòîÿíèé ñåòè Ïåòðè îò óðàâíå-
íèé ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè çàêëþ÷àþòñÿ â ñëåäóþùåì:
— âìåñòî îáû÷íîé ìàðêèðîâêè èñïîëüçóåòñÿ ðàñøèðåííàÿ ìàðêèðîâêà ñåòè
Ïåòðè, âêëþ÷àþùàÿ íå òîëüêî ìàðêåðû, êîòîðûå íàõîäÿòñÿ â äàííûé ìîìåíò
âðåìåíè â ïîçèöèÿõ ñåòè Ïåòðè, íî è ìàðêåðû, îæèäàþùèå âûõîäà â ïåðåõîäàõ;
— èìååòñÿ óðàâíåíèå, îòâå÷àþùåå çà ïðîäâèæåíèå âðåìåíè, èç êîòîðîãî
ñëåäóåò, ÷òî ìîìåíò áëèæàéøåãî ñîáûòèÿ ïîëíîñòüþ îïðåäåëÿåòñÿ òåêóùèì ñî-
ñòîÿíèåì ïåðåõîäîâ ñåòè Ïåòðè;
— ôàêòè÷åñêîå êîëè÷åñòâî âõîäîâ â ïåðåõîäû îãðàíè÷åíî òðåáîâàíèåì äîñ-
òèæåíèÿ òàêîãî ñîñòîÿíèÿ ñåòè Ïåòðè, ïðè êîòîðîì äëÿ âñåõ åå ïåðåõîäîâ íå âû-
ïîëíÿåòñÿ óñëîâèå çàïóñêà;
— äëÿ ðàçðåøåíèÿ êîíôëèêòîâ ïåðåõîäîâ ïðåäëîæåí àëãîðèòì âûáîðà ïåðå-
õîäà èç ìíîæåñòâà ïåðåõîäîâ ñ âûïîëíåííûì óñëîâèåì çàïóñêà, îñíîâàííûé íà
çíà÷åíèÿõ ïðèîðèòåòîâ è âåðîÿòíîñòåé çàïóñêîâ ïåðåõîäîâ.
Óðàâíåíèÿ ïðåîáðàçîâàíèé ñåòè Ïåòðè, ñîîòâåòñòâóþùèå âõîäó è âûõîäó
ìàðêåðîâ èç ïåðåõîäîâ, ïðåäñòàâëÿþò ïîëíîå ôîðìàëèçîâàííîå îïèñàíèå àëãî-
ðèòìà èìèòàöèè ñòîõàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè ñ êîíôëèêòíûìè è ìíî-
ãîêàíàëüíûìè ïåðåõîäàìè, ñ èíôîðìàöèîííûìè ñâÿçÿìè. Ìàòðè÷íûå óðàâíåíèÿ
ñîñòîÿíèé ïðèìåíÿþòñÿ äëÿ àíàëèòè÷åñêèõ ìåòîäîâ èññëåäîâàíèÿ ñâîéñòâ ñòî-
õàñòè÷åñêîé âðåìåííîé ñåòè Ïåòðè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ç à é ö å â Ä . À . , Ñ ë å ï ö î â À . È . Óðàâíåíèÿ ñîñòîÿíèé è ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ
âðåìåííûõ ñåòåé Ïåòðè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1997. — ¹ 5. — Ñ. 59–76.
2. Ï è ò å ð ñ î í Ä æ . Òåîðèÿ ñåòåé Ïåòðè è ìîäåëèðîâàíèå ñèñòåì. — Ì.: Ìèð, 1984. — 264 ñ.
3. Ñ ò å ö å í ê î ² .  . Ìîäåëþâàííÿ ñèñòåì: Íàâ÷. ïîñ³á. — ×åðêàñè: Ìàêëàóò, 2011. — 502 ñ.
4. Ñ ò å ö å í ê î ² .  . , Ä à í è ë þ ê À . À . ²ì³òàö³éíå ìîäåëþâàííÿ ñèñòåì óïðàâë³ííÿ çàñîáàìè
ñ³òîê Ïåòð³ // ³ñí. ×åðêàñ. äåðæ. òåõíîë. óí-òó. — 2005. — ¹ 3. — Ñ. 293–295.
5. Ñ ò å ö å í ê î ² .  . , Á î é ê î Î .  . Ñèñòåìà ³ì³òàö³éíîãî ìîäåëþâàííÿ çàñîáàìè ñ³òîê Ïåòð³ //
Ìàò. ìàøèíè ³ ñèñòåìè. — 2009. — ¹ 1. — Ñ. 117–124.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5
Ðèñ. 5. Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ ïàðàìåòðîâ ñèñòåìû óïðàâëåíèÿ
ðàñïðåäëåíèåì ðåñóðñîâ ïðè ðàçëè÷íûõ êðèòåðèÿõ: îáùåå êîëè÷åñòâî âûïîëíåííûõ çàäàíèé âñåõ
êëàññîâ (à), ñóììàðíîå ïðåâûøåíèå êîëè÷åñòâà âûïîëíåííûõ çàäàíèé âñåõ êëàññîâ íàèìåíüøåãî
êîëè÷åñòâà âûïîëíåííûõ çàäàíèé (á), êîëè÷åñòâî âûïîëíåííûõ çàäàíèé êëàññà Ñ (â)
10 2 3
a /b
Êðèòåðèé
1000
1500
2000
10 2 3
a /b
Êðèòåðèé
500
1000
10 2 3
a /b
Êðèòåðèé
200
400
à á â
6. Ñ ò å ö å í ê î ² .  . , Ñ ò å ö å í ê î  . à . , Ä è ô ó ÷ è í Þ . Ì . ²ì³òàö³éíà ìîäåëü äîðîæíüîãî
ðóõó íà ïåðåõðåñò³, êåðîâàíîìó ñâ³òëîôîðîì // ³ñí. ×åðêàñ. äåðæ. òåõíîë. óí-òó. — 2005. —
¹ 1. — Ñ. 28–32.
7. Ñ ò å ö å í ê î ² .  . ²ì³òàö³éíå ìîäåëþâàííÿ ñèñòåìè óïðàâë³ííÿ íàâ÷àëüíèì ïðîöåñîì ÂÍÇ
ç âèêîðèñòàííÿì îá’ºêòíî-îð³ºíòîâàíîãî ï³äõîäó // Ìàò. ìàøèíè ³ ñèñòåìè. — 2011. — ¹ 2.
— Ñ. 162–170.
8. Ê î ò î â Â . Å . Ñåòè Ïåòðè. — Ì.: Íàóêà, 1984. — 158 ñ.
9. Ç à é ö å â Ä . À . Ïîñòðîåíèå ñåòè Ïåòðè, èñïîëíÿþùåé ìàøèíó Òüþðèíãà // Ìàòåðèàëû IV
ìåæäóíàð. íàó÷.-òåõí. êîíô. «Êîìïüþòåðíàÿ ìàòåìàòèêà â íàóêå, èíæåíåðèè è îáðàçîâàíèè»
(CMSEE-2010), Ïîëòàâà, 1–31 îêò. 2010 ã. — Êèåâ: Èçä-âî ÍÀÍ Óêðàèíû, 2010. — Ñ. 12–14.
10. W a n g J . Timed Petri nets: theory and application. — Massachusetts: Kluwer Acad. Publ., Oct.,
1998. — 290 p.
11. H a a s P . J . Stochastic Petri nets: modelling, stability, simulation // Springer Series in Operations
Research. — 2002. — 529 p.
12. Ê å ë ü ò î í Â . , Ë î ó À . Èìèòàöèîííîå ìîäåëèðîâàíèå. Êëàññèêà ÑS. — 3-å èçä. — ÑÏá.:
Ïèòåð; Êèåâ: Èçä. ãðóïïà BHV, 2004. — 847 c.
13. M u r a t a T . Petri nets: properties, analysis and applications // Proc. IEEE. — 1989. — 77, N 4. —
P. 541–580.
14. Ç à é ö å â Ä . À . Èíâàðèàíòû âðåìåííûõ ñåòåé Ïåòðè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2004. — ¹ 2. — Ñ. 92–106.
15. Ñ ò å ö å í ê î ² .  . Ìîäåëþâàííÿ óïðàâëÿþ÷èõ ñèñòåì çàñîáàìè ìåðåæ Ïåòð³ ç ³íôîð-
ìàö³éíèìè çâ’ÿçêàìè // ³ñí. ×åðêàñ. äåðæ. òåõíîë. óí-òó. — 2011. — ¹ 3. — Ñ. 3–9.
Ïîñòóïèëà 25.05.2011
|
| id | nasplib_isofts_kiev_ua-123456789-84151 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:15:08Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стеценко, И.В. 2015-07-03T10:16:41Z 2015-07-03T10:16:41Z 2012 Уравнения состояний стохастических временных сетей Петри с информационными связями / И.В. Стеценко // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 164-179. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84151 519.876.5 Розглянуто застосування мереж Петрі з часовими затримками для імітаційного моделювання систем. Отримано рівняння перетворень стану мережі Петрі та фундаментальні матричні рівняння стохастичної мережі Петрі з часовими затримками, багатоканальними та конфліктними переходами, інформаційними зв’язками. The use of timed Petri nets in systems simulation is analyzed. The equations of timed Petri net state transformations and fundamental matrix equations of stochastic timed Petri net with conflict and multi-transitions, with information ties are obtained. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Уравнения состояний стохастических временных сетей Петри с информационными связями Рівняння станів стохастичних часових мереж Петрі з інформаційними зв’язками The state equations of stochastic timed Petri nets with information ties Article published earlier |
| spellingShingle | Уравнения состояний стохастических временных сетей Петри с информационными связями Стеценко, И.В. Системный анализ |
| title | Уравнения состояний стохастических временных сетей Петри с информационными связями |
| title_alt | Рівняння станів стохастичних часових мереж Петрі з інформаційними зв’язками The state equations of stochastic timed Petri nets with information ties |
| title_full | Уравнения состояний стохастических временных сетей Петри с информационными связями |
| title_fullStr | Уравнения состояний стохастических временных сетей Петри с информационными связями |
| title_full_unstemmed | Уравнения состояний стохастических временных сетей Петри с информационными связями |
| title_short | Уравнения состояний стохастических временных сетей Петри с информационными связями |
| title_sort | уравнения состояний стохастических временных сетей петри с информационными связями |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84151 |
| work_keys_str_mv | AT stecenkoiv uravneniâsostoâniistohastičeskihvremennyhseteipetrisinformacionnymisvâzâmi AT stecenkoiv rívnânnâstanívstohastičnihčasovihmerežpetrízínformacíinimizvâzkami AT stecenkoiv thestateequationsofstochastictimedpetrinetswithinformationties |