Моделирование эволюции систем на основе теории Марковских процессов

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

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

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

Стохастический процесс, протекающий в системе S, с дискретными состояниями s₁, s₂,…, s_i, называется Марковским, если для любого момента времени t₀ вероятность каждого из состоянии в будущем (при t > t₀) определяется только ее состоянием в настоящем (при t=t₀) и не зависит от ее поведения в прошлом (при t < t₀ ).

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

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

Если t₀ , t₁ , ... , t_n-1 , t_n , ... есть моменты времени, когда происходят некоторые события в системе S и Х_n = t_n - t_n-1 , n = 1, 2, . . . - независимые и одинаково распределенные случайные величины, то мы имеем процесс, который в указанные моменты времени себя «восстанавливает», и, следовательно, {X_n} можно назвать процессом восстановления. Если N (t} есть число актов восстановления, имеющих место в момент t , т. е. N (t) = mах {n ½ Х₁ + Х₂ . . . + Х_n £ t }, то процесс {N (t) , t ³ 0} есть процесс учета актов восста­новления.

Пусть имеется система S с возможными дискретными состояниями s₁, s₂, ..., s_n. Если переходы из одного состояния s_i в другое s_j происходят только в определенные моменты времени t₀, t₁, t₂,…,t_n с шагом t, то процесс представляет собой случайную цепь блужданий. Случайная цепь, для которой в каждый момент вся дальнейшая последовательность событий зависит только от состояния системы S в данный момент, есть марковская цепь.

Рассмотрим некоторый стохастический процесс X (t), в котором параметр t и значения случайных величин X (t) могут меняться непрерывно. Пусть (t₀< t₁ < t₂ <... < t_n < t) - конечное множество точек в пространстве параметров. Тогда X (t) называют Марковским процессом, если

Pr {X (t) £ х \ X (t_n) = x_n , X (t_n-1) = x_n-1 ,…, X (t₀) = x₀ } = Pr {X (t) £ x | X(t_n) = x_n}

т.е. если условное распределение X (t) при заданных значениях X (t₀) , X (t₁) , . . . , X (t_n) зависит лишь от X (t_n) т. е. от значения X (t) в последний из указанных моментов времени.

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

Пусть {Х_n, n = 0, 1, 2 . ..} - цепь Маркова именно такого типа и P_ij^m,m+n = Рг {X_т+n = j | Х_т = I }.

Если P_ij^m,m+n = P_ij^0,n (º P_ij⁽ⁿ⁾) для всех значений m, то такую цепь Маркова называют однородной во времени. Матрица, элементами которой являются Р_ij (º Р_ij⁽¹⁾) называется матрицей вероятностей переходов между состояниями системы (или стохастической матрицей). Она полностью определяет цепь Маркова.

С практической точки зрения наиболее важной характеристикой марковской цепи являются вероятности:

P_i (k) = P {s(k)=s_i}; I = 1,2,…,n; k = 0,1,2,…,n,

Это есть вероятности нахождения системы в состоянии s_i на k-м шаге. Основной задачей исследования марковской цепи является нахождение этих вероятностей Р_i(k). Для нахождения этих вероятностей необходимо знание условных вероятностей P_ij(k) перехода системы на k-м ваге в состояние s_j, если известно, что на предыдущем (k-1)-м шаге она находились в состоянии s_i. Вероятности P_ij (k) = P{s(k) = s_j|s(k-1)=s_i}; i,j = 1,2,…,n называются вероятностями переходов, или переходными вероятностями Марковской цепи на k-м шаге. Вероятность P_ij(k) есть вероятность задержки системы в i-м состоянии на k-м шаге.

Переходные вероятности записываются в виде матрицы размером n*n:

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

Чтобы найти безусловные вероятности P_i(k), кроме стохастической матрицы ||P_ij(k)||, необходимо знание начального распределения вероятностей P_i(0), соответствующего моменту t=0 и представляющего из себя вектор (0)={Р₁(0),P₂(0),..., Р_n(0)}, который также обладает свойством .

Если известно, что в начальный момент система S находилась точно в состоянии s_i, то можно записать: Р_i(0) = 1, а все остальные вероятности равны 0:

Р₁ (0) = Р₂ (0) = ... = Р_i-1 (0) = Р_i+1 (0) = ... =Р _n(0) = 0

Иначе говоря, вектор начального состояния есть (0) = {0,0....,1,....0}, где единица стоит на месте i – го состояния.

Марковская цепь называется однородной, если остальные вероятности P_ij(k) не зависят от шага k, т.е. если P_ij (k) P_ij. Стохастическая матрица однородной Марковской цепи имеет вид табл.1 при отсутствии зависимости от k. В дальнейшем для простоты рассматривается только однородная Марковская цепь.

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

Всякий граф задается своими ребрами u_j и вершинами V_i,. Если в системе имеет значение только факт связи между вершинами, то понятие дуги заменяется понятием ребра, которое геометрически изображается линией без ориентации. В теории Марковских процессов речь идет о дугах. Дуга (ребро) графа u_j инцидентно (принадлежит) вершине V_i, а вершина V_i конинцидентна дуге (ребру) u_j, если V_i Î u_j. Вершины V_i и V_j графа g = [V, u] смежны, если {V_i, V_j} Î U. Для задания орграфов существует несколько классов матриц, основными из которых являются класс матриц инциденций и класс матриц смежности. Если орграф g содержит n вершин и m дуг, то матрица инциденций B(g) = [b_ij] m´n определяется как

