Марковские процессы и потоки событий

1. Лекция №5

План.
1.
Марковские процессы и потоки событий.
2.
Системы массового обслуживания (СМО): структура,
классификация, эффективность работы.
3.
Одноканальная СМО с отказами.
4.
Многоканальная СМО с отказами.
5.
Многоканальная СМО с ожиданием и ограничением на
длину очереди.
6.
Одноканальная СМО с ожиданием и ограниченной
очередью.
7.
Многоканальная СМО с ожиданием и неограниченной
очередью.
8.
Одноканальная СМО с ожиданием и неограниченной
очередью
1

2. 1.Марковские процессы и потоки событий.

Теория массового обслуживания в
качестве аппарата использует
понятия теории случайных величин:
= Случайный процесс
• дискретный
• непрерывный
= Марковский случайный процесс
2

3. 1.Марковские процессы и потоки событий.

= Поток
• без последействия
• регулярный
• ординарный
• стационарный
• пуассоновский
= Интенсивность потока
3

4. 1.Марковские процессы и потоки событий.

Теорема. Для простейшего потока событий
с интенсивностью l случайное число
событий x(t)=m (m=1,2,…), наступающих
за промежуток времени t , распределено по
закону Пуассона
m
(λτ) -λτ
p m (τ)=
e
m!
4

5. 2. Системы массового обслуживания(СМО).

Схема структуры СМО
1
2
…………………..
n
5

6. 2. Системы массового обслуживания(СМО).

Основные элементы СМО:
• Входной поток заявок
• Очередь
• Каналы обслуживания
• Выходной поток заявок
6

7. 2. Системы массового обслуживания(СМО).

Классификация СМО
СМО
Организация отбора
заявок
Характер
образования очереди
Разомкнутые
С отказами
Замкнутые
С ожиданием
Наличие ограничений на очередь
Дисциплина
очереди
С ожиданием
Смешанного типа
Количество
каналов
Одноканальные
Многоканальные
Характеристики
каналов
Расположение
каналов
Без приоритета
Однородные
Параллельно
С приоритетом
Неоднородные
Последователь7
но

8. 2. Системы массового обслуживания(СМО).

Классификация СМО (продолжение)
Смешанного типа
Без приоритета
Однородные
Вид ограничения
Правило отбора заявок
Характеристика
приоритета
На длину очереди
На время
пребывания
в очереди
Первый
пришел –
первый
обслужен
Последний
пришел –
первый
обслужен
Случайный
отбор
Абсолютный
приоритет
Относительный
приоритет
Специальные
правила
приоритета
8

9. 2. Системы массового обслуживания(СМО).

Показатели эффективности работы СМО:
• Абсолютная пропускная способность (А);
• Относительная пропускная способность (Q);
• Приведенная интенсивность ( );
•Средняя продолжительность периода
занятости СМО (время обслуживания
заявок);
• Коэффициент использования СМО (время
обслуживания заявок/время работы
системы).
9

10. 2. Системы массового обслуживания(СМО).

Показатели качества обслуживания заявок:
• Среднее время ожидания заявки в очереди (Tline);
• Среднее время пребывания заявки в СМО (Tsys );
• Вероятность отказа заявки в обслуживании без
ожидания;
• Вероятность немедленного приема заявки;
• Закон распределения времени ожидания заявки в
очереди в СМО;
• Среднее число заявок в очереди (Nline);
• Среднее число заявок, находящихся в СМО (Nsys).
10

11. 3. Одноканальная СМО с отказами.

Граф состояний СМО
l
S1
S0
Система уравнений Колмогорова
p = -l p0 (t ) p1 (t ),
'
p1 = p1 (t ) l p0 (t ).
'
0
11

12. 3. Одноканальная СМО с отказами.

Нормировочное условие
p0 p1 = 1
Предельные значения вероятностей
состояния СМО
p0 = /(l );
p1 = l /(l ).
12

13. 3. Одноканальная СМО с отказами.

Основные характеристики работы СМО
Относительная пропускная способность (Q)
Q = /(l )
Абсолютная пропускная способность (A)
A = l /(l ) = lQ
Вероятность отказа в обслуживании заявки, когда канал
занят:
p1 = l /(l )
13

14. 3. Одноканальная СМО с отказами.

Основные характеристики работы СМО
Среднее время обслуживания заявки:
TS = 1/
Среднее время простоя канала:
Tst = 1/ l
Среднее время пребывания заявки в системе:
Tsys = p0Ts = 1/(l ) = TsTst /(Ts Tst )
14

