Как найти предельные вероятности примеры - Сайт, где вы сможете решить свои вопросы

Уравнения Колмогорова.
Предельные вероятности состояний

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем* на примере случайного процесса из примера 1, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния S_i в S_j происходят под воздействием простейших потоков событий с интенсивностями $lambda_{ij},(i,j=0,1,2,3)$ ; так, переход системы из состояния S_0 в S_1 будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния S_1 в S_0 — под воздействием потока “окончаний ремонтов” первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 1). Рассматриваемая система имеет четыре возможных состояния: S_0,,S_1,,S_2,,S_3 .

Граф системы состояний случайного процесса

Вероятностью i-го состояния называется вероятность p_i(t) того, что в момент система будет находиться в состоянии S_i . Очевидно, что для любого момента сумма вероятностей всех состояний равна единице:

$sum_{i=0}^{3}p_i(t)=p_0(y)+p_1(t)+p_2(t)+p_3(t)=1.$

(8)

Рассмотрим систему в момент и, задав малый промежуток Delta t , найдем вероятность p_0(t+Delta t) того, что система в момент будет находиться в состоянии S_0 . Это достигается разными способами.

1. Система в момент с вероятностью p_0(t) находилась в состоянии S_0 , а за время Delta t не вышла из него.

Вывести систему из этого состояния (см. граф на рис. 1) можно суммарным простейшим потоком с интенсивностью $(lambda_{01}+lambda_{02})$ , т.е. в соответствии с формулой (7), с вероятностью, приближенно равной $(lambda_{01}+lambda_{02})Delta t$ . А вероятность того, что система не выйдет из состояния S_0 , равна $[1-(lambda_{01}+lambda_{02})Delta t]$ . Вероятность того, что система будет находиться в состоянии S_0 по первому способу (т.е. того, что находилась в состоянии S_0 и не выйдет из него за время Delta t ), равна по теореме умножения вероятностей:

$p_0(t)[1-(lambda_{01}+lambda_{02})Delta t].$

2. Система в момент с вероятностями p_1(t) (или p_2(t) ) находилась в состоянии S_1 или S_2 и за время Delta t перешла в состояние S_0 .

Потоком интенсивностью $lambda_{10}$ (или $lambda_{20}$ — с- рис. 1) система перейдет в состояние S_0 с вероятностью, приближенно равной $lambda_{10}Delta t$ (или $lambda_{20}Delta t$ ). Вероятность того, что система будет находиться в состоянии S_0 по этому способу, равна $p_1(t)lambda_{10}Delta t$ (или $p_2(t)lambda_{20}Delta t$ ).

Применяя теорему сложения вероятностей, получим

$p_0(t+Delta t)= p_1(t)lambda_{10}Delta t+ p_2(t)lambda_{20}Delta t+p_0(t)[1- (lambda_{01}+lambda_{02})Delta t],$

откуда

$frac{p_0(t+Delta t)-p_0(t)}{Delta t}= p_1(t)lambda_{10}+ p_2(t)lambda_{20}-(lambda_{01}+lambda_{02})p_0(t).$

Переходя к пределу при Delta tto0 (приближенные равенства, связанные с применением формулы (7), перейдут в точные), получим в левой части уравнения производную p'_0(t) (обозначим ее для простоты p'_0 ):

$p'_0=lambda_{10}p_1+lambda_{20}p_2-(lambda_{01}+lambda_{02})p_0.$

Получили дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы , можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

$begin{cases} p'_0=lambda_{10}p_1+lambda_{20}p_2-(lambda_{01}+lambda_{02})p_0,\[2pt] p'_1=lambda_{01}p_0+lambda_{31}p_3-(lambda_{10}+lambda_{13})p_1,\[2pt] p'_2=lambda_{02}p_0+lambda_{32}p_3-(lambda_{20}+lambda_{23})p_2,\[2pt] p'_3=lambda_{13}p_1+lambda_{23}p_2-(lambda_{31}+lambda_{32})p_3. end{cases}$

(9)

Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности i-го состояния. В правой части — сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния).

В системе (9) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение (8).

Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задать так называемые начальные условия, т.е. в данном случае вероятности состояний системы в начальный момент t=0 . Так, например, систему уравнений (9) естественно решать при условии, что в начальный момент оба узла исправны и система находилась в состоянии S_0 , т.е. при начальных условиях p_0(0)=1, p_1(0)=p_2(0)=p_3(0)=0 .

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы p_i(t) в предельном стационарном режиме, т.е. при ttoinfty , которые называются предельными (или финальными) вероятностями состояний.

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

Предельная вероятность состояния S_i имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S_0 , т.е. p_0=0,!5 , то это означает, что в среднем половину времени система находится в состоянии S_0 .

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы с графом состояний, изображенном на рис. 1), такая система уравнений имеет вид:

$begin{cases}(lambda_{01}+lambda_{02})p_0= lambda_{10}p_1+lambda_{20}p_2,\[2pt] (lambda_{10}+lambda_{13})p_1= lambda_{01}p_0+lambda_{31}p_3,\[2pt] (lambda_{20}+lambda_{23})p_2= lambda_{02}p_0+lambda_{32}p_3,\[2pt] (lambda_{31}+lambda_{32})p_3= lambda_{13}p_1+lambda_{23}p_2. end{cases}$

(10)

