Файл: Шнепс, М. А. Численные методы теории телетрафика.pdf

Предполагаем, что матрица В приведена к виду (7). Рассмот­ рим уравнения системы (17). соответствующие всем матрицам. Bi,..., В>i (в отдельности или вместе). Имеем однородную линей­ ную систему, уравнения которой независимы, так как матрица не­ особенная, а число данных уравнений равно числу неизвестных, ко­ торые в них явно фигурируют. Следовательно, все эти неизвестные равны нулю. Подставляем найденные значения в уравнения, соот­ ветствующие матрице Си Как и выше, получаем, что величины ри соответствующие этой матрице, все равны нулю. Такую же подста­ новку и рассуждения применяем поочередно ко всем матрицам С&..., Си В результате устанавливаем, что все величины pi, соответ­ ствующие вершинам исходных или промежуточных компонент (матрицы Bi,..., Bh, Ci,..., Ci в (7)), имеют нулевые значения. Под­ ставляем эти значения в следующие уравнения. Для каждой ИЗ' матриц Di,..., Dm получаем свою систему линейных однородных уравнений со своими неизвестными. Каждая из систем содержит столько же уравнений, сколько неизвестных. Устанавливаем, что ранг определителя системы на единицу ниже его порядка. Следо­ вательно, каждая система однозначно определяет отношения между величинами р,- для вершин каждой стационарной компоненты

Dи..., Dm.

