Как найти предельную вероятность для графа - Исправление недочетов и поиск решений вместе с Examum.ru

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

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем на примере случайного процесса из задачи 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, граф которого изображен на рис. 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). Рассматриваемая
система S имеет четыре возможных
состояния: S₀,
S₁,
S₂,
S₃.

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

.
(8)

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

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

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

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

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

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

откуда

Переходя
к пределу при t0
(приближенные равенства, связанные
с применением формулы (7), перейдут в
точные), получим в левой части уравнения
производную p’₀(t)
(обозначим ее для простоты
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, при ₀₁=1,
₀₂=2,
₁₀=2,
₁₃=2,
₂₀=3,
₂₃=1,
₃₁=3,
₃₂=2.

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

(11)

(Здесь
мы вместо одного «лишнего» уравнения
системы (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) будет
означать увеличение вдвое интенсивностей
потока «окончаний ремонтов» каждого
узла, т.е. теперь ₁₀=4,
₂₀=6,
₃₁=6,
₃₂=4
и система линейных алгебраических
уравнений (10), описывающая
стационарный режим системы вместе с
нормировочным условием (8) примет вид:

Решив
систему, получим 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%), то экономическая
целесообразность ускорения ремонтов
узлов очевидна.

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

Г
раф
состояний процесса гибели и размножения
имеет вид, показанный на рис. 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,
— при гибели одного члена популяции).

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

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

(12)

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

(13)

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

(14)

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

(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, граф которого изображен на рис. 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). Найти предельные вероятности состояний.

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

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

Основные понятия и классификация систем массового

Обслуживания

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

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

Требованием (клиентом, заявкой) в СМО называется каждый отдельный запрос на выполнение какой-либо работы. Обслуживание — это выполнение работы по удовлетворению поступившего требования. Объект, выполняющий обслуживание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.

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

СМО классифицируются по разным признакам.

1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

2. В зависимости от условий ожидания требованием начала обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.

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

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

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

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

В качестве характеристик эффективности может применяться вероятность отказа как в системах с потерями (или характеристики времени ожидания) и в системах с ожиданием.

3. По дисциплине обслуживания СМО делятся на системы с приоритетом в обслуживании и на системы без приоритета в обслуживании.

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

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

5. По месту нахождения источника требований СМО делятся на разомкнутые (когда источник требования находится вне системы) и замкнутые (когда источник находится в самой системе).

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

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

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

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

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

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

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t, ровно kтребований задается формулой:

P_k= e — λt

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

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

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

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

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

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

Вероятность того, что на временном интервале t = τ не поступит ни одного требования p₀ определяется как:

Тогда вероятность того, что на этом же временном интервале появится хотя бы одно требование определяется соотношением

p(t) = 1– p₀ = 1– e — λτ .

Вероятность попадания на элементарный временной интервал, т.е. когда τ = Δt, хотя бы одного события (требования) потока, можно определить, заменив функцию e — λτ двумя первыми числами её разложения в ряд Маклорена по степеням Δt. Действительно:

p(Δt) = 1–e — λΔt ≈ λ Δt.

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