Систему (10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния p_i , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пример 2. Найти предельные вероятности для системы из примера 1, граф состояний которой приведен на рис. 1, при

$lambda_{01}=1,quad lambda_{02}=2,quad lambda_{10}=2,quad lambda_{13}=2,quad lambda_{20}=3,quad lambda_{23}=1,quad lambda_{31}=3,quad lambda_{32}=2.$

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

$begin{cases}3p_0=2p_1+3p_2,\ 4p_1=p_0+3p_3,\ 4p_2=2p_0+2p_3,\ p_0+p_1+p_2+p_3=1.end{cases}$

(11)

(Здесь мы вместо одного “лишнего” уравнения системы (10) записали нормировочное условие (8)).

Решив систему (11), получим p_0=0,!4,~p_1=0,,2,~p_2=0,!27,~p_3=0,!13 , т.е. в предельном, стационарном режиме система в среднем 40% времени будет находиться в состоянии S_0 (оба узла исправны), 20% — в состоянии S_1 (первый узел ремонтируется, второй работает), 27% — в состоянии S_2 (второй узел ремонтируется, первый работает) и 13% времени — в состоянии S_3 (оба узла ремонтируются)

Пример 3. Найти средний чистый доход от эксплуатации в стационарном режиме системы в условиях примеров 1 и 2, если известно, что в единицу времени исправная работа первого и второго узлов приносит доход соответственно в 10 и 6 ден.ед., а их ремонт требует затрат соответственно в 4 и 2 ден.ед. Оценить экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Решение. Из примера 2 следует, что в среднем первый узел исправно работает долю времени, равную p_0+p_3=0,!4+0,!27=0,!67 , а второй узел — p_0+p_1=0,!4+0,!2=0,!6 . В то же время первый узел находится в ремонте в среднем долю времени, равную p_1+p_3=0,!2+0,!13=0,!33 , а второй узел — p_2+p_3=0,!27+0,!13=0,!4 . Поэтому средний чистый доход overline{D} в единицу времени от эксплуатации системы, т.е. разность между доходами и затратами, равен

overline{D}= 0,!67cdot10+0,!6cdot6-0,!33cdot4-0,!4cdot2= 8,!18 ден. ед.

Уменьшение вдвое среднего времени ремонта каждого из узлов в соответствии с (6) будет означать увеличение вдвое интенсивностей потока “окончаний ремонтов” каждого узла, т.е. теперь $lambda_{10}=4,$ $lambda_{20}=6,$ $lambda_{31}=6,$ $lambda_{32}=4$ и система линейных алгебраических уравнений (10), описывающая стационарный режим системы , вместе с нормировочным условием (8) примет вид:

$begin{cases}3p_0=4p_1+6p_2,\ 6p_1=p_0+6p_3,\ 7p_2=2p_0+4p_3,\ p_0+p_1+p_2+p_3=1.end{cases}$

Решив систему, получим p_0=0,!6,~p_1=0,!15,~p_2=0,!2,~p_3=0,!05 .

Учитывая, что p_0+p_2=0,!8,~p_0+p_1=0,!75,~p_1+p_3=0,!2,~p_2+p_3=0,!25 , а затраты на ремонт первого и второго узла составляют теперь соответственно 8 и 4 ден.ед., вычислим средний чистый доход $overline{D}_1$ в единицу времени:

$overline{D}_1=0,!8cdot10+0,!75cdot6-0,!2cdot8-0,!25cdot4=9,!9$ ден.ед.

Так как $overline{D}_1$ больше (примерно на 20%), то экономическая целесообразность ускорения ремонтов узлов очевидна.

Процесс гибели и размножения

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 4.

Граф состояний процесса гибели и размножения

Рассмотрим упорядоченное множество состояний системы S_0,S_1,S_2,ldots,S_k . Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния S_k возможны переходы только либо в состояние $S_{k-1}$ , либо в состояние $S_{k+1}$ .

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями $lambda_{k,k+1}$ или $lambda_{k+1,k}$ .

В соответствии с правилом составления таких уравнений (см. 13) получим: для состояния S_0

$lambda_{01}cdot p_0=lambda_{10}cdot p_1,$

(12)

для состояния S_1 имеем $(lambda_{12}+lambda_{10})p_1=lambda_{01}p_0+ lambda_{21}p_2$ , которое с учетом (12) приводится к виду

$lambda_{12}cdot p_1=lambda_{21}cdot p_2.$

(13)

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

$begin{cases}lambda_{01}cdot p_0=lambda_{10}cdot p_1,\ lambda_{12}cdot p_1=lambda_{21}cdot p_2,\ cdotscdotscdotscdotscdots\ lambda_{k-1,k}cdot p_{k-1}=lambda_{k,k+1}cdot p_k,\ cdotscdotscdotscdotscdots\ lambda_{n-1,n}cdot p_{n-1}=lambda_{n,n+1}cdot p_n.end{cases}$

(14)

к которой добавляется нормировочное условие

p_0+p_1+p_2+ldots+p_n=1.

(15)

При анализе численности популяций считают, что состояние S_k соответствует численности популяции, равной , и переход системы из состояния S_k в состояние $S_{k+1}$ происходит при рождении одного члена популяции, а переход в состояние $S_{k-1}$ – при гибели одного члена популяции.

Решая систему (14), (15), можно получить

$p_0={left(1+ frac{lambda_{01}}{lambda_{10}}+ frac{lambda_{12}lambda_{01}}{lambda_{21}lambda_{10}}+ldots+ frac{lambda_{n-1,n}cdotslambda_{12}lambda_{01}}{lambda{n,n-1}cdotslambda_{21}lambda_{10}}right)!}^{-1},$

(16)

$p_1=frac{lambda_{01}}{lambda_{10}}p_0,quad p_2=frac{lambda_{12}lambda_{01}}{lambda_{21}lambda_{10}}p_0,quad ,ldots,quad p_n=frac{lambda_{n-1,n}cdotslambda_{12}lambda_{01}}{lambda{n,n-1}cdotslambda_{21}lambda_{10}}p_0.$

(17)

Процесс гибели и размножения - Рисунок

Легко заметить, что в формулах (17) для p_1,p_2,ldots,p_n коэффициенты при p_0 есть слагаемые, стоящие после единицы в формуле (16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния S_k,(k=1,2,ldots,n) , а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния S_k .

Пример 4. Процесс гибели и размножения представлен графом (рис. 5). Найти предельные вероятности состояний.

Решение. По формуле (16) найдем

$p_0={left(1+frac{1}{4}+frac{2cdot1}{3cdot4}right)!}^{-1}= 0,!706,$ по (17) $p_1=frac{1}{4}cdot0,!706= 0,!176,~ p_2=frac{2cdot1}{3cdot4}cdot 0,!706=0,!118,$

т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии S_0 , 17,6% — в состоянии S_1 и 11,8% — в состоянии S_2 .

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

Уравнения Колмогорова. Предельные вероятности состояний

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем на примере случайного процесса из задачи 1, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния S_i в S_j происходят под воздействием простейших потоков событий с интенсивностями l_ij(i, j=0,1,2,3); так, переход системы из состояния S₀ в S₁ будет происходить под воздействием потока отказов первого узла,
а обратный переход из состояния S₁ в S₀ — под воздействием потока «окончаний ремонтов» первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 1). Рассматриваемая система S имеет четыре возможных состояния: S₀, S₁, S₂, S₃.

Вероятностью i-го состояния называется вероятность p_i(t) того, что в момент t система будет находиться в состоянии S_i. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

. (8)

Рассмотрим систему в момент t и, задав малый промежуток Dt, найдем вероятность p₀(t+Dt) того, что система в момент t+ Dt будет находиться в состоянии S₀. Это достигается разными способами.

1. Система в момент t с вероятностью p₀(t) находилась в состоянии S₀, а за время Dt не вышла из него.

Вывести систему из этого состояния (см. граф на рис. 1) можно суммарным простейшим потоком с интенсивностью (l₀₁+l₀₂), т.е. в соответствии с (15.7), с вероятностью, приближенно равной (l₀₁+l₀₂)Dt. А вероятность того, что система не выйдет из состояния S₀, равна [1-(l₀₁+l₀₂)Dt]. Вероятность того, что система будет находиться в состоянии S₀, по первому способу (т.е. того, что находилась в состоянии S₀ и не выйдет из него за время Dt), равна по теореме умножения вероятностей:

p₀(t)·[1-(λ₀₁+λ₀₂)*Δt].

2. Система в момент t с вероятностями р₁(t) (или p₂(t)) находилась в состоянии S₁ или S₂ и за время Dt перешла в состояние S₀.

Потоком интенсивностью l₁₀ (или l₂₀ — см. рис. 1) система перейдет в состояние S₀ с вероятностью, приближенно равной l₁₀Dt (или l₂₀Dt). Вероятность того, что система будет находиться в состоянии S₀ по этому способу, равна р₁(t)×l₁₀Dt (или р₂(t)×l₂₀Dt).

Применяя теорему сложения вероятностей, получим

p₀(t+Δt)=p₁·λ₁₀·Δt+p₂(t)·λ₂₀·Δt+p₀(t)[1-(λ₀₁+λ₀₂)·Δt],

откуда

Переходя к пределу при Dt→0 (приближенные равенства, связанные с применением формулы (7), перейдут в точные), получим в левой части уравнения производную p’₀(t) (обозначим ее для простоты p’₀):

p′₀ = λ₁₀·p₁+λ₂₀·p₂+(λ₁₀+λ₂₀)·p₀,

Получили дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы S, можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

(9)

Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности i-го состояния. В правой части — сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния).

