5. Процессы размножения и гибели.

Процессы размножения и гибели являются частным случаем марковских случайных процессов, которые тем не менее находят весьма широкое применение при исследовании дискретных систем со стохастическим характером функционирования. Процесс размножения и гибели представляет собой марковский случайный процесс, в котором переходы из состояния E i допустимы только в соседние состояния E i- 1 , E i и E i+1 . Процесс размножения и гибели является адекватной моделью для описания изменений, происходящих в объеме биологических популяций. Следуя этой модели, говорят, что процесс находится в состоянии E i , если объем популяции равен i членам. При это переход из состояния E i в состояние E i +1 соответствует рождению, а переход из E i в E i-1 - гибели, предполагая, что объем популяции может изменяться не более чем на единицу; это означает, что для процессов размножения и гибели не допускаются многократные одновременные рождения и/или гибели.

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

В случае процесса размножения и гибели с дискретным временем вероятности переходов между состояниями

Здесь d i - вероятность того, что на следующем шаге (в терминах биологической популяции) произойдет одна гибель, уменьшающая объем популяции до i -1 при условии, что на данном шаге объем популяции равен i . Аналогично, b i - вероятность рождения на следующем шаге, приводящего к увеличению объема популяции до i +1; 1-d i -b i представляет собой вероятность того, что ни одно из этих событий не произойдет и на следующем шаге объем популяции не изменится. Допускаются только эти три возможности. Ясно, что d 0 =0, так как гибель не может наступить, если некому погибать.

Однако в противовес интуиции допускается, что b 0 >0, что соответствует возможности рождения, когда в популяции нет ни одного члена. Хотя это можно расценивать как спонтанное рождение или божественное творение, но в теории дискретных систем такая модель представляет собой вполне осмысленное допущение. А именно, модель такова: популяция представляет собой поток требований, находящихся в системе, гибель означает уход требования из системы, а рождение соответствует поступлению в систему нового требования. Ясно, что в такой модели вполне возможно поступление нового требования (рождение) в свободную систему. Матрица вероятностей переходов для общего процесса размножения и гибели имеет следующий вид:

Матрица T содержит нулевые члены только на главной и двух ближайших к ней диагоналях. Из-за такого частного вида матрицы T естественно ожидать, что анализ процесса размножения и гибели не должен вызывать трудностей.

Далее будем рассматривать только непрерывные процессы размножения и гибели, в которых переходы из состояния E i возможны только в соседние состояния E i-1 (гибель) и E i+1 (рождение). Обозначим через l i интенсивность размножения; она описывает скорость, с которой происходит размножение в популяции объема i . Аналогично, через m i обозначим интенсивность гибели, задающую скорость с которой происходит гибель в популяции объема i . Заметим, что введенные интенсивности размножения и гибели не зависят от времени, а зависят только от состояния E i , следовательно, получаем непрерывную однородную цепь Маркова типа размножения и гибели. Эти специальные обозначения введены потому, что они непосредственно приводят к обозначениям, принятым в теории дискретных систем. В зависимости от ранее введенных обозначений имеем:

l i = q i , i +1 и m i = q i , i -1 .

Требование о допустимости переходов только в ближайшие соседние состояния означает, что исходя из (14), q ii =-(m i + l i ). Таким образом, матрица интенсивностей переходов общего однородного процесса размножения и гибели принимает вид

Заметим, что за исключением главной и соседних с ней снизу и сверху диагоналей все элементы матрицы равны нулю. Соответствующий граф интенсивностей переходов представлен на рис. 4.

Более точное определение непрерывного процесса размножения и гибели состоит в следующем: некоторый процесс представляет собой процесс размножения и гибели, если он является однородной цепью Маркова с множеством состояний {E 0 , E 1 , E 2 , …}, если рождение и гибель являются независимыми событиями (это вытекает непосредственно из марковского свойства) и если выполняют следующие условия:

1) Pr [точно 1 рождение в промежутке времени (t ,t + Δt )| объем популяции равен i ]= ;

2) Pr [точно 1 гибель в промежутке времени (t ,t + Δt )| объем популяции равен i ]= ;

3) Pr [точно 0 рождений в промежутке времени (t ,t + Δt )| объем популяции равен i ]= ;

4) Pr [точно 0 гибелей в промежутке времени (t ,t + Δt )| объем популяции равен i ]= .

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

Вероятность того, что непрерывный процесс размножения и гибели в момент времени t находится в состоянии E i (объем популяции равен i ) определяется напрямую из (16) в виде