р (t — t ,

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

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

p(Δt) = 1–e -Δ t ≈ μλ Δt.

При анализе случайных процессов с дискретными состояниями пользуются графиком состояний, где прямоугольником изображаются состояния, а переходы из состояния в состояние – стрелками. У стрелок обычно проставляются значения интенсивностей λ_ij (μ_ij) перехода системы из состояния S_i в состояние S_j, которые происходят под воздействием простейших потоков событий.

Рассмотрим систему, которая может находиться в двух состояниях: S₀– система исправна; S₁ – система находится в состоянии отказа и ремонтируется (рис. 8.1).

Рис. 8.1. Граф системы

Будем характеризовать состояние системы (S₀,S₁) вероятностями состояния р₀ (t) и р₁ (t). Очевидно, что

Найдем вероятность того, что система в момент (t+Δt) будет находиться в состоянии S₀.

Это возможно, во-первых, в том случае, если система в момент времени t с вероятностью р₀(t)находилась в состоянии S₀ и за время Δtиз него не вышла. Вероятность выхода системы за время Δt из состояния S₀ в состояние S₁ определяется как λ· Δt. Противоположная вероятность (что система не выйдет из S₀) определяется как (1 – λΔt). Вероятность того, что система, находившаяся в состоянии S₀ с вероятностью р₀(t), за время Δt не выйдет из него, равна по теореме умножения вероятностей

Во-вторых, система в момент времени t находилась с вероятностью р₁(t)в состоянии S₁ и за интервал времени Δt с вероятностью μ·Δt перешла в состояние S₀, т.е.

Вероятность р₀(t + Δt) нахождения системы в состоянии S₀ момент времени (t + Δt)по какому-либо из двух рассмотренных способов равна сумме рассмотренных вероятностей

Преобразуем соотношение к виду

Переходя к пределу при Δt→0, получим

По аналогии составляется уравнение, описывающее вероятность того, что система в момент (t + Δt)будет находиться в состоянии S₁, но проще это найти из условия нормирования

С учетом этого условия система уравнений для двух состояний графа имеет вид

Задав начальные условия, можно решить систему уравнений и найти систему функций времени р_i(t), где i – номер состояния.

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

Тогда система уравнений упрощается (стационарный режим)

Откуда вероятности состояний установившегося процесса определяются как

В частности, если μ=2; λ=1, то Р₀=0,67; Р₁=0,33. Таким образом, в среднем система будет находиться в рабочем состоянии 67%, а в состоянии ремонта 33% времени.

В общем случае система уравнений Колмогорова может быть составлена по следующему алгоритму.

1. В левой части каждого уравнения стоит производная вероятности i-го состояния.

2. В правой части каждого уравнения стоит:

2.1. Сумма произведений вероятностей всех состояний, из которых идут стрелки в i-е состояние, на интенсивности соответствующих потоков событий.

2.2. Минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го состояния.

Система Колмогорова состоит из независимых уравнений и условия нормирования.

СМО с ожиданием

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

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

Постановка задачи в общем виде выглядит следующим образом.

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

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

Замкнутая СМО с ожиданием

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

Такую систему можно классифицировать как многоканальную СМО (n – каналов) и ограниченной данной очереди l, причем n +l = m.

Граф состояний такой системы изображен на рис. 8.2.

Рис. 8.2. Граф состояний многоканальной СМО с ограниченной очередью

Состояния данной системы означают:

S₀ – отсутствие требований в системе;

S₁ – одно требование обслуживается, очереди нет;

S₂ – два требования обслуживаются, очереди нет;

S_n– n требований обслуживаются, очереди нет;

S_n₊₁ – n требований обслуживаются, одно требование стоит в очереди;

S_n₊_l– n требований обслуживаются, l требований стоят в очереди.

Система уравнений вероятностей состояний в стационарном режиме для цепочки S₀ – S_n будет:

Для цепочки состояний S_n₊₁ – S_n₊_lсистема уравнений стационарного режима будет:

В качестве основных критериев, характеризующих качество функционирования рассматриваемой системы, выберем: 1) отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе – коэффициент простоя обслуживаемого объекта; 2) отношение среднего числа незанятых обслуживающих каналов к их общему числу – коэффициент простоя обслуживаемого канала.

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

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

P_k=α_kP₀, (1 k n),

где α_k= или α_k= ;

;

– интенсивность поступления требований в систему от одного источника;

_об – средняя продолжительность обслуживания одного требования;

т – наибольшее возможное число требований, находящихся в обслуживающей системе одновременно (m=n+l);

п– число обслуживающих аппаратов;

Р₀ – вероятность того, что все обслуживающие аппараты свободны.

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

P_k= _kP₀, (n k m),

где _k= ( _об) k или α_k= .

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

4. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди):

.

5. Коэффициент простоя требования в ожидании обслуживания:

a₁= .

6. Вероятность того, что все обслуживающие аппараты заняты:

P_отк= .

7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания):

A₂= = .

8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:

a₂= .

9. Среднее время простоя требования в очереди на обслуживание:

T_ож=a₁/ .

10. Среднее число свободных обслуживающих аппаратов:

A₃= .

11 . Коэффициент простоя обслуживающих аппаратов:

a₃ = .

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

P_—_B = = .