В системе (9) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение (8).

Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задать так называемые начальные условия, т.е. в данном, случае вероятности состояний системы в начальный момент t = 0. Так, например, систему уравнений (9) естественно решать при условии, что в начальный момент оба узла исправны и система находилась в состоянии S₀, т.е. при начальных условиях p₀(0)=1, p₁(0)=p₂(0)=p₃(0)=0.

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы p_i(t) в предельном стационарном режиме, т.е. при t→∞, которые называются предельными (или финальными) вероятностями состояний.

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

Предельная вероятность состояния S_i имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S₀, т.е. p₀=0,5, то это означает, что в среднем половину времени система находится в состоянии S₀.

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы S с графом состояний, изображенном на рис. 1, такая система уравнений имеет вид:

(10)

Систему (10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния p_i, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Задача 2. Найти предельные вероятности для системы S задачи 1, граф состояний которой приведен на рис. 1, при l₀₁=1, l₀₂=2, l₁₀=2, l₁₃=2, l₂₀=3, l₂₃=1, l₃₁=3, l₃₂=2.

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

3p₀=2p₁+3p₂ (11)

4p₁=p₀+3p₃

4p₂=2p₀+2p₃

p₀+p₁+p₂+p₃=1

(Здесь мы вместо одного “лишнего” уравнения системы (10) записали нормировочное условие (8)).

Решив систему (11), получим p₀=0,40, p₁=0,20, p₂=0,27, p₃=0,13, т.е. в предельном, стационарном режиме система S в среднем 40% времени будет находиться в состоянии S₀ (оба узла исправны), 20% — в состоянии S₁ (первый узел ремонтируется, второй работает), 27% — в состоянии S₂ (второй узел ремонтируется, первый работает) и 13% времени — в состоянии S₃ (оба узла ремонтируются).

Задача 3. Найти средний чистый доход от эксплуатации в стационарном режиме системы S в условиях задач 1 и 2, если известно, что в единицу времени исправная работа первого и второго узлов приносит доход соответственно в 10 и 6 ден.ед., а их ремонт требует затрат соответственно в 4 и 2 ден.ед. Оценить экономическую эффективность СМО имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Решение. Из задачи 2 следует, что в среднем первый узел исправно работает долю времени, равную p₀+p₃=0,40+0,27=0,67, а второй узел — p₀+p₁=0,40+0,20=0,60. В то же время первый узел находится в ремонте в среднем долю времени, равную p₁+p₃=0,20+0,13=0,33, а второй узел – p₂+p₃=0,27+0,13=0,40. Поэтому средний чистый доход в единицу времени от эксплуатации системы, т.е. разность между доходами и затратами, равен

Д=0,67 ×10+0,60×6-0,33 ×4-0,40×2=8,18 ден.ед.

Уменьшение вдвое среднего времени ремонта каждого из узлов в соответствии с (6) будет означать увеличение вдвое интенсивностей потока “окончаний ремонтов” каждого узла, т.е. теперь l₁₀=4, l₂₀=6, l₃₁ =6, l₃₂=4 и система линейных алгебраических уравнений (10), описывающая стационарный режим системы вместе с нормировочным условием (8) примет вид:

3p₀=4p₁+6p₂

6p₁=p₀+6p₃

7p₂=2p₀+4p₃

p₀+p₁+p₂+p₃=1

Решив систему, получим p₀=0,60, p₁=0,15, p₂=0,20, p₃=0,05.

Учитывая, что p₀+p₂=0,60+0,20=0,80, p₀+p₁=0,60+0,15=0,75, p₁+p₃=0,15+0,05=0,20,
p₂+p₃=0,20+0,05=0,25, а затраты на ремонт первого и второго узла составляют теперь соответственно 8 и 4 ден. ед., вычислим средний чистый доход в единицу времени:Д₁=0,80 ×10+0,75×6-0,20 ×8-0,25×4=9,9 ден.ед.

Так как Д₁ больше Д (примерно на 20%), то экономическая целесообразность ускорения ремонтов узлов очевидна.

Пример. Техническое устройство может находиться в одном из трех состояний S₀, S₁, S₂. Интенсивность потоков, переводящих устройство из состояния, заданы в таблице.

Задача	Интенсивности потоков
λ₀₁	λ₀₂	λ₁₀	λ₁₂	λ₂₀	λ₂₁
78	2	2	1	2	3	0

Необходимо построить размеченный граф состояний, записать систему уравнений Колмогорова, найти финальные вероятности и сделать анализ полученных решений.

Размеченный граф состояний имеет вид.

По графу запишем систему уравнений Колмогорова в общем виде:

p₀(t) + p₁(t) + p₂(t) = 1

Вместо интенсивности потоков λ_ij запишем их конкретные значения и получим искомую систему:

p₀(t) + p₁(t) + p₂(t) = 1

Чтобы найти финальные вероятности состояний, в уравнениях Колмогорова отбросим первое уравнения, а по остальным составим систему алгебраических уравнений:

2p₀-3p₁ = 0

2p₀+2p₁-3p₂=0

p₀ + p₁ + p₂ = 1

Решим СЛАУ с помощью метода Гаусса.

Вывод: При достаточно большом времени работы техническое устройство с вероятностью p₀ = 0.36 будет находиться в состоянии S₀, с вероятностью p₁ = 0.24 в состоянии S₁ и с вероятностью p₂ = 0.4 в состоянии S₂.

Пример.

Техническое устройство может находиться в одном из трех состояний S₀, S₁, S₂. Интенсивность потоков, которые переводят устройства из одного состояния во второе, известны λ₀₁=2, λ₁₀=4, λ₂₁=2, λ₁₂=3, λ₂₀=4.

Необходимо построить размеченный граф состояний, записать систему уравнений Колмогорова, найти финальные вероятности и сделать анализ полученных решений.

Размеченный граф состояний имеет вид.

По графу запишем систему уравнений Колмогорова в общем виде:

Вместо интенсивности потоков λ_ij запишем их конкретные значения и получим искомую систему:

Чтобы найти финальные вероятности состояний, в уравнениях Колмогорова отбросим первое уравнения, а по остальным составим систему алгебраических уравнений:

2p₀-7p₁+2p₂=0

3p₁-6p₂=0

p₀+p₁+p₂=1

Делим первое уравнение на 2, а второе на 3 и получим систему

p₀-7p₁+2p₂=0

3p₁-6p₂=0

p₀+p₁+p₂=1

Из третьего уравнения вычитаем первое

p₀-3.5p₁+p₂=0

p₁-2p₂=0

4.5p₁=1

Отсюда получим p₁=0,22, p₂=0,11 и p₀=0,67.

Вывод: При достаточно большом времени работы техническое устройство с вероятностью p₀ = 0,67 будет находиться в состоянии S₀, с вероятностью p₁ = 0,22 в состоянии S₁ и с вероятностью p₂ = 0,11 в состоянии S₂.

Процесс гибели и размножения

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 4.

Рис. 4

Рассмотрим упорядоченное множество состояний системы S₀, S₁, S₂, …, S_k. Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния S_k возможны переходы только либо в состояние S_k-1, либо в состояние S_k+1. (При анализе численности популяций считают, что состояние S_k соответствует численности популяции, равной k, и переход системы из состояния S_k в состояние S_k+1 происходит при рождении одного члена популяции, а переход в состояние S_k-1, — при гибели одного члена популяции).

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями l_{k, k+1} или l_{k+1, k}.

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

В соответствии с правилом составления таких уравнений (см. 13) получим: для состояния S₀

λ₀₁p₀ = λ₁₀p₁ (12)

для состояния S₁ – (l₁₂+l₁₀)p₁=l₀₁ p₀+l₂₁p₂, которое с учетом (12) приводится к виду

λ₁₂p₁ = λ₂₁p₂ (13)

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

(14)

к которой добавляется нормировочное условие

p₀+p₁+p₂+…+p_n=1 (15)

Решая систему (14), (15), можно получить

(16)

(17)

Легко заметить, что в формулах (17) для p₁, p₂, …, p_n коэффициенты при p₀ есть слагаемые, стоящие после единицы в формуле (16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния S_k (k=1, 2, …, n), а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния S_k.

Задача 4.Процесс гибели и размножения представлен графом (рис. 5). Найти предельные вероятности состояний.

Рис. 5

Решение. По формуле (16) найдем

по (17) – т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии S₀, 17,6% — в состоянии S₁ и 11,8% — в состоянии S₂.

Источник

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

Рассмотрим
марковский процесс с дискретным
состоянием и дискретным временем.

Пусть
имеется физическая система
,
которая может находиться в состояниях
,
,
…,
,
причем переход системы из состояния в
состояние осуществляется скачками
только в моменты времени
,
,
…,
,
…, для которых разности

равны постоянному числу — шагу, для
простоты принимаемому за единицу
времени. Такие марковские процессы
называются марковскими цепями.

Определение.
Вероятностью состояния

называется вероятность системы

находиться в состоянии

после
-го
шага.

Очевидно,
что для каждого шага

Будем
считать, что вероятности

перехода системы из состояния

в состояние

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

Введем
так называемую матрицу вероятностей
перехода

.
(1)

Элементы
матрицы

неотрицательны, но могут равняться 0:
,
если переход системы

из состояния

в состояние

невозможен. Сумма элементов любой строки
матрицы

равна 1. Такие матрицы называются
стохастическими.

1.
Вероятности перехода из состояния

в состояние

за

шагов

определяются матрицей

где
,
откуда следует, что

.
(2)

2.
Теорема Маркова. Если при
некотором

все элементы матрицы

положительны, то существуют такие
положительные числа
,
,
…,
,
что независимо от начального состояния
системы

имеют место равенства

,
причем

.
(3)

Вектор

называется предельным распределением,
а числа

— предельными вероятностями состояний.

Предельное
распределение

можно найти как собственный вектор
матрицы

(
транспонированная), соответствующий
собственному значению
.

Пример
2. Задана матрица

вероятностей перехода цепи Маркова из
состояния

в состояние

за один шаг. Найти матрицу

перехода из состояния

в состояние
за
два шага и вероятность появления цепочки
состояний
——
за два шага. Выяснить, можно ли к матрице
применить теорему Маркова. Если да,
найти предельное распределение.

Решение.

Матрицу

получаем по формуле (2)

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

Матрица

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

как собственный вектор матрицы

из
матричного уравнения

(4)

при
,
т.е.

или
из системы

Эта
система равносильна системе

Решая
ее, например методом Жордана-Гаусса,
получим

~~,
откуда

А
с учетом (3)

т.е.
в стационарном режиме система в среднем

всего времени находится в состоянии
,

— в состоянии

и

— в состоянии
.

Рассмотрим
марковский процесс с дискретным
состоянием и непрерывным временем
временем.

Для
таких процессов рисуется граф состояний,
вершины которого соответствуют состояниям
S₀, S₁,…,S_n,
а дуги − переходам из одного состояния
в другое. Как правило, переход из одного
состояния в другое происходит под
действием простейшего потока событий
с интенсивностью
.
Граф, дугам которого приписаны
интенсивности
,
называется размеченным.

− вероятность
того, что в момент времени
система
находиться в состоянии
.

Для
вероятностей

имеет место условие нормировки:

(1)

и
система уравнений Колмогорова:

(2)

Гдеберётся
по всем состояниям
,
дуги из которых идут в состояния
.
Во второй сумме берутся все состояния,
в которые идут дуги из состояния
.

Особый
интерес представляет случай, когда
система может перейти в стационарный
режим.

,

− это предельные вероятности, получающиеся
при
.
Их находят из системы:

(3)

Среди
системы уравнений (3) одно лишнее (любое),
его следует отбросить и добавить условие
(1). Доказано, что если число состояний
конечно и из каждого состояния можно
перейти в любое другое, то предельные
вероятности существуют.

Пример:

Найти
предельные вероятности для системы,
размеченный граф которой имеет вид.

С
учетом условия нормировки получаем
систему

Отбрасываем
третье из уравнений, получаем:

§
4 Процессы гибели и размножения

описывают
изменение численности биологических
популяций.

Граф
состояний процесса гибели и размножения
имеет вид

т.к.
переход из любого состояния может
осуществляться только в состояния с
соседними номерами.

,
т.к.
,
то остается

и
далее аналогично

…………………..

Получаем
систему

из
которой с учетом условия нормировки
получаем окончательно

и
далее из системы находим
,
,…,
.

Пример.
Дан граф процесса гибели и размножения.

Найдите
предельные вероятности состояний.

Решение.
,

Отбрасываем
последнее уравнение, добавляем условие
нормировки и получаем систему

или

Окончательно

§
5. Некоторые задачи теории массового
обслуживания

Системы
массового обслуживания СМО − системы,
предназначенные для многократного
использования при решении однотипных
задач. Каждая система состоит из
определенного количества обслуживающих
единиц − каналов.

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

1.

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

2.

— абсолютная пропускная способность
СМО, т.е. среднее число заявок,
рассматриваемых в единицу времени.

3.

— относительная пропускная способность,
т.е. средняя доля пришедших заявок,
обслуживаемых системой.

4.

— вероятность отказа, т.е. того, что
заявка покинет систему необслуженной.

5.

— среднее число занятых каналов для
многоканальной системы.

6.

— интенсивность обслуживания, т.е.
количество заявок, обслуживаемых одним
каналом за единицу времени.

7.

— среднее время обслуживания, т.е.
.

Итак,
имеется

каналов, на которые поступает поток
заявок с интенсивностью
.
Поток обслуживания каждого канала имеет
интенсивность
.
Найдем предельные вероятности состояний
системы и показатели ее эффективности.

Система

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

— состояние системы, когда в ней находятся

заявок (занято

каналов).

Граф
состояний соответствует процессу гибели
и размножения.

Переход
в соседнее состояние с большим номером
всегда происходит под действием
простейшего потока с интенсивностью
,
а вот переход из состояния

в состояние

происходит под действием потока
интенсивности
,
так как освободиться может любой из

занятых каналов.

Формула
для предельной вероятности состояния

примет вид

,
(1)

где

— так называемая интенсивность
нагрузки канала, а

,
,
…,
,
…,
.
(2)

Найдем
показатели эффективности СМО.

Вероятность
отказа системы есть предельная вероятность
того, что все

каналов будут заняты, т.е.

Относительная
пропускная способность — вероятность
того, что заявка будет обслужена

Абсолютная
пропускная способность

Среднее
число занятых каналов
,
т.е. математическое ожидание числа
занятых каналов

или
иначе
.

Далее
разбирайте задачи к практическому
занятию и используйте методички (см.
список литературы).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

ПРЕДЕЛЬНЫЕ ВЕРОЯТНОСТИ СОСТОЯНИЙ

Пусть имеется физическая система S с дискретными состояниями:

в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Граф состояний показан на рис. 23.

Предположим, что все интенсивности потоков событий, переводящих систему из состояния в состояние, постоянны:

другими словами, все потоки событий – простейшие (стационарные . пуассоновские) потоки.

Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим вероятности состояний, как функции времени, т. е. n функций:

при любом t дающих в сумме единицу: .

Поставим теперь следующий вопрос: что будет происходить с системой S при t®¥? Будут ли функции p₁(t), p₂(t),…,p_n(t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными (или «финальными») вероятностями состояний.

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

На рис. 24 показан граф состояний, удовлетворяющий поставленному условию: из любого состояния система может рано или поздно перейти в любое другое. Напротив, для системы, граф состояний которой показан на рис. 25, условие не выполнено. Очевидно, что если начальное состояние такой системы S₁ то, например, состояние S₆ при t®¥ может быть достигнуто, а если начальное состояние S₂ – не может.

Предположим, что поставленное условие выполнено, и предельные вероятности существуют:

(i = 1, 2. n). (6.1)

Предельные вероятности мы будем обозначать теми же буквами р₁, р₂, … р_n, что и сами вероятности состояний, разумея подними на этот раз не переменные величины (функции времени), а постоянные числа.

Очевидно, предельные вероятности состоянии, так же как и допредельные, в сумме должны давать единицу:

Таким образом, при t®¥ в системе S устанавливается некоторый предельный стационарный режим: он состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени: каждое из состояний осуществляется с некоторой постоянной вероятностью. Каков смысл этой вероятности? Она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Например, если у системы S три возможных состояния: S₁,S₂ и S₃, причем их предельные вероятности равны 0,2, 0,3 и 0,5, это означает, что после перехода к установившемуся режиму система S в среднем две десятых времени будет находиться в состоянии S₁ три десятых – в состоянии S₂ и половину времени – в состоянии S₃. Возникает вопрос: как вычислить предельные вероятности состояний р₁, р₂, … р_n?

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

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

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

(7.2)

(так называемым «нормировочным условием») эти уравнения дают возможность вычислить все предельные вероятности

Пример 1. Физическая система S имеет возможные состояния: S_l, S₂, S₃, S₄, размеченный граф которых дан на рис. 26 (у каждой стрелки поставлено численное значение соответствующей интенсивности). Вычислить предельные вероятности состояний: р₁, р₂, р₃, р₄.

Решение. Пишем уравнения Колмогорова для вероятностей состояний:

(6.3)

Полагая левые части равными нулю, получим систему алгебраических уравнений для предельных вероятностей состояний:

(6.4)

Уравнения (6.4) – так называемые однородные уравнения (без свободного члена). Как известно из алгебры, эти уравнения определяют величины р₁, р₂, р₃, р₄ только с точностью до постоянного множителя. К счастью, у нас есть нормировочное условие:

которое, совместно с уравнениями (64), дает возможность найти все неизвестные вероятности.

Действительно, выразим из (6.4) все неизвестные вероятности через одну из них, например, через p₁. Из первого уравнения:

Подставляя во второе уравнение, получим:

Четвертое уравнение дает:

Подставляя все эти выражения вместо р₂, р₃, р₄ в нормировочное условие (6.5), получим

Таким образом, предельные вероятности состояний получены, они равны;

Это значит, что в предельном, установившемся режиме система S будет проводить в состоянии S₁ в среднем одну двадцать четвертую часть времени, в состоянии S₂ – половину времени, в состоянии S₃ – пять двадцать четвертых и в состоянии S₄ – одну четверть времени.

Заметим, что решая эту задачу, мы совсем не пользовались одним из уравнений (6.4) – третьим. Нетрудно убедиться, что оно является следствием трех остальных: складывая все четыре уравнения, мы получим тождественный нуль. С равным успехом, решая систему, мы могли бы отбросить любое из четырех уравнений (6.4).

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

Пример 2. Граф состоянии системы показан на рис. 27. Написать алгебраические уравнения для предельных вероятностей состояний.

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

(6.7)

Чтобы в дальнейшем сразу же писать такие уравнения, полезно запомнить следующее мнемоническое правило: «что втекает, то и вытекает», то есть для каждого состояния сумма членов, соответствующих входящим стрелкам, равна сумме членов, соответствующих выходящим; каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого выходит стрелка.

В дальнейшем мы во всех случаях будем пользоваться именно этим кратчайшим способом записи уравнений для предельных вероятностей.

Пример 3. Написать алгебраические уравнения для предельных вероятностей состояний системы S, граф состояний которой дан на рис. 28. Решить эти уравнения.

Решение.Пишем алгебраические уравнения для предельных вероятностей состояний;

(6.8)

Выразим с помощью первых двух уравнений (6.8) р₂ и р₃ через р₁:

(6.10)

Подставим их в нормировочное условие (6.9):

откуда .

Далее, из (6.10) получим

; .

Уравнения Колмогорова.
Предельные вероятности состояний

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем* на примере случайного процесса из примера 1, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния в происходят под воздействием простейших потоков событий с интенсивностями ; так, переход системы из состояния в будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния в — под воздействием потока “окончаний ремонтов” первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 1). Рассматриваемая система имеет четыре возможных состояния: .

Вероятностью i-го состояния называется вероятность того, что в момент система будет находиться в состоянии . Очевидно, что для любого момента сумма вероятностей всех состояний равна единице:

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

1. Система в момент с вероятностью находилась в состоянии , а за время не вышла из него.

Вывести систему из этого состояния (см. граф на рис. 1) можно суммарным простейшим потоком с интенсивностью , т.е. в соответствии с формулой (7), с вероятностью, приближенно равной . А вероятность того, что система не выйдет из состояния , равна . Вероятность того, что система будет находиться в состоянии по первому способу (т.е. того, что находилась в состоянии и не выйдет из него за время ), равна по теореме умножения вероятностей:

2. Система в момент с вероятностями (или ) находилась в состоянии или и за время перешла в состояние .

Потоком интенсивностью (или — с- рис. 1) система перейдет в состояние с вероятностью, приближенно равной (или ). Вероятность того, что система будет находиться в состоянии по этому способу, равна (или ).

Применяя теорему сложения вероятностей, получим

Переходя к пределу при (приближенные равенства, связанные с применением формулы (7), перейдут в точные), получим в левой части уравнения производную (обозначим ее для простоты ):

Сформулируем правило составления уравнений Колмогорова . В левой части каждого из них стоит производная вероятности i-го состояния. В правой части — сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния).

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

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

Предельная вероятность состояния имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии . Например, если предельная вероятность состояния , т.е. , то это означает, что в среднем половину времени система находится в состоянии .

Систему (10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом , согласно которому слева в уравнениях стоит предельная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пример 2. Найти предельные вероятности для системы из примера 1, граф состояний которой приведен на рис. 1, при

(Здесь мы вместо одного “лишнего” уравнения системы (10) записали нормировочное условие (8)).

Решив систему (11), получим , т.е. в предельном, стационарном режиме система в среднем 40% времени будет находиться в состоянии (оба узла исправны), 20% — в состоянии (первый узел ремонтируется, второй работает), 27% — в состоянии (второй узел ремонтируется, первый работает) и 13% времени — в состоянии (оба узла ремонтируются)

Решение. Из примера 2 следует, что в среднем первый узел исправно работает долю времени, равную , а второй узел — . В то же время первый узел находится в ремонте в среднем долю времени, равную , а второй узел — . Поэтому средний чистый доход в единицу времени от эксплуатации системы, т.е. разность между доходами и затратами, равен

Уменьшение вдвое среднего времени ремонта каждого из узлов в соответствии с (6) будет означать увеличение вдвое интенсивностей потока “окончаний ремонтов” каждого узла, т.е. теперь и система линейных алгебраических уравнений (10), описывающая стационарный режим системы , вместе с нормировочным условием (8) примет вид:

Решив систему, получим .

Учитывая, что , а затраты на ремонт первого и второго узла составляют теперь соответственно 8 и 4 ден.ед., вычислим средний чистый доход в единицу времени:

Так как больше (примерно на 20%), то экономическая целесообразность ускорения ремонтов узлов очевидна.

Процесс гибели и размножения

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 4.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями или .

В соответствии с правилом составления таких уравнений (см. 13) получим: для состояния

для состояния имеем , которое с учетом (12) приводится к виду

к которой добавляется нормировочное условие

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

Решая систему (14), (15), можно получить

Легко заметить, что в формулах (17) для коэффициенты при есть слагаемые, стоящие после единицы в формуле (16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния , а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния .

Пример 4. Процесс гибели и размножения представлен графом (рис. 5). Найти предельные вероятности состояний.

Теория случайных процессов и теория массового обслуживания

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

Содержание:

Элементы теории случайных процессов и теории массового обслуживания

Теория случайных процессов – это раздел математической науки, который изучает закономерности случайных явлений в динамике их развития.

Определение случайного процесса и его характеристики

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

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

Количество реализаций определенного случайного процесса изображено на рис. 4.1. Пусть сечение процесса при данном является непрерывной случайной величиной. Тогда случайный процесс при данном определяется плотностью вероятности

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

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

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

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

Случайный процесс может быть задан числовыми характеристиками.

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

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

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

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

Корреляционной функцией случайного процесса называется детерминированная функция

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

Корреляционная функция характеризует не только степень близости линейной зависимости между двумя сечениями, а и разброс этих сечений относительно математического ожидания

Поэтому рассматривается также нормированная корреляционная функция случайного процесса.

Нормированной корреляционной функцией случайного процесса называется функция

Пример. Случайный процесс определяется формулой где – случайная величина. Найти основные характеристики этого процесса, если

Решение. Согласно свойствам математического ожидания и дисперсии получим:

Находим далее корреляционную функцию

а также нормированную корреляционную функцию

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

Основные понятия теории массового обслуживания

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

Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, кассы, где продаются железнодорожные или авиабилеты, магазины, парикмахерские и т.п.

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

Заявки поступают в СМО конечно нерегулярно, а случайно, образуя так называемый случайный поток заявок (ссылок). Обслуживание заявок также длится в течение определенного случайного времени. Учитывая случайность потока заявок и время обслуживания, СМО загружаются неравномерно: в определенные периоды накапливается очень много заявок (они или стают в очередь, или оставляют СМО не обслуженными), в другие периоды СМО работает с малой загрузкой или простаивает.

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

Показателями эффективности СМО являются:

– среднее количество заявок, которые она обслуживает за единицу времени;
– среднее количество заявок в очереди;
– среднее время ожидания обслуживания;
– вероятность отказа в обслуживании без ожидания;
– вероятность того, что количество заявок в очереди превышает определенное значение и т.д.

СМО делятся на два основных класса: СМО с отказами и СМО с ожиданием (очередью).

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

В СМО с ожиданием заявка, которая поступает в момент, когда все каналы заняты, не оставляет систему, а становится в очередь на обслуживание.

Процесс работы СМО представляет собой случайный процесс.

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

Процесс функционирования СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем.

Математический анализ работы СМО существенно упрощается, если процесс этой работы – марковский.

Понятие марковского процесса

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

Пример. Система – счетчик в такси. Состояние системы в момент характеризуется количеством километров, пройденных автомобилем до данного момента. Пусть в момент счетчик показывает Вероятность того, что в момент счетчик будет показывать то или иное количество километров зависит от но не зависит от того, в какие моменты времени изменялись показатели счетчика до момента

Некоторые процессы можно приблизительно считать марковскими.

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

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

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

Решение. Возможные состояния системы: – оба узла исправны; – первый узел ремонтируется, а второй исправный; второй узел ремонтируется, а первый исправный; – оба узла ремонтируются.

Граф системы приведен на рис. 4.2.

Стрелка, направленная из до означает переход системы в момент отказа первого узла; стрелка из до – переход в момент окончания ремонта этого узла. Стрелки из до нет, поскольку допускается, что узлы выходят из строя независимо друг от друга.

Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, которое происходит в СМО, рассмотрим одно из важных понятий теории вероятностей – понятие потока событий.

Простейший поток событий

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

Поток называется простейшим, если он имеет такие свойства:

1) стационарность – вероятность того, что за некоторый промежуток времени произойдет то или иное количество событий, зависит только от длины промежутка и не зависит от начала его отсчета, то есть интенсивность потока постоянная;

2) отсутствие последействия – вероятность наступления некоторого количества событий в произвольном промежутке времени не зависит от того, какое количество событий произошло до начала этого промежутка;

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

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

Пример. Среднее количество заявок, поступающих на комбинат бытового обслуживания за 1 час равно 4. Найти вероятность того, что за 3 часа поступит: 1) 6 заявок; 2) менее 6 заявок; 3) не менее 6 заявок.

