Уравнения Колмогорова, процесс "размножения и гибели", формулы Полячека-Хинчика и Литтла

Оглавление

Введение. 2

1. Уравнения Колмогорова для вероятностных состояний. 3

2. Процесс «размножения и гибели». 4

3. Формулы Полячека — Хинчина и Литтла. 6

Заключение. 10

Список использованной литературы: 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

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

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

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

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

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

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

1. Уравнения Колмогорова для вероятностных состояний.

Если  известны вероятности перехода λ_ij для всех пар состояний Si и Sj, то, построив граф состояний системы S, удобно против каждой дуги графа ставить соответствующее значение λ_ij. Получится размеченный граф состояний (рис.1). Имея в распоряжении размеченный граф состояний системы, легко построить математическую модель данного процесса, а по модели определить вероятности состояний p_i(t). Для этого составляются и решаются так называемые уравнения Колмогорова. Методика их составления может быть легко продемонстрирована на конкретном примере.

Рис.1

Пусть система  S имеет четыре возможных состояния: S1, S2, S3, S4 (рис.1). Как найти одну из вероятностей состояний, например, p1(t), т.е. какова вероятность того, что в момент t система будет в состоянии S1. Для этого времени t дается малое приращение t+Δt и находится вероятность p1(t+Δt) того, что в момент t+Δt система будет в состоянии S1. Это может произойти двумя способами (в соответствии с рис.1):

1. если в момент t система была в состоянии S1, то за Δt она не вышла из него;
2. если в момент t система была в состоянии S2, то за Δt она перешла из S2 в S1.

Для первого  случая искомая вероятность равна  произведению вероятности p1(t) на условную вероятность того, что из состояния S1 система за время Δt не перейдет ни в S2, ни в S3. Вероятность того, что за Δt система выйдет из состояния S1 равна (λ₁₂+λ₁₃)Δt, а вероятность того, что не выйдет: 1-(λ₁₂+λ₁₃)Δt. Тогда для первого случая вероятность равна p1(t)(1-(λ₁₂+λ₁₃)Δt).

Для второго  случая – равна вероятности того, что в момент времени t система была в S2, а за Δt перешла в S1, т.е. она равна p2(t)λ₂₁Δt. По правилу сложения вероятность

p1(t+Δt) = p1(t)(1-(λ₁₂+λ₁₃)Δt) + p2(t)λ₂₁Δt .

Перенося p1(t) в левую часть полученного уравнения и деля обе части его на Δt, можно записать:

(p1(t+Δt) - p1(t)) / Δt = λ₂₁p2(t) - (λ₁₂+λ₁₃)p1(t) .

Далее, переходя к пределу, получают дифференциальное уравнение:

dp1/dt = λ₂₁p2 - (λ₁₂+λ₁₃)p1 .  (1)

Подобным  образом можно привести еще одно уравнение для вероятности состояния p2(t). Для этого рассматривают состояние S2 и находят p2(t+Δt), учитывая, что в S2 система могла перейти одним из следующих способов:

1. в момент t система была в состоянии S2 и за Δt не перешла из этого состояния ни в S1, ни в S4;
2. в момент t система была в состоянии S1 и за Δt она перешла в S2;
3. в момент t система была в состоянии S3 и за Δt перешла в S2.

Вероятность первого варианта: p2(t)(1-(λ₂₁+λ₂₄)Δt); вероятность второго варианта: p1(t)λ₁₂Δt; третьего варианта: p3(t)λ₃₂Δt. Складывая полученные варианты и приравнивая их p2(t+Δt), получают:

p2(t+Δt) = p2(t)(1-(λ₂₁+λ₂₄)Δt) + p1(t)λ₁₂Δt + p3(t)λ₃₂Δt .

Переходя  к дифференциальному уравнению, можно записать:

dp2/dt = λ₁₂p1 + λ₃₂p3 - (λ₂₁+λ₂₄)p2 .  (2)

Получая по изложенной методике уравнения для  состояний S3 и S4 и присоединяя к  ним уравнения (1) и (2), можно записать системы дифференциальных уравнений  для вероятностей состояний:

dp1/dt = λ₂₁p2 - (λ₁₂+λ₁₃)p1

dp2/dt = λ₁₂p1 + λ₃₂p3 - (λ₂₁+λ₂₄)p2

dp3/dt = λ₁₂p1 + λ₄₃p4 – λ₃₂p3

dp4/dt = λ₂₄p2 – λ₄₃p4

Эти уравнения  называются уравнениями Колмогорова. Это система четырех линейных дифференциальных уравнений с четырьмя неизвестными функциями р1, р2, р3, р4. Начальные условия задаются в зависимости от того, каково было начальное состояние системы S. Например, если в начальный момент времени (при t=0) система была в состоянии Si, то pi(0) = 1, а все остальные вероятности равны нулю. Так, например, данную систему уравнений можно решать при начальных условиях: р1(0)=1, р2(0)=р3(0)=р4(0)=0.

Нужно отметить, что все четыре уравнения системы  можно не записывать, так как можно  воспользоваться условием р1+р2+р3+р4 = 1. Поэтому любую из вероятностей можно выразить через остальные и получить систему трех уравнений.