Рассмотрим пример расчета характеристик замкнутой СМО.

Пример 8.1. Оптовый склад строительных материалов обслуживает шесть предприятий-потребителей материалов. Каждый из потребителей направляет на склад автомашину за материалами в среднем один раз в смену (продолжительность смены 8 ч). На складе имеется один автопогрузчик, который используется только для погрузки материалов на прибывающие автомашины. Прибывшая на склад автомашина становится в очередь, если автопогрузчик занят погрузкой другой автомашины. Обработка статистических данных о продолжительности погрузки одной автомашины и проверка соответствующей гипотезы показали, что продолжительность погрузки одной автомашины подчиняется показательному закону распределения и составляет в среднем 48 мин (0,1 смены). Статистическое исследование потока автомашин показало, что число автомашин, поступающих на склад в единицу времени, подчиняется пуассоновскому закону распределения. Требуется провести расчет характеристик функционирования приведенной производственной системы как СМО.

Решение. Рассчитаем основные параметры системы для условий задачи.

Вероятность того, что все обслуживающие аппараты свободны (на складе нет автомашин) определяется как P₀, λ=1, μ=0,1.

Вероятность того, что на складе одна автомашина:

P₁= 0,1P₀=0,6P₀,

а вероятность того, что на складе две автомашины (одна под погрузкой, а другая в очереди):

P₂= 0,1 2 P₀=0,3P₀.

Рассчитывая аналогично, получим: Р₃=0,12Р₀; Р₄=0,036Р₀;Р₅= 0,0072Р₀; Р₆= 0,0007Р₀. Так как сумма вероятностей нахождения системы в любом из состояний равна 1, т.е.

=1,

то P₀(1 + 0,6 + 0,3 + 0,12 + 0,036 + 0,0072 + 0,0007) = 2,0639; Р₀ = 1.

Отсюда находим Р₀ = 0,4845.

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

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

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

Содержание:

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

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

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

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

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

Количество реализаций определенного случайного процесса изображено на рис. 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 запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

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

источники:

http://lektsii.org/7-1858.html

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

Источник

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

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

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

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

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

Марковские процессы делятся на два класса:

· дискретные марковские процессы (марковские цепи);

· непрерывные марковские процессы.

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

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

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

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

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

Известны вероятности перехода системы за один шаг из состояния в состояние .

Цель моделирования: определить вероятности состояний системы после -го шага.

Обозначим эти вероятности (не путать с вероятностями ).

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

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

Значения обычно сводятся в матрицу переходных вероятностей:

Значения могут также указываться на графе состояний системы. На рис. показан размеченный граф для четырех состояний системы. Обычно вероятности переходов «в себя» — , и т. д. на графе состояний можно не проставлять, так как их значения дополняют до 1 сумму переходных вероятностей, указанных на ребрах (стрелках), выходящих из данного состояния.

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

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

где — вероятность -го состояния системы после -го шага, ;

— вероятность -го состояния системы после -го шага, ;

— число состояний системы;

-переходные вероятности.

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

Для неоднородной марковской цепи вероятности состояний системы находятся по формуле:

где — значения переходных вероятностей для -го шага.

Сформулируем методику моделирования по схеме дискретных марковских процессов (марковских цепей).

1. Зафиксировать исследуемое свойство системы.

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

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

3. Составить и разметить граф состояний.

4. Определить начальное состояние.

5. По рекуррентной зависимости определить искомые вероятности.

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

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

Поэтому вместо переходных вероятностей вводятся в рассмотрение плотности вероятностей переходов :

где — вероятность того, что система, находившаяся в момент времени в состоянии за время перейдет в состояние .

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

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

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

Сформулируем методику моделирования по схеме непрерывных марковских процессов.

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

2. Составить и разметить граф состояний.

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

4. B левой части уравнения записывается производная вероятности -го состоянии

5. В правой части записывается алгебраическая сумма произведений и . Число произведений столько, сколько стрелок связано с данным состоянием. Если стрелка графа направлена в данное состояние, то соответствующее произведение имеет знак плюс, если из данного состояния — минус.

6. Определить начальные условия и решить систему дифференциальных уравнений.

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

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

Очевидно, .

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

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