15.

Пример: АТС имеет одну линию, на которую в
среднем приходит 0.8 вызова в минуту. Среднее
время разговора 2 минуты. Вызов, пришедший во
время разговора, не обслуживается. Считая потоки
вызовов пуассоновскими найти абсолютную и
относительную пропускную способности станции,
вероятность отказа абоненту.
Решение:
Интенсивность потока обслуживания
= 1/tобс=1/2=0.5 выз./мин.
Интенсивность потока заявок
l = 0.8 выз./мин.
15

16.

Относительная пропускная способность
Q = p0 = /(l+ ) = 0.5/(0.5+0.8) =0.385
Абсолютная пропускная способность
А = l*Q = 0.8*0.385 = 0.308 выз./мин.
Вероятность отказа в обслуживании
p1 = 1 - p0 = 1- 0.385 = 0.615
16

17.

Пример: Телефонная станция имеет одну линию,
на которую в среднем приходит 0.9 вызова в
минуту. Производительность линии 1.5выз./мин.
Вызов, пришедший во время разговора, не
обслуживается. Считая потоки вызовов
пуассоновскими найти абсолютную пропускную
способности станции, среднее время обслуживания
одного вызова, вероятность отказа в обслуживании,
среднее время пребывания заявки в системе.
Решение:
Интенсивность потока обслуживания
= 1.5 выз./мин.
Интенсивность потока заявок
l = 0.9 выз./мин.
17

18.

Среднее время обслуживания одного вызова
tобс = 1/ =1/1.5=0.67мин.
Абсолютная пропускная способность
А = l * /(l+ )= 0.9*1.5/(0.9+1.5) = 0.563 выз./мин.
Вероятность отказа в обслуживании
p1 = l /(l+ )= 0.9/(0.9+1.5) = 0.375
Время пребывания заявки в системе:
Tsys = 1 / (l ) = 1 / (0.9 1.5) = 0.42 мин.
18

19. 4. Граф состояний многоканальной СМО с отказами

S0
λ
μ
S1
λ
2μ
…
λ
kμ
Sk
λ
(k+1)μ
Sk+1
λ
nμ
…
λ
(n-1)μ
Sn-1
λ
Sn
nμ
19

20. Уравнение Колмогорова для многоканальной СМО

p0' = -l p0 (t ) p1 (t ),
'
pk = l pk -1 (t ) - (l k ) pk (t ) (k 1) pk 1 (t ), k = 1,..., n -1,
pn' = l pn-1 (t ) - n pn (t ).
Нормировочное условие
p0 (t ) p1 (t ) ... pn (t ) = 1
20

21. Предельные вероятности системы

pk = lim pk (t ), p = 0, k = 1,..., n
t
'
k
Предельный режим работы СМО
l p0 p1 = 0,
l pk 1 (l k ) pk (k 1) pk 1 = 0, k = 2,..., n 1,
l pn 1 n p0 = 0.
21

22.

Уравнение нормировки в стационарном
виде
p0 p1 ... pn = 1
Приведенная интенсивность входящего
потока (измеряется в эрлангах):
l
=
22

23.

Решение системы уравнений:
po =
1
n
( / i !)
,
i
i =0
p0
pk =
, k = 1,..., n
k!
k
Формулы
Эрланга
23

24.

Основные характеристики СМО
Отказ в обслуживании заявки
p0
pr = pn =
n!
n
Вероятность обслуживания заявки
ps = 1 pr = 1 pn
Относительная пропускная способность
Q = ps
Абсолютная пропускная способность
A = λQ = λ(1- pn)
24

25.

Среднее число занятых каналов
l (1 pn )
K = N sys = = (1 pn ) =
A
Среднее время пребывания заявки в СМО
T sys =
N sys
l
25

26.

Пример: в отделении банка на обслуживании клиентов
работают 3 оператора. Среднее время обслуживания
одного клиента оператором – 12 минут. В среднем за час
в банк обращаются 15 клиентов. Если все операторы
заняты, клиенты банком не обслуживаются.
I. Найти основные средние характеристики работы
отделения банка, а также вероятность того, что не менее
двух операторов простаивают.
II. Рассчитать, как изменятся характеристики работы
СМО, если операторы будут тратить на обслуживание
клиентов 10 минут.
III. Определить минимальную среднюю
производительность операторов, чтобы вероятность
обслуживания клиентов банка была бы не ниже 0,9
26

