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

Как было определено ранее, для случайных процессов с дискретным временем изменения состояний возможны только в определенные моменты времени, и эти моменты обозначим через t₀, t₁, t₂, …. В случае дискретной цепи Маркова для описания переходов между состояниями используются вероятностипереходов, определяемые как

(4)

p_ij (t_k) = Pr{ g (t_k+1)= E_j|g (t_k)= E_i }, i,j =0, n.

Вероятность перехода (за один шаг) p_ij (t_k) задет вероятность того, что случайный процесс на следующем (k +1)-ом шаге перехода (в момент времени t_k+1) окажется в состоянии E_j при условии, что на текущем k -ом шаге (в момент времени t_k) он находится в состоянии E_i.

Если вероятности переходов p_ij (t_k) не зависят от момента времени t_k, т.е. p_ij (t_k)= p_ij, то цепь Маркова называется однородной, в противном случае - неоднородной. Далее будем рассматривать только однородные цепи Маркова.

Вероятности переходов p_ij, i,j =0, n, обычно задаются в виде квадратной матрицы T размерности (n +1)´(n +1):

(5)

элементы которой удовлетворяются условиям:

, i =0, n;

(6)

, i,j =0, n.

Условие (5) означает, что в любой момент времени t₀, t₁, t₂, … процесс обязательно (с вероятностью 1) перейдет из состояния E_i в какое-либо другое состояние E₀, E₁,×××, E_n, причем не исключается возможность перехода в то же самое состояние.

Матрица, удовлетворяющая условиям (5) и (6), называется стохастической. Поскольку элементами стохастической матрицы Т являются вероятности переходов p_ij, то эта матрица называется матрицей вероятностей переходов.

Наряду с вероятностями переходов p_ij за один шаг, определим вероятности переходов за m шагов в виде

, m = 1, 2, …

Здесь задет вероятность того, что через m переходов случайный процесс окажется в состоянии E_j при условии, что на текущем шаге он находится в состоянии E_i. В силу однородности марковской цепи вероятности, i,j =0, n, не зависят от текущего времени t_k.

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

(7)

, m = 2, 3, …

Это равенство означает, что для попадания из состояния E_i в состояние E_j за m шагов необходимо сначала попасть из состояния E_i в некоторое состояние E_k за m -1 шагов, а затем за один шаг перейти из E_k в E_j. Вероятность этих двух независимых событий (они независимы в силу марковского свойства) равна произведению вероятностей каждого из них, и, если просуммировать эти произведения по всем возможным промежуточным состояниям E_k, то получится вероятность.

Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния, т.е. для каждой пары состояний E_i и E_j существует целое число m₀ такое, что. Состояние E_i называется поглощающим, если процесс достигнув это состояние, не покидает его. Очевидно, для поглощающего состояния p_ii =1. Состояние E_i называется невозвратным, если случайный процесс после какого-то числа переходов непременно покидает его.

Вернемся к вопросу определения вероятностей состояний P_i (t_k), i =0, n, предполагая, что начальные вероятности P_i (t₀), i =0, n, при t₀ =0 известны.

Используя доводы, аналогичные тем, что были приведены для обоснования равенства (7), легко определить, что искомые вероятности после первого шага, т.е. на момент времени t₁

, i =0, n.

Вероятности состояний после второго шага на момент времени t₂ определяются аналогично:

, i =0, n.

В общем случае после k -го шага на момент времени t_k, k =1, 2,..., вероятности состояний будут равны

(8)

, i =0, n.

(9)

В векторной форме равенства (8) имеют вид:

P (t_k)= P (t_{k -1}) T.

Если случайный процесс обладает эргодическим свойством, т.е. существуют пределы, i =0, n, то соответствующие предельные значения вероятностей состояний P_i, i =0, n, для стационарного режима определяются из решения системы уравнений:

, i =0, n

(10)

или в векторном виде

P = PT

.

 

(11)

с нормировочным условием

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

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