Дата добавления: 2015-04-03 ; просмотров: 7867 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тема 5. Случайные процессы с дискретными состояниями и непрерывным временем.
Статистическое моделирование экономических систем
(метод Монте-Карло)

Вступление

На прошлой лекции мы начали рассматривать вероятностные модели.

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

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

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

Непрерывные цепи Маркова

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

В этом случае мы должны ввести в рассмотрение непрерывное время, чтобы отслеживать (ловить) эти случайные моменты срабатывания переходов.

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

Примеры

Поступление заявок на выполнение банковских операций.

Поломка машины в дороге.

Задание системы с конечным числом состояний и непрерывным временем наступления события (перехода из состояния в состояние)

Пусть система характеризуется n состояниями S₀, S₁, S₂. S_n, а переход из состояния в состояние может осуществляться в любой момент времени. Обозначим через P_i(t) вероятность того, что в момент времени t система S будет находиться в состоянии S_i (i = 0,1. n). Требуется определить для любого t вероятности состояний P₀(t), P₁ (t), …P_n(t). Очевидно, что

Определение плотности вероятностей перехода

Для процесса с непрерывным временем вместо переходных вероятностей Р_ij рассматриваются плотности вероятностей перехода λ_ij, представляющие собой предел отношения вероятности перехода системы за время из состояния S_i в состояние S_j к длине промежутка :

Если λ_ij=const, то процесс называется однородным.

Если плотность вероятности λ_ij(t), то процесс — неоднородный.

При рассмотрении непрерывных марковских процессов принято представлять переходы системы S из состояния в состояние как происходящие под влиянием некоторых потоков событий.

Потоки событий

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

В предыдущем примере – это поток отказов машины и поток восстановлений. Другие примеры: поток заявок в банкомат, поток покупателей в магазине, поток документов и т. д.

Поток событий можно наглядно изобразить рядом точек на оси времени Ot (рис. 1).

Рис. 1

Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.

Интенсивность потока событий (λ) – это среднее число событий, приходящееся на единицу времени.

Пусть задан момент времени t и промежуток времени .

Обозначим – среднее число событий на промежутке .

Тогда .

Свойства потока событий

Рассмотрим некоторые свойства (виды) потоков событий.

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

стационарность;
ординарность;
отсутствие последействия.

Стационарность

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

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.

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

Ординарность

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

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

Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по нескольку сразу. Иначе говоря, два события не происходят в один и тот же момент времени. Например, две машины не подъедут одновременно к стоянке, два человека не подойдут к банкомату, не обратятся с запросом к одной и той же БД и т.д.

За промежуток времени что может произойти?

ни одного события;
1 событие;
> 1 события.

Если рассмотреть очень маленький промежуток времени (0), то на нем можно выписать вероятности, которые зависят от времени t и от :

– вероятность того, что ничего не случится;

– вероятность, что случится 1 событие;

– вероятность, что случится больше 1-го события.

По природе вероятности можно записать

Последним слагаемым пренебрегаем в виду его малости.

Можно сформулировать свойство ординарности таким образом: для любого момента времени t можно указать две вероятности: (ничего не произойдет), (произойдет 1 событие)

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

Для ординарных потоков интенсивность (математическое ожидание числа событий в единицу времени) (число событий может быть либо 0, либо 1)

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

Отсутствие последействия

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

Например, поставили сачок в двух местах реки. Можно ли утверждать, что если в первый сачок поймали 10 рыб, то и во второй попадутся 10 рыб?

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:

стационарен;
ординарен;
не имеет последействия.

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

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

Если поток событий удовлетворяет описанным выше свойствам, то справедлива теорема Цинлара.

Теорема. Пусть <N (t), > – простейший поток событий. Пусть некоторый фиксированный интервал времени. Тогда количество событий k, приходящихся на промежуток, является случайной величиной с распределением Пуассона, имеющим параметр a = (), т.е.

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

Для простейшего потока , где – длина участка времени; – интенсивность потока:

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

Для простейшего потока с интенсивностью λ=const интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью

Для случайной величины T, имеющей показательное распределение, математическое ожидание m_T есть величина, обратная параметру, а среднее квадратичное отклонение σ_T равно математическому ожиданию