27.

Решение:
I. Число каналов: n=3
Интенсивность входного потока заявок: λ = 15
клиентов/час
Интенсивность одного канала обслуживания μ =1/tобс=
1/(12/60) = 5 клиентов/час
Тогда приведенная интенсивность: ρ = λ/ μ =15/5=3
Вероятность простоя системы:
p0 = 1/(1+3+3^2/2+3^3/6) = 0,077
Вероятность отказа:
pr = p3 = p0*3^3/6 = 0,346
Относительная пропускная способность:
Q = pS = 1 – pr = 1- 0,346 = 0,654
Абсолютная пропускная способность:
A = λ*Q= 9,81 клиент/час
Среднее число занятых каналов Ňsys= A/μ = 1,962
Среднее время пребывания заявки в СМО
27
Tsys = Nsys/ λ = 0,131 ч = 7,85 мин.

28.

Вероятность того, что не менее 2 операторов
простаивают: p0 + p1 = 0,077*(1+3) = 0,308
II. Интенсивность одного канала обслуживания μ = 6
клиентов/час
Тогда ρ = λ/ μ =15/6=2,5
p0= 1/(1+2,5+2,5^2/2+2,5^3/6) = 0,108
pr= p3 = p0*2,5^3/6 = 0,28
Q = p3 = 1 – pr = 1- 0,28 = 0,72
A = λ*Q= 10,8 клиент/час
Среднее число занятых каналов Ňsys= A/μ = 1,8
Среднее время пребывания заявки в СМО
Tsys = Nsys/ λ = 0,12 ч = 7,2 мин.
28

29.

III. Из условия следует 1- pn >=0,9 pn<=0,1
Путем подбора определяем:
μ
p0
pr
pS
5
6
7
8
9
10
11
12
0,077 0,108 0,141 0,174 0,207 0,239 0,269 0,298
0,346 0,282 0,232 0,192 0,160 0,134 0,114 0,097
0,654 0,718 0,768 0,808 0,840 0,866 0,886 0,903
Ответ: μ >= 12
29

30. Граф состояний n-канальной СМО с ограничением на длину очереди m

5. Многоканальная СМО с ожиданием и ограничением
на длину очереди
Граф состояний n-канальной СМО с ограничением
на длину очереди m
Очереди нет
S0
λ
μ
S1
λ
2μ
…
Очередь есть
λ
kμ
Sn
λ
nμ
Sn+1
λ
nμ
…
λ
nμ
Sn+r
λ
Sn+m
nμ
30

31. Основные соотношения

Уравнения Колмогорова для многоканальной СМО с
ожиданием и ограничением на длину очереди
l p0 p1 = 0,
l pk 1 (l k ) pk (k 1) pk 1 = 0,
l pn 1 (l n ) pn n pn 1 = 0,
l pn k 1 (l n ) pn k n pn k 1 = 0, k = 1,..., m 1,
l pn m 1 n pn m = 0.
31

32. Нормировочное условие:

n m
p =1
k =0
k
Показатель нагрузки на один канал
l
= =
n n
32

33. Решение системы уравнений:

n k n
k
p0 =
n ! k = n 1
k =0 k !
n n m
k
n
1
Упрощенная формула:
n
n (1 )
k
, 1;
n ! (1 )
k =0 k !
p0 =
1
k
n
n
n n
k ! n ! m , = 1.
k =0
n
k
n
n 1
m
1
33

34. Остальные предельные вероятности:

(n k / k !) k p0 , k = 1, 2,..., n;
pk = n
k
(n / n !) p0 , k = n 1,..., n m
34

35. Основные характеристики СМО

Вероятность отказа:
pr = pn m = n / n !)
n
n m
p0
Вероятность приема заявки:
psys = Q = 1 pr = 1 n / n !)
n
n m
p0
Абсолютная пропускная способность:
n
n m
A = lQ = l 1 n / n !) p0
35

36.

Среднее
число занятых каналов
_
_
n
n m
N s = K = A / = Q = 1 n / n !)
p0
Среднее число заявок в очереди
m
n
n 1 1 ( m 1 m )
p0 , 1;
n / n !)
2
_
(1 )
N line =
n
n
m(m 1) p = 1.
0,
n !
2
Среднее число заявок, находящихся в системе
_
_
_
N sys = N line N s
36

37.

