Материал: 2443

16

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

3.В чём состоит основная идея метода имитационного моделирования?

4.Сравните аппаратный и программный способ генерации случайных чисел по недостаткам и преимуществам.

5.Объясните способ генерации случайных чисел по методу серединных квадратов.

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

чисел.

7.Объясните на примере конкретных систем, как Вы понимаете основные свойства системы.

ГЛАВА 2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ МАРКОВСКИХ

СЛУЧАЙНЫХ ПРОЦЕССОВ

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

системы массового обслуживания (СМО). Математический аппарат изучения этих систем давно разработан и позволяет построить модели таких систем для описания процессов обслуживания и вычислить основные характеристики функционирования системы с целью определения её эффективности [7, c. 78]. Этот аппарат основывается на теории вероятностей и теории случайных процессов. Рассмотрим основные идеи и понятия.

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

Функция X(t) называется случайной, если её значение при любом аргументе t является случайной величиной.

Случайная функция X(t), аргументом которой является время,

называется случайным процессом.

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

17

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

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

если он обладает следующим свойством: для любого момента времени t0 вероятность любого состояния системы в будущем зависит только от её состояния в настоящем и не зависит от того, когда и каким образом система S пришла в это состояние.

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

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

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

с непрерывными дискретным временем (марковские

Мы будем рассматривать только марковские процессы с дискретными состояниями S1, S2, ..., Sn.

Граф состояний. Марковские процессы с дискретными состояниями удобно иллюстрировать с помощью так называемого графа состояний (рис. 2.1), где кружками обозначены состояния S1, S2,...

системы S, а стрелками – возможные переходы из состояния в состояние.

Рис. 2.1. Пример графа состояний системы S

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

18

как конечным, так и бесконечным (несчётным).

2.2.Марковские цепи

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

Событие S (k) = Si , состоящее в том, что сразу после k-го шага система находится в состоянии Si (i = 1, 2,...), является случайным событием. Последовательность состояний S (0), S (1),..., S (k),... можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью, если для каждого шага вероятность перехода из любого состояния Si в любое Sj не зависит от того, когда и как система пришла в состояние Si.

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

n

Понятно, что для каждого k: Pi k 1.

i 1

Начальным распределением вероятностей Марковской цепи называется распределение вероятностей в момент t = 0: P1 (0), P2 (0), Pn

(0). В частном случае, если S (0) = Si, то Pi (0) = 1, а остальные равны 0. Вероятностью перехода из состояния Si в состояние Sj (переходной вероятностью) называется вероятность того, что система окажется в состоянии Sj ,при условии, что до этого она находилась в состоянии Si. Поскольку система может пребывать в одном из n состояний, то для каждого момента надо задать n2 вероятностей, которые записывают в матрицу переходных

вероятностей:

19

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

однородной.

Отметим особенности переходной матрицы:

каждая строка характеризует выбранное состояние системы и её элементы – это вероятности переходов за один шаг из этого состояния в любое другое или в само себя;

элементы столбцов показывают вероятности переходов из любого состояния в конкретное;

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

по главной диагонали стоят вероятности того, что система не выйдет, а останется в прежнем состоянии.

Если для однородной марковской цепи задано начальное распределение вероятностей и матрица переходных вероятностей известна, то вероятности состояний системы Pi (k) в момент времени k определяются по формуле:

j 1

Пример.

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

S1 S2

Рис. 2.2. Граф возможных состояний системы S

p11 = 0,8 – вероятность того, что автомобиль останется в исправном состоянии;

20

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

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

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

Пусть в начальный момент времени автомобиль был исправен, т. е. P1(0)=1, P2(0) = 0. Тогда, найдём вероятности состояний системы в момент времениt=1:

P1 (1) = P1 (0) p11 + P2 (0) p21 = 0,8

P2 (1) = P1(0) p12 + P2 (0) p22 = 0,2.

В момент времени t = 2:

P1 (2) = P1 (1) p11 + P2 (1) p21 = 0,8 0,8 + 0,2 0,9 = 0,82

P2 (2) = P1(1) p12+ P2 (1) p22 = 0,8 0,2 + 0,2 0,1 = 0,18.

В момент времени t = 3:

P1 (3) = P1(2) p11 + P2(2)p21 = 0,82 0,8 +0,18 0,9 = 0,818

P2 (3) = P1(2) p11 +P2(2)p21 =0,182.

Т. е. после трёх суток автомобиль будет находиться в состоянии «исправен» с вероятностью 0,818 , а «неисправен» – с вероятностью 0,182.

Заметим, что формулу (2.1) можно переписать в матричном виде:

где P (k) = ( P1(k), P2 (k), … ,Pn (k) ) – вектор вероятностей состояний системы в момент k;

P = {pij} – матрица переходных вероятностей.

Действительно:

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

2.3.Непрерывные цепи Маркова

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