вар 4. 1. Марковский процесс с дискретными состояниями и дискретным временем
 Скачать 1.31 Mb.
|
|
1.Марковский процесс с дискретными состояниями и дискретным временем. Марковский процесс с дискретными состояниями и непрерывным временем ещё называют непрерывной цепью Маркова. Пусть имеется ряд дискретных состояний  . Обозначим через  вероятность того, что в момент времени  система  будет находиться в состоянии  , где  .Определим для любого момента времени вероятности состояний:  и рассмотрим элементарный промежуток времени  , примыкающий справа к моменту времени . Назовем плотностью вероятности перехода  – предел отношения вероятности  – перехода системы за время из состояния в состояние  к длине промежутка  Если все плотности вероятностей перехода не зависят от , то непрерывную цепь Маркова называют однородной; если эти плотности представляют функции времени, то процесс называется неоднородным.Пометим каждую стрелку графа состояний соответствующей плотностью вероятностей перехода. Такой граф называют размеченным графом состояний. Покажем, что, зная размеченный граф состояний, можно определить вероятность состояний как решение дифференциальных уравнений Колмогорова.Пример: Система имеет четыре возможных состояния  . Найдем вероятность  .Это событие может произойти двумя способами: В момент времени система была в состоянии  , а за время ничего не изменилось:  В момент времени система была в состоянии  , а за время перешла в состояние :  Применяя правило сложения вероятностей, получим:  или  Таким образом, выведено дифференциальное уравнение, которому должна удовлетворять функция  .Рассуждая аналогично, получим систему дифференциальных уравнений Колмогорова:  Заметим, что всегда справедливо:  .Таким образом, при  в системе устанавливается некоторый стационарный режим: он состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени: каждое из состояний осуществляется с некоторой постоянной вероятностью, которая представляет собой среднее относительное время пребывания системы в данном состоянии. Для вычисления финальных вероятностей достаточно в системе уравнений Колмогорова все левые части положить равными нулю.2.Циклический процесс Марковский случайный процесс, протекающий в системе, называется циклическим, если состояния связаны между собой в кольцо с односторонними переходами.  Алгебраические уравнения для предельных вероятностей состояний имеют следующий вид:  Решая эти уравнения, получим:  После элементарных преобразований  получим то есть финальные вероятности состояний в циклической схеме относятся как средние времена пребывания системы в каждом из состояний. 3.Процесс “Гибели и размножения” Марковская непрерывная цепь называется процессом «гибели и размножения», если её граф состояний имеет следующий вид:  Происхождение термина «схема гибели и размножения» ведёт начало от биологических задач, где подобной схемой описывается процесс изменения численности популяции. Рассмотрим случайный процесс «гибели и размножения». Для него справедлива следующая система алгебраических уравнений:  и нормированное уравнение  .Решая эту систему, получим:  В числителе стоит произведение всех плотностей вероятности перехода (интенсивности) , стоящих у стрелок, направленных слева направо с начала и вплоть до той, которая идет в состояние  ; в знаменателе стоит произведение всех интенсивностей , стоящих у стрелок, идущих справа налево с начала и вплоть до стрелки, исходящей из состояния .Из нормировочного условия получим:  4. СМО типа M/M/m Входной поток требований подчинен закону Пуассона. Время обслуживания подчинено показательному закону.  – интенсивность входного потока требований – интенсивность обслуживания требований (среднее число обслуживаний в единицу времени) – среднее время обслуживания каждого времени  – параметр обслуживания – число требований – число обслуживающих устройствКогда число требований в системе меньше числа обслуживающих устройств (  ), то все требования одновременно обслуживаются, но не все устройства заняты, и общая норма обслуживания равна  .Когда число требований в системе больше числа обслуживающих устройств (  ), то не все требования одновременно обслуживаются, все устройства заняты, и общая норма обслуживания равна  . – вероятность того, что в системе в момент времени  имеется требований, включая те, которые находятся в состоянии обслуживания.Тогда  – вероятность того, что в системе в момент времени  тоже имеется требований. – вероятность того, что за время произошло одно событие, так как  – вероятность того, что за время закончило работу одно из занятых устройств.В силу ординарности входного потока и потока обслуживания получаем:  – вероятность того, что за время прибытий не произошло; – вероятность того, что за время окончаний обслуживания не было.Рассмотрим возможные случаи появления события  .В момент в системе требований, а за время нет новых прибытий и окончаний обслуживания.Тогда при получаем а при получаем В момент времени в системе  требований, а за время нет новых прибытий, и окончилось одно обслуживание.Тогда при получаем а при  получаем В момент времени в системе  требований, а за время произошло одно прибытие, но окончаний обслуживания не было.Тогда при  получаем а при получаем Вероятность равна сумме вероятностей рассмотренных выше случаев.Для случая   Для случая  Эти формулы справедливы для  .Для случая  имеем:В момент времени 0 требований, а за время нет новых прибытий В момент времени 1 требование, за время нет новых прибытий, и завершилось 1 обслуживание   Таким образом, получено, что СМО типа M/M/m в установившемся режиме описывается системой уравнений:  (3)Методом математической индукции можно доказать: для :  ,для  :  , где  Доказательство: Для и  доказано, что  и  Предположим: для :  ;  для :  ;  Тогда для  Для  ,что и требовалось доказать. Алгебраические уравнения (3) позволяют представить систему M/M/m в виде следующего графа:  Тогда  – вероятность того, что в системе нет требований, можно вычислить как следующим образом: где  , но  так как   Вычислим среднее число требований в очереди:  , где Обозначим  через  .Но – производная  .Тогда  и    Вычислим среднее число требований в обслуживающем устройстве:  (В G/G/m  )Таким образом, для системы M/M/m получено:   6. Многоканальная СМО с ограниченным ожиданием M/M/m/k Состояния системы будем нумеровать по числу заявок, связанных с системой. S0 – все каналы свободны S1 – занят один канал, остальные свободны --- Sm+1 – заняты все m каналов, одна заявка в очереди --- Sm+k – заняты все m каналов, k заявок в очереди  Выражения для предельных вероятностей состояний будут выглядеть:  Найдем некоторые характеристики обслуживания: Pотк=pm+kq=1-PоткA=  qКаждый занятый канал обслуживает в среднем заявок в единицу времени; вся СМО за это время обслуживает A заявок. Среднее число занятых каналов: V=A/= qСреднее число заявок в очереди:  |