Среднее
_ время_ обслуживания заявки
T s = N s/ l
Среднее время ожидания заявки в очереди
_
_
T line = N line / l
Среднее время пребывания заявки в СМО
T sys = T s T line = ( N s N line ) / l = N sys / l
_
_
_
_
_
_
37

38.

Пример. В пункте валютного обмена работают два
оператора, каждый из которых обслуживает клиента
в среднем за 2,5 минуты. По условиям безопасности
в
помещении
пункта
может
находиться
одновременно не более 5 человек, включая
обслуживаемых
клиентов.
Если
помещение
заполнено, то очередной клиент не становится в
очередь, а уходит. В среднем клиенты приходят
каждые 2 минуты. Найти основные характеристики
работы обменного пункта.
38

39.

Решение:
Число каналов: n= 2
Длина очереди m =3
Интенсивность входного потока заявок: λ = 0,5
клиент/мин.
Интенсивность потока обслуживания μ = 1/2.5 = 0,4
клиент/мин.
Нагрузка СМО ρ = λ/ μ = 0,5/0,4 = 1,25
Нагрузка на один канал Ψ = ρ/n = 1,25/2 = 0,625
Вероятность простоя СМО
p0= [1+(2/1!)*0,625+ (2^2/2!)*0,625^2+(2^2/2!)*0,625^3*(1
- 0,625^3)/(1-0,625)] ^(-1)= 0,249
Вероятность отказа
pr = p5 = (2^2/2!)* 0,625^(2+3)*0,249 = 0,048
Относительная пропускная способность
Q = 1 - 0,048= 0,952
39

40.

Абсолютная пропускная способность
A= λ*Q= 0,5*0,952= 0,476 клиент/мин.
Среднее
число занятых операторов
_
N s = A / = * Q = 1, 25*0,953 = 1,191
Среднее число клиентов в очереди:
N line = 22 / 2!) *0,6253 * 1 0,6253 *(3 1 3*0,625) */(1 0,625)2 *0,249 = 0,416
_
Среднее число клиентов в системе:
_
_
_
N sys = N line N s = 0, 416 1,191 = 1, 607
40

41.

Среднее время обслуживания клиента:
_
T s = N s / l = 1,191/ 0,5 = 2,381 мин.
Среднее время пребывания клиента в очереди:
_
_
T line = N line / l = 0, 416 / 0,5 = 0,832 мин.
= 832*60 /1000 50 сек.
Среднее время пребывания клиента в пункте обмена:
_
_
_
T sys = T s T line = 2,381 0,832 = 3, 213 мин.
41

42. 6.Одноканальная СМО с ожиданием и ограниченной очередью.

n=1 ψ = ρ
m 1 k 1
1
, 1;
=
m 2
1
k =0
p0 =
1
m 1
1
k
= m 2 , = 1.
k =0
Вероятность отказа в обслуживании
pr = pm 1 =
m 1
)p
0
Вероятность принятия заявки
psys = 1 pr = 1
m 1
* p0
42

43.

Предельные вероятности состояний:
pm 1 = ) p0
при = 1 p0 = p1 = p2 = ... pm
m 1
Относительная пропускная способность:
Q = 1 pr = 1 pm 1 = 1
m 1
)p
0
Абсолютная пропускная способность:
A = lQ = l 1 pr
Среднее число заявок в очереди:
_
N line = 1* p2 2* p3 ... m * pm 1
43

44.

Среднее число заявок в очереди:
1 *(m m * 1)
N line = *
* p0 , 1
2
(1 )
_
m *(m 1)
N line =
, =1
2(m 2)
_
m
2
Среднее время ожидания в очереди:
_
_
T line = N line / l
Среднее время пребывания в системе:
_
_
T sys = T line
44

45. 7. Многоканальная СМО с ожиданием и неограниченной очередью

Решение системы уравнений:
1
n k n
p0 = *
;
n ! 1
k =0 k !
(n k / k !) * k p0 , k = 1, 2,..., n;
pk = n
k
(
n
/
k
!)
*
p0 , k = n 1, n 2,...
Нормировочное условие:
n
k
n
n 1
p =1
k =0
k
45

46.

Вероятность отказа:
pr = 0
Вероятность принятия заявки:
Q = psys = 1
Абсолютная пропускная способность:
A=l
Среднее число занятых каналов:
_
_
Ns = K = A/ =
n 1
Среднее число заявок _
n
N line = n / n !) *
p0
2
в очереди:
(1 )
46

47.

