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

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

Министерство образования Республики Беларусь

Учреждение образования

"Гомельский государственный университет

имени Франциска Скорины"

Математический факультет

Кафедра экономической кибернетики и теории вероятностей

Курсовой проект

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

Исполнитель:

Буховец Виктория

Александровна

Научный руководитель:

заведующий кафедрой,

Малинковский Юрий

Владимирович

Гомель 2011

Содержание

Введение

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

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

.1 Определение математического ожидания для системы массового обслуживания M/M/1

.2 Определение математического ожидания для системы массового обслуживания M/M/n/0

.3 Определение математического ожидания для системы массового обслуживания M/M/n

.4 Определение математического ожидания для системы массового обслуживания M/M/n/N

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

.1 Процесс размножения и гибели с линейно растущей интенсивностью рождения и гибели

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

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

.4 Дополнительный поток и бесконечное число приборов

.5 Система с ограничением на время пребывания заявки

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

Заключение

Список использованных источников

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

Введение

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

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

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

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

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

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

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

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

q_ii(t)=.

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

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

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

Т=

Если цепь Маркова является конечной, то последняя строка матрицы записывается в виде [0 0… 0  ]; это соответствует тому, что не допускаются никакие размножения после того, как популяция достигает максимального объема n. Матрица T содержит нулевые члены только на главной диагонали и двух ближайших к ней диагоналях. Из-за такого частного вида матрицы T естественно ожидать, что анализ процесса размножения и гибели не должен вызывать трудностей [1, 3]. Далее будем рассматривать только непрерывные процессы размножения и гибели, в которых переходы из состояния 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.

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

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

Q =

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

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

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

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

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

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

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

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

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

 (2.1)

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

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

 (2.2)

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

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

P₀(t)=e^-lt.

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

.

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

P₁(t)= lte^-lt.

Далее по индукции в качестве решения уравнения (2.2) находим:

.

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

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

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

 (2.3)

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

. (2.4)

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

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

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

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

.

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

. (2.5)

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

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

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

При i=1 имеем

при i=2

при i=3

 .

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

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

 (2.6)

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

. (2.7)

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

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

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

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

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

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

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

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

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

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

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

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

.1 Определение математического ожидания для системы массового обслуживания M/M/1

Рассматриваемая система массового обслуживания является процессом размножения и гибели со следующим графом переходов (рисунок 3.1):

Рисунок 3.1 - Граф интенсивностей переходов для системы M/M/1

Из условия эргодичности для процесса гибели и размножения следует, что если , то существует единственное стационарное распределение, совпадающее с эргодическим,  называется коэффициентом загрузки сети. Уравнение равновесия имеет вид , , откуда находим, что:

.

Вероятность  можно найти, используя условие нормировки (2.4), откуда следует, что  и поэтому

, ,

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

Легко найти производящую функцию такого распределения:

, .

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

.

Очевидно, что очередь в системе массового обслуживания неограниченно растёт [3, 4].

.2 Определение математического ожидания для системы массового обслуживания M/M/n/0

Это система с потерями без ожидания. Если заявка поступает в систему в момент, когда обслуживанием заняты все n линий, то она теряется. Такая система была введена датским инженером Эрлангом в начале прошлого столетия и применена в качестве модели обработки вызовов, поступающих на телефонную станцию. Граф переходов для такой системы массового обслуживания имеет вид (рисунок 3.2):

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

.

Отсюда получаем:

.

Вероятность , как всегда, можно найти из условия нормировки (2.4), откуда:

.

Таким образом, получаем:

.

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

.

При больших n можно использовать асимптотику  [4].

2.3 Определение математического ожидания для системы массового обслуживания M/M/n

Это многолинейная система с ожиданием. Если обслуживанием заявок заняты все n линий, то интенсивность обслуживания равна . Граф перехода для этой системы имеет вид (рисунок 3.3):

Рисунок 3.3 - Граф интенсивностей переходов для системы M/M/n

Стационарное распределение существует, если

.

Уравнения равновесия имеют следующий вид:

откуда, аналогично предыдущему случаю, получаем

.

Условие нормировки в этом случае примет вид:

,

откуда следует, что

.

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

.

2.4 Определение математического ожидания для системы массового обслуживания M/M/n/N

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

Рисунок 3.4 - Граф интенсивностей переходов для системы M/M/n/N

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

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

Вероятность  определяется из условия нормировки (2.4):

,

откуда получаем:

.

Среднее число заявок в системе определяется соотношением [4]:

.

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

.1 Процесс размножения и гибели с линейно растущей интенсивностью рождения и гибели

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по следующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

Для определения математического ожидания используем следующую формулу:

где  определяется по формуле [5].

Таким образом, среднее число заявок в системе в стационарном режиме равно:

.

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

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по следующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

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

.

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

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по следующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

.

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

.

3.4 Дополнительный поток и бесконечное число приборов

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по следующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

.

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

.

Сделаем оценку сверху:

,

таким образом:

.

Получаем следующую оценку для среднего числа заявок в системе в стационарном режиме:

.

3.5 Система с ограничением на время пребывания заявки

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по следующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

.

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

.

Сделаем оценку сверху:

,

таким образом:

.

Получаем следующую оценку для среднего числа заявок в системе в стационарном режиме:

.

3.6 Система с ограничением на время пребывания заявки, дополнительный поток и бесконечное число приборов

Пусть скорость l_i, с которой происходит размножение в популяции объема i, и интенсивность гибели m_i, задающую скорость с которой происходит гибель в популяции объема i, определяются по слудующему правилу:

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

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

Запишем уравнения равновесия для стационарных вероятностей состояний:

.

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

Сделаем оценку сверху:

,

таким образом:

.

Получаем следующую оценку для среднего числа заявок в системе в стационарном режиме:

.

Заключение

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

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

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

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

Список использованных источников

Вентцель, Е.С. Теория случайных процессов и её инженерные приложения: учебное пособие для студентов / Е.С. Вентцель, Л.А. Овчаров - 2-е изд. - М.: "Высшая школа", 2000. - 384 с.

Малинковский, Ю.В. Лекции по теории массового обслуживания: учебное пособие для вузов / Ю.В. Малинковский. - Гомель: ГГУ им. Ф. Скорины, - 184 с. (электронный вариант)

Баруча-Рид, А.Т. Элементы теории марковских процессов и их приложения / А.Т. Баруча_Рид - М.: Наука, 1969. - 512 с.

Севастьянов, Б.А. О некоторых типах марковских процессов / Б.А. Севастьянов - т. 4, вып. 4 - УМН, 1949. - с. 194.

Колмогоров, А.Н. Введение в теорию вероятностей: учеб. для вузов / И.Г. Журбенко, А.В. Прохоров - М.: Наука, 1982. - 160 с.