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

Марковские случайные процессы.

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

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

- i-тое состояние системы зависит от k параметров.

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

Следует учесть, что переход из состояния S_i в состояние S_j носит стохастический характер. Функционирование системы начинаем рассматривать с начального состояния S₀, которому соответствует момент времени t₀. То есть, то, что было с системой до момента времени t₀, относится к «прошлому оной», к предыстории.

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

Полагаем, что состояние системы описывается функцией S(t), аргумент этой функции, - время t непрерывно, известны моменты времени перехода системы из одного состояния в другое t: t₁<t₂< … <t_n. Причем переход из одного состояния в другое происходит «скачком», практически мгновенно.

Пришли к тому, что процессу функционирования системы ставится в соответствие цепь дискретных состояний: S₁®S₂® … ®S_n-1®S_n (последовательный переход из одного состояния в другое, без «перескакивания» через какое-либо состояние). То есть, рассматриваемая система описывается марковским случайным процессом с дискретными состояниями и непрерывным временем.

Из теории вероятности мы знаем, что функция плотности вероятности для n-го состояния ищется как совместная функция плотности для всей «предыстории» процесса прихода системы в это состояние: .

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

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

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

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

Определение. Граф – это совокупность множества вершин V и множество упорядоченных пар вершин A={(a₁ a_i) (a₂ a_j) … }, элементы которого называются ребрами G(V,A).

Состояниям системы ставятся в соответствие вершины графа, а переходам из одного состояния в другое – верви с указанием «направления протекания» процесса.

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

Пример №1. ТЭА техническая эксплуатация автомобиля.

Упрощенная модель ТЭА подразумевает наличие хотя бы четырех следующих состояний: S₁ – диагностика состояния автомобиля, S₂ – работа на линии (автомобиль исправен), S₃ – техническое обслуживание, S₄ – устранение неисправности (ремонт).

Соответствующий данной системе размеченный граф

m _ij плотность вероятности перехода из состояния S_i в состояние S_j ( S_i®S_j ), где P_ij(Dt) – вероятность того, что за промежуток времени Dt произойдет данный переход.

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

Значения вероятностей переходов определяются из системы дифференциальных уравнений (Колмогорова) по следующим правилам:

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

2) в левой части уравнения – производная вероятности соответствующего состояния;

3) в правой части столько слагаемых, сколько переходов (ветвей) в размеченном графе связано с данным состоянием;

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

5) в правой части со знаком «+» идут (складываются) элементы, описывающие попадание системы в данное состояние, и со знаком «-» (вычитаются) элементы, описывающие «выход» системы из данного состояния;

6) для упрощения «решаемости» в систему вводится нормирующее уравнение, описывающее полную группу событий: , где N-количество вершин в размеченном графе состояний.

Для рассматриваемого графа состояний получаем следующую систему уравнения:

Данная система уравнений будет легче решаема в случае, когда она описывает стационарный процесс работы исследуемой технической системы (обычно вхождение системы в стационарный режим функционирования занимает от 2-х до 4-х тактов).

На практике считаем, что предположение о стационарности функционирования системы правомерно, если время функционирования системы в целом на порядок выше, чем (20¸40)×тактов работы системы («последовательное» одинарное прохождение по ветвям графа).

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

Система уравнений приводится к следующему виду:

и его решение уже не представляет особой сложности.

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

Пример №2.

Рассмотрим техническую систему S, состоящую из двух параллельно работающих узлов (два поста на СТО, два заправочных автомата на АЗС). Будем полагать, что переходы системы из одного состояния в другое происходят мгновенно, в случайные моменты времени. Как только узел выходит из строя, он «мгновенно» поступает на ремонт и после приведения его в рабочее состояние он также «мгновенно» начинает эксплуатироваться.

Полагаем, что данная система полностью описывается всего четырьмя состояниями: S₀ – оба узла исправны; S₁ – первый узел ремонтируется, второй исправен; S₂ – второй узел ремонтируется, первый исправен; S₃ – ремонтируются оба узла.

l₁, l₂ – плотность вероятности выхода из строя первого и второго поста, m₁, m₂ – плотность вероятности восстановления первого и второго узла соответственно.

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

Чтобы решить уравнения Колмогорова и найти численные значения для вероятностей соответствующих состояний, необходимо задаться начальными условиями.

Будем полагать, что в начальный момент времени оба узла исследуемой системы исправны, система находится в состоянии S₀ , т.е. P₀(t=0)=1, а все остальные начальные вероятности равны нулю: P₁(0)=P₂(0)=P₃(0)=0.

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

Стационарность режима работы предполагает равенство нулю от производных по времени от вероятностей состояния, т.е., i=1, 2, … , n , , где n – количество возможных состояний. А с учётом полной группы событий добавляется уравнение

Последнее, так называемое нормировочное условие, позволяет исключить из системы одно из уравнений…

Решим данную систему при следующих данных: l₁=1, l₂=2, m₁=2, m₂=3. Запишем систему без четвертого уравнения.

Решая их, получим: P₀=0,4; P₁=0,2; P₂@0,27; P₃@0,13.

Т.е. в стационарном режиме работы наша система в среднем 40% времени будет находиться в состоянии S₀ – оба узла исправны, и т.д..

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

Совокупный доход от работы данной системы W=0,4×8+0,2×3+0,27×5+0,13×0=5,15 у.е..

Теперь оценим загрузку ремонтных органов (рабочих), занятых ремонтом первого и второго узла. Доля времени, затрачиваемая на ремонт первого узла, равна Р₁+Р₃=0,2+0,13=0,33. Доля времени, затрачиваема на ремонт второго узла, равна Р₂+Р₃=0,4.

Аналогичным образом можно оценить экономические потери, вызванные поломками (затрачиваемые на ремонт).

Пример №3.

Работа диспетчера АТП, принимающего заказы на выполнение грузоперевозочных работ по телефону. Для данной системы возможны четыре следующие состояния: S₀ – простой, нет звонков, S₁ – прием заказа по телефону, S₂ – разрыв линии связи (сбой в работе АТС), либо «ошибочный» звонок (ошиблись номером), S₃ – оформление путевого листа.

Система дифференциальных уравнений, описывающих функционирование данной системы, будет записана следующим образом.

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

Пример №4.

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

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