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

и при хотя бы одном положительном a.jh в силу теоремы 4.3 для

1

и для всех а#,, j ^ k ^ h , имеет место ajh — qhbj, где bj = 'Zaig. Тогда

qh будет вероятностью того, что при первом выходе из 2 переход произойдет именно в состояние h.

Таким образом, если для каждого состояния s исследуемой си­ стемы имеем интенсивности перехода типа bj (обусловленные дли­ тельностью обслуживания, входными потоками и т. д.) и вероятно­ сти первого перехода типа qh, то, сопоставляя этому состоянию s подмножество состояний 2 с подходящим образом подобранными ац и djh, получаем точную модель пребывания фактического про­ цесса в каждом состоянии s и переходов из s в другие состояния. Следовательно, будет получена точная модель всей данной системы, причем эта модель — процесс Маркова с конечным числом со­ стояний.

Указанным способом могут моделироваться не все вероятности p(t) первого выхода из 2, представляемые как линейные комбина­ ции собственных функций. Точно не моделируются, например, та­ кие вероятности, даже монотонно убывающие от 1 до 0 при возрас­ тании г1от 0 до оо, для которых производная равна нулю при поло­ жительных значениях t. Пример:

Р(0 = ( 1 + ^ е “ <,

где производная

ш

имеет нуль при f= .l. Однако можно ожидать, что функции p(t) та­ кого типа или, например, ступенчатые функции p(t) можно прибли­ зить функциями ps (t) для подмножества 2 с достаточно большим числом состояний. Косвенным подтверждением этой гипотезы мо­ жет служить факт, что многие свойства и соотношения, установлен­ ные первоначально для процессов Маркова с дискретным множест­ вом состояний, были затем обобщены для более общих марков­ ских (процессов. Приведем несколько примеров.

При k = 2 pxj(t) может равняться любой из функций

fi(*)=re-w + ( l - / - ) e - * “

или

U (0 = (1 + р 0 е м •

Рассматривая эти функции как вероятности пребывания, имеем следующие параметры для простейшей модели.

74

При р=Я имеем две известные эрланговские фазы.

При k /^Ъ система может иметь и комплексные характеристиче­ ские значения Яг/ в таком случае рх (t) может содержать и экспо­ ненциально убывающие члены колебательного характера. Пример:

при 0< г< 0 ,5 ; 0 < 6 < 1 —г\ 0 < с < 1 —г, 2/-3< Ьс,/множество 2 с /г= 3 и

Функции рх такого типа с компонентами Яг могут появиться толь­ ко в случае, когда граф непосредственных переходов в 2 содержит хотя бы один контур. Действительно, если таких контуров нет, то состояния, входящие в 2, можно пронумеровать так, что непосред­ ственные переходы имеются только от состояний с меньшим номе­ ром к состояниям с большим номером. Тогда матрица коэффициен­ тов правой части (21) — поддиагональная, характеристические зна­ чения Я,-= —-щ, t'= l, 2,..., k, следовательно, все действительные.

Последний «факт показывает неточность утверждения, что любое распределение положительной случайной величины, преобразова­ ние Лапласа которого является отношением двух полиномов, мо­ жет быть представлено комбинацией этапов обслуживания и типов требований. Действительно, такая комбинация может дать только множества 2 без контуров, следовательно, с действительными соб­ ственными значениями. В то же время распределения, соответст­ вующие (22), имеют преобразование Лапласа в виде отношения

.двух полиномов, .но моделируются множеством 2 с контуром (1, 2,

.3). Таким образом, вопрос об определении всех распределений, точ­ но моделируемых подмножествами 2, остается открытым.

75

Ясно, что приведенные в этом пункте способы моделирования: разбиение входных потоков и использование подмножеств S су­ щественно увеличивают число состояний, рассматриваемых в ис­ пользуемом для моделирования процессе Маркова. Однако при расчете основных стационарных характеристик приемы укрупнения, указанные в следующем параграфе, позволяют снизить число рас­ сматриваемых состояний и уравнений.

4.3. АЛГОРИТМЫ

1. Применение алгоритма Гаусса для вычисления стационарных вероятностей

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

Пусть дана матрица интенсивностей перехода марковского про­ цесса

удобно применить метод исключения Гаусса, так как с учетом по­ ложительности коэффициентов а,ц и вида матрицы (23) вычисления можно проводить без потери точности. Действительно, к элементам

/-Й строки (7='2,..., п) в (23) добавляем соответствующие элементы

11

первой строки, умноженные на а^/ £ aih. В результате под главной

Расчет a'ij происходит без потери точности, поскольку сумми­ руются величины одного знака (если ни одна из них не равна ну­ лю). Если опасна потеря точности при вычислении аи, так как

76

то новые значения а'ц на главной диагонали следует вычислять не непосредственно, а через суммирование:

ных элементов второй колонки в нули повторяем описанные дейст­ вия с элементами второй строки и остальной матрицей.

Алгоритмом Гаусса удобно пользоваться для вычисления ха­ рактеристик коммутационных схем, для которых (д-М ) n<lN, где д — число состояний схемы; N — объем оперативной памяти ЭВМ. При больших д надо привлекать другие виды памяти, что резко уд­ линяет время счета, или следует переходить к другим алгоритмам, например, итерационным.

N — число ячеек оперативной памяти ЭВМ, то распределение ве­ роятностей состояний системы можно вычислить итерационным ме­ тодом (методом последовательных приближений). При этом сле­ дует учесть, что матрицы систем линейных уравнений, возникаю­ щих на практике и имеющих большой порядок, как правило, бы­ вают редкими (имеют много нулей). Для таких матриц метод иск­ лючения Гаусса крайне неудобен, поскольку он многие из нулевых элементов переводит в ненулевые.

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

Алгоритм решения (28) методом последовательных приближе­ ний следующий.

1.Задается начальное приближение

р<°) = 1, г = 1, . . ., л.

77