Решение. Пусть событие – “поступление одной заявки”. Поток заявок простейший. Поэтому для решения задачи используем приведенную только что формулу, в которой Вычислим соответствующие вероятности:

Уравнения Колмогорова. Предельные вероятности состояний

Вероятностью состояния называется вероятность того, что в момент система будет находиться в состоянии

Очевидно, что для любого момента сумма вероятностей состояний равна 1:

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

Например, для системы которая имеет четыре состояния система дифференцированных уравнений Колмогорова для вероятностей состояний принимает такой вид:

В системе (2) независимых уравнений на одно меньше от общего количества уравнений. Поэтому для решения системы необходимо прибавит уравнений (1) при

Особенность решения дифференциальных уравнений вообще состоит в том, что нужно задавать так называемые начальные условия, в данном случае – вероятности состояний системы в начальный момент Так, систему (2) должны решать при условии, что в начальный момент оба узла исправны и система находилась в состоянии то есть при начальных условиях

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

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

Предельная вероятность состояния имеет такое содержание: она показывает среднюю относительную продолжительность пребывания системы в этом состоянии. Например, если предельная вероятность состояния составляет то это означает, что в среднем половину времен системы находится в состоянии

Пример 1. Найти предельные вероятности для системы из последнего примера, граф состояний которой приведен на рис. 4.2. При

