ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 143
Скачиваний: 0
Вероятность того, что первый переход из S; произойдет именно в sj, равен
4i = ^ • |
(34) |
О/ |
|
Стакой вероятностью имеет место ур-ние (33) с определенным /. Вводим обозначения: 7\, Tj — средние значения и di, dj — дис
персии для времени до первого достижения некоторого st из s,-, Sj соответственно; 7^ и dij — среднее время и дисперсия времени для перехода из Si в Sj, если известно, что именно этот переход был первым; T'it d'i — значения 7\-, d,- при том же дополнительном ус ловии. Тогда, усредняя по всем возможным траекториям
S, — Sj —> |
. . . — sh |
|
||
на основе |
(33) |
имеем |
|
|
7'i = |
7'"' |
T ' l . |
(35) |
|
d( —d^ + dj |
j |
|
||
Каждое из этих соотношений имеет место с вероятностью (34). Усредняя (35) по всем возможным Sj и учитывая, что для первого перехода среднее значение времени пребывания в состоянии Sj
равно
1 ___________________ 1____________________
а/ ап + ■ • •+ ai, ,-_i + ai, i+i -г ■ ■ •+ аш
и дисперсия этого времени 1/а?, получаем после простых преобра зований:
щ Тс— |
2 |
a‘iTi = |
1 |
(36) |
/>/, /gL |
|
|
||
a 4 i — X |
i |
а чdi = — |
’ |
(37) |
i r i . |
e 1* |
a ‘ |
|
|
В суммах левых частей исключили значения / 6 L, так как для лю бого такого I как Т[, так и di равны нулю. Исключаются также и все j, недостижимые из i.
Линейные системы (36) и (37) отличаются только правыми час тями, а транспонированная матрица коэффициентов совпадает с некоторым главным минором матрицы В. Как было установлено выше, определитель такой матрицы отличен от нуля только тогда, когда соответствующее ему множество вершин Xj имеет корневой лес, т. е. каждая стационарная компонента, вершина которой до стижима из I, должна иметь хотя бы одну вершину в XL. Можно проверить, что в противном случае системы (36) и (37) несовме стимы.
В случае процесса размножения и гибели системы (36) и (37) дают, понятно, те же значения, как и выражения другого вида, при водимые в § 3.1. В общем случае для расчета значений 7\ и di мож но указать приемы расчета без вычитаний, аналогичные приему, описанному в § 4.3.1.
79
4. Локальное укрупнение состояний
Иногда описание коммутационной системы можно упростить укрупнением состоянии системы. Изложим алгоритм укрупнения, основанный па применении метода исключения Гаусса.
Систему уравнений для расчета стационарных вероятностей со стояний
£ a }ipj = 0, / =■ 1. . . ., п, |
(38) |
i=i |
|
с условием нормировки |
|
V ру = 1 |
(39) |
;'=1
можно преобразовать следующим образом. Из первого ур-ния (38) выражаем рх как функцию от остальных неизвестных
|
(40) |
и подставляем это значение в (38), что дает |
|
= 1. |
|
/>2 |
(39), а именно: |
Это соотношение получает вид, аналогичный |
|
2 < i, = i. |
н о |
/>2 |
|
при введении новых неизвестных |
|
|
|||
|
|
; > |
2 - |
|
т |
Неиспользованная часть ур-ний (38) после подстановок (40) и |
|||||
(42) принимает вид |
|
|
|
||
Yi |
bjfli = °. |
i = 2. • • -Л, |
|
(43) |
|
i>з |
|
|
|
|
|
где |
|
|
|
|
|
b |
= а и а 1 + а и а и |
^ |
.2> |
(44) |
|
|
а-х + |
a i i |
|
|
|
|
|
|
|
||
Очевидно, если а,ц —0, то
4i = Pj, bjc = ац. (45)
Полученная новая система ур-ний (43) и (41) имеет ту же струк туру, что и исходная система (38) и (39), только на одну неизвест ную меньше. При этом изменяются значения лишь тех неизвестных и могут изменяться значения лишь тех коэффициентов, которым в
80
графе состояний соответствуют дуги, входящие в устраненную вер шину 1, другими словами, в некоторой окрестности первого поряд ка этой вершины. Последнее позволяет назвать сделанное преоб разование локальным укрупнением. Таким же образом, последова тельно или одновременно, можно исключить любое подмножество состояний.
Приведем соотношения для одновременного исключения состоя ний с номерами 1, 2,..., k, /г<п. Получаем систему вида (43) и (41), где j ^ k + 1, а формулы преобразования имеют вид:
Я 1 = -^ Р Г , |
(46) |
Ьц = ^ ~ , |
(47) |
ci |
|
--- ^21 • . |
— 0*1 |
д = |
|
---a l k ---- °2* ‘ |
• •а к |
a Cj н dji — соответствующим образом окаймленное Д:
1 |
1 . |
. 1 |
|
an |
alt . |
■ -a ki |
|
Cj = —Яд |
аг . . |
Oftl |
, j |
k , dji — ~ а ц |
<h ■ |
■—akl |
|
ftjk —<hk • • •ak |
|
—ajk |
aik |
ak |
|
||
При этом расчеты следует проводить только для тех j > k , |
для |
||||||
которых имеется |
хотя |
бы |
одно а ^ > 0 о i ^ /г. Для всех других / |
||||
имеет место |
(45). |
|
|
|
|
|
|
В случае больших k для расчета значений определителей можно |
|||||||
использовать их приведение к наддиагональному |
виду. При этом |
||||||
первые строки всех ёц |
подвергаются тем же преобразованиям, |
как |
|||||
и первая строка Cj, и значения Ьц равны отношениям конечных пер вых элементов этих строк. Легко проверить, что коэффициенты Ьц имеют те же свойства, что и величины ад, только с учетом измене
ния множества значений |
индексов. Очевидно, с: > 0 и |
0 при |
в силу положительности и неотрицательности значений эле |
||
ментов первой строки соответственно. |
|
|
Соотношению |
|
|
— 6, / — 1, . |
. ., П, |
(48) |
L |
|
|
соответствует |
|
|
2 &д = 0* i = k + \, . . ., п, |
(49) |
|
i>k |
|
|
81
а последнее будет иметь место одновременно с таким же соотно шением для dji. Сумма же последних равна
S a /( |
V flli . |
* |
V aki |
i>k |
i>k |
i>k |
|
— а.ц |
аг ■ |
|
-Oki |
&jk |
|
|
ak |
В этом определителе в силу (48) элементы первой строки рав ны сумме всех других элементов соответствующего столбца. Следо
вательно, имеет место (49) и Ьц = —БЬд. i'ti
Рассмотренный прием укрупнения фактически является оста новкой на некотором этапе алгоритма исключения Гаусса. Поэтому он в общем случае дает экономию по числу необходимых операций и может быть выгодным в смысле уменьшения требуемой опера тивной памяти машины.
5. Укрупнение посредством производящих функций
Другой прием укрупнения системы, т. е. снижения числа рас сматриваемых уравнений и неизвестных, — использование частич ных производящих функций. При помощи их удается заменить под систему уравнений небольшим числом уравнений. Покажем это на примере процессов размножения и гибели с п состояниями, прону
мерованными от 1 до п, причем при малых |
значениях |
номера t |
|
интенсивности Аа = а,-,г--н1 и ц,г = |
i_t имеют произвольные положи |
||
тельные значения и, понятно, |
p,i= 0, а при i ^ k |
p.j='[x (но |
|
Х„ = 0). Такой процесс описывает, например, |
^-линейную систему с |
||
ожиданием.
При расчете стационарных вероятностей р, вводим производя
щие функции |
|
|
|
|
Р (*) = |
pk + |
pk+xx + . . |
. + pnxn~k t |
(50) |
умножаем уравнение |
|
|
||
Х Pk+j |
(Ц + |
Ц Pk+j+l + |
Г Pk+ л -2 ~ 0 |
|
соответственно на х*+2, уравнение
Рп-1 + И- Рп = 0
на xn~k+i и суммируем. В результате получаем
(X— 1)(A.JC — |Х) Р (*) + (* + 1 ) [|ЛPk — xn~“+l Х Рп\+Х\х Рк—т + 1 1= °-
82