МАССОВОГО ОБСЛУЖИВАНИЯ

 

 

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

2.Случайные процессы.

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

4.Нестационарный пуассоновский поток.

5.Поток Пальма.

6.Потоки Эрланга.

7. Цепи Маркова.

8. Матрица переходов и граф состояний.

9. Предельные вероятности.

10.Марковские цепи с конечным числом состоянии и непрерывным временем

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

12.Системы массового обслуживания и их классификация.

13.Марковские системы массового обслуживания

14.Показатели эффективности систем массового обслуживания

15.Замкнутые системы массового обслуживния

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

17 Таблица основных формул для открытых СМО

18. Одноканальная система с произвольным распределением времени обслуживания

Литература

 

 

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

 

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

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

Теория массового обслуживания описывает закономерности функционирования таких систем.

 

2. Случайные процессы.

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

Рассмотрим физическую систему, которая в каждый момент времени может находиться в одном из k различных состояний, которые обозначим через

А₁, А₂,... , А_k..

Предположим теперь, что в определенные моменты времени t=0, 1, 2,... , называемыешагами, система может переходить из одного состояния в другое. Если переходы системы из состояния в состояние на каждом шаге происходят случайно, то гово­рят, что в системе возникслучайный процесс с дискретным временемили система относится к дискретному типу. В таком случае можно рассмотреть последовательность случайных величин:

X₀, X₁, X₂, ..., X_m, ...,

где X_m=i, если в момент времени m система находилась в состоянии A_i.

 

 

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

 

 

Распределение вероятностей p_k(t) для каждого момента времени характеризует данное сечение случайного процесса.

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

Большинство реальных систем массового обслуживания являются системами с с непрерывным временем.

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

 

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

 

 

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

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

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

Однородный поток можно изобразить последовательностью точек t₁, t₂, ... , t_i, …— моментов наступления событий на оси времени Ot. Здесь t₀ -начальный момент.

 

t₀ t₁ t₂ t₃ . . . t_i . . . t

· · · · ·

 

 

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

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

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

 

 

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

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

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

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

 

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

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

 

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

 

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

P_i(t) = e^- , (i 0),

Поэтому простейший поток называют такжепуассоновскимпотоком.

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

F(t) = P(T < t) = 1 - P(T ³ t) = 1 – P₀(t), (1)

где P(T < t) — вероятность того, что случайная величина Т примет значение, меньшее, чем t;

P(T ³ t) = P₀(t) — вероятность противо­положного события (т. е. за время t в СМО не поступила ни одна заявка). По формуле Пуассона имеем:

P₀(t) = e^- = e^- ,

поэтому из (1) получим

 

F(t) = 1 - e^- , (t > 0). (2)

 

Плотность распределения случайной величины Т:

f(t) = F^’(t) = l e^- , (t > 0).

Математическоеожидание и дисперсия слу­чайной величины Т:

M[T] = , D[T] = , . (3)

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

 

 

Пример. В бюро обслуживания в среднем поступает 12 заявок в час. Считая поток заказов простейшим, определить вероятность того, что: а) за 1 минуту не поступит ни одного заказа, б) за 10 минут поступит не более трех заказов.

 

Сначала найдем плотность (интенсивность) потока, выразив ее в количестве заявок в минуту. Очевидно, эта величина равна .

Далее находим вероятность того, что за время t = 1 мин не поступит ни одной заявки по формуле:

 

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

 

 

 

Пример. В ресторан прибывает в среднем 20 посетителей в час. Считая поток посетителей простейшим, и зная, что ресторан открывается в 11.00, определите:

а) вероятность того, что в 11.12 в ресторан придет 20 посетителей при условии, что в 11.07 их было 18

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

 

Для ответ на первый вопрос фактически надо найти вероятность того, что в промежуток от 11.07 до 11.12 (t = 5 минут) придет ровно 2 посетителя. При этом мы знаем интенсивность потока посетителей - l = 20/60 = 1/3 посетителей в минуту. Конечно, данная величина носит условный характер, т.к. посетители не могут приходить по частям.

Искомая вероятность равна:

 