Решение. Система алгебраических уравнений, которая описывает стационарный режим для данной системы, принадлежит к виду (1):

Решая эту систему уравнений, получаем Следовательно, в предельном стационарном режиме система в среднем 40% времени находится в состоянии 20% – в состоянии 27% – в состоянии 13% – в состоянии

Пример 2. Найти прибыль от эксплуатации в стационаром режиме системы когда известно, что за единицу времени исправная работа первого и второго узлов приносит доход, который составляет соответственно 10 и 6 ус. ед., а их ремонт требует расходов, которые составляют соответственно 4 и 2 ус. ед.

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

Решение. Из примера 1 следует, что в среднем первый узел исправен в течение части времени, которая составляет а второй узел – в течение части В этом случае первый узел находится в ремонте в среднем часть времени, равной а второй – Поэтому средняя прибыль за единицу времени от эксплуатации системы (разница между доходом и расходами) будет такой:

Прибыль = (ус. ед.).

Уменьшение вдвое среднего времени ремонта каждого из узлов согласно с будет означать увеличение вдвое интенсивности потока “окончания ремонта” каждого узла. Следовательно, в этом случае и система линейных алгебраических уравнений (1) принимает вид:

Решая эту системы, получаем

Поскольку то расходы на ремонт первого и второго узла будут составлять соответственно 8 и 4 ус. ед. Отсюда получим среднюю прибыль за единицу времени:

