BC/NW 2015 № 2 (27):8.1

ЗАДАЧИ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯМЕТОДАМИ ТЕОРИИ ДИСКРЕТНЫХ МАРКОВСКИХ ПРОЦЕССОВ

Дорошенко А.Н.

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

Любая подобная  система неизбежно испытывает различного pода возмущения,  источниками которых могут быть либо внешние воздействия,  обусловленные  случайными  или систематическими изменениями окружающих условий, либо внутренние флуктуации,  возникающие в самой  системе  в  результате взаимодействия элементов. При исследовании эти системы в теории массового обслуживания представляются конечным или счетным множеством состояний, а процесс функционирования системы – последовательностью случайного перемещения системы из одного состояния в другое. Все характеристики, связанные с таким многошаговым функционированием системы,  сравнительно просто рассчитываются, если предположить, что случайный процесс, протекающий в системе, удовлетворяет условию без последействия, сформулированному Марковым [1, 2].  Суть этого условия состоит в следующем: для любого момента времени t₀ вероятностные характеристики процесса в будущем зависят только от состояния S_i в данный момент t₀ и не зависят от того, как и когда система пришла в это состояние, то есть не учитывается предистория процесса и причины попадания системы в S_i. Последовательность переходов системы из состояния в состояние, характеризующаяся свойством без последействия, называется случайным марковским процессом или  марковской цепью.  В зависимости от характера изменения состояний во времени различаются два вида цепей Маркова: непрерывные, и дискретные. Случайный процесс образует непрерывную цепь, если переход из состояния в состояние  возможен в любой случайный момент времени. Дискретной цепью называется случайный процесс перехода системы из состояния в состояние в дискретные моменты времени.

При изучении курсов моделирования сложных систем и процессов студентам  наиболее часто излагаются только   непрерывные цепи Маркова, что, естественно, ограничивает область возможных применений этого математического аппарата,  например, рассмотрением типовых схем: одно- и многоканальных СМО с отказами, с обслуживанием, с потерями из-за ограничения длины очереди [3,4].

В данной статье рассматриваются возможности вычисления дополнительны характеристик СМО применением дискретных цепей Маркова (ДЦМ). Для этого сначала напомним некоторые понятия и особенности ДЦМ.

Вся совокупность вероятностей переходов {p_ij}  из любого i-того состояния в любое j-тое представляет собой квадратную несимметричную матрицу Р, то есть в общем случае p_ij не равно p_ji, а p_ii – вероятность того, что система останется в состоянии i на очередном шаге моделирования.  Из условия p_ij = 0 следует, что система, находясь в i-том состоянии,  не может непосредственно (за один шаг моделирования) перейти в j-тое состояние. Каждая строка матрицы Р характеризует полную группу случайных событий, так что сумма вероятностей всех элементов строки матрицы Р равна 1. Из этого следует, что если система попадает в некоторое состояние i, из  которого нет перехода в другое состояние, тогда p_ii = 1, и такое состояние называется поглощающим. Условие p_ij = 1 соответствует безусловному переходу из состояния i в состояние j.

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

Циклической называется эргодическая цепь, в которой в каждое состояние можно попадать через определенное число переходов (для ДЦМ – через определённые периоды времени).

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

Ниже приводятся примеры ДЦМ, представленных матрицами вероятностей переходов (МВП).

Пример 1. Эргодическая цепь с циклической траекторией, меняющая свои состояния с периодом 3 шага: S₁àS₂àS₃àS₁…

	S1	S2	S3
S1	0	0	1
S2	1	0	0
S3	0	1	0

Пример 2. Цепь с невозвратным состоянием S₁.

	S1	S2	S3
S1	½	¼	¼
S2	0	1/3	2/3
S3	0	¼	¾

При неограниченном числе шагов n  с вероятностью, приближающейся к 1, система попадает в одно из состояний S₂, либо S₃, из которых никогда не перейдёт в состояние S1, называемое невозвратным.

Пример 3. Регулярная эргодическая цепь.

	S1	S2	S3
S1	½	0	½
S2	0	½	½
S3	2/5	3/5	0

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

Пример 4. Цепь с поглощающим состоянием S₂.

	S1	S2	S3
S1	½	0	½
S2	0	1	0
S3	¼	½	¼

Цепь не является регулярной и эргодической, так как из состояния S₂ нельзя попасть в S₁ и S₃.

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

Регулярные цепи Маркова. Перемещения в регулярной цепи Маркова с конечным множеством состояний { S₁, S₂,...S_n} полностью определяются вектором распределения вероятностей начальных состояний Рso=(рso₁, pso ₂ , ..., pso _n)  и МВП Р с элементами р_ij , i=1,...,n, j=1,...,n.

Задачи, имеющие прикладное значение для систем, представляемых регулярными цепями Маркова:

Задача 1. Найти относительное время T_i пребывания системы в  состоянии S_i при достаточно длительном функционировании.

Задача 2. Найти среднее число шагов (математическое ожидание) n_ij⁰ до первого достижения состояния S_j из заданного состояния S_i.

Задача 3. Вычислить дисперсию как меру разброса текущих значений n_ij, получаемых при длительном перемещений системы по цепи Маркова, относительно n_ij⁰.