Теперь перейдем ко второму вопросу. Нам не сказано, сколько именно новых посетителей будет в промежутке от 11.28 до 11.30, главное чтобы был хоть один. Эта вероятность равна . Здесь Р₀ (2) – вероятность того, что в этом промежутке не будет ни одного посетителя.

 

Пример.В процессе эксплуатации ЭВМ возникают неисправности (сбои). Поток сбоев считается простейшим. Среднее число сбоев за сутки равно m. Найти вероятности следующих событий:

A - за суток нет ни одного сбоя

B - за одни сутки будет хотя бы один сбой

C - за неделю произойдет не менее сбоев

 

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

 

Определение. Мгновенной плотностьюпотока событий называется предел отношения среднего числа событий, приходящегося на элементарный отрезок времени (t, t + Dt), к длине этого участка, которая стремиться к нулю.

 

 

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

3. Нестационарный пуассоновский поток

Определение. Нестационарным пуассоновским потокомназывается ординарный поток однородных событий без последействий с переменной плотностью l(t).

 

Для такого потока число событий, попадающих на участок длины t, начинающийся в точке t₀, подчиняется закону Пуассона:

 

 

Здесь а – математическое ожидание числа событий на участке от t₀ доt + t₀ . Оно вычисляется по формуле:

 

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

Вероятность того, что на участке времени от t₀ до t + t₀ не появится ни одного события, равна

 

 

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

 

 

Плотность распределения можно найти дифференцированием:

 

 

Эта плотность распределения уже не будет показательной. Она зависит от параметра t₀ и вида функции l(t). Однако, условие отсутствия последействия в этом виде потока сохраняется.

 

 

5.Поток Пальма.

 

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

 

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

 

Если промежутки времени Т₁, Т₂, … распределены по показательному закону, то поток Пальма становится простейшим потоком.

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

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

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

 

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

 

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

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

 

6.Потоки Эрланга.

 

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

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

 

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

 

Очевидно, что простейший поток может рассматриваться как поток Эрланга нулевого порядка.

 

Пусть имеется простейший поток с интервалами Т₁, Т₂, … между событиями. Величина Т – промежуток времени между двумя соседними событиями в потоке Эрланга k – го порядка.

Очевидно, что . Так как первоначальный поток – простейший, то случайные величины Т₁, Т₂, … распределены по показательному закону:

 

 

Обозначим f_k(t) плотность распределения величины Т для потока Эрланга k – го порядка. Если умножить эту плотность на элементарный отрезок времени dt, мы получим вероятность того, что величина Т примет значение в некоторой сколь угодно малой окрестности точки t- (t, t + dt). На этот участок должна попасть конечная точка промежутка, а предыдущие k точек простейшего потока – на промежуток (0, t).

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

 

 

 

Полученный закон распределения называется законом распределением Эрланга k- го порядка.

При k = 0 получаем показательный закон распределения.

 

Математическое ожидание, дисперсия и среднее квадратическое отклонение для распределения Эрланга находятся по формулам:

 

 

Плотность потока Эрланга равна

 

 

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

 

Закон распределения для такого потока будет иметь вид:

 

,

 

Математическое ожидание и дисперсия будут равны:

 

Получается, что неограниченном увеличении k нормированный поток Эрланга приближается к регулярному потоку с постоянными интервалами, равными .

Изменение порядка нормированного потока Эрланга позволяет получить различную степень последействия. Последействие возрастает с увеличением k.

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

 

Пример. На диспетчерский пульт поступает поток заявок, который является потоком Эрланга второго порядка. Интенсив­ность потока заявок равна заявок в час. Если диспетчер в слу­чайный момент оставляет пульт, то при первой же очередной за­явке он обязан вернуться к пульту.

Найти плотность распределения времени ожидания очеред­ной заявки и построить ее график. Вычислить вероятность того, что диспетчер сможет отсутствовать от t₁ до t₂. минут.

 

Дано:

 

Решение: Поскольку поток Эрланга второго порядка является стационарным потоком с ограниченным последействием, то для него справедлива формула Пальма:

 

(1)

,

 

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

- интенсивность потока;

- порядок потока;

- функция распределения вероятностей для времени между двумя соседними событиями потока Эрланга k-го порядка (Э_k).

 

Известно, что функция распределения для потока Э_k имеет вид:

 

(2)

,

 