ì 1, если вершина V_j является началом дуги U_i;

b_ij = í –1, если вершина V_j является концом дуги U_i;

î 0, если вершина V_j неконинцидентна дуге U_i;

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

то для его дуг матрица инциденций имеет вид

.

а для ребер этого графа матрица инциденций следующая:

.

Иногда орграф содержит петли, то есть дуги вида (V_i, V_i); в этом случае некоторые элементы матрицы В одновременно будут равны и 1 и –1, что приводит к неоднозначности элементов матрицы В.

Для задания орграфа с петлями можно разложить матрицу В на две матрицы: В⁺ = [b_ij⁺]_m´n, где b_ij⁺ =

и В^– = [b_ij^–]_m´n,

где b_ij^– =

Если орграф составлен без петель, то В = В⁺ – В^–. Матрицы В⁺ и В^– описывают орграф без учета весов вершин и дуг. Вес вершин орграфа g задается в виде столбцевой матрицы:

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

Матрицы В⁺, В^-, Р, W, полностью описывает взвешенный граф. Если имеется следующий орграф:

то матрица смежности для этого графа имеет вид

.

Матрицы A, P, W полностью описывают взвешенный орграф. Матрицы этих классов задают графы с точностью до изоморфизма.

Графы g = < V, U > и g' = < V', U' > называются изоморфными, если существует такое взаимнооднозначное соответствие j между их вершинами V и V', что (V_i, V_j) Î U в том и только в том случае, если

[j (V_i), j (V_j)] Î U, V_i' = j (V_i), V_j' = j (V_j).

При нахождении вероятностей состояний Марковской цепи с помощью теории графов каждое состояние представляется в виде некоторой вершины графа, а возле каждой стрелки (дуги графа), переводящей систему из состояния s_i в состояние s_j, проставляется вероятность этого перехода Р_ij. Ниже приведен пример такого размеченного графа состояний для некоторой технической системы S.

Рис. 15. Размеченный граф состояний некоторого технического устройства.

Для этого графа вероятности задержек Р_ij в состояниях равны

Если известно, что в начальный момент (k=0) система находилась в состояниях s_i с вероятностью P_i(0) = Р{s(0) = s_i} и известны элементы стохастической матрицы Р_ij = P {s(1) = s_j | s(0) =s_i},то на первом шаге эволюции системы (k = 1) система будет описываться вектором состояний с компонентами:

j=1,2,…,n.

Если теперь известен вектор состояний на первом шаге, то аналогично получим компоненты вектора состояний системы на втором шаге эволюции (k = 2):

j=1,2,…,n.

В общем случае при переходе от k-го к (k+1) - му шагу эволюции системы имеется рекуррентную формулу

j=1,2,…,n; k=1,2,… .

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

s₁ - устройство полностью исправно;

s₂ - обнаружена неисправность, требуется наладка;

s₃ - серьезная поломка, требуется ремонт;

s₄ - признано непригодным и списано.

В течение недели возможны как наладка, так и ремонт, поэтому имеют место переходы s₂ → s₁ и s₃ → s₁. Состояние s₄ поглощающее, поскольку переходы из него в другие состояния невозможны. Допустим, нам каким-либо образом стали известны вероятности переходов между состояниями устройства и мы смогли придать размеченному графу состояний достойный вид:

Рис. 16. Размеченный граф состояний технического устройства с известными вероятностями переходов между возможными состояниями.

Этому графу соответствует следующая стохастическая матрица:

Теперь мы можем количественно рассчитать эволюцию данного устройства (Рис. 16). Пусть нам известно, что в начальный момент времени устройство исправно, т.е. вектор начального состояния имеет компоненты Р₁(0) = 1, Р₂(0) = 0, Р₃(0) = 0, Р₄(0) = 0, иначе говоря, мы можем описать начальное состояние устройства с помощью вектора-строки (0) = {1,0,0,0}. Состояние устройства на следующей неделе получим по обычному правилу перемножения матриц, т.е. по правилу "строка на столбец":

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

.

Аналогично на третьем шаге эволюции устройства получим:

(2)= (1)||Р_ij||={0.421,0.131,0.113,0.335}.

На четвертом:

(2)= (1)||Р_ij||={0.3435,0.1207,0.0986,0.4372} , и т. д.

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

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

Например, рассмотрим устройство с всего двумя возможными состояниями: s₁ - исправно и s₂ - неисправно, переходы между которыми описываются следующим простым размеченным графом:

Если вначале устройство исправно, т.е. вектор начального состояния есть (0)={1,0}, то последовательность шагов k = 1, 2, 3,... приводит к такой последовательности векторов состояний:

(1)={1,0}× ={0.7,0.3}; (2)={0.61,0.39};

(3)={0.583,0.4177}; (4)={0.575,0.425}.

Продолжая вычисления (k), можно убедиться, что с ростом k вероятность (k) стремится к определенному пределу и, действительно, можно доказать, что limP₁(k) = P₂₁/(P₁₂+P₂₁) = 0.5714 при kà .

Если система s имеет поглощающее состояние, как, например, состояние s₄ устройства, отображаемого размеченным графом рис. 16, то, в каком бы состоянии ни находилась система s в начальный момент, в конце концов она неизбежно "скатится" в это поглощающее состояние. В случае Рис. 16 этим поглощающим состоянием будет состояние s₄ полностью непригодного к восстановлению устройства. Предельным вектором Марковской цепи в этом случае будет lim (k)={0,0.0,1}, при kà .