Если имеется только одна стационарная компонента, то значе­ ния отношений между pi и нормирующее условие однозначно опре­ деляют все Pi. Если же число стационарных компонент /п> 1, то наряду с соотношениями величин р { внутри каждой компоненты не­ обходимо знать еще значения т— 1 независимого отношения p jp j для различных компонент. Эти значения «внешних» отношений за­ висят, очевидно, от начальных значений (если постоянные P i полу­ чаются как пределы переменных при ^->-оо). Так, например, если все начальные P i ( 0 ) положительны только для одной стационарной компоненты, то это же свойство будут иметь и предельные ри

Отношения различных P i для отдельной стационарной компонен­ ты можно получить по известным формулам Крамера. Покажем, что в качестве величин, пропорциональных рь можно брать значе­ ния определенных главных миноров матрицы В.

Рассматриваем одну стационарную компоненту. После перену­ мерации соответствующая ей система может быть приведена к ви­ ду (17) (понятно, с другим, в общем случае, значением п). Соглас­ но формулам Крамера получим величины г{, пропорциональные ис­

70

Имеем

для любого I. В определителе правой части к элементам i-й строки добавляем сумму соответствующих элементов всех других строк. Значения определителя при этом изменятся и на основе (19):

Последний определитель — ни что иное, как минор матрицы ле­ вой части, соответствующий pi. Так как раньше установили, что все эти миноры положительны, то положительны и все отношения стационарных pi внутри стационарной компоненты, как и должно быть из вероятностных соображений. Поэтому стационарные значе­ ния для вершин каждой стационарной компоненты либо все поло­ жительны, либо все равны нулю. Пример системы с более чем од­ ной стационарной компонентой: процесс размножения и гибели с несколькими поглощающими состояниями.

Отметим еще одно свойство стационарных вероятностей, кото­ рое иногда полезно знать. Пусть рассматриваемая стационарная компонента с множеством вершин Xj содержит точку сочленения х. Это значит, что можно так разбить множество Х.,\ х на две части X', X", что любой путь из вершины одной части в вершину другой части проходит через х. В таком случае значения отношений для вершин каждого из множеств X' (J х, X" (J х можно рассматривать отдельно.

Действительно, пусть система (17) относится к рассматривае­ мой компоненте и пусть X' содержит к— 1 вершину. В силу свобод­ ной нумерации вершин внутри каждой компоненты можно выбрать такую, в которой все вершины множества X' получают номера от 1 до k— 1, вершина х получает номер к, а вершины множества X" — дальнейшие номера. С другой стороны, установлено, что взаимные отношения величин pi для рассматриваемой компоненты однознач­ но определяются системой, получаемой из (17) отбрасыванием лю­ бого из уравнений. Отбросим к-е уравнение. Тогда, в силу свойств вершины Хь, уравнения с номером i ^ k — 1 в числе к— 1 содержат только неизвестные р,- с номером от 1 до k и определяют их отно­ шения. Остальные же уравнения в числе т—k содержат т —k + 1 неизвестное Хъ,—, хт и также однозначно определяют их отношения.

В качестве примера процессов с отмеченным свойством можно привести процесс размножения и гибели, где каждая вершина гра­ фа, за исключением двух крайних (для конечного п) или крайней {для бесконечного числа состояний), является точкой сочленения.

71

3. Матрица А и уравнения Кирхгофа

Пусть множество N = { 1, 2...} индексов вершин графа разбито на два •непересекающ'ихся подмножества / и К и пусть АД, Хк — множества всех тех вершин, индексы которых принадлежат соот­ ветственно / и К- Множество всех ребер типа [i, k], i 6 L k 6К, на­ зывается разрезом, который обозначим через [/, /<] или i[/(, /].

Рассматриваемые величины P i ( t ) можем истолковать как массы некоторой жидкости, находящейся в момент t в вершине лщ а про­ изведения ciiuPi — как интенсивности потоков, текущих из Х{ в xh

массы р,- в Xj равна интенсивности суммарного потока, притекающе­ го в .V;. Для стационарного соотношения имеем систему уравнений

Теорема 4.5. Скорость изменения суммарной массы в верши­ нах множества Xj равна интенсивности суммарного потока, вте­ кающего в Xj.

Для стационарного случая все производные по времени равны нулю. Имеет место следующее следствие.

С л е д с т в и е . В стационарном случае суммарная интенсивность, потока, протекающего через любой разрез, равна нулю.

Понятно, применяя следствие, все значения интенсивностей по­ токов через отдельные ребра разреза необходимо брать в согласо­ ванных направлениях: для К], например, рассматривать потоки либо все как втекающие в вершины АД, либо все как вытекающие из них.

72

4.Построение марковского процесса в случае неэкспоненциальных распределений

Процесс Маркова непосредственно моделирует систему мас­ сового обслуживания, в которой все потоки требований — пуассо­ новские, а все распределения времени обслуживания — экспонен­ циальные. Однако таким процессом возможно моделировать и не­ который класс более общих систем. Во-первых, пусть некоторый входной поток не всегда ординарный. Тогда молено выделить от­ дельно потоки поступления требований по одному, по два и т. д. и каждый из них приближать пуассоновским потоком или же нилее рассмотренным способом. Во-вторых, для аппроксимации распре­ делений времени обслуживания, отличающегося от экспоненциаль­ ного, молено одному фактическому состоянию системы сопоставить подходящим образом подобранную подсистему 2 состояний моде­ лирующего процесса Маркова. Частным случаем такого сопостав­ ления является разбиение обслуживания на последовательные фа­ зы. Например, аппроксимация распределений длительности обслулеивания распределениями Эрланга.

Рассмотрим один более общий вопрос. Будем искать вероят­

ность того, что процесс, находясь в момент ^=0 в некотором состоя­ нии s некоторого собственного подмнолсества 2 всех состояний, до момента t не покинет это подмножество. Такую вероятность будем называть вероятностью пребывания в 2. Для упрощения записи без ограничения общности можем предпололщть, что состояние s имеет номер 1, а множество / номеров состояний подмножества

2 — это множество {1, 2,..., k} и что все индексы множества J достижимы из 1.

Рассматриваемый процесс до первого выхода из 2 будет проте­ кать так л<е, как усеченный процесс, в котором оставлены без из­ менений все Щ] с i ^ k , а все остальные а^- аннулированы. Ход усе­ ченного процесса характеризуется системой уравнений

М 0 = £ л ( 0 - i=i

В общем случае система (21) имеет k характеристических функ­ ций, и p-z (t) является определенной линейной комбинацией этих функций. Установим, что в случаях, представляющих интерес, ког­ да хотя бы одно djh, h > k , в (21) строго ноложителыно, новпда Ps (t) — убывающая функция. Действительно, согласно i(20)

Е

£=1 \<i<k,h>k