(Прибыль) (ус. ед.)

(Прибыль) больше, чем Прибыль (приблизительно – на 2%), поэтому экономическая целесообразность сокращения срока ремонта узлов очевидна.

Лекции:

Присылайте задания в любое время дня и ночи в ➔

Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.

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

Сайт предназначен для облегчения образовательного путешествия студентам очникам и заочникам по вопросам обучения . Наталья Брильёнова не предлагает и не оказывает товары и услуги.

[spoiler title=”источники:”]

http://mathhelpplanet.com/static.php?p=uravneniya-kolmogorova

http://natalibrilenova.ru/teoriya-sluchajnyih-protsessov-i-teoriya-massovogo-obsluzhivaniya/

[/spoiler]

Источник

(Андрей Андреевич Марков (1856-1922) – русский математик, академик)

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

Определение. Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из K несовместных событий Ai из полной группы. При этом условная вероятность Pij(S) того, что в S –ом испытании наступит событие Aj при условии, что в (S – 1) – ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.

Независимые испытания являются частным случаем цепи Маркова. События называются Состояниями системы, а испытания – Изменениями состояний системы.

По характеру изменений состояний цепи Маркова можно разделить на две группы.

Определение. Цепью Маркова с дискретным временем Называется цепь, изменение состояний которой происходит в определенные фиксированные моменты времени. Цепью Маркова с непрерывным временем Называется цепь, изменение состояний которой возможно в любые случайные моменты времени.