Если в системе все потоки пуассоновские, то процесс, протекающий в системе S, будет марковским. И к нему применима теория непрерывных цепей Маркова.

Задача

Банкомат обслуживает одного человека в среднем 2 мин. К банкомату подходит в среднем 20 чел/ч. Считая поток клиентов к банкомату и поток выдачи денег из банкомата простейшими пуассоновскими, определить интенсивности этих потоков в одних единицах измерения (единиц/мин).

– интенсивность потока клиентов к банкомату = 1/3 чел/мин;

μ – интенсивность потока выдачи денег = 0,5 операции/мин.

Модель 8. Гараж-непрерывный

Автомобиль может находиться в двух состояниях – Исправен S₁ или Ремонт S₂. Поток событий, при котором автомобиль переходит из состояния Исправен в состояние Ремонт, является простейшим и характеризуется заданной интенсивностью λ, которую можно трактовать как количество поломок (отказов) в единицу времени. Поток восстановлений автомобиля также является простейшим и характеризуется заданной интенсивностью µ, которую можно трактовать как количество отремонтированных машин в единицу времени.

Рис. 2

Интенсивность потока отказов – λ.

Интенсивность потока восстановлений – μ.

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

Начинаем выписывать производные:

Поясним смысл слагаемых в правой части этих выражений.

Событие (состояние) S₁ наступает за счет того, что осуществляется переход из узла (состояния) S₂ с интенсивностью μ, таким образом 1-е слагаемое показывает приращение вероятности, а уменьшение вероятности происходит от того, что осуществляется обратный переход к другому узлу с интенсивностью.

Пояснение на примере автомобиля. p₁(t)– вероятность того, что автомобиль исправен, может быть определено как отношение промежутка нахождения в исправном состоянии на общее время протекания процесса. Что увеличивает промежуток исправного состояния? Переход из неисправного состояния в исправное с интенсивностью μ. А что уменьшает этот промежуток? Соответственно, обратный переход с интенсивностью. Если автомобили ломаются и чинятся с одинаковой интенсивностью, то можно предположить, что вероятности нахождения в обоих состояниях будут равны 1/2.

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

Таким образом, изменение вероятности p₁(t) (т. е. производная функции) увеличивается за счет выхода из ремонта и уменьшается за счет нахождения в ремонте. Это и отражают слагаемые в 1-м уравнении (соответственно со знаком «+» и «–»).

p₂(t) – вероятность того, что автомобиль неисправен, может быть определено как отношение времени неисправного состояния на общее время протекания процесса.

Если сложим эти равенства, то получим

Интегрируя ДУ, получим, .

Если забудем, что функции – это вероятности, то получим систему ДУ, которые можно решить и получить законы вероятности нахождения в состояниях.

Одно из ДУ можно заменить соотношением вида, т. е., например, решать такую систему уравнений

Что может интересовать исследователя при решении таких ДУ?

Например, устойчивые решения, т. е. параметры, при которых имеют место устойчивые решения. То есть если есть устойчивое решение, то переходные процессы заканчиваются и, начиная с некоторого T*, функции p₁(t),p₂(t) выходят на стационарное значение (финальная вероятность).

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

Другое направление исследования – это собственно сами эти переходные процессы.

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

Уравнения Колмогорова

Пусть система характеризуется n состояниями S₀, S₁, S₂. S_n, а переход из состояния в состояние может осуществляться в любой момент времени и является простейшим потоком событий. Обозначим через Р_i(t) вероятность того, что в момент времени t система S будет находиться в состоянии S_i(i = 0,1. n). Требуется определить для любого t вероятности состояний P₀(t), P₁ (t), …P_n(t).

Прежде всего, построим граф состояний системы.

Итак, на систему, находящуюся в состоянии S_i, действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния S_i в состояние S_j(на графе состояний по стрелке S_iS_j).

Для наглядности на графе состояний системы у каждой дуги проставляют интенсивности того потока событий, который переводит систему по данной дуге (стрелке). λ_ij– интенсивность потока событий, переводящий систему из состояния S_i в S_j. Такой граф называется размеченным.

Уравнения Колмогорова представляют собой систему ДУ для определения вероятностей P_i(t)

Слагаемые вида , которые входят в систему со знаками «+» и «–», называются потоком вероятности перехода. При этом λ_ij могут быть постоянными или зависящими от времени.

Производная вероятности каждого состояния равна сумме всех потоков вероятности, идущих из других состояний в данное, и минус сумма всех потоков вероятности, идущих из данного состояния в другие.

Сформулируем мнемоническое правило, по которому в ДУ включаются те или иные слагаемые и те или иные знаки.

К этой системе можно добавить нормирующее уравнение:

Это уравнение дает возможность составить на одно ДУ меньше.

Систему можно решить вручную или с помощью компьютера.

Если записать ДУ Колмогорова для системы «Гараж», то получатся именно такие уравнения, которые мы выписали исходя из эмпирических рассуждений.

Финальные вероятности состояний

Если процесс, протекающий в системе, длится достаточно долго, то имеет смысл говорить о предельном поведении вероятностей P₁ (t), P₂ (t)… при .

Что будет происходить с вероятностями состояний при ? Будут ли P₁ (t), P₂ (t)… стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.

где n – конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что

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

Финальные вероятности состояний (если они существуют) могут быть получены путем решения системы линейных алгебраических уравнений, которые получаются из дифференциальных уравнений Колмогорова, если приравнять производные к нулю, а вероятностные функции состояний P₁(t), P₂(t)… в правых частях уравнений заменить соответственно на неизвестные финальные вероятности p ₁, p ₂ …

Финальная вероятность состояния S_i – это, по существу, среднее относительное время пребывания системы в этом состоянии.

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

Пример 1.

Например, рассмотрим граф системы:

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

Пример 2.

Здесь циклическое повторение событий.

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

Эргодичность может быть не по отношению ко всем узлам системы. Можно эргодическое поведение выделить в отдельную систему.

Пример. Составление ДУ Колмогорова

Система имеет размеченный граф. В начальный момент система находилась в состоянии S₁.

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

Граф после разметки

ДУ для состояния S₁:

Задание для самостоятельной работы.

Дописать систему ДУ Колмогорова.

Как найти финальные вероятности системы?

Вернемся к примеру состояний автомобиля (модель 8).

Мы выписали ДУ для вероятностей состояний исходя из здравого смысла. Но, зная уравнения Колмогорова, которые теоретически строго доказаны, мы видим, что полученная система уравнений соответствует этим уравнениям.

У нас записана система ДУ 1-го порядка, однородная с постоянными коэффициентами. Условие стационара для такой системы – равенство нулю правой части.

Это уравнения зависимые, т. к. в сумме дают 0.

Поэтому вместо одного используем равенство p₁+p₂=1, где p₁, p₂– финальные вероятности, т. е. система будет иметь вид:

Решив эту систему относительно p₁ и p₂, получим финальные вероятности системы:

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

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

Встречается в разнообразных практических задачах.

Марковский процесс с дискретными состояниями S₀, S₁, S₂. S_n называется процессом гибели и размножения, если все состояния можно вытянуть в одну цепочку, в которой каждое из средних состояний (S₀, S₁, S₂. S_n) может переходить только в соседние состояния, которые, в свою очередь, переходят обратно, а крайние состояния (S₀, S_n) переходят только в соседние состояния (рис. 3).

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

Название взято из биологических задач, где состояние популяции S_k означает наличие в ней k единиц особей.

Переход вправо связан с размножением единиц, а влево — с их гибелью.

У λ и μ индекс того состояния, из которого стрелка выходит.

С состоянием S_k связана неслучайная величина X_k: которая означает следующее: если система S в момент времени t находится в состоянии S_k, то дискретная случайная величина X(t), связанная с функционированием системы, принимает значение k. Таким образом, получаем случайный процесс X(t), который в случайные, заранее неизвестные моменты времени скачком изменяет свое состояние.

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

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

Пример

Рассмотрим эксплуатацию компьютеров в вычислительном центре. Интенсивность приобретения новых компьютеров равна (t). Каждый поступивший компьютер списывается через случайное время Т_с. Срок службы компьютера Т_с распределен по показательному закону с параметром μ. Процесс эксплуатации компьютера является случайным процессом. А(t) – число компьютеров, находящихся в эксплуатации в момент t. Требуется вычислить вероятности P_i(t)=Р , если: 1) нет ограничений на число эксплуатируемых компьютеров, 2) может эксплуатироваться не более N компьютеров.