По условию задачи поток заявок является Эрланговским порядка k=2. Тогда из (1) и (2) получим:

 

(3)

.

 

Из последнего соотношения (3) при будем иметь:

 

.

 

При .

 

Рассмотрим предел:

 

 

При вычислении предела числа для неопределенности типа использовано правило Лопиталя.

Перейдем к одним единицам времени:

 

 

 

 

 

 

 

 

Û Q = 0.

 

Û .

 

Из курса теории вероятностей известно, что вероятность попадания случайной величины X в отрезок численно равна площади под кривой плотности распределения вероятностей f(x). Эта площадь выражается определенным интегралом:

 

 

Следовательно, искомая вероятность равна:

 

 

Этот интеграл вычисляется по частям, если положить

Используя формулу:

получим

 

Ответ: вероятность того, что диспетчер сможет отсутствовать от 20 до 30 минут равна 0,71.

7.Цепи Маркова.

 

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

 

 

Определение. Случайный процесс с дискретным временем называется марковским, если на любом шаге S вероятность P (S) перехода системы из состояния i , в состояние jзависитлишь от состояния А в которое попала система на (S—1) шаге, и не зависит от того, как и когда она в это состояние попала. Кратко это свойство формулируют так: при задан­ном настоящем будущее не зависит от прошлого. В силу это­го марковский процесс еще называют процессомбез после­действияили однородным.

 

Определение. Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий A_i из полной группы. При этом условная вероятность p_ij(s) того, что в s –ом испытании наступит событие A_j при условии, что в (s – 1) – ом испытании наступило событие A_i, не зависит от результатов предшествующих испытаний.

 

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

 

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

 

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

 

8. Матрица переходов и граф состояний.

 

Определение. Однороднойназывается цепь Маркова, если условная вероятность p_ij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность p_ij называется переходной вероятностью.

 

Пусть, число состояний конечно и равно k.

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

 

 

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

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

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

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

 

 

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

S₁

0,2 0,7

 

 

S₂ 0,4 S₄

0,6 0,5

 

0,1 0,5

S₃

 

На графе не отмечаются вероятности перехода системы из одного состояния в то же самое.

Пусть P_ij(n) – вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r – некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое p_ij(1) = p_ij.

 

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

 

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

Равенство Маркова можно трактовать как видоизмененную формулу полной вероятности.

Используя матрицу перехода Р₁, можно найти вероятности P_ij(2) перехода из состояния i в состояние j за два шага , т.е. матрицу Р₂:

так как при n=2 равенство Маркова – формула умножения матрицы P₁ на P₁ , следовательно, можно получить:

 

 

 

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

 

 

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

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

 

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

 

 

8. Предельные вероятности

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

 

Т.о. матрица Р^(¥) состоит из одинаковых строк. Числа u₁, u₂, …, u_n называются предельными вероятностями.Эти вероятности не зависят от исходного состояния системы и являются компонентами собственного вектора матрицы Р^Т (транспонированной к матрице Р).

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

 

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

 

 

 

 

C учетом того, что u₁ + u₂ = 1, получаем:

 

 

Итак:

Возможные состояния системы в момент t=m можно охарактеризовать векторами ^(m)=(q₁^(m), q₂^(m), ..., q_k^(m)),

где q_i^(m) – это вероятность того, что в момент t=m система находится в состоянии А_i.

Используя формулу полной вероятности, нетрудно показать, что имеет место равенство:

^(m+1)= ^(m)×Р.

Применяя эту формулу последовательно при m=0, 1, 2,... , можно получить выражение для вектора ^(m) через вектор начальных состояний ⁽⁰⁾ и матрицу вероятностей переходов Р, а именно:

^{(m)= (0)×}Р^m.

Предельным распределением вероятностей цепи Маркова называется вектор q^p={q₁, q₂, ..., q_k} такой, что

 

Стационарным распределением называется вектор q={q₁, q₂, ..., q_k}, который удовлетворяет условиям:

 

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

(*)

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

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

 

Задача 1. Задана матрица P₁ вероятностей перехода дис­кретной цепи Маркова из i-ro в j-oe состояние за один шаг (i, j = 1, 2). Распределение вероятностей по состояниям в началь­ный момент t = 0 определяется вектором .

Найти:

