3.14.2. Уравнения глобального баланса

Обозначим через Sj множество всех возможных микросостояний системы, при которых на обслуживании находится ровно j заявок, а через (Jj - количество элементов в Sj . Далее в соответствии с диаграммой переходов для выбранной модели построим матрицы интенсивностей переходов из микросостояний j-го яруса:

Aj[aj X cTji] - в Sji (прибытие заявки);

Cj[(Tj X <Tj] - в Sj (конец промежуточной фазы обслуживания);

Bj[(Tj X CTj-i] - в Sj-i (полное завершение обслуживания);

Dj[aj X (Tj] - ухода из состояний яруса j (в квадратных скобках здесь и далее указывается размер матриц).

Введем векторы-строки 7j = {7j,b7j,2j 7j,<Tj} нахождения СМО в состоянии (j, г) , j = 0,1,... Теперь можно записать векторно-матричные уравнения баланса переходов между состояниями

7ojDo = 7oCo+7ib 14 n

= 7i-ii-i + 7jQ+7j+i5j+b i=l,2,... -

В связи с зависимостью структуры матриц переходов от типа и порядка аппроксимирующих фазовых распределений ценность программной реализации расчетной схемы определяется возможностью автоматического построения матриц переходов. Эту проблему можно решить следующим образом:

а) для каждого j-го яруса системы, j = 0,гг, автоматически сгенерировать последовательность ключей микросостояний;

б) сформировать матрицы переходов, сопоставляя ключи- источни-ки j-ro яруса и совместимые с ними по выбранному типу переходов ключи- преемники : для матрицы В на (j - 1)-м ярусе, для матрицы С - на j-м, для А - на (j -f 1)-м ярусе.

Именно такой подход применен в описанном ниже (разд. 3.17) пакете подпрограмм МОСТ.

Система (3.14.1), дополненная условием нормировки, даже для моделей с ограниченной очередью характеризуется чрезвычайно высокой размерностью, и стандартные методы решения систем линейных алгебраических уравнений применительно к ней оказываются малоэффективными. Мы рассмотрим два метода ее решения: итерационный и матрично-геометрической прогрессии.

3.14.3. Итерационный метод

Идея этой схемы была впервые предложена Такахаси и Таками [209]. Мы опишем ее в более общей форме и с детальной проработкой расчетных зависимостей [66, 67, 68].

Положим tj = 7j/Pj . где pj - суммарная вероятность наличия в системе ровно j заявок, и обозначим

= Pj+i/Pj = Pj-i/Pj- (3.14.2)

Тогда систему (3.14.1) можно переписать относительно векторов условных вероятностей {ij} , нормированных к единице в пределах яруса:

toDo = /оСо-f oii, 14 3 !

bj = i = i,2,... - -

с помощью векторов-столбцов Ij = {1, 1,.. ., 1}- размера ctj для всех j могут быть записаны дополняющие систему (3.14.3) условия нормировки

tjlj = 1 (3.14.4)

И баланса суммарных интенсивностей переходов между смежными ярусами

tjAjlji = XjtjiBjilj. (3.14.5)

Алгоритм расчета набора векторов {tj} и чисел {xj] и {zj} , удовлетворяющих соотношениям (3.14.3)-(3.14.5), в случае разомкнутой системы с неограниченной очередью опирается на существование предельного вектора условных вероятностей to = litiij ooj . которое является следствием стабилизации переходных матриц при j > п . Алгоритм основан на последовательном приближении к искомым характеристикам для ограниченного множества индексов j = 0,N и по существу является блочныг\л вариантом известного итерационного метода Гаусса-Зейделя.

Перепишем уравнения системы (3.14.3) для j > 1 в виде

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

<( ) = ,] )/?;. +4 )/?;, (3.14.6)

/ =51 Bj+.m-c,)-,

При j - N считается, что

Pn = 4 i.v(Av - Cn)-- (3.14.8)

Осталось указать способ расчета {] } и {л } . Перепишем (3.14.5) с учетом (3.14.6):

Отсюда следует пропорциональность

с коэффициентом

в этой и последующих формулах произведения матриц перехода на вектор Ij равны суммам строк соответствующих матриц и могут быть вычислены до начала итераций.

Подстановка (3.14.8) в (3.14.6) и умножение обеих частей результата на Ij дают

l = 4 h, = 4 (c/.+/3pi,-.

Итак,

а;И = 1/[(с/?; + /?;)1]. (3.14.11)

Удобным критерием прекращения итераций является условие

тахх- - х\ Ч < сь j J J -

Описанный алгоритм в связи с усечением числа ярусов - см. формулу (3.14.8) - будет давать надежные результаты лишь при условии

lliv-ooll <е2. (3.14.12)