МАРКОВСКИЙ СЛУЧАЙНЫЙ ПРОЦЕСС

С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ

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

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

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

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

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

Примерами случайных процессов могут быть:

— процесс функционирования ЭЦВМ;

— процесс наведения на цель управляемой ракеты или космического летательного аппарата;

— процесс обслуживания клиентов парикмахерской или ремен­ной мастерской;

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

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

— поступление заказов на ЭЦВМ и вид этих заказов; случайные выходы ЭЦВМ из строя;

— случайные возмущения (помехи) в системе управления ракетой;

— случайный характер потока заявок (требований), поступаю­щих со стороны клиентов;

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

Случайный процесс, протекающий в системе S, называется марковским процессом (или «процессом без последействия»), если он обладает следующим свойством:

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

Другими словами, в марковском случайном процессе будущее раз­витие его зависит только от настоящего состояния и не зависит от «пре­дыстории» процесса.

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

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

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

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

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

S₁, S₂, S₃,...

можно перечислить (перенумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Пример 1. Техническое устройство S состоит из двух узлов: I и II, каждый из которых может в ходе работы устройства отказать (выйти из строя). Воз­можны следующие состояния системы:

S₁ — оба узла работают;

S₂ — первый узел отказал, второй работает;

S₃ — второй узел отказал, первый работает;

S₄ — оба узла отказали.

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

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

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

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

Пусть имеется система S с дискретными состояниями:

S₁, S₂,,..., S_n.

Мы будем изображать каждое состояние прямоугольником, а воз­можные переходы («перескоки») из состояния в состояние — стрел­ками, соединяющими эти прямоугольники (рис. 1).

Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния S₁ в S₃ только через S₂, то стрелками отмечаются только переходы S₁ ® S₂ и S₂ ® S₃, но не S₁ ® S₃.

Пример 2. Система S — автомашина, которая может находиться в одном из пяти возможных состояний:

S₁ — исправна, работает; |

S₂ — неисправна, ожидает осмотра;

S₃ — осматривается;

S₄ — ремонтируется;

S₅ — списана.

Граф состояний системы показан на рис. 2.

Пример 3. Построить граф состояний в условиях примера 1 (предпола­гается, что ремонт узлов в ходе процесса не производится).

Решение. Граф состояний представлен на рис. 3. Отметим, что на графе не показан возможный переход из состояния S₁, непосредственно в S₄, который осуществится, если строго одновременно выйдут из строя оба узла. Возможностью такого события мы пренебрегаем.

Пример 4. Система S, как и в примере 1, представляет собой техническое устройство, состоящее из двух узлов: I и II; каждый из них может в какой-то момент времени отказать. Отказавший узел немедленно начинает восстанавливаться. Возможные состояния системы:

S₁ — оба узла работают;

S₂ — первый узел восстанавливается, второй работает;

S₃ — первый узел работает, второй восстанавливается;

S₄ — оба узла восстанавливаются

Граф состояний системы показан на рис. 4

Пример 5. В условиях примера 4 каждый узел перед тем, как начать вос­станавливаться, подвергается осмотру с целью локализации неисправности.

Состояния системы будем для удобства нумеровать не одним, а двумя ин­дексами; первый будет означать состояния первого узла:

1 — работает,

2 — осматривается,

3 — восстанавливается;

второй — те же состояния для второго узла, так что, например, S₂₃ будет озна­чать: первый узел осматривается, второй — восстанавливается, и т. д.

Возможные состояния системы S будут:

S₁₁ — оба узла работают,

S₁₂ — первый узел работает, второй осматривается,

....................

S₃₃ — оба узла восстанавливаются (всего 9 состояний).

Граф состояний показан па рис. 5.

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

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

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: