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

Оглавление

Введение. 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)

Но сумма  в формуле (18) есть не что иное, как  сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и  знаменателем ρ; эта сумма

равна , а ее производная .Подставляя это выражение в (18), получим:

L_сист = .               (19)

Ну, а  теперь применим формулу Литтла и найдем среднее время пребывания заявки в системе:

W_сист =          (20)

Найдем  среднее число заявок в очереди L_оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L_оч равно среднему числу заявок в системе L_сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р_зан). Очевидно, Р_зан равно единице минус вероятность р₀ того, что канал свободен:

Р_зан = 1 - р₀ = ρ.            (21)

Следовательно, среднее число заявок под обслуживанием  равно

L_об = ρ,                  (22)

отсюда

L_оч = L_сист – ρ =

и окончательно

L_оч =              (23)

По формуле  Литтла  найдем среднее время пребывания заявки в очереди:

              (24)

Если  на одноканальную СМО с неограниченной очередью поступает простейший поток  заявок с интенсивностью λ, а время обслуживания имеет произвольное распределение с математическим ожиданием t_об = 1/μ. и коэффициентом вариации v_μ, то среднее число заявок в очереди равно

              (25)

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

           (26)

где, как  и ранее, ρ = λ/μ., a v_μ — отношение среднего квадратического отклонения времени обслуживания к его математическому ожиданию. Формулы (14), (15) носят название формул Полячека — Хинчина.

Деля L_оч, и L_сист на λ, получим, согласно формуле Литтла, среднее время пребывания заявки в очереди и среднее время пребывания в системе:

                 (27)

         (28)

Заметим, что в частном случае, когда  время обслуживания — показательное, v_μ = 1 и формулы (25), (26) превращаются в уже знакомые нам формулы

L_оч =              (23)

L_сист = .                (19),

А формулы (21.3), (21.4) в формулы 

              (24)

W_сист =          (20)

для простейшей одноканальной СМО. Возьмем другой частный случай — когда время  обслуживания вообще не случайно и v_μ = 0. Тогда среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем. Это и естественно: если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании

Заключение.

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

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

1. Алиев  Т.И.  Основы  моделирования  дискретных  систем. – СПб.: СПбГУ ИТМО, 2009.

2. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. - М.: Изд-во МГУ, 1984.