Пример. Рассмотрим систему, которая состоит из двух устройств y₁ и y₂, каждое из которых может находиться в одном из двух состояний: не работает (обозначим это состояние через 0) и работает (состояние 1). В определенные моменты времени может включиться или выключиться только одно устройство. Пусть процесс функционирования такой системы описывается процессом с дискретным временем.

29) Одноканальная СМО с отказами

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

При этом система массового обслуживания состоит только из одного канала (n = 1) и на нее поступает пуассоновский поток заявок с интенсивностью , зависящей, в общем случае, от времени:

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

(5.35)

Из этого следует, что «поток обслуживания» — простейший, с интенсивностью Чтобы представить себе этот поток, вообразим один непрерывно занятый канал, который будет выдавать обслуженные заявки потоком с интенсивностью

Требуется найти:

1)абсолютную пропускную способность СМО (А);

2)относительную пропускную способность СМО (q).

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

ГСП системы показан на рис. 5.6, а.

Рис. 5.6. ГСП для одноканальной СМО с отказами (а); график решения уравнения (5.38) (б)

Из состояния в систему, очевидно, переводит поток заявок с интенсивностью ; из в — «поток обслуживания» с интенсивностью .

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

= 1. (5.36)

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

(5.37)

Из двух уравнений (5.37) одно является лишним, так как и связаны соотношением (5.36). Учитывая это, отбросим второе уравнение, а в первое подставим вместо выражение :

или

(5.38)

Поскольку в начальный момент канал свободен, уравнение следует решать при начальных условиях: = 1, =0.

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

интенсивность этого потока со временем меняется.

Для первого случая решение есть:

Зависимость величины от времени имеет вид, изображенный на рис. 5.6, б. В начальный момент (при t = 0) канал заведомо свободен ( (0) = 1). С увеличением t вероятность уменьшается и в пределе (при ) равна . Величина, дополняющая до единицы, изменяется так, как показано на том же рисунке.

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

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

Зная относительную пропускную способность q, легко найти абсолютную А. Они связаны очевидным соотношением:

В пределе, при , абсолютная пропускная способность тоже установится и будет равна

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

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

Многоканальная СМО с отказами

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

— все каналы свободны;

—занят ровно один канал, остальные свободны;

—заняты ровно к каналов, остальные свободны;

—заняты все п каналов.

ГСП СМО представлен на рис. 5.7. Около стрелок поставлены интенсивности соответствующих потоков событий. По стрелкам слева направо систему переводит один и тот же поток — поток заявок с интенсивностью . Если система находится в состоянии (занято к каналов) и пришла новая заявка, то система переходит в состояние

Рис. 5.7. ГСП для многоканальной СМО с отказами

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

нято k каналов — в к раз интенсивнее . Соответствующие интенсивности указаны у стрелок, ведущих справа налево.

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

Пользуясь общими правилами, можно составить уравнения Колмогорова для вероятностей состояний:

(5.39)

Уравнения (5.39) называют уравнениями Эрланга. Поскольку при t = 0 система свободна, начальными условиями для их решения являются:

Интегрирование системы уравнений (5.39) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно и такое решение дает все вероятности состояний как функции времени.

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

(5.40)

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

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

С учетом этого обозначения, соотношения (5.40) принимают вид:

(5.41)

Соотношения (5.41) называются формулами Эрланга. Они выражают предельные вероятности всех состояний системы в зависимости от параметров и n.

Имея вероятности состояний можно найти характеристики эффективности СМО: относительную пропускную способность q, абсолютную пропускную способность А и вероятность отказа .

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

(5.42)

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

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

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

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

или, переходя к обозначению ,

(5.43)

30) Как было упомянуто выше СМО с ожиданием подразумевает наличие буфера с очередью из заявок, заставших все каналы занятыми и ждущих освобождения одного из каналов. Если время ожидания заявки в очереди ничем не ограничено, то система называется «чистой системой с ожиданием». Если оно ограничено какими-то условиями, то система называется «системой смешанного типа». Это промежуточный случай между чистой системой с отказами и чистой системой с ожиданием.

Для практики наибольший интерес представляют именно системы смешанного типа. Ограничения, наложенные на ожидание, могут быть различного типа. Часто бывает, что ограничение накладывается на время ожидания заявки в очереди; считается, что оно ограничено сверху каким-то сроком , который может быть как строго определенным, так и случайным. При этом ограничивается только срок ожидания в очереди, а начатое обслуживание доводится до конца, независимо от того, сколько времени продолжалось ожидание (например, в системах с коммутацией каналов после установления соединения между абонентами процесс разговора уже не прерывается). В других задачах естественнее наложить ограничение не на время ожидания в очереди, а на общее время пребывания заявки в системе (например, при передаче SMS-сообщений, если после определенного количества попыток сообщение не доходит до адресата оно аннулируется). Наконец, можно рассмотреть и такую смешанную систему (она ближе всего к типу торговых, предприятий, торгующих предметами не первой необходимости), когда заявка становится в очередь только в том случае, если длина очереди не слишком велика. Здесь ограничение накладывается на число заявок в очереди (или на размер буфера , рис. 5.13).

 

Рис. 5.13. Логическая схема односерверной СМО

 

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

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

Рассмотрим смешанную СМО с каналами при следующих условиях [6]. На вход системы поступает простейший поток заявок с плотностью . Время обслуживания одной заявки - показательное, с параметром . Заявка, заставшая все каналы занятыми, становится в очередь и ожидает обслуживания; время ожидания ограничено некоторым сроком ; если до истечения этого срока заявка не будет принята к обслуживанию, то она покидает очередь и остается необслуженной. Срок ожидания будем считать случайным и распределенным по показательному закону

, ,

где параметр - величина, обратная среднему сроку ожидания: .

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

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

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

Возможные состояния системы будут (рис. 5.14):

- ни один канал не занят, очереди нет;

- занят ровно один канал, очереди нет;

……………………………………………….

- занято ровно каналов, очереди нет;

……………………………………………….

- заняты все каналов, очереди нет;

- заняты все каналов, одна заявка стоит в очереди;

……………………………………………….

- заняты все каналов, заявок стоят в очереди.

 

Рис. 5.14. Диаграмма возможных переходов для СМО с очередью

 

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

Очевидно, первые ДУ ничем не будут отличаться от соответствующих уравнений Эрланга (5.28):

(5.37)

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

Составим ДУ для . Зафиксируем момент и найдем - вероятность того, что система в момент будет в состоянии . Эта вероятность вычисляется как вероятность суммы трех событий:

- в момент система уже была в состоянии , а за время не вышла из него (не пришло ни одной заявки и ни один из каналов не освободился);

- в момент система была в состоянии , а за время перешла в состояние (пришла одна заявка);

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

В итоге имеем:

,

откуда ДУ для состояния имеет вид

. (5.38)

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

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

- в момент система была в состоянии , а за время перешла в состояние (пришла одна заявка);

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

Следовательно:

откуда ДУ для состояния имеет вид

(5.39)

Таким образом, мы получили для вероятностей состояний систему бесконечного числа ДУ:

(5.40)

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

Выведем, формулы, аналогичные формулам Эрланга, для вероятностей состояний системы в установившемся режиме обслуживания (при ). Из уравнений (5.40), полагая все постоянными, а все производные - равными нулю, получим систему алгебраических уравнений:

(5.41)

К ним необходимо добавить условие

. (5.42)

Найдем решение системы (5.41), для чего применим тот же прием, которым мы пользовались в случае системы с отказами; разрешим первое уравнение относительно , подставим во второе, и т. д. Для любого , как и в случае системы с отказами, получим:

(5.43)

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

,

и вообще при любом

. (5.44)

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

,

откуда имеем

. (5.45)

Преобразуем выражения (5.43), (5.44) и (5.45), вводя в них вместо плотностей и «приведенные» плотности:

(5.46)

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

В новых обозначениях формулы (5.43), (5.44) и (5.45) примут вид:

, (5.47)

, (5.48)

. (5.49)

Подставляя (5.49) в (5.47) и (5.48), получим окончательные выражения для вероятностей состояний системы:

, (5.50)

. (5.51)

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

. (5.52)

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

.

Получим:

. (5.53)

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

.

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