1 Антюхов В.И.

2 Тема 3. Теория массового обслуживания Лекция 2: Схема гибели и размножения. Формула Литтла Учебные вопросы: 1.Схема гибели и размножения 2.Формула Литтла

3 Учебный вопрос 1 Схема гибели и размножения

4 Учебный вопрос 1. Схема гибели и размножения Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции Схема гибели и размножения очень часто встречается в разных задачах практики, в частности – в теории массового обслуживания

5 Учебный вопрос 1. Схема гибели и размножения Имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей

6 Учебный вопрос 1. Схема гибели и размножения Для некоторых случаев удается уравнения Колмогорова решить заранее, в буквенном виде В частности, это удается сделать, если граф состояний системы представляет собой так называемую «схему гибели и размножения»

7 Учебный вопрос 1. Схема гибели и размножения Граф состояний для схемы гибели и размножения имеет вид: S0S0 S1S1 S2S2 SkSk S n-1 λ 01 λ 12 λ 23 λ k-1,k λ k,k+1 λ n-1,n λ 10 λ 21 λ 32 λ k,k-1 λ k+1,k λ n,n-1 Рис.1 SnSn

8 Учебный вопрос 1. Схема гибели и размножения Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1, S 2,…, S n-1 ) связано прямой и обратной стрелкой с каждым из соседних состояний – правым и левым, а крайние состояния (S 0, S n ) – только с одним соседним состоянием

9 Учебный вопрос 1. Схема гибели и размножения Предположим, что все потоки событий, переводящие систему по стрелкам графа, представленного выше, простейшие

10 Учебный вопрос 1. Схема гибели и размножения Пользуясь указанным графом, составим и решим алгебраические уравнения для финальных вероятностей состояний (их существование вытекает из того, что из каждого состояния можно перейти в каждое другое, и число состояний конечно) Для первого состояния S 0 имеем: λ 01 p 0 = λ 10 p 1 (1) Для второго состояния S 1 : (λ 12 + λ 10 ) p 1 = λ 01 p 0 + λ 21 p 2

11 Учебный вопрос 1. Схема гибели и размножения В силу (1) последнее равенство приводится к виду: λ 12 p 1 = λ 21 p 2 ; далее совершенно аналогично: λ 23 p 2 = λ 32 p 3 ; и вообще: λ k-1,k p k-1 = λ k,k-1 p k, где k принимает все значения от 0 до n

12 Учебный вопрос 1. Схема гибели и размножения Итак, финальные вероятности p 0, p 1,…, p n удовлетворяют уравнениям: λ 01 p 0 = λ 10 p 1, λ 12 p 1 = λ 21 p 2, …………….. (2) λ k-1,k p k-1 = λ k,k-1 p k, ……………... λ n-1,n p n-1 = λ n,n-1 p n ; кроме того, надо учесть нормировочное условие: p 0 + p 1 + p 2 +…+ p n = 1 (3)

13 Учебный вопрос 1. Схема гибели и размножения Решим эту систему уравнений. Из первого уравнения (2) выразим p 1 через p 0 : p 1 = (λ 01 / λ 10 ) p 0 (4) Из второго уравнения, с учетом (4), получим: p 2 = (λ 12 / λ 21 ) p 1 = [(λ 12 λ 01 ) / (λ 21 λ 10 )] p 0 (5) Из третьего уравнения, с учетом (5), получим: p 3 = [(λ 23 λ 12 λ 01 ) / (λ 32 λ 21 λ 10 )] p 0, (6) и вообще для любого k (от 1 до n): p k = [(λ k-1,k … λ 12 λ 01 ) / (λ k,k-1 …λ 21 λ 10 )] p 0 (7)

14 Учебный вопрос 1. Схема гибели и размножения Обратим внимание на формулу (7): p k = [(λ k-1,k … λ 12 λ 01 ) / (λ k,k-1 …λ 21 λ 10 )] p 0 В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k ), а в знаменателе – произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k )

