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

1. МАРКОВСКИЙ СЛУЧАЙНЫЙ ПРОЦЕСС С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 4.1

Рис. 4.2

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

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

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

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

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

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

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

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

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

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

— списана.

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

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

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

Рис. 4.3

Рис. 4.4

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

Рис. 4.5

Возможные состояния системы:

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

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

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

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

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

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

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

1 — работает,

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

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

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

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

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

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

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

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