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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 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%.

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

Введение

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

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

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

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

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

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

Процессы размножения и гибели являются частным случаем марковских случайных процессов, которые, тем не менее, находят весьма широкое применение при исследовании дискретных систем со стохастическим характером функционирования. Процесс размножения и гибели представляет собой марковский случайный процесс, в котором переходы из состояния 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), в которой нужно положить все интенсивности потоков процессов гибели равными нулю: .

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

Название схемы взято из биологических задач, где состояние популяции означает наличие в ней особей.

На рис.4 переход вправо соответствует увеличению популяции, влево - ее уменьшению. Таким образом, можно определить как интенсивности размножения, а - как интенсивности гибели. Используется следующее соглашение: буквам и приписывается индекс того состояния, из которого выходит стрелка.

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

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

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

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

Интенсивность поступления автомобилей на предприятие равна. Каждый поступивший на предприятие автомобиль списывается через случайное время. Срок службы автомобиля распределен по показательному закону с параметром. Процесс эксплуатации автомобилей является случайным процессом. - число автомобилей данной марки, находящихся в эксплуатации в момент времени.

Рассмотрим два случая: 1) нет ограничений на число эксплуатируемых автомобилей, 2) на предприятии может эксплуатироваться не более автомобилей.

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

Аналогично, если при эксплуатировалось автомобилей, то начальные условия имеют вид:

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

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

1. Максимальное число автомобилей не ограничено:

2. Математическое ожидание (среднее значение) числа эксплуатируемых автомобилей.

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

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

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

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

Для процесса гибели и размножения с множеством состояний 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 (-АД По индукции можно получить, что

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

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

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

Рис. 29

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

Марковская непрерывная цепь называется «процессом гибели и размножения», если ее граф состояний имеет вид, представленный на рис.29, т. е. все состояния можно вытянуть в одну цепочку, в кото­рой каждое из средних состояний (S 2 , ..., S n –1) связано прямой и об­ратной связью с каждым из соседних состояний, а крайние состояния (S 1 , S n) – только с одним соседним состоянием.

Пример 1. Техническое устройство состоит из трех одинаковых узлов; каждый из них может выходить из строя (отказывать); отказавший узел немедленно начинает восстанавливаться. Состояния систе­мы нумеруем по числу неисправных узлов:

S 0 – все три узла исправны;

S 1 – один узел отказал (восстанавливается), два исправны;

S 2 – два узла восстанавливаются, один исправен;

S 3 – все три узла восстанавливаются.

Граф состояний показан на рис.30. Из графа видно, что про­цесс, протекающий в системе, представляет собой процесс «гибели и размножения».

Рис. 30

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

Итак, рассмотрим случайный процесс гибели и размножения с гра­фом состояний, представленным на рис.31

Рис. 31

Напишем алгебраические уравнения для вероятностей состояний. Для первого состояния S 1 имеем:

λ 12 p 1 = λ 21 p 2 (7.1)

Для второго состояния S 2 суммы членов, соответствующих входя­щим и выходящим стрелкам, равны:

λ 23 p 2 + λ 21 p 2 = λ 32 p 3 + λ 12 p 1

Но, в силу (7.1), можно сократить справа и слева равные друг дру­гу члены и; получим:

λ 23 p 2 = λ 32 p 3

λ 34 p 3 = λ 43 p 4

. . . . . . . . .

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

λ k -1,k p k -1 = λ k,k -1 p k (7.2)

где k принимает все значения от 2 до n.

Итак, предельные вероятности состояний р 1 , р 2 , ..., р n в любой схеме гибели и размножения удовлетворяют уравнениям:

λ 12 p 1 = λ 21 p 2

λ 23 p 2 = λ 32 p 3

λ 34 p 3 = λ 43 p 4

. . . . . . . . . . . (7.3)

λ k -1,k p k -1 = λ k,k -1 p k

. . . . . . . . . . .

λ n -1, n p n -1 = λ n , n -1 p n

и нормировочному условию:

р 1 + р 2 + ... + р n = l (7.4)

Будем решать эту систему следующим образом: из первого урав­нения (7.3) выразим р 2:

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

(7.6)

Из третьего, с учетом (7.6):

(7.7)

Эта формула справедлива для любого k от 2 до n .

Обратим внимание на ее структуру. В числителе стоит произведе­ние всех плотностей вероятности перехода (интенсивностей) λ ij , стоя­щих у стрелок, направленных слева направо, с начала и вплоть до той, которая идет в состояние Sk ; в знаменателе – произве­дение всех интенсивностей λ ij , стоящих у стрелок, идущих справа налево, опять-таки, с начала и вплоть до стрелки, исходящей из состояния S k . При k =n в числителе будет стоять произведение интен­сивностей λ ij , стоящих у всех стрелок, идущих слева направо, а в знаменателе – у всех стрелок, идущих справа налево

Итак, все вероятности р 1 , р 2 , ..., р n выражены через одну из их: p 1. Подставим эти выражения в нормировочное условие: р 1 + р 2 + ... + р n = l Получим:

Остальные вероятности выражаются через p 1:

(7.9)

Таким образом, задача «гибели и размножения» решена в общем виде: найдены предельные вероятности состояний.

Пример 2. Найти предельные вероятности состояний для процесса гибели и размножения, граф которого показан на рис. 32.

Рис. 32

Решение. По формулам (7.8) и (7.9) имеем:

Пример 3. Прибор состоит из трех узлов; поток отказов – простейший, среднее время безотказной работы каждого узла равно . Отказавший узел сра­зу же начинает ремонтироваться; среднее время ремонта (восстановления) узла равно ; закон распределения этого времени показательный (поток восста­новлений простейший). Найти среднюю производительность прибора, если при трех работающих узлах она равна 100%, при двух – 50%, а при одном и менее – прибор вообще не работает.

Решение. Перечень состояний системы и граф состояний уже приводились в примере 1 данного параграфа. Разметим этот граф, т. е. проставим у каждой стрелки соответствующую интенсивность λ ij (см. рис. 33.).

Рис. 33.

Так как поток отказов каждого узла – простейший, то промежуток вре­мени между отказами в этом потоке распределен по показательному закону с па­раметром , где –среднее время безотказной работы узла.

По стрелкам вправо систему переводят отказы. Если система на­ходится в состоянии S 0 , то работают три узла; каждый из них подвергается по­току отказов с интенсивностью ; значит, поток отказов, действующий на всю систему, в три раза более интенсивен: = 0,5 и

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

Номинала.

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