Понятие о марковском процессе

До сих пор мы рассматривали главным образом детерминированные задачи исследования операций и методы оптимизации решений в этих задачах. Начиная с этой главы и до конца книги мы будем заниматься задачами исследования операций в условиях неопределенности. В этой главе мы рассмотрим сравнительно благоприятный случай «доброкачественной» или «стохастической» неопределенности (см. § 5 гл. 2), когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Мы будем здесь заниматься, главным образом, прямыми задачами исследования операций, т. е. построением ма­тематических моделей некоторых случайных явлений, лишь бегло останавливаясь на обратных задачах (оптимизации решений), потому что они, как правило, сложны. В стохастических задачах исследования операций часто затруднительно даже построение математической модели, уже не говоря об оптимизации («не до жиру, быть бы живу»). В большинстве случаев не удается построить простую математическую модель, позволяющую в явном (аналитическом) виде найти интересующие нас величины (показатели эффективности) в зависимости от условий операции а и элементов решения х. Однако в некоторых особых случаях такую математическую модель удается построить. Это — когда исследуемая операция представляет собой (точно или приближенно) Так называемый марковский случайный процесс.

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

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

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

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

Теперь спустимся из космоса в околоземную зону. Физическая система S — обыкновенный самолет, совершающий рейс на заданной высоте, по определенному маршруту. Является ли этот процесс случайным? Безусловно, да, так как он неизбежно (в силу турбулентности атмосферы и других факторов) сопровождается случайными возмущениями, колебаниями (в этом не усомнится никто, испытавший на себе так называемую «болтанку» или нарушение графика полетов).

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

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

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

О £_д (S_о) t

Рис. 15.1.

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

Это очень важное определение стоит того, чтобы его растолковать подробнее. Пусть в настоящий момент t₀ (см. рис. 15.1) система находится в определенном состоянии S₀. Мы наблюдаем процесс со стороны и в момент t₀ знаем состояние системы S₀ и всю предысторию процесса, все, что было при t < t₀. Нас, естественно, интересует будущее (t > t₀). Можем ли мы его предугадать (предсказать)? В точности — нет, наш процесс случайный, значит — непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время т система S окажется в состоянии S₁ или сохранит состояние S₀, и т. п.

Так вот, для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S₀ и забыв о его «предыстории» (поведении системы при t < t₀). Само состояние So, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Иначе формулируя, в марковском процессе «будущее зависит от прошлого только через настоящее».

Пример марковского процесса: система S — счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент t характеризуется показанием счетчика — числом частиц, пришедших до данного момента. Пусть в момент t₀ счетчик показывает S₀. Вероятность того, что в момент t> t₀ счетчик покажет то или другое число частиц S₁ (или не менее S₁), разумеется, зависит от S₀, но не зависит от того, в какие именно моменты приходили частицы до момента t₀.

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком- то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — х и «синих» — у, сохранившихся (не сбитые) к какому-то моменту. В момент t₀ нам известны численности сторон — х₀ и y₀. Нас ин­тересует вероятность того, что в какой-то момент t₀ + т численный перевес будет на стороне «красных». Спросим себя, от чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент to, а не от того, когда и в какой последовательности погибали сбитые до момента t₀ самолеты.

Итак, более или менее ясно, что такое марковский случайный процесс. Теперь ошеломим читателя неожиданным парадоксом: в сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент t₀ оно еще исправно, и нас интересует вероятность того, что оно проработает еще время т. Если за настоящее состояние системы считать просто «система исправна», то процесс безусловно не марковский, пото­му что вероятность того, что она не откажет за время т, зависит, в общем случае, от того, сколько времени она уже проработала и когда был послед ний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние системы, то процесс уже можно будет, пожалуй, считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, так как (если число параметров прошлого велико) оно зачастую приводит к «про­клятию многомерности», о котором мы уже говорили. Поэтому в дальнейшем, говоря о марковском процессе, мы будем подразумевать его простым, «бесхитростным», с небольшим числом параметров, определяющих «настоящее».

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

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

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

50 — оба узла исправны,

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

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

53 — оба узла ремонтируются.

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

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состояний. Состояния системы изображаются прямоугольниками (или кругами, или даже точками), а возможные переходы из состояния в состояние — стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S₁, S₂,......................................, S_n.

Построим граф состояний для рассмотренного выше примера (см. рис. 15.2). Стрелка, направленная из S₀ в S₁, означает переход в момент отказа первого узла; стрелка, направленная обратно, из S₁ в S₀, — переход в момент окончания ремонта этого узла. Остальные стрелки объясняются аналогично.

Внимательный читатель может спросить: а почему нет стрелки, ведущей непосредственно из S₀ в S₃? Разве не может быть, что оба узла откажут одновременно, например, вследствие короткого замыкания? Вопрос законный. Ответим, что мы предполагаем узлы выходящими из строя независимо друг от друга, а вероятностью строго одновременного выхода их из строя пренебрегаем (ниже будет дано более точно обоснование этого допущения).

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