Среднее время ожидания в очереди:
_
_
N line
T оч =
l
Среднее число заявок, находящихся в системе:
_
_
_
_
N sys = N line N s = N line
Среднее время пребывания заявок в системе:
_
_
T sys =
N sys
l
47

48.

Пример. В кассе метрополитена, продающей карточки на
проезд, работают два окна. В среднем один кассир тратит
на обслуживание одного пассажира 0,5 минуты. В среднем
к кассе подходит 3 чел./мин.
Найти основные характеристики работы кассы.
48

49.

Решение:
Двухканальная СМО с ожиданием и без ограничения на
длину очереди.
Число каналов: n= 2
Интенсивность входного потока заявок: λ = 3 чел./мин.
Интенсивность потока обслуживания μ = 2 чел./мин.
Нагрузка СМО ρ = λ / μ = 3/2 = 1,5
Нагрузка на один канал Ψ = ρ/n = 1,5/2 = 0,75
Вероятность простоя СМО (оба кассира свободны):
p0=1/ [1+(2/1!)*0,75+ (2^2/2!)*0,75^2+(2^2/2!)*0,75^3/(10,75)]= 0,143
Вероятность отказа
pr = 0
Относительная пропускная способность
Q=1
49

50.

Среднее число
занятых кассиров:
_
N s = A / = = 1,5
Среднее число пассажиров в очереди:
3
0,75
N line = 22 / 2!) *
0,143 = 1,931
2
(1 0,75)
Среднее число пассажиров у касс:
N sys = N line N s = 1,931 1,5 = 3, 431
Среднее время пребывания пассажиров в очереди:
T line = N line / l = 1,931/ 3 = 0, 644 мин.
Среднее время затрачиваемое пассажиром на
покупку карточки:
T sys = N sys / l = 3, 431/ 3 = 1,144 мин.
50

51. Граф состояний одноканальной СМО с неограниченной очередью

8.Одноканальная СМО с ожиданием и неограниченной
очередью
Граф состояний одноканальной СМО с
неограниченной очередью
Очереди нет
S0
λ
μ
S1
Очередь любой длины
λ
μ
S2
λ
μ
…
λ
μ
Sk
λ
…
μ
51

52.

Приведенная интенсивность нагрузки СМО:
при l <
= l /
Вероятность обслуживания: pобс = 1
Вероятность отказа: pотк = 0
Вероятность простоя системы: p0 = 1 -
Вероятность занятости системы: p1 = 1 – p0
Вероятность пребывания в очереди k заявок:
pk = k(1- )
52

53.

Относительная пропускная способность :
Q = pобс = 1
Абсолютная пропускная способность:
A = l *Q = l
Среднее число обслуженных заявок:
Lоб =
Среднее число заявок в очереди:
Lоч =
2
1
Среднее число заявок в системе:
LСМО = Lоч + Lоб
53

54.

Пример. В магазине работает только один продавец.
Интенсивность обслуживания составляет 25 чел./час.
Простейший поток покупателей поступает с
интенсивностью 20 чел./час.
Найти основные характеристики работы СМО.
54

55.

Интенсивность входного потока:
l = 20 чел./час
Интенсивность потока обслуживания:
= 25 чел./час.
Приведенная интенсивность нагрузки СМО:
при l <
= l / = 20/25 = 0,8
Вероятность обслуживания: pобс = 1
Вероятность отказа: pотк = 0
55

56.

Вероятность простоя продавца: p0 = 1 - =
1 – 0,8 = 0,2
Вероятность занятости продавца: p1 = 1 – p0
= 1- 0,2 = 0,8
Вероятность пребывания в очереди k заявок:
pk = k(1- )
Вероятность пребывания в очереди 3 человек:
p3 = 3(1- ) = 0,83(1 - 0,8 ) = 0,102
56

57.

Относительная пропускная способность :
Q = pобс = 1
Абсолютная пропускная способность:
A = l *Q = l = 20 чел./час
Среднее число обслуженных покупателей:
Lоб = = 0,8
Среднее число покупателей в очереди:
2
0.82
Lоч =
=
= 3.2 чел.
1 1 0.8
Среднее число покупателей в магазине:
LСМО = Lоч + Lоб = 3.2 + 0.8 = 4
57

58.

Среднее время ожидания в очереди:
Lоч
3.2
Tоч =
=
= 0.16 час.
l
20
Среднее время пребывания покупателей в магазине:
TСМО = Tоч + Tобс = 0,16+ 1/25 = 0.2 час. = 12 мин.
58