1) матрицу P₂ перехода цепи из состояния i в со­стояние j за два шага;

2) распределение вероятностей по состоя­ниям в момент t = 2;

3) вероятность того, что в момент t = 1 со­стоянием будет i = 2;

4) стационарное распределение.

 

Дано:

 

Решение: Для дискретной цепи Маркова в случае её однородности справедливо соотношение ,

где P₁ – матрица переходных вероятностей за один шаг

P_n – матрица переходных вероятностей за n шагов;

 

1) Найдем матрицу P₂ перехода за 2 шага.

Пусть распределение вероятностей по состояниям на S-ом шаге определяется вектором

Зная матрицу P_n перехода за n шагов можно определить распределение вероятностей по состоянием на (s+n)-ом шаге.

(4)

,

 

2) Найдем распределение вероятностей по состоянием системы в момент t=2. Положим (4) S=0 и n=2. Тогда .

Получим

 

3) Найдем распределение вероятностей по состояниям системы в момент t=1. Положим в (4) S(0) и n=1, тогда

Откуда видно, что вероятность того, что в момент t=1 состоянием цепи будет A₂, равна p₂(1)=0,87.

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

(5)

Тогда из соотношения (4) при n=1 получим или

4) Найдем стационарное распределение. Так как k=2 имеем . Запишем систему линейных уравнений (5) в координатной форме:

 

; ; ; ; .

Следовательно, .

Ответ:

1) матрица перехода за два шага для данной цепи Маркова имеет вид ;

2) распределение вероятностей по состояниям в момент t=2 равно ;

3) вероятность того, что в момент t=1 состоянием цепи будет A₂, равна p₂(1)=0,87;

4) Стационарное распределение имеет вид .

Задача 2. Ремонтная мастерская располагает двумя диагностическими приборами. Известно, что если в какой-то день оба прибора были незаняты, то на следующий день с вероятностью 0,6 они снова окажутся незанятыми и с одинаковыми вероятностями будет занят один или два прибора. Если был занят один прибор, то назавтра с вероятностью 0,2 оба будут свободны и с вероятностью 0,5 – оба заняты. Наконец, если оба прибора были заняты, то назавтра с вероятностью 0,6 оба опять будут заняты и с вероятностью, вдвое меньшей, будет занят только один прибор. Предполагая, что в начале недели (в понедельник) нет никакой информации о занятости приборов, найти вероятность того, что в среду оба прибора будут заняты. Кроме того, найти предельное распределение вероятностей.

Решение. Рассмотрим следующие состояния:

Е₀ – не занят ни один прибор;

Е₁ – занят один прибор;

Е₂ – заняты оба прибора.

Исходя из условия задачи матрица вероятностей переходов имеет вид:

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

=(1/3; 1/3; 1/3).

Вероятности состояний в среду определяются вектором q⁽²⁾.

Имеем:

 

Таким образом, вероятность занятости сразу двух приборов будет равна 136/300.

Предельные вероятности найдем как решение системы:

Решая эту систему методом Гаусса, найдем:

q₁=13/51;

q₂=14/51;

q₃=24/51.

 

 

10.Марковские цепи с конечным числом состоянии и непрерывным временем

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

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

Для непрерывной цепи Маркова. вероятность перехода из состояния А_i в состояние А_j в любой момент времени равна нулю. Поэтому вместо вероятности перехода Р_ij рассматривают плотность вероят­ности перехода l_ij которая определяется как предел отно­шения вероятности перехода Р_ij{Dt} за время Dt из состо­яния A_i в состояние A_j; к длине промежутка Dt при Dt 0, т. е.

l_ij = . (1)

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

Если плотность ве­роятности перехода l_ij не зависит от t, марковский процесс(цепь) называетсяоднородным.

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

Из курса дифференциального исчисления известно, что соотношение (1) можно записать в виде Р_ij(Dt)=l_ijDt + a_ij(Dt), где a_ij(Dt)— бесконечно малая высшего порядка по сравнению с Dt. Тогда с точностью до бесконеч­но малой имеем:

P_ij(Dt) = l_ijDt, i j (2)

т. е. вероятность перехода Р_ij(Dt) за малое время Dt равна произведению плотности вероятности перехода l_ij на Dt. По­этому l_ij еще называютинтенсивностью перехода системы из А_i в Aj.

