|
|
|
содержание .. 18 19 20 21 ..
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* !)!@&’! +($*,#)KH (*L*)&M
5
@!"!
3
C0:
D+-+A.
,7+.
/
4
5.D+
*E$
.
Как
отмечено
выше
,
аналитические
модели
СМО
удается
полу
-
чить
при
довольно
серьезных
допущениях
.
К
числу
типичных
допущений
относятся
следующие
.
Во
-
первых
,
как
правило
,
считают
,
что
в
СМО
используются
бесприоритетные
дисциплины
об
-
служивания
типа
FIFO.
Во
-
вторых
,
времена
обслуживания
заявок
в
устройствах
выбираются
в
соответствии
с
экспонен
-
циальным
законом
распределения
.
В
-
третьих
,
в
аналитических
моделях
СМО
входные
потоки
заявок
аппроксимируются
0"#+&$;
-
>’/’
потоками
,
т
.
е
.
потоками
,
обладающими
свойствами
стационарности
,
ординарности
(
невозмож
-
ности
одновременного
поступления
двух
заявок
на
вход
СМО
),
отсутствия
последействия
.
В
большинстве
случаев
модели
СМО
отображают
процессы
с
конечным
множеством
состояний
и
с
отсутствием
последействия
.
Такие
процессы
называют
%#*$1*./’
/)"%#(+%’/’
=$09/’
.
Марковские
цепи
характеризуются
множеством
состояний
S
,
матрицей
вероятностей
переходов
из
одного
состояния
в
другое
и
начальными
условиями
(
начальным
состоянием
).
Удобно
представлять
марковскую
цепь
в
виде
графа
,
в
котором
вершины
соответствуют
состояниям
цепи
,
дуги
—
перехо
-
дам
,
веса
дуг
—
вероятностям
переходов
(
если
время
дискретно
)
или
интенсивностям
переходов
(
ес
-
ли
время
непрерывно
).
Отметим
,
что
интенсивностью
перехода
называют
величину
V
ij
= lim
P
ij
(
t
1
) /
t
1
при
t
1
→
0,
где
P
ij
(
t
1
) —
веро
-
ятность
перехода
из
состояния
S
i
в
состояние
S
j
за
время
t
1
.
Обычно
принимается
условие
V
ii
= -
∑
V
ij
,
j
≠
i
что
означает
N
∑
V
ij
= 0.
(3.44)
j
=
1
где
N
—
число
состояний
.
На
рис
. 3.
1
7
приведен
пример
марковской
цепи
в
виде
графа
с
состояния
-
ми
S
1
,...,
S
4
,
а
в
табл
. 3.9
представлена
матрица
интенсивностей
переходов
для
этого
примера
.
Большинство
выходных
параметров
СМО
можно
определить
,
используя
информацию
о
поведе
-
нии
СМО
,
т
.
е
.
информацию
о
состояниях
СМО
в
установившихся
(
стационарных
)
режимах
и
об
их
изменениях
в
переходных
процессах
.
Эта
информация
имеет
вероятностную
природу
,
что
обусловли
-
вает
описание
поведения
СМО
в
терминах
вероятностей
нахождения
системы
в
различных
состояни
-
ях
.
Основой
такого
описания
,
а
следовательно
,
и
многих
аналитических
моделей
СМО
являются
7")(
-
*$*’9
O#4/#8#"#()
.
Уравнения
Колмогорова
можно
получить
следующим
образом
.
Изменение
вероятности
P
i
нахождения
системы
в
состоянии
S
i
за
время
t
1
есть
вероятность
пе
-
рехода
системы
в
состояние
S
i
из
любых
других
состояний
за
вычетом
вероятности
перехода
из
состо
-
яния
S
i
в
другие
состояния
за
время
t
1
,
т
.
е
.
P
i
(
t
) =
P
i
(
t
+
t
1
) -
P
i
(
t
) =
∑
P
ji
(
t
1
)
P
j
(
t
) -
∑
P
ik
(
t
1
)
P
i
(
t
),
(3.45)
j
∈
J
k
∈
K
где
P
i
(
t
)
и
P
j
(
t
) —
вероятности
нахождения
системы
в
состояниях
S
i
и
S
j
соответственно
в
момент
вре
-
мени
t
,
а
P
ji
(
t
1
)
и
P
ik
(
t
1
) —
вероятности
изменения
состояний
в
течение
времени
t
1
;
произведение
вида
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
79
Состояние
S
1
S
2
S
3
S
4
S
1
-
V
1
2
-
V
1
3
-
V
1
4
V
1
2
V
1
3
V
1
4
S
2
V
2
1
-
V
2
1
0
0
S
3
0
0
-
V
34
V
34
S
4
0
V
42
0
-
V
42
M:BD+=:
3.9
%+,
.3.
)
7.
Пример
марковской
цепи
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* !)!@&’! +($*,#)KH (*L*)&M
5
@!"!
3
P
ji
(
t
1
)
P
j
(
t
)
есть
безусловная
вероятность
перехода
из
S
j
в
S
i
,
равная
условной
вероятности
перехода
,
ум
-
ноженной
на
вероятность
условия
;
J
и
K
—
множества
индексов
инцидентных
вершин
по
отношению
к
вершине
S
i
по
входящим
и
исходящим
дугам
на
графе
состояний
соответственно
.
Разделив
выражение
(3.45)
на
t
1
и
перейдя
к
пределу
при
t
→
0,
получим
lim
P
i
(t)/
t
1
=
∑
(lim
P
ji
/
t
1
)
P
j
-
∑
(lim
P
ik
/
t
1
)
P
i
,
t
→
0
j
t
→
0
k
t
→
0
откуда
следуют
уравнения
Колмогорова
dP
i
/
dt
=
∑
(
V
ji
P
j
) -
P
i
∑
V
ik
.
j
k
В
стационарном
состоянии
dP
i
/
dt
= 0
и
уравнения
Колмогорова
составляют
систему
алгебраиче
-
ских
уравнений
,
в
которой
i
-
й
узел
представлен
уравнением
∑
(
V
ji
P
j
) =
P
i
∑
V
ik
.
(3.46)
j
k
Прибавляя
V
ii
P
i
к
левой
и
правой
частям
уравнения
(3.46)
и
учитывая
(3.44),
получаем
N
N
∑
(
V
ji
P
j
) =
P
i
∑
V
ik
=0,
j
=
1
k
=
1
т
.
е
.
N
∑
(
V
ji
P
j
) = 0,
j
=
1
где
P
j
—
финальные
вероятности
.
"8+/.8
:0:
D+-+A.
,7
42
/
4
5.D+
.
Примером
СМО
,
к
которой
можно
применить
аналитические
методы
исследования
,
является
одноканальная
СМО
с
простейшим
входным
потоком
интенсивнос
-
тью
λ
и
длительностью
обслуживания
,
подчиняющейся
экспоненциальному
закону
обслуживания
ин
-
тенсивностью
µ
.
Для
этой
СМО
нужно
получить
аналитические
зависимости
среднего
числа
N
av
за
-
явок
,
находящихся
в
системе
,
среднюю
длину
Q
av
очереди
к
ОА
,
время
?
av
пребывания
заявки
в
сис
-
теме
,
время
?
or
ожидания
в
очереди
.
На
рис
. 3.
1
8
представлен
граф
состояний
рассматриваемой
СМО
,
где
S
k
—
состояние
с
k
заявками
в
системе
.
Матрица
интенсивностей
представлена
в
табл
. 3.
1
0.
Уравнения
Колмогорова
для
устано
-
вившегося
режима
имеют
вид
λ
P
0
+
µ
P
1
= 0,
λ
P
0
- (l+
µ
)
P
1
+
µ
P
2
= 0,
µ
P
1
- (l+
µ
)
P
2
+
λ
P
3
= 0,
µ
P
2
- (l+
µ
)
P
3
+
λ
P
4
= 0,
.....
Используя
уравнения
Колмогорова
,
можно
выразить
все
P
W
, i
=
1
,2,3...,
через
P
0
.
Получим
P
1
=
λ
P
0
/
µ
=
aP
0
,
P
2
= ((l+
µ
)
P
1
-
λ
P
0
) /
µ
= (
1
+
a
)
P
1
-
aP
0
=
a
2
P
0
;
P
3
= (
1
+
a
)
P
2
-
aP
1
=
a
2
P
1
=
a
3
P
0
и
т
.
д
.
Здесь
введено
обозначение
)
=
λ
/
µ
.
Отметим
также
,
что
установившийся
режим
возможен
только
при
)
<
1
.
&
.
+
.
)
"#$%!#&’&($"!))$* +($*,#&($"!)&*
80
Состояние
S
0
S
1
S
2
S
3
S
4
...
S
0
-
λ
λ
0
0
0
...
S
1
µ
-
λ
-
µ
λ
0
0
...
S
2
0
µ
-
λ
-
µ
λ
0
...
S
3
0
0
µ
-
λ
-
µ
λ
...
S
4
0
0
0
µ
-
λ
-
µ
...
...
...
...
...
...
...
...
M:BD+=:
3.
)
0
%+,
.3.
)
8.
Граф
состояний
%
!#*%!#&
F
*:,$* $I*:+*
F
*)&* !)!@&’! +($*,#)KH (*L*)&M
5
@!"!
3
∞
Так
как
∑
P
i
=
1
,
то
i
=0
∞
P
0
=
1
-
∑
P
i
=
1
-
P
0
(
a + a
2
+
a
3
+ ...) =
1
/ (
1
+
a + a
2
+
a
3
+...) =
1
-
a
.
i
=0
Теперь
нетрудно
|