Каждая СМО состоит из определенного числа обслуживающих единиц (приборов, устройств, пунктов, станций), которые будем называть каналами обслуживания. Каналами могут быть линии связи, рабочие точки, вычислительные машины, продавцы и др. По числу каналов СМО подразделяют на одноканальные и многоканальные.
Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). Обслуживание заявок, вообще говоря, также продолжается какое-то случайное время. Случайный характер потока заявок и времени обслуживания приводит к тому, что СМО оказывается загруженной неравномерно: в какие-то периоды времени скапливается очень большое количество заявок (они либо становятся в очередь, либо покидают СМО необслуженными), в другие же периоды СМО работает с недогрузкой или простаивает.
Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, характер потока заявок и т.п.) с показателями эффективности СМО, описывающими ее способность справляться с потоком заявок.
В качестве показателей эффективности СМО используются: среднее (здесь и в дальнейшем средние величины понимаются как математические ожидания соответствующих случайных величин) число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение и т.п.
СМО делят на два основных типа (класса)
: СМО с отказами и href="cmo_length.php">СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной).
В СМО с ожиданием заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь на обслуживание.
СМО с ожиданием подразделяются на разные виды в зависимости от того, как организована очередь: с ограниченной или неограниченной длиной очереди, с ограниченным временем ожидания и т.п.
Процесс работы СМО представляет собой случайный процесс.
Под случайным (вероятностным или стохастическим) процессом
понимается процесс изменения во времени состояния
какой-либо системы в соответствии с вероятностными закономерностями.
Процесс называется процессом с дискретными состояниями,
если его возможные состояния S 1 , S 2 , S 3 … можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем,
если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.
Процесс работы СМО представляет собой случайный процесс c дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки,
окончания обслуживания и т.п.).
Математический анализ работы СМО существенно упрощается, если процесс этой работы - марковский. Случайный процесс называется марковским
или случайным процессом без последствия,
если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.
Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t 0 счетчик показывает S 0 .
Вероятность того, что в момент t > t 0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S 1 , зависит от S 0 , но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t 0 .
Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S -
группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t 0 . Вероятность того, что в момент t > t 0 материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t 0 ,
а не того, когда и в какой последовательности исчезли фигуры с доски до момента t 0 .
В ряде случаев предысторией рассматриваемых процессов можно просто пренебречь и применять для их изучения марковские модели.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой - так называемым графом состоянии.
Обычно состояния системы изображаются прямоугольниками (кружками), а возможные переходы из состояния в состояние - стрелками (ориентированными дугами), соединяющими состояния.
Задача 1 .
Построить граф состояний следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время.
Решение.
Возможные состояния системы: S 0 - оба узла исправны; S 1 - первый узел ремонтируется,
второй исправен; S 2 - второй узел ремонтируется, первый исправен; S 3 - оба узла ремонтируются. Граф системы приведен на рис.1.
Рис. 1
Стрелка, направленная, например, из S 0 в S 1 означает переход системы в момент отказа первого узла, из S 1 в S 0 - переход в момент окончанияремонта этого узла.
На графе отсутствуют стрелки из S 0 , в S 3 и из S 1 в S 2 . Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например,
вероятностью одновременного выхода из строя двух узлов (переход из S 0 в S 3) или одновременного окончания ремонтов двух узлов (переход из S 3 в S 0) можно пренебречь.
Поток событий
Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, протекающего в СМО, познакомимся с одним из важных понятий теории вероятностей - понятием потока событий.Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов ЭВМ, поток покупателей и т.п.).
Поток характеризуется интенсивностью l - частотой появления событий или средним числом событий, поступающих в СМО в единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: l(t)= l. Например, поток автомобилей на городском проспекте не является стационарным в течение суток, но этот поток можно считать стационарным в течение суток, скажем, в часы пик. Обращаем внимание на то, что в последнем случае фактическое число проходящих автомобилей в единицу времени (например, в каждую минуту) может заметно отличаться друг от друга, но среднее их число будет постоянно и не будет зависеть от времени.
Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 - число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени Dt двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поемов, подходящих к станции, ординарен, а поток вагонов не ординарен.
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.
Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа n независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям l 1 (i=1,2, ..., п) получается поток, близкий к простейшему с интенсивностью l, равной сумме интенсивностей входящих потоков, т.е.
Рассмотрим на оси времени Ot (рис. 2) простейший поток событий как неограниченную последовательность случайных точек.
Рис. 2
Можно показать, что для простейшего потока число т событий (точек), попадающих на произвольный участок времени t, распределено по закону Пуассона
, (1)
для которого математическое ожидание случайной величины равно ее дисперсии: a= s 2 = l t.
В частности, вероятность того, что за время t не произойдет ни одного события (m=0), равна (2)
Найдем распределение интервала времени Т между произвольными двумя соседними событиями простейшего потока.
В соответствии с (15.2) вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна (3)
а вероятность противоположного события, т.е. функция распределения случайной величины Т, есть (4)
Плотность вероятности случайной величины есть производная ее функции распределения (рис. 3), т.е.
(5)
Рис. 3
Распределение, задаваемое плотностью вероятности (5) или функцией распределения (4), называется показательным (или экспоненциальным). Таким образом, интервал времени между двумя соседними произвольными событиями имеет показательное распределение, для которого математическое ожидание равно среднему квадратическому отклонению случайной величины (6)
и обратно по величине интенсивности потока l.
Важнейшее свойство показательного распределения (присущее только показательному распределению) состоит в следующем: если промежуток времени, распределенный по показательному закону, уже длился некоторое время t, то это никак не влияет на закон распределения оставшейся части промежутка (T-t): он будет таким же, как и закон распределения всего промежутка Т.
Другими словами, для интервала времени Т между двумя последовательными соседними событиями потока, имеющего показательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения оставшейся части. Это свойство показательного закона представляет собой, в сущности, другую формулировку для "отсутствия последействия" - основного свойства простейшего потока.
Для простейшего потока с интенсивностью l вероятность попадания на элементарный (малый) отрезок времени Dt хотя бы одного события потока равна согласно (4)
(7)
(Заметим, что эта приближенная формула, получаемая заменой функции e - l Dt лишь двумя первыми членами ее разложения в ряд по степеням Dt, тем точнее, чем меньше Dt).
Эволюция которого после любого заданного значения временно́го параметра t {\displaystyle t} не зависит от эволюции, предшествовавшей t {\displaystyle t} , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»).
Энциклопедичный YouTube
1 / 3
✪ Лекция 15: Марковские случайные процессы
✪ Происхождение марковских цепей
✪ Обобщенная модель марковского процесса
Субтитры
История
Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым , который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова .
Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым .
Марковское свойство
Общий случай
Пусть
(Ω
,
F
,
P)
{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P})}
- вероятностное пространство с фильтрацией
(F
t
,
t
∈
T)
{\displaystyle ({\mathcal {F}}_{t},\ t\in T)}
по некоторому (частично упорядоченному) множеству
T
{\displaystyle T}
; и пусть
(S
,
S)
{\displaystyle (S,{\mathcal {S}})}
- измеримое пространство . Случайный процесс
X
=
(X
t
,
t
∈
T)
{\displaystyle X=(X_{t},\ t\in T)}
, определённый на фильтрованном вероятностном пространстве, считается удовлетворяющим марковскому свойству
, если для каждого
A
∈
S
{\displaystyle A\in {\mathcal {S}}}
и
s
,
t
∈
T:
s
<
t
{\displaystyle s,t\in T:s
Марковский процесс - это случайный процесс, удовлетворяющий марковскому свойству с естественной фильтрацией .
Для марковских цепей с дискретным временем
В случае, если S {\displaystyle S} является дискретным множеством и T = N {\displaystyle T=\mathbb {N} } , определение может быть переформулировано:
P (X n = x n | X n − 1 = x n − 1 , X n − 2 = x n − 2 , … , X 0 = x 0) = P (X n = x n | X n − 1 = x n − 1) {\displaystyle \mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{0}=x_{0})=\mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1})} .Пример марковского процесса
Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета - если выпал герб, то точка X перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания ») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).
Потоком событий называют последовательность однородных событий, появляющихся одно за другим в случайные моменты времени. Примеры: поток вызовов на телефонной станции; поток сбоев ЭВМ; поток заявок на проведение расчетов в вычислительном центре и т.п.
Поток событий наглядно изображается рядом точек с абсциссами Q 1, Q 2 , ..., Q n , ... (рис. 6.15) с интервалами между ними: Т 1 = Q 2 - Q 1, T 2 = Q 3 -Q 2 , ..., Т п = Q n +1 - Q n . При его вероятностном описании поток событий может быть представлен как последовательность случайных величин:
Q 1 ; Q 2 = Q 1 + T 1 ; Q 3 = Q 1 + T 1 + T 2 ; и т.д.
На рисунке в виде ряда точек изображен не сам поток событий (он случаен), а только одна его конкретная реализация.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от выбора начала отсчета или, более конкретно, если вероятность попадания того или другого числа событий на любой интервал времени зависит только от длины этого интервала и не зависит от того, где именно на оси 0-t он расположен.
Рисунок 6.15 – Реализация потока событий
Поток событий называется ординарным, если вероятность попадания на элементарный интервал времени двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Рисунок 6.16 – Поток событий как случайный процесс
Ординарный поток событий можно интерпретировать как случайный процесс Х(t) - число событий, появившихся до момента t(рис. 6.16). Случайный процесс Х(t) скачкообразно возрастает на одну единицу в точках Q ,Q 2 ,...,Q n .
Поток событий называется потоком без последействия, если число событий, попадающих на любой интервал времени , не зависит от того, сколько событий попало на любой другой не пересекающийся с ним интервал. Практически отсутствие последействия в потоке означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга.
Поток событий называется простейшим, если он стационарен, ординарен и не имеет последействия. Интервал времени T между двумя соседними событиями простейшего потока имеет показательное распределение
(при t>0 ); (6.21)
где / М [Т] -величина, обратная среднему значению интервала Т.
Ординарный поток событий без последействия называется пуассоновским. Простейший поток является частным случаем стационарного пуассоновского потока. Интенсивностью потока событий называется среднее число событий, приходящееся на единицу времени. Для стационарного потока ; для нестационарного потока она в общем случае зависит от времени: .
Марковские случайные процессы . Случайный процесс называют марковским , если он обладает следующим свойством: для любого момента времени t 0 вероятность любого состояния системы в будущем (при t >t 0 ) зависит только от ее состояния в настоящем (при t =t 0 ) и не зависит от того, каким образом система пришла в это состояние.
В данной главе будем рассматривать только марковские процессы c дискретными состояниями S 1, S 2 , ...,S n . Такие процессы удобно иллюстрировать с помощью графа состояний (рис. 5.4), где прямоугольниками (или кружками) обозначены состояния S 1 , S 2 , … системы S, а стрелками - возможные переходы из состояния в состояние (на графе отмечаются только непосредственные переходы, а не переходы через другие состояния).
Рисунок 5.4 – Граф состояний случайного процесса
Иногда на графе состояний отмечают не только возможные переходы из состояния в состояние, но и возможные задержки в прежнем состоянии; это изображается стрелкой («петлей»), направленной из данного состояния в него же, но можно обходиться и без этого. Число состояний системы может быть как конечным, так и бесконечным (но счетным).
Марковский случайный процесс с дискретными состояниями и дискретным временем обычно называют марковской цепью. Для такого процесса моменты t 1 , t 2 ..., когда система S может менять свое состояние, удобно рассматривать как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, рассматривать не время t, а номер шага: 1, 2, . . ., k;…. Случайный процесс в этом случае характеризуется последовательностью состояний
если S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы непосредственно после первого шага; ...; S(k) - состояние системы непосредственно после k-го шага....
Событие S i , (i= 1,2,...) является случайным событием, поэтому последовательность состояний (5.6) можно рассматривать как последовательность случайных событий. Начальное состояние S(0) может быть как заданным заранее, так и случайным. О событиях последовательности (5.6) говорят, что они образуют марковскую цепь.
Рассмотрим процесс с n возможными состояниями S 1, S 2 , ..., S n . Если обозначить через Х(t) номер состояния, в котором находится система S в момент t, то процесс описывается целочисленной случайной функцией Х(t)>0 , возможные значения которой равны 1, 2,...,n . Эта функция совершает скачки от одного целочисленного значения к другому в заданные моменты t 1 , t 2 , ... (рис. 5.5) и является непрерывной слева, что отмечено точками на рис. 5.5.
Рисунок 5.5 – График случайного процесса
Рассмотрим одномерный закон распределения случайной функции Х(t). Обозначим через вероятность того, что после k -го шага [и до (k+1 )-го] система S будет в состоянии S i (i=1,2,...,n) . Вероятности р i (k) называются вероятностями состояний цепи Маркова. Очевидно, для любого k
. (5.7)
Распределение вероятностей состояний в начале процесса
p 1 (0) ,p 2 (0),…,p i (0),…,p n (0) (5.8)
называется начальным распределением вероятностей марковской цепи. В частности, если начальное состояние S(0) системы S в точности известно, например S(0)=S i , то начальная вероятность P i (0) = 1, а все остальные равны нулю.
Вероятностью перехода на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шагов) она находилась в состоянии S i . Вероятности перехода иногда называются также «переходными вероятностями».
Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага, а зависят только от того, из какого состояния и в какое осуществляется переход:
Переходные вероятности однородной марковской цепи Р ij образуют квадратную таблицу (матрицу) размером n * n :
(5.10)
. (5.11)
Матрицу, обладающую таким свойством, называют стохастической. Вероятность Р ij есть не что иное, как вероятность того, что система, пришедшая к данному шагу в состояние S j , в нем же и задержится на очередном шаге.
Если для однородной цепи Маркова заданы начальное распределение вероятностей (5.8) и матрица переходных вероятностей (5.10), то вероятности состояний системы 
могут быть определены по рекуррентной формуле
(5.12)
Для неоднородной цепи Маркова вероятности перехода в матрице (5.10) и формуле (5.12) зависят от номера шага k .
Для однородной цепи Маркова, если все состояния являются существенными, а число состояний конечно, существует предел 
определяемый из системы уравнений и Сумма переходных вероятностей в любой строке матрицы равна единице. 
При фактических вычислениях по формуле (5.12) надо в ней учитывать не все состояния S j , а только те, для которых переходные вероятности отличны от нуля, т.е. те, из которых на графе состояний ведут стрелки в состояние S i .
Марковский случайный процесс с дискретными состояниями и непрерывным временем иногда называют «непрерывной цепью Маркова» . Для такого процесса вероятность перехода из состояния S i в S j для любого момента времени равна нулю. Вместо вероятности перехода p ij рассматривают плотность вероятности перехода которая определяется как предел отношения вероятности перехода из состояния S i в состояние S j за малый промежуток времени , примыкающий к моменту t, к длине этого промежутка, когда она стремится к нулю. Плотность вероятности перехода может быть как постоянной (), так и зависящей от времени . В первом случае марковский случайный процесс с дискретными состояниями и непрерывным временем называется однородным. Типичный пример такого процесса - случайный процесс Х(t), представляющий собой число появившихся до момента t событий в простейшем потоке (рис. 5.2).
При рассмотрении случайных процессов с дискретными состояниями и непрерывным временем удобно представлять переходы системы S из состояния в состояние как происходящие под влиянием некоторых потоков событий. При этом плотности вероятностей перехода получают смысл интенсивностей соответствующих потоков событий (как только происходит первое событие в потоке с интенсивностью , система из состояния S i скачком переходит в Sj) . Если все эти потоки пуассоновские, то процесс, протекающий в системе S, будет марковским.
Рассматривая марковские случайные процессы с дискретными состояниями и непрерывным временем, удобно пользоваться графом состояний, на котором против каждой стрелки, ведущей из состояния S i , в S j проставлена интенсивность потока событий, переводящего систему по данной стрелке (рис.5.6). Такой граф состояний называют размеченным.
Вероятность того, что система S, находящаяся в состоянии S i , за элементарный промежуток времени () перейдет в состояние S j (элемент вероятности перехода из S i в S j ), есть вероятность того, что за это время dt появится хотя бы одно событие потока, переводящего систему S из S i в S j . С точностью до бесконечно малых высших порядков эта вероятность равна .
Потоком вероятности перехода из состояния Si в Sj называется величина (здесь интенсивность может быть как зависящей, так и независящей от времени).
Рассмотрим случай, когда система S имеет конечное число состояний S 1, S 2 ,..., S п. Для описания случайного процесса, протекающего в этой системе, применяются вероятности состояний
(5.13)
где р i (t) - вероятность того, что система S в момент t находится в состоянии S i:
. (5.14)
Очевидно, для любого t
Для нахождения вероятностей (5.13) нужно решить систему дифференциальных уравнений (уравнений Колмогорова), имеющих вид
(i=1,2,…,n),
или, опуская аргумент t у переменных р i ,
(i=1,2,…,n
).
(5.16)
Напомним, что интенсивности потоков ij могут зависеть от времени .
Уравнения (5.16) удобно составлять, пользуясь размеченным графом состояний системы и следующим мнемоническим правилом: производная вероятности каждого состояния равна сумме всех потоков вероятности, переводящих из других состояний в данное, минус сумма всех потоков вероятности, переводящих из данного состояния в другие. Например, для системы S, размеченный граф состояний которой дан на рис. 10.6, система уравнений Колмогорова имеет вид
(5.17)
Так как для любого t выполняется условие (5.15), можно любую из вероятностей (5.13) выразить через остальные и таким образом уменьшить число уравнений на одно.
Чтобы решить систему дифференциальных уравнений (5.16) для вероятностей состояний р 1 (t) p 2 (t ), …, p n (t ), нужно задать начальное распределение вероятностей
p 1 (0),p 2 (0), …,p i (0), …,p n (0 ), (5.18)
сумма которых равна единице.
Если, в частности, в начальный момент t = 0 состояние системы S в точности известно, например, S(0) =S i , и р i (0) = 1, то остальные вероятноcти выражения (5.18) равны нулю.
Во многих случаях, когда процесс, протекающий в системе, длится достаточно долго, возникает вопрос о предельном поведении вероятностей р i (t) при . Если все потоки событий, переводящие систему из состояния в состояние, являются простейшими (т.е. стационарными пуассоновскими с постоянными интенсивностями ), в некоторых случаях существуют финальные (или предельные) вероятности состояний
, (5.19)
независящие от того, в каком состоянии система S находилась в начальный момент. Это означает, что с течением времени в системе S устанавливается предельный стационарный режим, в ходе которого она переходит из состояния в состояние, но вероятности состояний уже не меняются. В этом предельном режиме каждая финальная вероятность может быть истолкована как среднее относительное время пребывания системы в данном состоянии.
Систему, в которой существуют финальные вероятности, называют эргодической. Если система S имеет конечное число состояний S 1 , S 2 , . . . , S n , то для существования финальных вероятностей достаточно, чтобы из любого состояния системы можно было (за какое-то число шагов) перейти в любое другое. Если число состояний S 1 , S 2 , . . . , S n , бесконечно, то это условие перестает быть достаточным, и существование финальных вероятностей зависит не только от графа состояний, но и от интенсивностей .
Финальные вероятности состояний (если они существуют) могут быть получены решением системы линейных алгебраических уравнений,
они получаются из дифференциальных уравнений Колмогорова, если положить в них левые части (производные) равными нулю. Однако удобнее составлять эти уравнения непосредственно по графу состояний, пользуясь мнемоническим правилом: для каждого состояния суммарный выходящий поток вероятности равен суммарному входящему.
Например, для системы S, размеченный граф состояний которой дан на р 
ис. 5.7, уравнения для финальных вероятностей состояний имеют вид
(5.20)
Таким образом, получается (для системы S с п состояниями) система n однородных линейных алгебраических уравнений с n неизвестными р 1, р 2 , ..., р п. Из этой системы можно найти неизвестные р 1 , р 2 , . . . , р п с точностью до произвольного множителя. Чтобы найти точные значения р 1 ,..., р п, к уравнениям добавляют нормировочное условие p 1 + p 2 + … + p п =1, пользуясь которым можно выразить любую из вероятностей p i через другие (и соответственно отбросить одно из уравнений).
Вопросы для повторения
1 Что называют случайной функцией, случайным процессом, сечением случайного процесса, его реализацией?
2 Как различаются случайные процессы по своей структуре и характеру протекания во времени?
3 Какие законы распределения случайной функции применяют для описания случайной функции?
4 Что представляет собой функция математического ожидания случайной функции, в чем ее геометрический смысл?
5 Что представляет собой функция дисперсии случайной функции, в чем ее геометрический смысл?
6 Что представляет собой корреляционная функция случайного процесса, и что она характеризует?
7 Каковы свойства корреляционной функции случайного процесса?
8 Для чего введено понятие нормированной корреляционной функции?
9 Объясните как по опытным данным получить оценки функций характеристик случайного процесса?
10 В чем отличие взаимной корреляционной функции от автокорреляционной функции?
11 Какой случайный процесс относят к стационарным процессам в узком смысле и в широком?
12 В чем заключается свойство эргодичности стационарного случайного процесса?
13 Что понимают под спектральным разложением стационарного случайного процесса и в чем его необходимость?
14 Какова связь между корреляционной функцией и спектральной плотностью стационарной случайной функции?
15 Что называют простейшим потоком событий?
16 Какой случайный процесс называют марковской цепью? В чем заключается методика расчета ее состояний?
17 Что представляет собой марковский случайный процесс с дискретными состояниями и непрерывным временем?
M(U)=10, D(U)=0.2 .
6.5 Найти нормированную взаимную корреляционную функцию случайных функций X(t)=t*U и Y(t)=(t+1)U , где U – случайная величина, причем дисперсия D(U)=10 .
Рассмотрим возможные состояния марковских
процессов .
0 Достижимые состояния : состояние / приводит к состоянию j (обозначают /->/), если существует путь i 0 =i, i=j такой, что все переходные вероятности я,- д j > 0, к = 0,..., п-1 .
Рис. 12.13.
На рис. 12.13 показан путь из одного состояния в другое. Гово- рят, что состояние j достижимо из состояния /.
О Сообщающиеся состояния : состояния /" и j сообщающиеся (обозначают //), если i~>j и у-»/- Сообщающиеся состояния могут быть сгруппированы в класс эквивалентности. Внутри класса все состояния сообщающиеся. Два состояния из различных классов не сообщаются друг с другом. Такие классы называются неприводимыми. Марковская цепь с состояниями, образующими неприводимый класс, называется неприводимой.
Рис. 12.14.
Все состояния эргодической цепи Маркова сообщающиеся и образуют эргодическое множество состояний. Марковская цепь называется эргодической , если все состояния эргодические (рис. 12.14).
О Невозвратные состояния : состояние к называется невозвратным, если существует такое состояние j (к ф j) и такое число шагов п, что д.,(«)> 0,71., (т) = Одля всех т> п. Бывают случаи, когда цепь
состоит из нескольких эргодических множеств, не сообщающихся друг с другом (многокомпонентный граф). Попав в одно эрго- дическое множество, процесс никогда не сможет его покинуть. Это множество по отношению к первоначальному является невозвратным, а входящие в него состояния называются невозвратными.
О Поглощающее состояние : состояние / называется поглощающим тогда и только тогда, когда я и (п) = 1 для любого п. Множество состояний называется замкнутым, если ни одно из них не приводит к состоянию, не входящему в это множество. Если эргодическое множество состоит из одного состояния, то это состояние поглощающее, так что, попав в него, уже нельзя из него выйти. Если среди всех состояний цепи Маркова имеется хотя бы одно поглощающее, то такая цепь называется поглощающей.
Каждое состояние может быть проходящим или повторяющимся рекуррентно.
О Проходящее состояние : состояние /" будет проходящим, если существует ненулевая вероятность того, что система никогда не возвратится в него. Подмножество состояний называется транзитивным (проходящим), если можно войти в это подмножество и выйти из него. Транзитивные состояния могут быть посещены лишь конечное число раз.
О Рекуррентное состояние : состояние будет рекуррентным, если вероятность возвращения равна 1. Рекуррентные состояния могут быть классифицированы в зависимости от времени первого возвращения в это состояние: если это время меньше бесконечности, то состояния называются положительно рекуррентные ; если время равно бесконечности, то нуль рекуррентные. Рекуррентные состояния могут быть периодическими и непериодическими. Непериодические положительно рекуррентные состояния называются эргоди- ческими.
В зависимости от типа состояний цепи Маркова матрицу переходных вероятностей можно представить в том или ином виде путем перестановки строк и столбцов. Если матрицу переходных вероятностей можно представить в виде блоков
то процесс, выходящий из некоторого состояния, принадлежащего множеству состояний S, никогда не сможет оказаться за любое число шагов в состоянии, принадлежащем множеству Q, и наоборот . Матрица П при этом называется разложимой, а два рассмотренных множества состояний замкнутыми. Данное утверждение очевидно, так как
то для всех четных степеней матрица будет блочно-диагональной, а для нечетных - иметь первоначальный вид. Например:
Процесс будет по очереди переходить от состояний, принадлежащих Т, к состояниям, принадлежащим R, и обратно. Такой процесс будет периодическим.
Если матрица переходных вероятностей имеет вид
то вероятность того, что процесс будет находиться в одном из состояний, принадлежащих Q, не возрастет с увеличением числа шагов. Переход из какого-либо состояния, принадлежащего Q, в одно из состояний, принадлежащих S, возможен, если R ф 0, но обратный переход произойти не может. Следовательно, состояния, соответствующие Q, невозвратные, a S - поглощающие.
Матрицу переходных вероятностей поглощающей цепи записывают в следующей канонической форме :
Подматрица 0 состоит из одних нулей, подматрица I - единичная матрица поглощающих состояний, подматрица Q описывает поведение процесса до выхода из множества невозвратных состояний, подматрица R отвечает переходам из невозвратных состояний в поглощающие.
Под случайным процессом понимают изменение во времени состояний некоторой физической системы заранее неизвестным случайным образом. При этом под физической системой будем понимать любое техническое устройство, группу устройств, предприятие, отрасль, биологическую систему и т.д.
Случайный процесс протекающий в системе называется Марковским – если для любого момента времени ,вероятностные характеристики процесса в будущем (t > ) зависят только от его состояния в данный момент времени (в настоящем ) и не зависят от того, когда и как система пришла в это состояние в прошлом .(Например, счетчик Гейгера, регистрирующий число космических частиц).
Марковские процессы принято делить на 3 вида:
1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).
2. Дискретный марковский процесс – множество состояний дискретно (можно перечислить), а время непрерывно (переход из одного состояния в другое – в любой момент времени).
3. Непрерывный марковский процесс – множество состояний и время -непрерывные.
На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числа учитываемых переменных и невозможности получить решение задачи.
В исследование операций большое значение занимают так называемые Марковские случайные процессы с дискретными состояниями и непрерывным временем .
Процесс называется процессом с дискретными состояниями , если все его возможные состояния , ,... можно заранее перечислить (перенумеровать). Переход системы из состояния в состояние переходит практически мгновенно –скачком.
Процесс называется процессом с непрерывным временем , если моменты перехода из состояния в состояние могут принимать любые случайные значения на временной оси.
Например : Техническое устройство S состоит из двух узлов , каждый из которых в случайный момент времени может выйти из строя (отказать ). После этого мгновенно начинается ремонт узла (восстановление ),который продолжается случайное время.
Возможны следующие состояния системы:
Оба узла исправны;
Первый узел ремонтируется,второй исправен.
– второй узел ремонтируется,первый исправен
Оба узла ремонтируются.
Переход системы из состояния в состояние происходит в случайные моменты времени практически мгновенно. Состояния системы и связь между ними удобно отобразить с помощью графа состояний .
Состояния
Переходы
Переходы и отсутствуют т.к. отказы и восстановления элементов происходят независимо и случайно и вероятность одновременного выхода из строя (восстановления) двух элементов бесконечно мала и ею можно пренебречь.
Если все потоки событий, переводящие систему S из состояния в состояние –простейшие , то процесс, протекающий в такой системе будетМарковским . Это обуславливается тем, что простейший поток не обладает последействием, т.е. в нем «будущее» не зависит от «прошлого» и, кроме того, он обладает свойством ординарности – вероятность одновременного появления двух и более событий бесконечно мала, т.е невозможен переход из состояния в состояние, минуя несколько промежуточных состояний.
Для наглядности на графе состояний удобно у каждой стрелки перехода проставить интенсивность того потока событий, который переводит систему из состояния в состояние по данной стрелке ( -интенсивность потока событий, переводящего систему из состояния в . Такой граф называется размеченным.
Используя размеченный граф состояний системы можно построить математическую модель данного процесса.
Рассмотрим переходы системы из некоторого состояния в предыдущее или последующее . Фрагмент графа состояний в этом случае будет выглядеть следующим образом:
Пусть система в момент времени t находится в состоянии .
Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии . Для любого момента времени t справедливо =1.
Определим вероятность того, что и в момент времени t+∆t система будет находиться в состоянии . Это может быть в следующих случаях:
1) и за время ∆ t из него не вышла. Это означает, что за время ∆t не возникло события, переводящего систему в состояние (поток с интенсивностью ) или события, переводящего её в состояние (поток с интенсивностью ). Определим вероятность этого при малых ∆t.
При экспоненциальном законе распределения времени между двумя соседними требованиями, соответствующему простейшему потоку событий вероятность того, что на интервале времени ∆t не возникнет ни одного требования в потоке с интенсивностью λ 1 будет равна
Разлагая функцию f(t) в ряд Тейлора (t>0) получим (для t=∆t)
f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=
= +(-l) *∆t+ (∆ + *(∆ +…»1-l*∆t при ∆t®0
Аналогично для потока с интенсивностью λ 2 получим
.
Вероятность, что на интервале времени ∆t (при ∆t®0) не возникнет ни одного требования будет равна
(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =
1 - - *∆t + 
1 - (
+
)*∆t + б.м.
Таким образом, вероятность того, что система за время ∆t не вышла из состояния , при малых ∆t будет равна
P( / )=1 – ( + )* ∆t
2) Система находилась в состоянии S i -1 и за время перешла в состояние S i . То есть в потоке с интенсивностью возникло хотя бы одно событие. Вероятность этого равна для простейшего потока с интенсивностью λ будет
Для нашего случая вероятность такого перехода будет равна
3)Система находилась в состоянии и за время ∆tперешла в состояние . Вероятность этого будет
Тогда вероятность, что система в момент времени (t+∆t) будет в состоянии S i равна
Вычтем из обеих частей P i (t), разделим на ∆tи, перейдя к пределу, при ∆t→0, получим
Подставив соответствующие значения интенсивностей переходов из состояний в состояния, получим систему дифференциальных уравнений, описывающих изменение вероятностей состояний системы как функций времени.
Данные уравнения называются уравнениями Колмогорова-Чепмена для дискретного марковского процесса.
Задав начальные условия (например, P 0 (t=0)=1,P i (t=0)=0 i≠0) и решив их, получим выражения для вероятностей состояния системы как функций времени. Аналитические решения достаточно просто получить, если число уравнений ≤ 2,3. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).
В теории случайных процессов доказано , что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то существует предел , к которому стремятся вероятности при t→ . Такие вероятности называются финальными вероятностями состояний, а установившийся режим - стационарным режимом функционирования системы.
Так как в стационарном режиме все 
, следовательно, все =0. Приравняв в системе уравнений левые части 0 и, дополнив их уравнением =1, получим систему линейных алгебраических уравнений, решив которую найдём значения финальных вероятностей.
Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие
Отказы
1эл: 
2эл: 
Ремонт
1эл: 
2эл: 
P 0 +P 1 +P 2 +P 3 =1
0=-(1+2)P 0 +2P 1 +3 P 2
0=-(2+2)P 1 +1P 0 +3P 3
0=-(1+3)P 2 +2P 0 +2P 3
0=-(2+3)P 3 +2P 1 +1P 2
Решив данную систему, получим
P 0 =6/15=0.4; P 1 =3/15=0.2; P 2 =4/15=0.27; P 3 =2/15≈0.13.
Т.е. в стационарном состоянии система в среднем
40% находится в состоянии S 0 (оба узла исправны),
20%- в состоянии S 1 (1-й эл-т ремонтируется, 2-й исправен),
27%- в состоянии S 2 (2-й эл-тремонтируется, 1исправен),
13%- в состоянии S 3 – оба эл-та в ремонте.
Знание финальных вероятностей позволяет оценить среднюю эффективность работы системы и загрузку службы ремонта.
Пусть система в состоянии S 0 приносит доход 8 усл.ед. в единицу времени; в состоянии S 1 -доход 3 усл.ед.; в состоянии S 2 - доход 5;в состоянии S 3 -доход=0
Стоимость ремонта в единицу времени для эл-та 1- 1(S 1, S 3) усл.ед., эл-та 2- (S 2, S 3) 2 усл.ед. Тогда в стационарном режиме:
Доход системы в единицу времени будет:
W дох =8P 0 +3P 1 +5P 2 +0P 3 =8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.
Стоимость ремонта в ед. времени:
W рем =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.
Прибыль в единицу времени
W= W дох -W рем =5.15-1.39=3.76 усл.ед
Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P i . и показателей эффективности системы.