15 Учебный вопрос 1. Схема гибели и размножения Таким образом, все вероятности состояний p 0, p 1,…, p n выражены через одну из них (p 0 ) Подставим эти выражения в нормировочное условие (3): p 0 + p 1 + p 2 +…+ p n = 1 (3) Получим, вынося за скобку p 0 :

16 Учебный вопрос 1. Схема гибели и размножения Отсюда получим выражение для p 0 :

17 Учебный вопрос 1. Схема гибели и размножения В выражении (8) скобка возведена в степень, чтобы не писать двухэтажных дробей Все остальные вероятности выражены через p 0 (см. формулы (4) – (7)) Заметим, что коэффициенты при p 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8) Значит, вычисляя p 0, мы уже нашли все эти коэффициенты Полученные формулы очень полезны при решении простейших задач теории массового обслуживания

18 Учебный вопрос 2 Формула Литтла

19 Учебный вопрос 2. Формула Литтла Выведем формулу, связывающую (для предельного, стационарного режима): - среднее число заявок L сист, находящихся в системе массового обслуживания (то есть обслуживаемых или стоящих в очереди); - и среднее время пребывания заявки в системе W сист

20 Учебный вопрос 2. Формула Литтла Рассмотрим любую СМО (одноканальную, многоканальную, марковскую, немарковскую, с неограниченной или ограниченной очередью) и связанные с нею два потока событий: - поток заявок, прибывающих в СМО; - поток заявок, покидающих СМО

21 Учебный вопрос 2. Формула Литтла Если в системе установился предельный, стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих её Оба потока имеют одну и ту же интенсивность λ

22 Учебный вопрос 2. Формула Литтла Обозначим: - X(t) – число заявок, прибывших в СМО до момента t; - Y(t) - число заявок, покинувших СМО до момента t И та и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X(t)) и уходов заявок (Y(t))

23 Учебный вопрос 2. Формула Литтла Вид функций X(t) и Y(t) показан на рис. Обе линии – ступенчатые, верхняя - X(t), нижняя - Y(t) X(t) Y(t) T t

24 Учебный вопрос 2. Формула Литтла Очевидно, что для любого момента t их разность Z(t) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО Когда линии X(t) и Y(t) сливаются, в системе нет заявок

25 Учебный вопрос 2. Формула Литтла Рассмотрим очень большой промежуток времени T (мысленно продолжив график далеко за пределы чертежа) и вычислим для него среднее число заявок, находящихся в СМО Оно будет равно интегралу от функции Z(t) на этом промежутке, деленному на длину интервала T:

26 Учебный вопрос 2. Формула Литтла Но этот интеграл представляет собой не что иное, как площадь фигуры, залитой на рис. Разглядим внимательней этот рисунок Фигура на рисунке состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т.д.)

27 Учебный вопрос 2. Формула Литтла Обозначим эти времена t 1, t 2,… Правда, под конец промежутка T некоторые прямоугольники войдут в залитую фигуру не полностью, а частично, но при достаточно большом T эти мелочи не будут играть роли Таким образом, можно считать, что: где сумма распространяется на все заявки, пришедшие за время T

28 Учебный вопрос 2. Формула Литтла Разделим правую и левую часть (10) на длину интервала T Получим, с учетом (9): Разделим и умножим правую часть (11) на интенсивность λ:

29 Учебный вопрос 2. Формула Литтла Но величина Tλ есть не что иное, как среднее число заявок, пришедших за время T Если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист Итак: L сист = λW сист, откуда: W сист = (1 / λ) L сист (12)

30 Учебный вопрос 2. Формула Литтла Это и есть формула Литтла: - для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок

31 Учебный вопрос 2. Формула Литтла Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди W оч и среднее число заявок в очереди L оч : W оч = (1 / λ) L оч (13)

32 Учебный вопрос 2. Формула Литтла Для вывода достаточно вместо нижней линии на рисунке взять функцию U(t) – количество заявок, ушедших до момента t не из системы, а из очереди (если заявка, пришедшая в систему, не становится в очередь, а сразу идет под обслуживание, можно все же считать, что она становится в очередь, но находится в ней нулевое время) Формулы Литтла (12) и (13) играют большую роль в теории массового обслуживания