Элементы теории случайных процессов и теории массового обслуживания

Естественно, по каждой строке ∑ p_ij = 1, i= 1, 2, …, m.

Обозначим p_ij(n) – вероятностью того, что в результате n шагов система перейдёт из состояния i в состояние j. При этом при i= 1 имеем вероятности перехода, образующие матрицу P₁, т.е.p_ij(1) =p_ij

Необходимо, зная вероятности перехода p_ij, найти p_ij(n) – вероятности перехода системы из состояния I в состояние j за n шагов. С этой целью будем рассматривать промежуточное (между I и j) состояние r, т.е. будем считать, что из первоначального состояния I за k шагов система перейдёт в промежуточное состояние r с вероятностью p_ir(k), после чего за оставшиеся n-k шагов из промежуточного состояния r она перейдёт в конечное состояние j с вероятностью p_rj(n-k). Тогда по формуле полной вероятности:

P_ij(n) = ∑ p_ir (k) p_rj (n-k) – равенство Маркова.

Убедимся в том, что, зная все вероятности перехода p_ij = p_ij(1), т.е. матрицу P₁ перехода из состояния в состояние за один шаг, можно найти вероятность p_ij(2), т.е. матрицу P₂ перехода из состояния в состояние за два шага. А зная матрицу P₂, - найти матрицу P₃ перехода из состояния в состояние за три шага, и т.д.

Действительно, полагая n = 2 в формуле P_ij(n) = ∑ p_ir (k) p_rj (n-k), т.е. k=1 (промежуточное между шагами состояние), получим

P_ij(2) = ∑ p_ir(1)p_rj (2-1) = ∑ p_ir p_rj

Полученное равенство означает, что P₂ =P₁P₁= P²₁

Полагая n = 3, k = 2, аналогично получим P₃ = P₁P₂ = P₁P₁² = P₁³, а в общем случае P_n = P₁ⁿ

Пример

Совокупность семей некоторого региона можно разделить на три  группы:

1. семьи, не имеющие автомобиля и не собирающиеся его покупать;
2. семьи, не имеющие автомобиля, но намеревающиеся его приобрести;
3. семьи, имеющие автомобиль.

Проведённое статистическое обследование показало, что матрица  перехода за интервал в один год  имеет вид:

(В матрице P₁ элемент р₃₁ = 1 означает вероятность того, что семья, имеющая автомобиль, также будет его иметь, а, например, элемент р₂₃ = 0,3 – вероятность того, что семья, не имевшая автомобиля, но решившая его приобрести, осуществит своё намерение в следующем году, и т.д.)

Найти вероятность того, что:

1. семья, не имевшая автомобиля и е собиравшаяся его приобрести, будет находиться в такой же ситуации через два года;
2. семья, не имевшая автомобиля, но намеревающаяся его приобрести, будет иметь автомобиль через два года.

РЕШЕНИЕ: Найдём матрицу перехода Р₂ через два года:

То есть искомые в примере 1) и 2) вероятности равны соответственно

р₁₁ =0,64, р₂₃ =0,51

 

4. Основные понятия теории массового обслуживания

На практике часто приходится сталкиваться с системами, предназначенными для многоразового использования при решении однотипных задач. Возникающие при этом процессы получили название процессов обслуживания, а системы — систем массового обслуживания (СМО). Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, билетные кассы, магазины, парикмахерские и т.п.

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

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

Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, характер потока заявок и т.п.) с показателями эффективности СМО, описывающими ее способность справляться с потоками заявок.

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

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

СМО с ожиданием подразделяются на разные виды в зависимости от того, как организована очередь: с ограниченной или неограниченной длиной очереди, с ограниченным временем ожидания и т.п.

Процесс работы СМО представляет собой случайный  процесс с дискретными состояниями и непрерывным временем. Математический анализ работы СМО существенно упрощается, если процесс этой работы — марковский.

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

 

5. Система массового обслуживания с отказами

 

В качестве показателей эффективности  СМО с отказами будем рассматривать:\

А — абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;

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

P_отк. — вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;

  — среднее число занятых каналов (для многоканальной системы).

Одноканальная система с отказами.

Рассмотрим задачу. Имеется один канал, на который поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ₁. Найти предельные вероятности состояний системы и показатели ее эффективности.

 Система S (СМО) имеет  два состояния: S₀ — канал свободен, S₁ — канал занят. Размеченный граф состояний представлен на рис.

 В предельном, стационарном режиме система алгебраических уравнений для вероятностей состояний имеет вид.

λp₀₌ µp₁

µp₁₌ λp₀

т.е. система вырождается  в одно уравнение. Учитывая нормировочное  условие p₀+p₁=1,найдем из предельные вероятности состояний  

которые выражают среднее  относительное время пребывания системы в состоянии S₀ (когда канал свободен) и S₁ (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа P_отк:

Абсолютную пропускную способность  найдем, умножив относительную пропускную способность Q на интенсивность потока отказов

 

Задача. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью λ, равной 90 заявок в час, а средняя продолжительность разговора по телефону _об.=2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

 Решение. Имеем λ=90 (1/ч), _об.=2 мин. Интенсивность потока обслуживании μ=1/ _об=1/2=0,5 (1/мин)=30 (1/ч). Относительная пропускная способность СМО (Q=30/(90+30)=0,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит Р_отк.=0,75. Абсолютная пропускная способность СМО ,A=90∙0,25=22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.

 Многоканальная система с отказами.

 Рассмотрим классическую задачу Эрланга. Имеется n каналов, на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ. Найти предельные вероятности состояний системы и показатели ее эффективности. Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S₀, S₁, S₂, …, S_k, …, S_n, где S_k — состояние системы, когда в ней находится k заявок, т.е. занято k каналов. Граф состояний СМО соответствует процессу гибели и размножения и показан на рис.

Поток заявок последовательно  переводит систему из любого левого состояния в соседнее правое с  одной и той же интенсивностью λ. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S₂ (два канала заняты), то она может перейти в состояние. S₁ (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2μ. Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S₃ (три канала заняты) в S₂. будет иметь интенсивность Зμ, т.е. может освободиться любой из трех каналов и т.д.

Вероятность отказа СМО есть предельная вероятность того, что  все n каналов системы будут заняты, т.е.

Относительная пропускная способность  — вероятность того, что заявка будет обслужена:

Абсолютная пропускная способность:

Среднее число занятых  каналов  есть математическое ожидание числа занятых каналов:

 

где p_k — предельные вероятности состояний.

Однако среднее число  занятых каналов можно найти  проще, если учесть, что абсолютная пропускная способность системы  А есть не что иное, как интенсивность потока обслуженных системой заявок (в единицу времени). Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени), то среднее число занятых каналов 

Или