Файл: Механики.pdf

180
Раздел 5. Численное моделирование
находится в
состоянии
E
i
:
}
)
(
Pr{
)
(
i
i
E
t
Z
t
p
=
=
В
любой момент времени
t система может находиться в
одном из
n возможных состояний
, то есть для любого момента времени
t выполняется условие
:
,
1
)
(
1
=
∑
=
t
p
n
i
i
(5.5) которое называется
нормировочным
Совокупность вероятностей
)
(t
p
i
может быть представлена вектором с
числом координат
, равным числу возможных состояний системы
:
{
}
,
)
(
),...,
(
)
(
1
t
p
t
p
t
P
n
=
причем
∑
=
=
≤
≤
n
i
i
i
t
p
t
p
1 1
)
(
;
1
)
(
0
. (5.6)
Вектор
, обладающий свойствами
(5.6), называется
стохастическим
Стохастический вектор называется
вектором
состояний
, если его компоненты представляют собой вероятности состояний системы
Вектор состояний
{
}
)
(
),...,
(
)
(
1
t
p
t
p
t
P
n
=
является основной характе
- ристикой марковского случайного процесса
На основе полученных значений вероятностей состояний случайного процесса
, протекающего в
исследуемой системе
, могут быть рассчитаны представляющие интерес реальные характеристики системы
, например для системы массового обслуживания могут быть рассчитаны длины очередей заявок
5.3.
Методы
расчета
марковских
моделей
5.3.1.
Эргодическое
свойство
случайных
процессов
Если по истечении достаточно большого промежутка времени веро
- ятности состояний стремятся к
предельным значениям
n
p
p
,
,
1
K
, не зави
- сящим от начальных вероятностей
)
0
(
,
),
0
(
1
n
p
p
K
и от текущего момента времени
t , то говорят
, что случайный процесс обладает
эргодическим
свойством
Таким образом
, для процессов
, обладающих эргодическим свойством
:
P
=
∞
=
∞
→
)
(
)
(
lim
P
t
P
t
, где
)
,
,
(
1
n
p
p K
=
P
– вектор вероятностей состояний системы
, называемых
стационарными
вероятностями
В
системе
, описываемой марковским случайным процессом
, облада
- ющим эргодическим свойством
, при
∞
→
t
устанавливается некоторый предельный режим
, при котором характеристики функционирования системы не зависят от времени
В
этом случае говорят
, что система

Раздел 5. Численное моделирование
181 работает в
установившемся
или
стационарном
режиме
Если характеристики функционирования системы зависят от времени
, то имеем
неустановившийся
режим
Отметим
, что для стационарных вероятностей
i
p должно выполняться нормировочное условие
(5.5).
При рассмотрении случайных процессов возникает вполне резонный вопрос
:
когда
случайный
процесс
обладает
эргодическим
свойством
?
Случайный процесс
с
дискретным
временем
обладает
эргодическим
свойством
, если матрица вероятностей переходов
не
является
периодической
или
разложимой
Матрица является
разложимой
, если она может быть приведена к
одному из следующих видов
:
1)






D
0
0
A
, 2)






D
C
0
A
, 3)






D
0
B
A
,
где
A, B, C, D
– ненулевые квадратные подматрицы
;
0
– нулевая квадратная подматрица
В
первом случае состояния
, соответствующие подмножествам
A
и
D
, называются
замкнутыми
, так как система
, находясь в
каком
- то состоянии одного из этих подмножеств
, никогда не сможет перейти в
какое
- либо состояние другого подмножества
Состояния
, соответствующие подмноже
- ству
D
во втором случае и
подмножеству
A
в третьем случае
, называются
невозвратными
, поскольку после того
, как процесс покинет эти состоя
- ния
, невозможен обратный переход в
эти состояния из состояний
, соответствующих другим подмножествам
Матрица является
периодической
, если она может быть приведена к
виду
:






