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

Моделирование операций по схеме марковских случайных процессов При выборе оптимального решения мы сталкиваемся с тем, что многие операции развиваются как случайные процессы, ход и исход которых зависит от ряда случайных факторов, сопровождающих эти операции. Для того, чтобы вычислить числовые параметры, характеризующие эффективность таких операций, нужно построить некоторую вероятностную модель явления, учитывающую сопровождающие его случайные факторы. Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применён математический аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов. Случайный процесс, протекающий в системе S, называется марковским процессом (или процессом без последействия), если он обладает следующим свойством: для каждого момента времени t0 вероятность любого состояния системы в будущем (при t> t0) зависит только от её состоянии в настоящем (при t= t0) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом). На практике часто встречаются случайные процессы, которые, с той или иной степенью приближения, можно считать марковскими. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы S1, S2,…, Sn можно перечислить одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое. Пример. Система S – станок, который может находиться в одном из пяти возможных состояний: S1 – исправен, работает; S2 – неисправен, ожидает осмотра; S3 – осматривается; S4 – ремонтируется; S5 – списан. Рис1. Граф состояний системы Случайный процесс называется процессом с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определённые, заранее фиксированные моменты времени: t1, t2, … , tk. В промежутке времени между этими моментами система S сохраняет своё состояние. Рассмотрим марковский процесс с дискретными состояниями и дискретным временем. Пусть имеется физическая система S , которая может находиться в состояниях S1, S2,…, Sn, причём переходы системы из состояния в состояние возможны только в моменты: t1, t2, … , tk. Будем называть эти моменты шагами процесса и рассматривать случайный процесс, происходящий в системе S, как функцию целочисленного аргумента: 1, 2, … , k (номера шага). Случайный процесс, происходящий в системе, состоит в том, что в последовательные моменты времени t1, t2, … , tk система S оказывается в тех или иных состояниях. В общем случае система в моменты t1, t2, … , tk может не только менять состояние, но и оставаться в прежнем. Условимся обозначать Si(k) событие, состоящее в том, что после k шагов система находится в состоянии Si . Процесс, происходящий в системе, можно представить как цепочку событий, например: S1(0), S1(1),, S2(2), S3(3), S4(4)… Такая случайная последовательность событий называется марковской цепью, если для каждого шага вероятность перехода из любого состояния Si в любое Sj . Будем описывать марковскую цепь с помощью так называемых вероятностей состояний. Пусть в любой момент времени ( после k-го шага) система S может быть в одном из состояний: S1 ,S2 ,…, Sn , т.е. осуществляется одно из событий: S1(k) , S2(k) , … , Sn(k). Обозначим вероятности этих событий: P1(1), P2(1), …, Pn(1) – вероятности всех состояний после первого шага; P1(2), P2(2), …, Pn(2) – вероятности всех состояний после второго шага; . . . P1(k), P2(k), …, Pn(k) – вероятности всех состояний после первого шага; Для каждого номера шага k P1(k) + P2(k) + …+ Pn(k) =1 как вероятности несовместных событий. Будем называть вероятности P1(k), P2(k), …, Pn(k) вероятностями состояний. Поставим задачу: найти вероятности состояний системы для любого k. Изобразим состояния системы и переходы между ними в виде графа, в котором состояния системы представлены в виде вершин, а все возможные переходы из одного состояния в другой – стрелками (рис.1). Случайный процесс (марковскую цепь) можно представить себе так, что будто точка, изображающая систему S, случайным образом перемещается по графу состояния в моменты t1, t2, … , tk, а иногда задерживается на одном и том же состоянии. Будем называть эти вероятности переходными вероятностями марковской цепи. Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. Рассмотрим однородную марковскую цепь. Пусть система S имеет n возможных состояний S1, S2,…, Sn. Предположим, что для каждого состояния нам известна вероятность перехода в любое другое состояние за один шаг ( в том числе и вероятность задержки в данном состоянии). Обозначим через Pij вероятность перехода за один шаг из состояния Si в состояние Sj. Pii – вероятность задержки системы в состоянии Si . Запишем переходные вероятности Pij в виде прямоугольной матрицы: P11 P12 … P1j … P1n P21 P22 … P2j … P2n Pij = . . . Pi1 Pi2 … Pij … Pin . . . Pn1 Pn2 … Pnj … Pnn Некоторые из переходных вероятностей могут быть равны нулю: это означает, что за один шаг переход системы из i-го состояния в j-е невозможен. Сумма членов, стоящих в каждой строке матрицы, должна быть равна единице., т.к. в каком бы состоянии система ни была перед k-м шагом, события S1(k), S2(k), … , Sn(k) несовместны. При рассмотрении марковских цепей часто бывает удобно пользоваться графом состояний, на котором у стрелок проставлены соответствующие переходные вероятности. Такой граф мы будем называть размеченным графом состояний. Имея в распоряжении размеченный граф состояний (матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний P1(k), P2(k), …, Pn(k) после любого (k-го ) шага. Покажем, как это делается. Предположим, что в начальный момент система находится в каком-то определённом состоянии, например Sm . Тогда, для начального момента (0) будем иметь: P1(0) = 0, P2(0) = 0, … Pm(0) = 1, … , Pn(0) = 0, т.е. вероятности всех состояний равны 0, кроме вероятности начального состояния: вероятность Sm равна единице. Найдём вероятности всех состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии Sm . Значит, за первый шаг она перейдёт в состояния S1, S2,…, Sm , … , Sn с вероятностями Pm1, Pm2, …, Pmm , … , Pmn , записанными в m-й строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут: P1(1) = Pm1, P2(1) = Pm2, …, Pm(1) = Pmm , Pn(1) = Pmn . Найдём вероятности состояний после второго шага: P1(2), P2(2), …, Pm(2), … ,Pn(2) . Будем вычислять их по формуле полной вероятности, с гипотезами: – после первого шага система была в состоянии S1 , – после первого шага система была в состоянии S2 , . . . – после первого шага система была в состоянии Sm , . . . – после первого шага система была в состоянии Sn , Вероятности гипотез известны, условные вероятности известны (из матрицы). По формуле полной вероятности получим: P1(2) = P1(1)P11 + P2(1)P21 + … + Pn(1)Pn1 ; P2(2) = P1(1)P12 + P2(1)P22 + … + Pn(1)Pn2 ; . . . Pm(2) = P1(1)P1m + P2(1)P2m + … + Pn(1)Pnm ; . . . Pn(2) = P1(1)P1n + P2(1)P2n + … + Pn(1)Pnn ; или, гораздо короче Рi(2) = j(1)Pji (i = 1,2,…,n). В формуле суммирование распространяется формально на все состояния S1 ,S2 ,…, Sn , фактически учитывать надо только те из них, для которых переходные вероятности Pii отличны от нуля. Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично: Рi(3) = j(2)Pji (i = 1,2,…,n). И вообще после k-го шага Рi(k) = j(k-1)Pji (i = 1,2,…,n). Итак, вероятности состояний Рi(k) после k-го шага определяются рекуррентной формулой через вероятности состояний после (k-1)-го шага и т.д. Пример реализации модели Некоторое техническое устройство (ТУ) может находиться в одном из четырёх состояний: S1 – ТУ работоспособно; S2 – ТУ требует текущего ремонта; S3 – ТУ требует капитального ремонта; S4 – ТУ списан. Матрица переходных вероятностей имеет вид: 0.3 0.4 0.2 0.1 ||Pij|| = 0 0.4 0.4 0.2 0 0 0.3 0.7 0 0 0 1 В начальный момент времени ТУ находится в состоянии S1 . Шаг – 1 год. Вероятности состояний после первого шага (берутся из первой строки матрицы): P1(1) = 0.3; P2(1) = 0.4; P3(1) = 0.2; P4(1) = 0.1. Вероятности состояний после второго шага: P1(2) = P1(1) · P11 = 0.3 · 0.3 = 0.09; P2(2) = P1(1) · P12 + P2(1) · P22 = 0.3 · 0.4 +0.4 · 0.4 = 0.28; P3(2) = P1(1) · P13 + P2(1) · P23 + P3(1) · P33 = 0.3 · 0.2 + 0.4 · 0.4 + 0.2 · 0.3 = 0.28; P4(2) = P1(1) · P14 + P2(1) · P24 + P3(1) · P34 + P4(1) · P44 = 0.3 ·0.1 + 0.4 · 0.2 + 0.2 · 0.7 + 0.1 · 1 = 0.35 . Вероятности состояний после третьего шага: P1(3) = P1(2) · P11 = 0.09 · 0.3 = 0.027; P2(3) = P1(2) · P12 + P2(2) · P22 = 0.09 · 0.4 +0.28 · 0.4 = 0.148; P3(3) = P1(2) · P13 + P2(2) · P23 + P3(2) · P33 = 0.09 · 0.2 + 0.28 · 0.4 + 0.28 · 0.3 = 0.214; P4(3) = P1(2) · P14 + P2(2) · P24 + P3(2) · P34 + P4(2) · P44 = 0.3 ·0.1 + 0.4 · 0.2 + 0.2 · 0.7 + 0.1 · 1 = 0.35 . Вероятности состояний после четвёртого шага: P1(4) = P1(3) · P11 = 0.0081; P2(4) = P1(3) · P12 + P2(3) · P22 = 0.27 · 0.4 +0.148 · 0.4 = 0.07; P3(4) = P1(3) · P13 + P2(3) · P23 + P3(3) · P33 = 0.027 · 0.2 + 0.148 · 0.4 + 0.214 · 0.3 = 0.1288; P4(4) = P1(3) · P14 + P2(3) · P24 + P3(3) · P34 + P4(3) · P44 = 0.027 ·0.1 + 0.148 · 0.2 + 0.214 · 0.7 + 0.611 · 1 = 0.793 . Таким образом нами получены вероятности всех состояний ТУ через 4 года: ТУ находится в работоспособном состоянии – 0.008; ТУ требует текущего ремонта – 0.070; ТУ требует капитального ремонта – 0.129; ТУ списано – 0.793. 1.3. Контрольное задание №1 Автоматическая линия, состоящая из 2-х станков и накопителя, может находиться в одном из следующих состояний (см. рис.1): S1 – все станки работают; S2 – 1-й станок простаивает из-за поломки, 2-й работает; S3 – 2-й станок простаивает из-за поломки, 1-й работает; S4 – 1-й и 2-й станки простаивают из-за поломки; S5 – 1-й станок простаивает из-за переполнения накопителя; S6 - 2-й станок простаивает из-за переполнения накопителя. S6 S1 S5 S2 S4 S3 Рис.1. Граф переходных вероятностей Определите вероятности всех состояний системы через 4 шага (шаг – 1час). В табл.1 представлены данные матрицы переходных вероятностей для вашего варианта задания. № вар. P12 P13 P21 P24 P26 P31 P34 P35 P42 P43 P51 P61 Начальное состояние 1 0.1 0.1 0.8 0.05 0.8 0.05 0.4 0.4 S1 2 0.1 0.2 0.7 0.05 0.6 0.1 0.5 0.4 S1 3 0.2 0.2 0.7 0.1 0.7 0.1 0.45 0.45 S4 4 0.2 0.2 0.8 0.1 0.8 0.1 0.9 0.9 S1 5 0.1 0.1 0.9 0.2 0.9 0.2 0.95 0.95 S1 6 0.1 0.1 0.8 0.05 0.8 0.05 0.4 0.4 S2 7 0.2 0.2 0.7 0.1 0.7 0.1 0.45 0.45 S1 8 0.1 0.2 0.7 0.05 0.6 0.1 0.5 0.4 S2 9 0.2 0.2 0.8 0.1 0.8 0.1 0.9 0.9 S2 10 0.1 0.1 0.9 0.2 0.9 0.2 0.95 0.95 S2 11 0.1 0.1 0.8 0.05 0.8 0.05 0.4 0.4 S3 12 0.1 0.2 0.7 0.5 0.6 0.1 0.5 0.4 S3 13 0.2 0.2 0.7 0.1 0.7 0.1 0.45 0.45 S3 14 0.2 0.2 0.8 0.1 0.8 0.1 0.9 0.9 S3 15 0.1 0.1 0.8 0.05 0.8 0.05 0.4 0.4 S4 16 0.1 0.1 0.8 0.05 0.8 0.05 0.4 0.4 S3 17 0.1 0.2 0.7 0.05 0.6 0.1 0.5 0.4 S4 18 0.2 0.2 0.7 0.1 0.7 0.1 0.45 0.45 S1 19 0.2 0.2 0.8 0.1 0.8 0.1 0.9 0.9 S6 20 0.1 0.1 0.9 0.2 0.9 0.2 0.95 0.95 S5 Табл.1. Варианты заданий