Пример

Процесс чистого размножения – производство товаров.

Статистическое моделирование экономических систем
(метод Монте-Карло)

Теоретические основы метода

Метод статистического моделирования (или метод Монте-Карло) – это способ исследования поведения вероятностных систем в условиях, когда неизвестны в полной мере внутренние взаимодействия в этих системах.

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

Цель метода – определение числовых характеристик рассматриваемого процесса в виде статистических оценок его параметров.

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

Закон больших чисел

Основой метода статистического моделирования является закон больших чисел (ЗБЧ). ЗБЧ доказывает для различных условий сходимость по вероятности средних значений результатов большого числа наблюдений к некоторым постоянным величинам.

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

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

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

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

Теорема (центральная предельная). Если сделать предельный переход, то распределение случайной величины t будет стремиться к нормальному с МО, равным сумме МО t_i и дисперсией, равной сумме дисперсий t_i

Рассматривается в различных математических постановках в литературе по теории вероятностей.

Пояснение. Практический смысл.

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

Предельная теорема о суперпозиции (наложении) потоков

Предположим, что можно наблюдать k независимых потоков событий. В каждом потоке можно наблюдать m_j элементарных событий. Интервалы между событиями – это независимые случайные величины, распределенные по неизвестному закону с МО . Если спроецировать на временную ось моменты наступления событий из наблюдаемых потоков, то получим случайные интервалы времени между событиями.

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

Теорема. Если сделать предельный переход , то распределение случайной величины интервала t будет стремиться к показательному с МО, равным

Пример.

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

Примеры потоков, имеющих показательное (экспоненциальное) распределение:

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

Схема решения задачи методом статистического моделирования

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

Результаты, получаемые при статистическом моделировании подвержены экспериментальным ошибкам.

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

Моделирование случайных величин

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

Наиболее общим способом получения последовательности случайных чисел, распределенных по произвольному закону, является способ, основанный на формировании их из последовательности равномерно распределенных чисел на промежутке [0, 1].

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

Экспоненциальное (показательное) распределение случайной величины задается плотностью распределения:

(мат.ожидание и среднеквадратическое отклонение равны 1/).

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

Генерируется случайное равномерно распределенное число ξ на промежутке [0,1]. В среде MVS это можно сделать с помощью функции uniform (0,1).
Для преобразования равномерно распределенного случайного числа в случайное число с заданным законом распределения F(t) надо решить уравнение вида. Если закон распределения задан плотностью распределения, то уравнение имеет вид.

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

Такие же соотношения получены и для других законов распределения

источники:

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

http://eos.ibi.spb.ru/umk/11_4/5/5_R0_T5.html

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тема 5. Случайные процессы с дискретными состояниями и непрерывным временем. Статистическое моделирование экономических систем (метод Монте-Карло)

Оглавление

Вступление

Непрерывные цепи Маркова

Примеры

Задание системы с конечным числом состояний и непрерывным временем наступления события (перехода из состояния в состояние)

Определение плотности вероятностей перехода

Потоки событий

Рис. 1

Свойства потока событий

Стационарность

Ординарность

Отсутствие последействия

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

Задача

Модель 8. Гараж-непрерывный

Рис. 2

Уравнения Колмогорова

Финальные вероятности состояний

Пример. Составление ДУ Колмогорова

Задание для самостоятельной работы.

Как найти финальные вероятности системы?

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

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

Пример

Пример

Статистическое моделирование экономических систем (метод Монте-Карло)

Теоретические основы метода

Закон больших чисел

Пояснение. Практический смысл.

Предельная теорема о суперпозиции (наложении) потоков

Пример.

Примеры потоков, имеющих показательное (экспоненциальное) распределение:

Схема решения задачи методом статистического моделирования

Моделирование случайных величин

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

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

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

Тема 5. Случайные процессы с дискретными состояниями и непрерывным временем.
Статистическое моделирование экономических систем
(метод Монте-Карло)

Статистическое моделирование экономических систем
(метод Монте-Карло)