0
C
B
0
Случайный процесс в
этом случае будет по очереди переходить из состояний
, соответствующих
B
, в
состояния
, соответствующие
С
Итак
, если матрица вероятностей переходов
],
,
1
,
|
[
n
j
i
q
ij
=
=
Q
случайного процесса с
дискретным временем не является периодической или разложимой
, то процесс обладает эргодическим свойством
:
)
,
1
(
)
(
lim
n
i
p
k
p
i
i
k
=
=
∞
→
. (5.7)
Транзитивный
случайный процесс с
непрерывным
временем
и
конечным
числом состояний
, среди которых нет невозвратных и
поглощающих состояний
, всегда обладает эргодическим свойством
:
)
,
1
(
)
(
lim
n
i
p
t
p
i
i
t
=
=
∞
→
. (5.8)

182
Раздел 5. Численное моделирование
5.3.2.
Марковские
процессы
с
дискретным
временем
Для однородного марковского процесса с
дискретным временем вероятности состояний на момент времени
k
t определяются на основе следующего рекуррентного выражения
:
,...)
2
,
1
;
,
1
(
)
1
(
)
(
1
∑
=
=
=
−
=
n
i
ij
i
j
k
n
j
q
k
p
k
p
(5.9)
Если рассматриваемый марковский процесс обладает эргодическим свойством
, то
, согласно
(5.7), при
∞
→
k
вероятности состояний
)
(k
p
i
стремятся к
стационарным значениям
i
p
, не зависящим от момента времени
k
t и
начальных вероятностей
)
0
(
i
p
С
учётом этого
, выражение
(5.9) может быть преобразовано к
виду
:
∑
=
=
=
n
i
ij
i
j
n
j
q
p
p
1
)
,
1
(
(5.10) а
нормировочное условие
(5.5) примет вид
:
1 1
=
∑
=
n
i
i
p
(5.11)
Уравнения
(5.10) с
условием
(5.11) образуют систему линейных алгебраических уравнений для расчёта стационарных вероятностей состояний марковского процесса
, которая обладает единственным решением
, если
Q
– эргодическая матрица
Доказательство выражения (5.9).
Рассмотрим однородный марковский процесс с
дискретным временем
, который может находиться в
одном из
n возможных состояний
:
Е
1
, …,
Е
n
Вероятности переходов
ij
q заданы в
виде матрицы переходов
]
,
1
,
|
[
n
j
i
q
ij
=
=
Q
, а
начальные вероятности на момент времени
0 0
=
t
в виде вектора
)}
0
(
,
),
0
(
{
1
n
p
p
P
K
=
Найдем вероятности состояний марковского процесса после первого шага
, то есть на момент времени
1
t .
По формуле полной вероятности получим
:







+
+
+
=
+
+
+
=
+
+
+
=
,
)
0
(
)
0
(
)
0
(
)
1
(
;
)
0
(
)
0
(
)
0
(
)
1
(
;
)
0
(
)
0
(
)
0
(
)
1
(
2 2
1 1
2 22 2
12 1
2 1
21 2
11 1
1
nn
n
n
n
n
n
n
n
n
q
p
q
p
q
p
p
q
p
q
p
q
p
p
q
p
q
p
q
p
p
или в
компактной форме
:
)
,
1
(
)
0
(
)
1
(
1
n
j
q
p
p
n
i
ij
i
j
=
=
∑
=

Раздел 5. Численное моделирование
183
Вероятности состояний после второго шага на момент времени
2
t определяются аналогично
:
)
,
1
(
)
1
(
)
2
(
1
n
j
q
p
p
n
i
ij
i
j
=
=
∑
=
После
k- го шага на момент времени
,...)
2
,
1
(
=
k
t
k
вероятности состояний будут определяться как
)
,
1
(
)
1
(
)
(
1
n
j
q
k
p
k
p
n
i
ij
i
j
=
−
=
∑
=
, что и
требовалось доказать
Пример
Рассмотрим систему
, которая состоит из двух устройств
У
1
и
У
2
, каждое из которых может находиться в
одном из двух состояний
:
0
– выключено и
1
– включено
В
определённые моменты времени устройства могут включаться или выключаться
Выделим возможные состояния системы
:
1 1
0 0
1 0
1 0
2 1
3 2
1 0
У
У
i
E
E
E
E
E
Состояние
0
E соответствует простою системы
, когда оба устройства выключены
, а
состояние
3
E соответствует случаю
, когда оба устройства включены
Положим
, что заданы вероятности переходов в
виде матрицы
0 6
,
0 4
,
0 0
5
,
0 0
0 5
,
0 4
,
0 1
,
0 0
5
,
0 3
,
0 5
,
0 2
,
0 0
3 2
1 0
3 2
1 0
E
E
E
E
E
E
E
E
Q
=
и начальные вероятности
0
)
0
(
;
0
)
0
(
;
2
,
0
)
0
(
;
8
,
0
)
0
(
3 2
1 0
=
=
=
=
p
p
p
p
Определим вероятности нахождения системы в
том или ином состоянии на различные моменты времени
Согласно выражению
(5.9) вероятности состояний системы
:
•
на момент времени
1
t
:
1
,
0
)
0
(
)
0
(
)
0
(
)
0
(
)
1
(
30 3
20 2
10 1
00 0
0
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
16
,
0
)
0
(
)
0
(
)
0
(
)
0
(
)
1
(
31 3
21 2
11 1
01 0
1
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
42
,
0
)
0
(
)
0
(
)
0
(
)
0
(
)
1
(
32 3
22 2
12 1
02 0
2
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
32
,
0
)
0
(
)
0
(
)
0
(
)
0
(
)
1
(
33 3
23 2
13 1
03 0
3
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
•
на момент времени
2
t
:
29
,
0
)
1
(
)
1
(
)
1
(
)
1
(
)
2
(
30 3
20 2
10 1
00 0
0
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;

184
Раздел 5. Численное моделирование
148
,
0
)
1
(
)
1
(
)
1
(
)
1
(
)
2
(
31 3
21 2
11 1
01 0
1
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
258
,
0
)
1
(
)
1
(
)
1
(
)
1
(
)
2
(
32 3
22 2
12 1
02 0
2
=
+
+
+
=
q
p
q
p
q
p
q
p
p
;
304
,
0
)
1
(
)
1
(
)
1
(
)
1
(
)
2
(
33 3
23 2
13 1
03 0
3
=
+
+
+
=
q
p
q
p
q
p
q
p
p
Аналогично вероятности состояний системы могут быть рассчитаны на моменты времени
,...
,
4 3
t
t
Нетрудно убедиться
, что сумма вероятностей состояний системы на каждый момент времени равна единице
:
1
)
(
)
(
)
(
)
(
3 2
1 0
=
+
+
+
k
p
k
p
k
p
k
p
для
,
2
,
1
=
k
Матрица вероятностей переходов рассматриваемой системы
– неразложимая и
непериодическая
, следовательно
, случайный процесс обладает эргодическим свойством
, и
вероятности состояний системы для стационарного режима
(
стационарные вероятности
)
3 2
1 0
,
,
,
p
p
p
p
могут быть найдены из системы линейных алгебраических уравнений
(5.10) с
учётом нормировочного условия
(5.11):








=
+
+
+
+
+
=
+
+
+
=
+
+
=
+
+
+
=
+
=
+
+
+
=
+
=
+
+
+
=
1
;
5
,
0 4
,
0 3
,
0
;
6
,
0 1
,
0 5
,
0
;
4
,
0 2
,
0
;
5
,
0 5
,
0 3
2 1
0 2
1 0
33 3
23 2
13 1
03 0
3 3
1 0
32 3
22 2
12 1
02 0
2 3
0 31 3
21 2
11 1
01 0
1 2
1 30 3
20 2
10 1
00 0
0
p
p
p
p
p
p
p
q
p
q
p
q
p
q
p
p
p
p
p
q
p
q
p
q
p
q
p
p
p
p
q
p
q
p
q
p
q
p
p
p
p
q
p
q
p
q
p
q
p
p
Решая систему уравнений, получим значения стационарных вероят- ностей:
236
,
0 55 13 0
≈
=
p
,
164
,
0 55 9
1
≈
=
p
,
309
,
0 55 17 2
≈
=
p
,
291
,
0 55 16 3
≈
=
p
Таким образом, система будет простаивать 23,6% времени, а более
76% времени система будет находиться в рабочем состоянии, причем почти 30% времени (точнее 29,1%) во включённом состоянии будут одновременно находиться оба устройства системы. Среднее число устройств, находящихся одновременно во включённом состоянии, будет равно:
055
,
1 2
3 2
1
=
+
+
=
p
p
p
M
, то есть во включённом состоянии нахо- дится в среднем одно устройство.