Для решения полученной системы дифференциальных уравнений в нестационарном случае, когда вероятности P i (t ), i =0,1,2,…, зависят от времени, необходимо задать распределение начальных вероятностей P i (0), i =0,1,2,…, при t =0. Кроме того, должно удовлетворяться нормировочное условие.

Рис.4. Граф интенсивностей переходов для процесса размножения и гибели.

Рассмотрим теперь простейший процесс чистого размножения, который определяется как процесс, для которого m i = 0 при всех i . Кроме того, для еще большего упрощения задачи предположим, что l i =l для всех i =0,1,2,... . Подставляя эти значения в уравнения (18) получим

Для простоты предположим также, что процесс начинается в нулевой момент при нуле членов, то есть:

Отсюда для P 0 (t ) получаем решение

P 0 (t )=e - l t .

Подставляя это решение в уравнение (19) при i = 1, приходим к уравнению

Решение этого дифференциального уравнения, очевидно, имеет вид

P 1 (t )= l te - l t .

Это знакомое нам распределение Пуассона. Таким образом, процесс чистого размножения с постоянной интенсивностью l приводит к последовательности рождений, образующей пуассоновский процесс.

Наибольший интерес в практическом плане представляют вероятности состояний процесса размножения и гибели в установившемся режиме. Предполагая, что процесс обладает эргодическим свойством, т.е. существуют пределы перейдем к определению предельных вероятностей P i .

Уравнения для определения вероятностей стационарного режима можно получить непосредственно из (18), учитывая, что dP i (t )/dt = 0 при :

Полученная система уравнений решается с учетом нормировочного условия

Систему уравнений (21) для установившегося режима процесса размножения и гибели можно составить непосредственно по графу интенсивностей переходов на рис.4, применяя принцип равенства потоков вероятностей к отдельным состоянием процесса. Например, если рассмотреть состояние E i в установившемся режиме, то:

интенсивность потока вероятностей в и

интенсивность потока вероятностей из .

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

Но это как раз и есть первое равенство в системе (21). Аналогично можно получить и второе равенство системы. Те же самые рассуждения о сохранении потока, которые были приведены ранее, могут быть применены к потоку вероятностей через любую замкнутую границу. Например, вместо того, чтобы выделять каждое состояние и составлять для него уравнение, можно выбрать последовательность контуров, первый из которых охватывает состояние E 0 , второй - состояние E 0 и E 1 , и т.д., включая каждый раз в новую границу очередное состояние. Тогда для i -го контура (окружающего состояния E 0 , E 1 , ..., E i -1 ) условие сохранения потока вероятностей можно записать в следующем простом виде:

Полученная система уравнений эквивалентна выведенной ранее. Для составления последней системы уравнений нужно провести вертикальную линию, разделяющую соседние состояния, и приравнять потоки через образовавшуюся границу.

Решение системы (23) можно найти методом математической индукции.

При i =1 имеем:

при i =2:

при i =3:

и т.д.

Вид полученных равенств показывает, что общее решение системы уравнений (23) имеет вид

или, учитывая, что, по определению, произведение по пустому множеству равно единице

Таким образом, все вероятности P i для установившегося режима выражаются через единственную неизвестную константу P 0 . Равенство (22) дает дополнительное условие, позволяющее определить P 0 . Тогда, суммируя по всем i , для P 0 получим:

Обратимся к вопросу о существовании стационарных вероятностей P i . Для того, чтобы полученные выражения задавали вероятности, обычно накладывается требование, чтобы P 0 > 0. Это, очевидно, налагает ограничение на коэффициенты размножения и гибели в соответствующих уравнениях. По существу требуется, чтобы система иногда опустошалась; это условие стабильности представляется весьма резонным, если обратиться к примерам реальной жизни. Определим следующие две суммы:

Все состояния E i рассматриваемого процесса размножения и гибели будут эргодическими тогда и только тогда, когда S 1 < и S 2 = . Только эргодический случай приводит к установившимся вероятностям P i , i = 0, 1, 2, …, и именно этот случай представляет интерес. Заметим, что условия эргодичности выполняются только тогда, когда, начиная с некоторого i , все члены последовательности {} ограничены единицей, т.е. тогда, когда существует некоторое i 0 (и некоторое С <1) такое, что для всех ii 0 выполняется неравенство:

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

Рассмотрим процесс гибели и размножения с непрерывным временем. Такой процесс является моделью изменений в численности популяции.

Процесс находится в состоянии Ей, если объем (численность) популяции равен к; переход в состояние Ек соответствует гибели одного члена популяции, а переход в состояние Ек+ - рождению.

Этот процесс можно рассматривать как модель СМО, в которой Ек соответствует к заявок в системе, а переход в состояние Ек- или Ек+ - уходу заявки из системы или ее приходу.

Для процесса гибели и размножения с множеством состояний 0, 1,2, ... должны выполняться следующие условия:

Здесь P(+i; bt; к) - вероятность i рождений за время bt при условии, что численность популяции равна к ; P(-i; bt; к) - вероятность i гибелей при тех же условиях.

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

Найдем вероятность того, что объем популяции в некоторый момент времени равен к р(к, t) = P.

Рассмотрим изменение объема популяции в промежутке времени (t, t + 5/). В момент времени t + bt процесс будет находиться в состоянии Ек, если произошло одно из трех взаимно исключающих друг друга и образующих полную группу событий:

1) в момент времени t объем популяции равнялся А: и за время bt состояние не изменилось;
2) в момент времени t объем популяции равнялся к - 1 и за время bt родился один член популяции;
3) в момент времени t объем популяции равнялся к + 1 и за время bt погиб один член популяции.

Тогда вероятность того, что в момент времени t + bt процесс будет находиться в состоянии Ек, равна

Приведенное равенство имеет смысл только при к > О, поскольку популяция не может состоять из (-1) члена. Граничное равенство при к = О имеет вид:

Кроме того, должно выполняться условие нормировки

Выделяя в уравнениях (49.3) и (49.5) р(к) и деля на Ьк получим

Переходя к пределу при bt -> 0, имеем:

Таким образом, рассматриваемый вероятностный процесс описывается системой линейных дифференциальных уравнений. Эти уравнения можно получить непосредственно на основе диаграммы состояний (рис. 49.2).

Рис. 49.2.

Состояние Ek обозначается овалом, в котором записывается число к. Переходы между состояниями обозначаются стрелками, на которых представлены интенсивности переходов.

Разность между интенсивностью, с которой система попадает в состояние Ek, и интенсивностью, с которой она покидает его, должна равняться интенсивности изменения потока в этом состоянии.

Интенсивность потока в состояние

Интенсивность потока из состояния ~

Разность между ними равна эффективной интенсивности потока вероятностей в состояние

Решение этой системы в общем виде невозможно. Модель даже простой системы является чрезвычайно сложной и трудно анализируемой. Если рассматривать СМО более сложного вида, то вычислительные трудности будут еще более высокими. Поэтому обычно рассматривают решения системы (49.3) - (49.4) в установившемся режиме при t -> оо, р"(к; t) -> 0,р(к, t) -> р{к) = const.

Процесс чистого размножения

Для этого процесса р*=О, А* = А = const. Его можно рассматривать как модель потока заявок, поступивших в СМО. Система уравнений для этого процесса имеет вид:

Пусть начальные условия следующие:

Тогда и при к= 1 получим: ехр

Решение этого уравнения естьр (; /) = А/ exp (-АД По индукции можно получить, что

Таким образом, вероятности распределены по закону Пуассона.

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

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

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

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

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

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

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

Для первого состояния имеем:

Для второго состояния

В силу (19.1) последнее равенство приводится к виду

где к принимает все значения от 0 до п. Итак, финальные вероятности удовлетворяют уравнениям

кроме того, надо учесть нормировочное условие

Решим эту систему уравнений. Из первого уравнения (19.2) выразим через :

Из второго, с учетом (19.4), получим;

из третьего, с учетом (19.5),

и вообще, для любого к (от 1 до ):

Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния ), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до ).

Таким образом, все вероятности состояний выражены через одну из них Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку

отсюда получим выражение для :

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через (см. формулы (19.4)-(19.7)). Заметим, что коэффициенты при в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя мы уже нашли все эти коэффициенты.

Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.

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

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

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

Обозначим: - число заявок, прибывших в СМО до момента число заявок, покинувших СМО до момента

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

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

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

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

(19.10)

Введение

В данной работе будет рассмотрена схема непрерывных марковских цепей - так называемая "схема гибели и размножения"

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

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

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

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

Процессы размножения и гибели

Процессы размножения и гибели являются частным случаем марковских случайных процессов, которые, тем не менее, находят весьма широкое применение при исследовании дискретных систем со стохастическим характером функционирования. Процесс размножения и гибели представляет собой марковский случайный процесс, в котором переходы из состояния E i допустимы только в соседние состояния E i-1 , E i и E i+1 . Процесс размножения и гибели является адекватной моделью для описания изменений, происходящих в объеме биологических популяций. Следуя этой модели, говорят, что процесс находится в состоянии E i , если объем популяции равен i членам. При этом переход из состояния E i в состояние E i+1 соответствует рождению, а переход из E i в E i-1 - гибели, предполагается, что объем популяции может изменяться не более чем на единицу; это означает, что для процессов размножения и гибели не допускаются многократные одновременные рождения и/или гибели .

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

В случае процесса размножения и гибели с дискретным временем вероятности переходов между состояниями

Здесь d i - вероятность того, что на следующем шаге (в терминах биологической популяции) произойдет одна гибель, уменьшающая объем популяции до при условии, что на данном шаге объем популяции равен i. Аналогично, b i - вероятность рождения на следующем шаге, приводящего к увеличению объема популяции до; представляет собой вероятность того, что ни одно из этих событий не произойдет и на следующем шаге объем популяции не изменится. Допускаются только эти три возможности. Ясно, что, так как гибель не может наступить, если некому погибать .

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

Если цепь Маркова является конечной, то последняя строка матрицы записывается в виде ; это соответствует тому, что не допускаются никакие размножения после того, как популяция достигает максимального объема n. Матрица T содержит нулевые члены только на главной диагонали и двух ближайших к ней диагоналях. Из-за такого частного вида матрицы T естественно ожидать, что анализ процесса размножения и гибели не должен вызывать трудностей . Далее будем рассматривать только непрерывные процессы размножения и гибели, в которых переходы из состояния E i возможны только в соседние состояния E i-1 (гибель) и E i+1 (рождение). Обозначим через i интенсивность размножения; она описывает скорость, с которой происходит размножение в популяции объема i. Аналогично, через i обозначим интенсивность гибели, задающую скорость с которой происходит гибель в популяции объема i. Заметим, что введенные интенсивности размножения и гибели не зависят от времени, а зависят только от состояния E i , следовательно, получаем непрерывную однородную цепь Маркова типа размножения и гибели. Эти специальные обозначения введены потому, что они непосредственно приводят к обозначениям, принятым в теории дискретных систем. В зависимости от ранее введенных обозначений имеем:

i = q i,i+1 и i = q i,i-1 .

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

получим q ii =-(i + i). Таким образом, матрица интенсивностей переходов общего однородного процесса размножения и гибели принимает вид:

Заметим, что за исключением главной диагонали и соседних с ней снизу и сверху диагоналей все элементы матрицы равны нулю. Соответствующий граф интенсивностей переходов представлен на соответствующем рисунке (2.1) :

Рисунок 2.1 - Граф интенсивностей переходов для процесса размножения и гибели

Более точное определение непрерывного процесса размножения и гибели состоит в следующем: некоторый процесс представляет собой процесс размножения и гибели, если он является однородной цепью Маркова с множеством состояний {E 0 , E 1 , E 2 , …}, если рождение и гибель являются независимыми событиями (это вытекает непосредственно из марковского свойства) и если выполняются следующие условия:

(точно 1 рождение в промежутке времени (t,t+Дt), объем популяции равен i) ;

(точно 1 гибель в промежутке времени (t,t+Дt)| объем популяции равен i);

= (точно 0 рождений в промежутке времени (t,t+Дt)| объем популяции равен i);

= (точно 0 гибелей в промежутке времени (t,t+Дt)| объем популяции равен i).

Таким образом, ?t с точностью до есть вероятность рождения новой особи в популяции из n особей, а - вероятность гибели особи в этой популяции за время .

Вероятности перехода удовлетворяют обратным уравнения Колмогорова. Таким образом, вероятность того, что непрерывный процесс размножения и гибели в момент времени t находится в состоянии E i (объем популяции равен i) определяется в виде (2.1):

Для решения полученной системы дифференциальных уравнений в нестационарном случае, когда вероятности P i (t), i=0,1,2,…, зависят от времени, необходимо задать распределение начальных вероятностей P i (0), i=0,1,2,…, при t=0. Кроме того, должно удовлетворяться нормировочное условие.

Рассмотрим теперь простейший процесс чистого размножения, который определяется как процесс, для которого i = 0 при всех i. Кроме того, для еще большего упрощения задачи предположим, что i = для всех i=0,1,2,... . Подставляя эти значения в уравнения (2.1) получим (2.2):

Для простоты предположим также, что процесс начинается в нулевой момент при нуле членов, то есть:

Отсюда для P 0 (t) получаем решение:

Подставляя это решение в уравнение (2.2) при i = 1, приходим к уравнению:

Решение этого дифференциального уравнения, очевидно, имеет вид:

Это знакомое нам распределение Пуассона. Таким образом, процесс чистого размножения с постоянной интенсивностью приводит к последовательности рождений, образующей пуассоновский поток .

перейдем к определению предельных вероятностей P i . Уравнения для определения вероятностей стационарного режима можно получить непосредственно из (2.1), учитывая, что dP i (t)/dt = 0 при:

Полученная система уравнений решается с учетом нормировочного условия (2.4):

Систему уравнений (2.3) для установившегося режима процесса размножения и гибели можно составить непосредственно по графу интенсивностей переходов на рисунке 2.1, применяя принцип равенства потоков вероятностей к отдельным состоянием процесса. Например, если рассмотреть состояние E i в установившемся режиме, то:

интенсивность потока вероятностей в и

интенсивность потока вероятностей из.

В состоянии равновесия эти два потока должны быть равны, и поэтому непосредственно получаем:

Но это как раз и есть первое равенство в системе (2.3). Аналогично можно получить и второе равенство системы. Те же самые рассуждения о сохранении потока, которые были приведены ранее, могут быть применены к потоку вероятностей через любую замкнутую границу. Например, вместо того, чтобы выделять каждое состояние и составлять для него уравнение, можно выбрать последовательность контуров, первый из которых охватывает состояние E 0 , второй - состояние E 0 и E 1 , и так далее, включая каждый раз в новую границу очередное состояние. Тогда для i-го контура (окружающего состояния E 0 , E 1 ,..., E i-1) условие сохранения потока вероятностей можно записать в следующем простом виде:

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

Решение системы (2.5) можно найти методом математической индукции.

При i=1 имеем

Вид полученных равенств показывает, что общее решение системы уравнений (2.5) имеет вид:

или, учитывая, что, по определению, произведение по пустому множеству равно единице:

Таким образом, все вероятности P i для установившегося режима выражаются через единственную неизвестную константу P 0 . Равенство (2.4) дает дополнительное условие, позволяющее определить P 0 . Тогда, суммируя по всем i, для P 0 получим (2.7) :

Обратимся к вопросу о существовании стационарных вероятностей P i . Для того чтобы полученные выражения задавали вероятности, обычно накладывается требование, чтобы P 0 >0. Это, очевидно, налагает ограничение на коэффициенты размножения и гибели в соответствующих уравнениях. По существу требуется, чтобы система иногда опустошалась; это условие стабильности представляется весьма резонным, если обратиться к примерам реальной жизни. Если растут слишком быстро по сравнению с, то может оказаться, что с положительной вероятностью в конечный момент времени t процесс уйдёт из фазового пространства {0,1,…} в "бесконечно удаленную точку?" (особей в популяции станет слишком много). Другими словами процесс станет не регулярным, и тогда равенство (2.4) будет нарушено. Определим следующие две суммы:

Для регулярности процесса размножения и гибели необходимо и достаточно, чтобы S 2 = .

Для существования его стационарного распределения необходимо и достаточно, чтобы S 1 < .

Для того чтобы все состояния E i рассматриваемого процесса размножения и гибели были эргодическими необходимо и достаточно сходимости ряда S 1 < , при этом ряд должен расходиться S 2 = . Только эргодический случай приводит к установившимся вероятностям P i , i = 0, 1, 2, …, и именно этот случай представляет интерес. Заметим, что условия эргодичности выполняются, например, когда, начиная с некоторого i, все члены последовательности {} ограничены единицей, т. е. тогда, когда существует некоторое i 0 (и некоторое С<1) такое, что для всех ii 0 выполняется неравенство:

Этому неравенству можно дать простое толкование: начиная с некоторого состояния E i и для всех последующих состояний интенсивность потока размножения, должна быть меньше интенсивности потока гибели .

Иногда в практике встречаются процессы "чистого" размножения. Процессом "чистого" размножения называется такой процесс гибели и размножения, у которого интенсивность всех потоков гибели равны нулю. Граф состояний такого процесса без ограничения на число состояний показан на рисунке (2.2):

Рисунок 2.2 - Граф интенсивностей переходов для процесса "чистого" размножения

