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

Воспользуемся также условием ортогональности

получено, вычисление P ij(t) сводится к подстановке в (39) полино­ миальной аппроксимации для e~xt и выражений полиномов Q i ( x ) , Q j ( x ) , получаемых из рекуррентных соотношений (40). Эти вычис­ ления можно проводить не только аналитически, но и на вычисли­ тельной машине при данных значениях параметров. Недостатком метода является быстрый рост знакопеременных коэффициентов ортогональных полиномов, что требует счета с удлиненной ячейкой машинной памяти.

Замечания и литературные ссылки

Алгоритм вычисления вероятностей первого перехода взят из книги Чжун Кай Лай [447], вывод распределения времени пер­ вого перехода — из статей Кейлсона 1236], Морана [263]. Метод факторизации применительно к переходным вероятностям процесса размножения и гибели развивается в ряде статей Карлина и МакГ­ регора, например, [234]. В этой же статье доказана теорема мажо­ рирования переходных вероятностей, полезная для приближенных вычислений, а именно, если для какого-либо значения k отношение W'p,fc+i возрастает (убывает), то независимо от i

убывает (возрастает) для / ^ k ;

возрастает (убывает) для / > к.

55

Численный анализ марковских процессов

Впредыдущих двух главах был подробно рассмотрен частный случай марковских про­

цессов с дискретным (конечным или счет­ ным) множеством состояний и непрерывным временем со стацио­ нарными интенсивностями перехода — процессы размножения и гибели, определяемые якобиевой матрицей интенсивностей перехо­ да. Й настоящей главе рассмотрим алгоритмы анализа марковских процессов в случае произвольных матриц интенсивностей перехо­ да, как они введены в § 1.3.

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

•подходящей выбранной методике расчета не происходит никакой потери точности.

Материал настоящей главы расположен в следующем порядке. В § :'4.1 дано представление множества состояний марковского процесса в виде графа, дана классификация множества состояний, показана связь главных миноров матрицы интенсивностей перехода с множеством корневых лесов.графа. В § 4.2 рассмотрены свойства переходных и -стационарных вероятностей, показана связь стацио­ нарных вероятностей с уравнением Кирхгофа, предложен один под­ ход к построению марковского процесса в случае неэкспоненциаль­ ных законов. Параграф 4.3 содержит изложение алгоритмов для вычислений характеристик марковских процессов: стационарных вероятностей, моментов времени первого перехода, алгоритмов укрупнения множества состояний.

56

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

4.1. АНАЛИЗ МНОЖЕСТВА СОСТОЯНИИ МЕТОДАМИ ТЕОРИИ ГРАФОВ

1. Представление марковского процесса в виде графа

Дан марковский процесс с дискретным множеством состоя­

переходов, например, a ih — это интенсивность перехода (i, k), 1ф1г. Переход (i, k) будем называть элементарным, если а ^ > 0, и неэле­ ментарным, если a.ih— 0.

Для сокращения записи формул будут использованы величины:

Из обеих частей этого уравнения мы вычитаем P i ( t ) , делим на At, устремляем At к нулю и получаем систему дифференциальных, уравнений Колмогорова—Чепмена:

Если рассматривать вектор-столбец Р с компонентами P i ( t ) и матрицу А, то система (3) будет эквивалентна векторному уравне­ нию:

Для изучения ряда вопросов и краткости некоторых формулиро­ вок полезно использовать представление процесса Маркова посред­ ством потоков в графе.

Ьт

Каждому состоянию s, сопоставим вершину графа, которую обо­

ребром {£, к] или [к, £], которое представляется отрезком линии, сое­

обозначается стрелкой в направлении от £ к к, поставленной рядом с ребром {£, к]; в случае надобности около стрелки можем также записать значение а,;,. Следовательно, каждое ребро получает одну или две противоположные стрелки и вместе с каждой из них обра­ зует по дуге.

Таким образом, представляющий граф задан через множество X своих вершин и множество U своих дуг. Для дуги (i, к) верши­ на Xi считается начальной точкой, вершина X/t — конечной. Будем считать, что дуга (i, k) исходит из £ и входит в k. Для дуги (k, i), -если такая имеется в графе, х,- и х& в указанных соотношениях меняются ролями.

Другой удобный вид задания графа G — задание его через X множество вершин и (в общем случае многозначное) отображение Г множества X в себя, а именно, каждой вершине х, ставится в со­ ответствие множество Г Xi .вершин. При этом х^б-Гх,- в том и толь­ ко том случае, когда G содержит дугу (i, к). Для графа, представ­ ленного на рис. 4.1, fx i = (хг, х4, х5}.

Если 5 — некоторое множество вершин графа G, то под Г 5 по­ нимается объединение образов всех вершин, входящих в 5. Такое соглашение позволяет определить положительные степени отобра­ жения Г через рекуррентное соотношение r hS = r ( r h~iS ). Так, в гра­ фе рис. 4.1 Г 2х = {хь хг, х5}.

первой) входит в образ, предшествующей ей. Будем говорить, что такой путь соединяет начальную вершину пути x(j с конечной

58

вершиной х ,А . Вершина хи считается достижимой из вершины х

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

является 1СШ1ыно шязньгм, так как .вершина 6 не достижима ни из одной другой вершины. Для таких графов можно рассмотреть раз­ биение на компоненты. Компонентой будем называть каждый под­ граф G' данного графа G, т. е. подмножество X' множества X всех вершин вместе со всеми дугами из G, которые связывают вершины, подмножества X', если: 1) G' сильно связный и 2) не существует сильно связного подграфа G" графа G, отличного от G' и содер­ жащего G'.

Нетрудно проверить, что граф на рис. 4.1 разлагается на сле­

2. Комбинаторный алгоритм классификации состояний

При расчете различных величин, 1ха.рактер.из'уюш,их исследуе­ мый процесс (переходные или стационарные вероятности, средние’ времена первого перехода и т. д.), целесообразно или даже необ­ ходимо знать разбиение на компоненты для графа „G, представляю­ щего процесс, а также и достижимость определенных вершин из: других. Ответ на эти два вопроса легко получить только в случаях,, когда граф G имеет немного вершин или легко обозримое строение.

Опишем простой комбинаторный способ классификации мно­ жества состояний произвольных марковских процессов, допускаю­ щий машинную реализацию. Для данного графа G с вершинами

X i,..., х п построим «скелетный» граф \G, каждая вершина которогосоответствует сильно связной компоненте G, а дуга — множеству дуг, идущих в G из вершин одной такой компоненты в вершины

другой. Граф IG получится в результате построения конечной после­

довательности графов G 0— G, |Gi, Gz,..., G v = G . В каждом из гра­ фов Gj обозначения отдельных вершин будут иметь либо один ин­

ва N . Строим новый граф G p + i, который содержит все вершины' х к

59 >