Модели с дискретными состояниями и непрерывным временем

Вводится конечное множество дискретных состояний системы X= (x ₀, x ₁,…, x_n) таким образом, чтобы выполнялись следующие условия^*:

- в любой рассматриваемый момент времени система обязательно находится в одном из состояний, составляющих множество X;

- система не может одновременно находиться в двух или более состояниях из множества X.

Логика процесса смены состояний описывается ориентированным графом (рис. 14), вершины которого соответствуют состояниям системы, а дуги – возможным переходам в другие состояния. Отсутствие у вершины входящих дуг означает невозможность перехода в соответствующее состояние из какого-либо другого. Такие состояния называются начальными, или источниками (x ₀ на рис. 14). Отсутствие у вершины исходящих дуг означает невозможность вы­хода из соответствующего состояния. Такие состоя­ния называются конечными, или терминальными (x ₅ и x ₇ на рис. 14). При наличии у вершин входящих и ис­ходящих дуг соответствующие состояния называются транзитивными (остальные состояния на рис. 14).

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

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

p ₀(t) =P (x (t)) =x ₀),

p ₁(t) =P (x (t)) =x ₁),

...

p_n (t) =P (x (t)) =x_n),

, ,

где каждая вероятность p_i (t) представляет собой вероятность пребывания системы в состояниии x_i в момент времени t в условиях многократного повторения рассматриваемого процесса смены состояний, начиная с t= 0.

Кроме того, для количественного описания процесса с дискретными состояниями и непрерывным временем могут использоваться переходные вероятности. Переходная вероятность p_ij (t ₀,t) - это условная вероятность того, что в момент времени t'= t ₀ + t система окажется в состоянии x_j, если в момент времени t ₀ она была в состоянии x_i.

Процесс смены состояний называется марковским, или процессом без последействия, если все его переходные вероятности зависят только от указанных в их обозначении параметров: в каком состоянии x_i система была в момент времени t ₀ и в какое состояние x_j она должна попасть в момент времени t ₀+t. Другими словами, все вероятностные характеристики марковского случайного процесса "в будущем" (t > t ₀) зависят только от его текущего состояния в момент t ₀ и не зависят от того, каким образом и когда оно достигнуто.

При построении математических моделей таких процессов используется аппарат теории потоков случайных событий. Потоком случайных событий, или случайным потоком, - называется последовательность моментов времени { t_n }, 0≤ t ₁≤ t ₂≤...≤ t_n ≤… наступления некоторых событий, в которой все t_n (n= 1,2,...) являются непрерывными случайными величинами. Поток случайных событий можно представить также как последовательность интервалов времени между отдельными событиями {t _n }: t _n = t_n–t_{n– 1}, n≥ 1, t ₀=0, где отдельные t _n также являются непрерывными случайными величинами. Понятие случайного потока предполагает невозможность регистрации бесконечного числа событий на конечном интервале времени.

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

Назовем наиболее важные свойства случайных потоков.

1. Ординарность - невозможность одновременного наступления двух или более событий. Если рассматривать вероятность наступления на некотором малом интервале времени D t после момента t более одного события p _>1(t,D t), то при ∆t→ 0 для ординарного потока она окажется бесконечно малой величиной более высокого порядка, чем D t:

. (2.13)

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

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

. (2.14)

Определим среднее число событий на малом интервале времени D t как математическое ожидание дискретной случайной величины с возможными значениями 0,1,2,..., k,... и с учетом (2.13)

,

где p ₀(t,D t) - вероятность отсутствия событий на интервале D t; p ₁(t,D t) - вероятность регистрации одного события на интервале D t и так далее.

В результате получим:

.

3. Стационарность - интенсивность случайного потока постоянна во времени:

l(t) = l = const.

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

Рассмотрим развитие марковского случайного процесса, граф которого представлен на рис. 14, считая, что в начальный момент времени система находится в состоянии x ₀. Поскольку момент времени t ₁ перехода системы в состояние x ₁ является непрерывной случайной величиной, будем рассматривать его как момент наступления первого события случайного потока П ₀₁, характеризующегося интенсивностью l₀₁(t). При этом принимается, что после перехода в x ₁ поток П ₀₁ обрывается и возникает новый поток П ₁₂ переходов из x ₁ в x ₂ с интенсивностью l₁₂(t).

Рассматривая дальнейшее развитие процесса, будем использовать такой принцип для всех состояний. Например, если система находится в состоянии x ₄, существуют два потока П ₄₅ с интенсивностью l₄₅(t) и П ₄₆ с интенсивностью l₄₆(t) переходов из x ₄ соответственно в x ₅ и x ₆. Если раньше наступит первое событие потока П ₄₅, система перейдет в состояние x ₅ и потоки П ₄₅ и П ₄₆ прервутся. Если раньше наступит первое событие потока П ₄₆, система перейдет в состояние x ₆, потоки П ₄₅ и П ₄₆ прервутся и возникнет поток П ₆₇ переходов из x ₆ в x ₇. Введенные таким образом случайные потоки П_ij называют потоками обрыва длительности состояний, а их интенсивности l _ij (t) - интенсивностями обрыва длительности состояний или интенсивностями смены состояний.

Чтобы случайный процесс в системе с дискретными состояниями и непрерывным временем, был марковским, необходимо и достаточно, чтобы все потоки, переводящие систему из состояния в состояние, были пуассоновскими [40].

Перейдем к количественному описанию рассматриваемого процесса.

Пребывание системы в состоянии x ₀ в некоторый момент времени t'=t ₀+t> t следует рассматривать как сложное событие: C ₀ =A ₀ Ù , где A ₀ - пребывание системы в состоянии x ₀ в момент t; - невыход из состояния x ₀ за интервал времени t. Вероятность события C ₀ определяется как произведение:

.

Вероятность невыхода определим через вероятность противоположного события - перехода из x ₀ в x ₁ - и используем интенсивность случайного потока П ₀₁ в соответствии с (2.14), считая t малой величиной:

p ₀₀(t, t) = 1 -p ₀₁(t, t) = 1 -p ₍₁₎(t, t) = 1 -l ₀₁(t)t - 0(t),

где p ₍₁₎(t,t) - вероятность наступления события потока П ₀₁ на интервале t.

Определим приращение вероятности p ₀ за интервал времени t и найдем ее производную:

= – l₀₁(t) p ₀(t). (2.15)

Составим теперь дифференциальное уравнение для вероятности транзитивного состояния x ₁. Пребывание системы в состоянии x ₁ в момент t'=t ₀+t представляет собой сложное событие: C₁=A₀ ÙB₁ÚA₁Ú , где A ₀ и A ₁ - пребывание системы в момент t соответственно в состояниях x ₀ и x ₁; B ₁ - переход из x ₀ в x ₁ на интервале t; - невыход из состояния x ₁ за интервал времени t. Вероятность события C ₁ определяется с учетом его состава следующим образом:

= p ₀(t) p ₀₁(t,t) +p ₁(t) p ₁₁(t,t)= p ₀(t) p ₀₁(t,t) +p ₁(t)(1 -p ₁₂(t,t)),

где p ₁₁(t,t) - вероятность невыхода из x ₁ за интервал времени t; p ₁₂(t,t) - вероятность противоположного события - перехода из x ₁ в x ₂ за интервал t. Аналогично предыдущему случаю, используя интенсивность случайного потока П ₁₂, найдем производную вероятности p ₁:

=l₀₁(t) p ₀(t) – l₁₂(t) p ₁(t). (2.16)

Аналогично (2.15), (2.16) при заданном графе смены состояний могут быть получены дифференциальные уравнения для вероятностей всех состояний марковского процесса с дискретными состояниями и непрерывным временем, которые носят название уравнений А. Н. Колмогорова. В общем случае система уравнений А. Н. Колмогорова имеет вид

, i= 0,1,..., n; j ¹ i, (2.17)

где l _ij (t) - интенсивности случайных потоков, соответствующих исходящим дугам i -й вершины; l _ji (t) - интенсивности случайных потоков, соответствующих входящим дугам i- й вершины.

Для практического использования систему (2.17) необходимо дополнить условием нормировки:

. (2.18)

В ряде случаев система (2.17), решаемая изолированно от (2.18), может не иметь решения.

При заданном начальном распределении вероятностей состояний p_i (0), i= 0,1,..., n, отвечающем условию нормировки, система уравнений (2.17), (2.18) позволяет определить распределение вероятностей состояний процесса для любого произвольного момента времени t> 0.

Для простейшего марковского процесса смены состояний, у которого интенсивности l _ij постоянны, иногда практический интерес представляет только финальное распределение вероятностей, соответствующее установившемуся режиму при t ® ¥. За исключением некоторых частных случаев, оно может быть определено решением системы алгебраических уравнений, получаемых из (2.17), если положить все производные равными нулю:

, i= 0,1,..., n; j ¹ i,(2.19)

и заменить одно из полученных уравнений условием нормировки (2.18).

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

Рассмотрим наиболее часто используемые для решения практических задач модели процессов и систем с дискретными состояниями и непрерывным временем. На рис. 15 показаны графы процессов "чистой гибели" (а), "чистого размножения" (б), "гибели и размножения" (в). В частных случаях могут задаваться l _i =l, m _i =m или m _i = i ^. m. Подробный анализ таких процессов содержится, например, в [1,40].

Для одноканальной и многоканальной систем массового обслуживания (СМО) с отказами (рис. 16) номер состояния соответствует числу занятых каналов, l - интенсивность потока заявок, m - производительность канала.

Для одноканальной СМО с ожиданием и ограниченной очередью длиной m (рис. 17, а) состояния вводятся следующим образом: x ₀ - канал свободен; x ₁- канал занят, очереди нет; x ₂ - канал занят, одна заявка в очереди; x_{m +1} - канал занят, m заявок в очереди.

Для n- канальной СМО с ожиданием и ограниченной очередью длиной m (рис. 17, б) состояния вводятся следующим образом: x ₀ - все каналы свободны; x ₁ - занят один канал, остальные свободны; x_n - все каналы заняты, очереди нет; x_n+k - все каналы заняты, k заявок в очереди; x_n+m - все каналы и места в очереди заняты.

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

Для лучшего понимания и более подробного знакомства с рассмотренной темой рекомендуются книги [9,40].

Дата добавления: 2015-11-04