Анализируя  систему уравнений, можно вывести  общее правило формирования таких  уравнений непосредственно по размеченному графу состояний, пригодное для  любой непрерывной марковской цепи. В левой части каждого уравнения находится производная вероятности состояния, а правая часть содержит столько слагаемых, сколько стрелок связано с данным состоянием. Если стрелка направлена из состояния, соответствующее слагаемое имеет знак «минус», если в состояние – «плюс». Каждое слагаемое равно произведению плотности вероятности перехода, соответствующей данной стрелке, умноженной на вероятность того состояния, из которого исходит стрелка.

2. Процесс «размножения и гибели».

На практике часто встречаются ситуации, когда  некоторые случайные процессы, относящиеся, например, к различным областям знаний, имеют одинаковые графы состояний. Тогда, если рассматриваемые процессы являются непрерывными цепями Маркова и имеют одинаковые графы состояний, можно найти аналитические выражения для предельных вероятностей состояний типовых процессов в общем виде, а затем подставить вместо λ_ij соответствующие значения.

Пусть некоторый  марковский случайный процесс, протекающий в системе S, может быть представлен графом состояний, как на рис. 2, т.е. все состояния можно вытянуть в одну цепочку, в которой каждое из средних состояний (S₁,…, S_n-1) связано прямой и обратной связью с каждым из соседних состояний, а крайние состояния (S₀ и S_n) — только с одним соседним состоянием.

Рис. 2. Граф процесса «размножения и гибели»

Процессы  такого рода описывают, в частности, процесс изменения численности  биологической популяции, что и  послужило основанием для появления  термина — процесс «размножения и гибели».

Схема «размножения и гибели» встречается во многих практических задачах, поэтому целесообразно  определить аналитические выражения  предельных вероятностей состояний  системы, граф которой приведен на рис. 2, и в дальнейшем пользоваться готовыми формулами.

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

Для состояния  S₀ получаем:

 (3)

а для  состояния S₁:

  (4)

Учитывая (3), из выражения (4) получают для состояния S₁:

 (5)

а далее аналогично:

- для  S₂

  (6)

- для  S_k-1

 (7)

- для  S_n-1

  (8)

Запишем нормировочное условие:

  (9)

Итак, получена система уравнений (3), (4), ... , (8) и нормировочное  условие (9). Уравнение (3) решается относительно р₁:

  (10)

из уравнения (5) с учетом (10) находится р₂:

  (11)

из (6) с  учетом (11) получают р₃:

и т. д., для  любого k:

   (12)

Структура формулы (12) следующая. В числителе  находится произведение всех λ_ij , стоящих у стрелок, направленных слева направо, от S₀ и до той, которая идет в S_k , а в знаменателе - произведение всех λ_ij, идущих в обратном направлении - справа налево от S_k до S₀.

Если  все р_i (кроме случая, когда i=0) подставить в выражение (9), то можно получить р₀:

(13)

Формулы (12), (13) дают общее решение задачи «размножения и гибели».

3. Формулы Полячека — Хинчина и Литтла.

Требуется найти финальные вероятности  состояний СМО, а также характеристики ее эффективности:

L_сист. — среднее число заявок в системе,

W_сист.— среднее время пребывания заявки в системе,

L_оч — среднее число заявок в очереди,

W_оч — среднее время пребывания заявки в очереди,

Получим выражение для р₀:

p₀ = [1 + λ/μ + (λ/μ)² + ... + (λ/μ)^k +.. ]^-1 = (1 + р + р² + ... + р^k +… .)^-1.(14)

Ряд в  формуле (14) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р₀, p₁, ..., p_k, ... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (22), имеем

1 + ρ + ρ² + ... + ρ^k + ... = ,

откуда

p₀ = 1 - ρ.                 (15)

Вероятности р₁, р₂, ..., р_k, ... найдутся по формулам:

p₁ = ρp₀,   p₂ = ρ²p₀ ,…,p_k = ρp₀, ...,

откуда, с учетом (15), найдем окончательно:

p₁ = ρ (1 - ρ),   p₂ = ρ² (1 - ρ), . . . , p_k = ρ^k (1 - ρ), . . .(16)

Как видно, вероятности p₀, p₁, ..., p_k, ... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р₀ — вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.

Найдем  среднее число заявок в СМО L_сист.. Тут придется немного повозиться. Случайная величина Z — число заявок в системе — имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p₀, р₁, р₂, ..., p_k, ... Ее математическое ожидание равно

L_сист = 0 · p₀ +1 · p₁ + 2 · p₂ +…+k · p_k +…= (17)

(сумма  берется не от 0 до ∞, а от 1 до ∞, так как нулевой член  равен нулю).

Подставим в формулу (17) выражение для p_k (16):

L_сист. =

Теперь вынесем за знак суммы  ρ (1-ρ):

L_сист. = ρ (1-ρ)

Тут мы опять  применим «маленькую хитрость»: kρ^k-1 есть не что иное, как производная по ρ от выражения ρ^k; значит,

L_сист. = ρ (1-ρ)

Меняя местами  операции дифференцирования п суммирования, получим:

L_сист. = ρ (1-ρ)             (18)