Определение. Однородной Называется цепь Маркова, если условная вероятность Pij перехода системы из состояния I В состояние J не зависит от номера испытания. Вероятность Pij называется Переходной вероятностью.

Допустим, число состояний конечно и равно K.

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

Эта матрица называется Матрицей перехода системы.

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

На основе матрицы перехода системы можно построить так называемый Граф состояний системы, его еще называют Размеченный граф состояний. Это удобно для наглядного представления цепи. Порядок построения граф рассмотрим на примере.

Пример. По заданной матрице перехода построить граф состояний.

Т. к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

0,2 0,7

S2 0,4 S4

0,6 0,5

0,1 0,5

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

Пусть Pij(N) – вероятность того, что в результате N испытаний система перейдет из состояния I в состояние J, R – некоторое промежуточное состояние между состояниями I И J. Вероятности перехода из одного состояния в другое Pij(1) = Pij.

Тогда вероятность Pij(N) может быть найдена по формуле, называемой Равенством Маркова:

Здесь Т – число шагов (испытаний), за которое система перешла из состояния I В состояние R.

В принципе, равенство Маркова есть ни что иное как несколько видоизменная формула полной вероятности.

Зная переходные вероятности (т. е. зная матрицу перехода Р1), можно найти вероятности перехода из состояния в состояние за два шага Pij(2), т. е. матрицу Р2, зная ее – найти матрицу Р3, и т. д.

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

Тогда в общем виде можно записать:

Вообще то этот факт обычно формулируется в виде теоремы, однако, ее доказательство достаточно простое, поэтому приводить его не буду.

Пример. Задана матрица переходов Р1. Найти матрицу Р3.

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

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

Теорема. (теорема о предельных вероятностях) Пусть дана регулярная цепь Маркова с п состояниями и Р – ее матрица вероятностей перехода. Тогда существует предел и матрица Р(¥) имеет вид:

Т. е. матрица состоит из одинаковых строк.

Теперь о величинах Ui. Числа U1, U2, …, Un называются Предельными вероятностями. Эти вероятности не зависят от исходного состояния системы и являются компонентами собственного вектора матрицы РТ (транспонированной к матрице Р).

Этот вектор полностью определяется из условий: