Методическое пособие 640

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

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

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

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

Классификация Марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции S(t) и параметра t. Различают следующие основные виды Марковских случайных процессов:

•с дискретными состояниями и дискретным временем (цепь Маркова);

•с непрерывными состояниями и дискретным временем

(Марковские последовательности);

•с дискретными состояниями и непрерывным временем (не-

прерывная цепь Маркова);

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

если переходные вероятности Pi / i+1 остаются постоянными в ходе процесса.

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

71

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

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

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

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

фа (рис. 4.1).

Рис. 4.1. Ориентированный взвешенный граф

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

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

Рис. 4.2. Невозвратное множество

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

72

множество, но не может вернуться в него.

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

Рис. 4.3. Возвратное множество

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

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

Рис. 4.4. Эргодическое множество

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

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

Рис. 4.5. Поглощающее множество

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

73

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

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

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

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

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

Моменты времени t1, t2, … , когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t, а номер шага 1, 2 ... k ... . Случайный процесс в этом случае характеризуется последовательностью состояний S(0), S(1), S(2), ..., S(k), ... , где S(0) – начальное со-

стояние системы (перед первым шагом); S(1) – состояние си-

74

стемы после первого шага; S(k) – состояние системы после k-го шага.

Вероятностями состояний цепи Маркова называются вероятности Pi(k) того, что после k-го шага (и до (k + 1)-го) система S будет находиться в состоянии Si (i = 1, 2, ..., n). Очевидно, для любого k

цепи называется распределение вероятностей состояний в начале процесса:

В частном случае, если начальное состояние системы S в точности известно S(0) = Si, то начальная вероятность Рi(0)=1, все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на k-м шаге из состояния Si в состояние Sj называется условная вероятность того, что система S после k-го шага окажется в состоянии Sj при условии, что непосредственно перед этим (после k - 1 шага) она находилась в состоянии Si.

Поскольку система может пребывать в одном из n состояний, то для каждого момента времени t необходимо задать n2 вероятностей перехода Pij, которые удобно представить в виде следующей матрицы:

где pij – вероятность перехода за один шаг из состояния Si в состояние Sj;

pii – вероятность задержки системы в состоянии Si. Матрица (4.8) называется переходной или матрицей пе-

реходных вероятностей.

75

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

Переходные вероятности однородной Марковской цепи Рij образуют квадратную матрицу порядка n. Отметим некоторые ее особенности [8]:

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

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

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

(см. рис. 2.2):

4.По главной диагонали матрицы переходных вероятностей стоят вероятности Рij того, что система не выйдет из состояния Si, а останется в нем.

Если для однородной Марковской цепи заданы начальное распределение вероятностей (4.7) и матрица переходных веро-

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

76

Рис. 4.6. Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)

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

Рис. 4.7. Пример Марковской цепи, смоделированной по Марковскому графу, изображенному на рис. 4.6

Основным математическим соотношением для дискретной Марковской цепи является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:

и называется уравнением Колмогорова-Чепмена.

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

77

стояниях.

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

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

Теория массового обслуживания — область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.

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

Пример. Рассмотрим процесс функционирования системы – автомобиль. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (S1) и неисправном (S2). Граф состояний системы представлен на рис. 4.8.

78

Рис. 4.8. Граф состояний автомобиля

В результате проведения массовых наблюдений за работой автомобиля составлена следующая матрица вероятностей перехода:

состоянии;

P12 = 0,2 – вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

P21 = 0,9 – вероятность перехода автомобиля из состояния «неисправен» в состояние «исправен»;

P22 = 0,1 – вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан P(0) = | 0 1|, т.е. Р1(0) = 0 и Р2(0)=1.

Требуется определить вероятности состояний автомобиля через трое суток.

Используя матрицу переходных вероятностей (4.10), определим вероятности состояний Pi(k) после первого шага (после первых суток):

P1(1) = P1(0)·P11 + P2(0)·P21 = 0·0,8 + 1·0,9 = 0,9;

P2(1) = P1(0)·P12 + P2(0)·P22 = 0·0,2 + 1·0,1 = 0,2.

Вероятности состояний после второго шага (после вторых суток) таковы:

P1(2) = P1(1)·P11 + P2(1)·P21 = 0,9·0,8 + 0,1·0,9 = 0,81; P2(2) = P1(1) ·P12 + P2(1) ·P22 = 0,9·0,2 + 0,1·0,1 = 0,19.

Вероятности состояний после третьего шага (после третьих суток) равны

P1(3) = P1(2) ·P11 + P2(2) ·P21 = 0,81·0,8 + 0,19·0,9 = 0,819; P2(3) = P1(2) ·P12 + P2(2) ·P22 = 0,81·0,2 + 0,19·0,1 = 0,181.

79

Таким образом, после третьих суток автомобиль будет находиться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

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

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

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

Решение.

S1 – состояние, в котором реализуются задачи пользова-

теля;

S2 – состояние, в котором реализуются программы операционной системы;

S3 – состояние простоя.

Граф функционирования системы имеет вид (рис. 4.9):

80