Из величин l_ij составим квадратнуюматрицу интенсивностей переходов:

L = (3)

обладающую свойствами:

1) l_ij 0, i j, это следует из (2), так как P_ij(Dt) 0;

2) l_ij 0, i=j, так как l_ii = (P_ii(Dt) – 1);

 

3) = 0 действительно, (l_i1 + l_i2 + … l_ii + … l_ik)Dt = P_i1(Dt) + P_i2(Dt) +…+( P_ii(Dt) – 1) + …+ P_ik(Dt)) = 0.

Интенсивности переходов l_ij удобно задавать на графе состояний. На графе указывают обычно интенсивности l_ij >0.

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

p₁ (t), p₂ (t), …, p_k(t), = 1, (4)

т. е. вероятности нахождения системы в состоянии А₁, А₂, … , А_k в момент времени t. Вероятности p_i(t) как функции t удовлетворяютсистеме дифференциальных уравнении Колмо­горова, которая в матричной форме имеет вид

p^’(t) = p(t) L (5)

где p^’(t) = ( p₁^’(t), p₂^’(t),…, p_k^’(t)); p(t) = ( p₁(t), p₂(t),…, p_k(t)), L —

матрица интенсивностей переходов (З).

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

p(t) = p, (6)

где p = ( p₁, p₂, …, p_k) = const, j = 1, 2, ..., k. Дифференцируя равенство (6) по t, получим: p^’(t) = 0.

С учетом уравнения (5) приходим к выводу, что стационар­ное распределение удовлетворяет соотно­шению

p L = 0, (7)

т. е. для получения стационарного распределения достаточно в системе дифференциальных уравнений Колмогорова поло­жить p^'_j =0; j =1, 2,.., k.

Уравнения системы (7) не в матричной форме удобно вы­писывать непосредственно по размеченному графику состоя­ний в соответствии со следующим правилом:

сумма произведений l_jip_i, j i для стрелок, выходящих из i-го состояния, рав­на сумме произведений l_ijp_j, j iдля стрелок, входящих в i-е состояние.

Задача 2. Задана матрица

интенсивностей переходов непрерывной цепи Маркова. Со­ставить размеченный граф состояний, соответствующий мат­рице L; выписать систему дифференциальных уравнений Колмогорова для вероятностей состояний; найти стационар­ное распределение вероятностей.

Решение. Размеченный граф должен иметь 3 состояния А₁, А₂, А₃. Из матрицы L находим интенсивности переходов l_ij>0, i j и отмечаем их над соответствующими стрелка­ми (рис. 2). Имеем l₁₂=5, соединяем состояния А₁ и А₂ стрел­кой, направленной от А₁ к А₂, отмечая интенсивность перехода над стрелкой; l₁₃=0, следовательно, состояния А₁ и А₃ стрелкой не соединяем и т. д. Составляем

уравнения Колмогорова: положим в уравнении (5); p(t) = (p₁(t), p₂(t), p₃(t)); p^’(t) = (p₁^’(t), p₂^’(t), p₃^’(t)),

тогда

(p₁^’(t), p₂^’(t), p₃^’(t)) = (p₁(t), p₂(t), p₃(t))

 

умножая вектор p(t) на матрицу L будем иметь:

p₁^’(t) = - 5 p₁(t) + p₂(t) + p₃(t);

p₂^’(t ) = 5p₁(t) - p₂(t) + p₃(t);

p₃^’(t ) = -2 p₃(t).

Для нахождения стационарного распределения достаточ­но в последней дифференциальной системе положить все производные p_i^’(t ) = 0, i = 1, 2, 3. Пусть p = (p₁, p₂, p₃)есть стационарное распределение, тогда:

0 = - 5 p₁ + p₂ + p₃;

0 = 5p₁ - p₂ + p₃; (8)

0 = -2 p₃.

 

Решая систему, получим p₃ = 0, p₂= 5p₁. В силу уравнения (4) p₁ + p₂ + p₃ = 1,следовательно, p = ( 1/6; 5/6; 0).

