Мартовский процесс. Понятие о марковских случайных процессах

Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.

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

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

Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

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

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

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

Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.

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

Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

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

С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется Марковским процессом с непрерывным временем.

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

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1

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

1. Невозвратное множество (рис. 2).

Рис.2.

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

2. Возвратное множество (рис. 3).

Рис. 3.

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

3. Эргодическое множество (рис. 4).

Рис. 4.

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

4. Поглощающее множество (рис. 5)

Рис. 5.

При попадании системы в это множество процесс заканчивается.

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

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

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

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

Этот с.п. можно рассматривать как последовательность (цепь) событий
.

начальное состояние системы, т.е. перед 1-м шагом;
состояние системы после 1-го шага,
состояние системы после 2-го шага и т.д.), т.е. событий вида
где.

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью (цепь Маркова).

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

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

исправная работа;

профилактический осмотр и обслуживание;

ремонтная работа;

списание за негодностью;

Граф состояние работы изображен на рисунке

Рис. 1.11.(А.А. Белов, и др.)

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

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

Рис.1.12(Белов…)

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

Основной задачей исследования является нахождение вероятностей состояния на любом
м шаге. Будем вычислять вероятности состояний дискретной системы

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

При дискретном времени изменения состояний системы каждый переход от одного состояния к другому называют шагом.

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

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

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

м шаге, в состояние
м шаге она была в состоянии, т.е.

(43),

где первый индекс указывает на номер предшествующего, а второй индекс на номер последующего состояния системы.

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

Далее, мы будем рассматривать только однородные цепи, которые могут быть заданы с помощью вектора - вероятности состояний в момент времени
и матрицы (называемой матрицей перехода )

(44)
.

Элементы матрицы
обладают основными свойствами обычных квадратных матриц и дополнительно следующими свойствами:

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

Вероятность состояния системы на следующем шаге определяется по рекуррентной формуле:

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

.

Имеет место утверждение.

Теорема 17.1. Для матрицы перехода вероятностей за шагов
справедлива формула

(45)
,

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

где

при этом, по определению матрицы перехода известно, что
при любом
.

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

Пример 3. Задана матрица перехода

.

Найти матрицы переходных вероятностей
.

На основании правила умножения двух матриц получим

.

Задание. Проверьте, что верно равенство

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

понимается состояние системы, а под «испытанием» понимается изменение состояния системы.

Если «испытания » (опыты) являются независимыми, то появление определённого события в любом опыте не зависит от результатов ранее произведённых испытаний.

Задания. а) Заданы матрицы переходов

1.
;

2.
;

3.
.

Найти в каждом случае матрицу
.

Ответы: а) 1.
;

2.
;

3.

в)Заданы матрицы переходов

;
.

Найти
.

Ответы: в) 1.
;2.
;

3.
.

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

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

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

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

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

Обычно вероятности объединяют в квадратную матрицу (конечную или счётную) в зависимости от рассматриваемого процесса:

,

и называют марковской матрицей, или матрицей переходных вероятностей марковской цепи.

В матрице
я строка представляет собой распределение вероятностей с.в.
при условии, что
. Если число состояний, конечно, то- конечная квадратная матрица, порядок которой (число строк) равен числу состояний.

Естественно, что вероятности удовлетворяют следующим двум условиям:

а)
,

б)
при каждом фиксированном

Условие б) отражает тот факт, что каждое испытание вызывает некоторый переход из одного состояния в другое состояние. Для удобства обычно говорят также о переходе и в том случае, когда состояние остаётся неизменным. Имеет место утверждение.

Теорема 17.2. Процесс полностью определён, если заданы вероятности (46), т.е.

и распределение вероятностей случайной величины .

Доказательство. Покажем, что для любого конечногокак вычисляются вероятности

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

По определению условной вероятности имеем

Но по определению марковского процесса получим

Поставляя равенство (49) в (48) получим

Продолжая этот процесс последовательно, получим:

Процесс полностью определён. Что требовалась доказать.

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

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

Итак, марковский процесс удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов — с дискретным и непрерывным временем .

В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени — такты (1, 2, 3, 4, …). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.

Во втором случае исследователя интересует и цепочка меняющих друг друга состояний, и моменты времени, в которые происходили такие переходы.

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

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

Итак, модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.1 .

Каждый переход характеризуется вероятностью перехода P ij . Вероятность P ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

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

Например, полностью граф может выглядеть так, как показано на рис. 33.3 .

Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4 ). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.

Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал на подынтервалы величиной P i 1 , P i 2 , P i 3 , … (P i 1 + P i 2 + P i 3 + … = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале случайное число r рр и определить, в какой из интервалов оно попадает (см. лекцию 23).

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 33.4 ) .

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

Определим следующие три состояния: S 0 — цель не повреждена; S 1 — цель повреждена; S 2 — цель разрушена. Зададим вектор начальных вероятностей:

Значение P 0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.

Зададим матрицу перехода состояний (см. табл. 33.1).

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

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 33.6 ).

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

Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное состояние будет S 0 . Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, … (случайные числа можно взять, например, из этой таблицы).

0.31 : цель находится в состоянии S 0 и остается в состоянии S 0 , так как 0 < 0.31 < 0.45;
0.53 : цель находится в состоянии S 0 и переходит в состояние S 1 , так как 0.45 < 0.53 < 0.45 + 0.40;
0.23 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.23 < 0.45;
0.42 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.42 < 0.45;
0.63 : цель находится в состоянии S 1 и переходит в состояние S 2 , так как 0.45 < 0.63 < 0.45 + 0.55.

Так как достигнуто состояние S 2 (далее цель переходит из S 2 в состояние S 2 с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.

На рис. 33.7 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.

Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S 0 —S 0 —S 1 —S 1 —S 1 —S 2 . Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.

Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S 0 —S 0 —S 1 —S 1 —S 2 ); 11 (S 0 —S 0 —S 0 —S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 4 (S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 0 —S 0 —S 1 —S 1 —S 1 —S 2 ). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.

Теперь следует определить точность. Именно точность может нам показать, насколько следует доверять данному ответу. Для этого проследим, как сходится последовательность случайных (приближенных) ответов к правильному (точному) результату. Напомним, что, согласно центральной предельной теореме (см. лекцию 25 , лекцию 21), сумма случайных величин есть величина неслучайная, поэтому для получения статистически достоверного ответа необходимо следить за средним числом снарядов, получаемых в ряде случайных реализаций.

На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем — (5 + 4 + 11)/3 = 6.7. Далее ряд средних величин, по мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и является ответом (см. рис. 33.8 ).

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

Алгоритм имитации будет иметь следующий вид (см. рис. 33.9).

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

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

Итак, снова модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.10 .

Теперь каждый переход характеризуется плотностью вероятности перехода λ ij . По определению:

При этом плотность понимают как распределение вероятности во времени.

Переход из i -го состояния в j -е происходит в случайные моменты времени, которые определяются интенсивностью перехода λ ij .

К интенсивности переходов (здесь это понятие совпадает по смыслу с распределением плотности вероятности по времени t ) переходят, когда процесс непрерывный, то есть, распределен во времени.

С интенсивностью потока (а переходы — это поток событий) мы уже научились работать в лекции 28 . Зная интенсивность λ ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.

где τ ij — интервал времени между нахождением системы в i -ом и j -ом состоянии.

Далее, очевидно, система из любого i -го состояния может перейти в одно из нескольких состояний j , j + 1 , j + 2 , …, связанных с ним переходами λ ij , λ ij + 1 , λ ij + 2 , ….

В j -е состояние она перейдет через τ ij ; в (j + 1 )-е состояние она перейдет через τ ij + 1 ; в (j + 2 )-е состояние она перейдет через τ ij + 2 и т. д.

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

Поэтому из последовательности времен: τ ij , τ ij + 1 , τ ij + 2 и т. д. надо выбрать минимальное и определить индекс j , указывающий, в какое именно состояние произойдет переход.

Пример. Моделирование работы станка . Промоделируем работу станка (см. рис. 33.10 ), который может находиться в следующих состояниях: S 0 — станок исправен, свободен (простой); S 1 — станок исправен, занят (обработка); S 2 — станок исправен, замена инструмента (переналадка) λ 02 < λ 21 ; S 3 — станок неисправен, идет ремонт λ 13 < λ 30 .

Зададим значения параметров λ , используя экспериментальные данные, получаемые в производственных условиях: λ 01 — поток на обработку (без переналадки); λ 10 — поток обслуживания; λ 13 — поток отказов оборудования; λ 30 — поток восстановлений.

Реализация будет иметь следующий вид (см. рис. 33.11 ).

В частности, из рис. 33.11 видно, что реализовавшаяся цепь выглядит так: S 0 —S 1 —S 0 —… Переходы произошли в следующие моменты времени: T 0 —T 1 —T 2 —T 3 —… , где T 0 = 0 , T 1 = τ 01 , T 2 = τ 01 + τ 10 .

Задача . Поскольку модель строят для того, чтобы на ней можно было решить задачу, ответ которой до этого был для нас совсем не очевиден (см. лекцию 01), то сформулируем такую задачу к данному примеру. Определить долю времени в течение суток, которую занимает простой станка (посчитать по рисунку) T ср = (T + T + T + T )/N .

Алгоритм имитации будет иметь следующий вид (см. рис. 33.12 ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 0 – оба узла исправны; S 1 – первый узел ремонтируется, второй исправен; S 2 – второй узел ремонтируется, первый исправен; S 3 – ремонтируются оба узла.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ниже представлены два примера матриц переходных вероятностей.

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

Пример

Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия.

В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1):

Первая итерация – построение матрицы двухступенчатых переходов.

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна

В результате расчетов получаем матрицу двухступенчатых переходов:

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

Для проведения этих процедур в среде Excel необходимо выполнить следующие действия:

• 1) формировать матрицу;
• 2) вызывать функцию МУМНОЖ;
• 3) указывать первый массив – матрицу;
• 4) указывать второй массив (эта же матрица или другая);
• 5) ОК;
• 6) выделить зону новой матрицы;
• 7) F2;
• 8) Ctrl+Shift+Enter;
• 9) получить новую матрицу.

Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид:

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