Аналогично вводится понятие "чистой" гибели. Процессом "чистой" гибели называется такой процесс гибели и размножения, у которого интенсивности всех потоков размножения равны нулю. Граф состояний такого процесса без ограничения на число состояний показан на рисунке:

Рисунок 2.3 - Граф интенсивностей переходов для процесса "чистой" гибели

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

В теории массового обслуживания широкое распространение имеет специальный класс случайных процессов – так называемый процесс гибели и размножения. Название этого процесса связано с рядом биологических задач, где он является математической моделью изменения численности биологических популяций.

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 15.4.

Рис. 15.4

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностямиили

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

В соответствии с правилом составления таких уравнений (см. 15.10) получим: для состояния S 0

для состояния S,

Которое с учетом (15.12) приводится к виду

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

(15.14)

к которой добавляется нормировочное условие

Решая систему (15.14), (15.15), можно получить

(15.16)

Легко заметить, что в формулах (15.17) для коэффициенты при есть слагаемые, стоящие после единицы в формуле (15.16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния , а знаменатели – произведение всех интенсивностей,стоящих у стрелок, ведущих справа налево из состояниядо.

15.4. Процесс гибели и размножения представлен графом (рис. 15.5). Найти предельные вероятности состояний.

Рис. 15.5

Решение. По формуле (15.16) найдем

по (15.17) т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии 5(), 17,6% – в состоянии 5, и 11,8% – в состоянии S2.

СМО с отказами

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

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

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

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

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

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

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

Система 5 (СМО) имеет два состояния: 50 – канал свободен, 5, – канал занят. Размеченный граф состояний представлен на рис. 15.6.

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

т.е. система вырождается в одно уравнение. Учитывая нормировочное условие р 0+р х = 1, найдем из (15.18) предельные вероятности состояний

(15.19)

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

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

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

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

Многоканальная система с отказами. Рассмотрим классическую задачу Эрланга.

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

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе):

где– состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 15.7.

Рис. 15.7

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

В формуле (15.16) для схемы гибели и размножения получим для предельной вероятности состояния

(15.23)

где члены разложениябудут представлять собой коэффициенты при р а в вы́ражениях для предельных вероятностейВеличина

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

(15.25)

Формулы (15.25) и (15.26) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.

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

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

(15.28)

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

(15.29)

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

где/;, – предельные вероятности состояний, определяемых но формулам (15.25), (15.26).

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

или, учитывая (15.29), (15.24):

15.6. В условиях задачи 15.5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок нс менее 90 заявок на переговоры.

Решение. Интенсивность нагрузки канала по формуле (15.24) р = 90/30 = 3, т.е. за время среднего (по продолжительности) телефонного разговора 7об = 2 мин поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) п = 2, 3, 4, ... и определим по формулам (15.25–15.29) для получаемой и-канальной СМО характеристики обслуживания. Например, при п = 2 р 0 = = (1 + 3 + 32/2!)“" =0,118 ≈ 0,12; Q = 1 – (з2/2l) – 0,118 = 0,47. А = 90 ∙ 0,47 = 42,3 и т.д. Значения характеристик СМО сведем в табл. 15.1.

Таблица 15.1

По условию оптимальности Q > 0,9, следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае Q = 0,90 – см. табл. 15.1). При этом в час будут обслуживаться в среднем 80 заявок (А = 80,1), а среднее число занятых телефонных номеров (каналов) по формуле (15.30) к = 80,1/30 = 2,67.

15.7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.

Решение. По условию п = 3, λ = 0,25 (1 /ч),^ = 3 (ч). Интенсивность потока обслуживаний μ=1/ίο6 =1/3 = = 0,33. Интенсивность нагрузки ЭВМ по формуле (15.24) р = 0,25/0,33 = 0,75. Найдем предельные вероятности состояний:

по формуле (15.25) р0 = (1 + 0,75 + 0,752/2!+ 0,753/3!) = 0,476;

по формуле (15.26) р, =0,75 0,476 = 0,357; р 2 = (θ,752/2ΐ)χ хО,476 = 0,134; р 3 = (θ,753/3ΐ) 0,476 = 0,033, т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% – имеется одна заявка (занята одна ЭВМ), 13,4% – две заявки (две ЭВМ), 3,3% – три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким образом, Ртк = р 3 = 0,033.

По формуле (15.28) относительная пропускная способность центра <2= 1 – 0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.

По формуле (15.29) абсолютная пропускная способность центра А = 0,25-0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.

По формуле (15.30) среднее число занятых ЭВМ к = = 0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5/3 = 24,2%.

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