Заметим, что для определения стационарного распределе­ния мы получили бы такую же систему, если бы воспользо­вались правилом, приведенным выше. Действительно, для состояния А₁ имеем 5 p_{1 =} 1 p₂ + 1 p₃ , для состояния А₂: 1 p₂ = 5p₁ + 1 p₃, для состояния A₃: 1 p₃ + 1p₃ = 0. Составляя из этих уравнений систему, убедимся, что она эквивалентна си­стеме(8).

Для многих практических случаев важно знать, как ведут себя вероятности p_i(t}, i=l, 2,..., k при большом времени работы системы, т. е. при t . Если при определенных ус­ловиях существуютпредельные вероятности состояний

p_i = p_i(t), i = 1, 2, …, k, (9)

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

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

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

Состояние А_i называетсянесущественным, если найдется такое состояние А_j что из A_i в А_j, перейти можно, а из Aj в A_i — нельзя. Состояние A_i называетсясущественным,если оно не является несущественным. Например, для систе­мы, граф состояний которой дан на рис. 2, состояние А₃ не­существенно (так как из него можно перейти в состояние А₁или А₂ но обратно вернуться нельзя), состояния А₁ и A₂ — существенны. Два существенных состояния A_i и A_j назы­ваютсясообщающимися, если из A_i можно попасть в A_j и из A_j в A_i. На рис. 2 представлены сообщающиеся состоя­ния A₁ и А₂.

Теорема 1. Если A_i — несущественное состояние, то

p_i(t) = 0. (10)

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

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

Пример. В условиях задачи 2 найти предельные веро­ятности состояний.

Решение. В рассматриваемой цепи состояния A₁ и A₂ являются существенными сообщающимися состояниями, A₃ — несущественно. Следовательно, по теореме 2 предель­ное распределение совпадает со стационарным и имеет вид p = ( 1/6; 5/6; 0). Заметим, что результат p₃(t) = 0 можно было получить непосредственно из теоремы 1, так как состояние A₃ несущественно.

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

Дано:

Решение: Однородная цепь Маркова с конечным числом состояний A₁,A₂,…,A_k характеризуется матрицей интенсивностей переходов

 

,

где - интенсивность перехода цепи Маркова из состояния A_i в состояние A_j;

- вероятность перехода A_i A_j за интервал времени .

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

Составим размеченный граф состояний для заданной матрицы интенсивностей переходов.

Пусть - вектор вероятностей , нахождения системы в состоянии A_j в момент t. Очевидно, что и . Тогда по правилу дифференцирования векторной функции скалярного аргумента получим . Вероятности удовлетворяют системе дифференциальных уравнений Колмогорова (СДУК), которая в матричной форме имеет вид

(6)

 

,

 

Если в начальный момент система находилась в состоянии A_j, то СДУК следует решать при начальных условиях

(7)

 

 

Совокупность СДУК (6) и начальных условий (7) однозначно описывает однородную цепь Маркова непрерывным временем и конечным числом состояний.

Составим СДУК для заданной цепи Маркова. Поскольку k=3, то j=1,2,3. Из соотношения (6) получим

Отсюда будем иметь:

Последнее условие называется нормировочным.

Распределение вероятностей по состояниям называется стационарным, если оно не меняется с течением времени, то есть , где p_j=const, j=1,2,…,k.

Отсюда . Тогда из СДУК (6) получаем систему для нахождения стационарного распределения , где .

Для данной задачи из СДУК будет иметь

Из нормировочного условия получим

 

Ответ: предельное распределение имеет вид .

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

Указание.Проведите классификацию состояний системы и примените следствия из теоремы Маркова.

а) Состояние 6 - существенное. Остальные - несущественные состояния. Поэтому единственное стационарное распределение совпадает с предельным.

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

б) Несущественные состояния 1, 2, 6. Состояния 3, 4, 5 - существенные сообщающиеся поэтому единственное стационарное распределение совпадает с предельным.

 

Приравнивая к каждую из строк-уравнений к 0 и учитывая, что сумма вероятностей = 1 получим:

 

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

 

Процессом гибели и размножения называется марковская цепь, размеченный граф состояний которой изображен на рис. 3. Здесь l₀, l₁, …,l_k-1— интенсивности переходов си­стемы из состояния в состояние слева направо; m₁, m₂,…, m_k—

 

 

Рис. 3

интенсивности переходов спра