Решение первой задачи основывается на фундаментальной теореме для регулярных цепей Маркова, суть которой в том, что при достаточно длительном движении цепи Маркова финальные вероятности R=(r₁, r₂, r₃,...,r_n) пребывания  системы в состояниях S_i, i=1..n стабилизируются (свойство стационарности) и не зависят от вектора распределения вероятностей начальных состояний R⁰.  Математически это выражается в виде  уравнения  R * P = R. Результатом его решения является вектор финальных вероятностей R⁰=(r₁⁰, r₂⁰, r₃⁰,...,r_n⁰). Решением первой задачи тогда будет набор относительных времён пребывания цепи в состоянии S_i за достаточно длительный период Т: 

T_i   =T* r_i⁰, i=1,...,n, где T₁+ T₂+...+T_n=T.

Решение второй задачи состоит в отыскании компонент n_ij⁰ неслучайной  матрицы  N размерностью (nXn) и основывается на вычислении по соотношению

N = (I_n – Z + E*Z₀)*R1,

где I_n  - единичная матрица c размерностью (nXn); Z – фундаментальная матрица регулярной цепи Маркова, вычисляемая по формуле

Z = ( I_n – P + R)^-1;

E – матрица  размерности (nxn) с элементами 1;

Z₀ – матрица, полученная из Z заменой недиагональных элементов нулями.; R1 - диагональная матрица, элементы которой вычисляются так:

r¹_ii  = 1/r_i, где r_i – элементы вектора R.

Решение третьей задачи основано на соотношении:    D = W – N⁽²⁾,

где N⁽²⁾  получается из N возведением в квадрат каждого элемента;

W = N*(2*Z₀*R1 – I_n) + 2*(Z*N – E*(Z*N)_o), где   Z₀ и (Z*N)_o – получаются из Z и Z*N заменой недиагональных элементов нулями.

Поглощающие цепи Маркова. Задачи для систем, поведение которых моделируется поглощающими  цепями Маркова:

Задача 1. Найти среднее число k_ijc посещений неустойчивого состояния S_j до попадания в состояние поглощения , если движение началось из неустойчивого состояния Si.

Задача 2. Найти дисперсию как меру разброса текущих значений k_ij , получаемых при длительном перемещений системы по цепи Маркова, относительно k_ijc.

Задача 3. Найти среднее число шагов n_ic, которое сделает система  до попадания в состояние поглощения, если движение началось из S_i.

Задача 4. Найти дисперсию d_i как меру разброса текущих значений n_i  относительно n_ic.

Задача 5. Найти вероятность того, что процесс перейдёт в поглощающее состояние S_j,  если он начался в состоянии S_i.

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

Например, в приведённой ниже МВП размером 4х4, задающей поглощающую цепь:

	S1	S2	S3	S4
S1	½	0	¼	¼
S2	0	1	0	0
S3	¼	½	¼	0
S4	0	0	0	1

поглощающие состояния S₂ и S₄ перемещаем в первые две строки и получаем каноническую форму, состоящую из четырех блоков, выделенных в таблице цветом:

	S2	S4	S1	S3
S2	1	0	0	0
S4	0	1	0	0
S1	0	¼	½	¼
S3	½	0	¼	¼

I – единичная матрица размерности (vXv), где v – число поглощающих состояний (в данном примере v=2),  0 – нулевая матрица размерности (vXu), v+u=n, L – матрица размерности (uxv), определяющая переходы из неустойчивых состояний в поглощающие, Q - матрица размерности (uXu), определяющая переходы из неустойчивых состояний в неустойчивые:

I	0
L	Q

Решение первой задачи основано на применении формулы для вычисления элементов фундаментальной матрицы K = (I_u - Q)^-1 размерности uXu  для поглощающей цепи. Её элементы характеризуют среднее число k_ijc посещений неустойчивого состояния S_j до попадания в состояние поглощения, если движение началось из неустойчивого состояния S_i, i,j=1,2,...,u. 

Решение второй задачи сводится к вычислению элементов дисперсии d_ij = M[(k_ij - k_ijc )² ] по формуле

D = K*(2*Ko - I_u) – K⁽²⁾,

где  Ko – матрица, полученная из К заменой недиагональных элементов нулями; K⁽²⁾ ={(k_ij)²}.

         Решение третьей и четвёртой задач:  значение n_ic образуется суммированием по j, j=1,...,u, всех значений k_ij в i-й строке, а дисперсия d_i – это элемент вектора-столбца размерности u:

D = (2*K – I_u)*N1 – N1⁽²⁾,

где N1 – вектор из элементов n_ic , то есть N1=(n_1c, n _2c, n_3c,..., n _nc), N1⁽²⁾ – вектор квадратов этих элементов.

Для решения пятой основной задачи поглощающих цепей используется соотношение B = K*L.

Литература

1. Бородюк В.П., Голяс Ю.Е. Дискретные цепи Маркова в задачах оптимизации технических систем. М.;МЭИ, 1989 г . – 75 с.

2. Кемени Дж.,Снелл Дж., Кнепп А. Счетные цепи Маркова М.: Наука, 1987. – 415 с.

3. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.

4. Афанасьев М.Ю., Багринский К.А., Матюшок В.М. Прикладные задачи исследования операций: Уч. пособие. –  М.: ИНФРА-М, 2006. – 352 с.