Механики
 Скачать 4.29 Mb.
|
|
5.3.3. Марковские процессы с непрерывным временем Для однородного марковского процесса с непрерывным временем вероятности состояний на произвольный момент времени t определяются из системы дифференциальных уравнений: ) 0 ; , 1 ( ) ( ) ( 1 > = = ∑ = t n j g t p dt t dp n i ij i j (5.12) с учетом начальных условий ) 0 ( , ), 0 ( 1 n p p K Для систем обладающих эргодическим свойством, имеет место стационарный режим, для которого, согласно (5.8), вероятности состояний Раздел 5. Численное моделирование 185 n p p , , 1 K при ∞ → t не зависят от начальных вероятностей и текущего момента времени t, и система дифференциальных уравнений (5.12) для установившегося режима преобразуется в систему линейных алгебраических уравнений: ), , 1 ( 0 1 n j g p n i ij i = = ∑ = (5.13) которая совместно с нормировочным условием (5.11) образует систему, обладающую единственным решением. Доказательство выражений (5.12) и (5.13). Рассмотрим однородный марковский процесс с непрерывным временем, который может находиться в одном из n возможных состояний: Е 1 , …, Е n . Интенсивности переходов ij q заданы в виде матрицы ], , 1 , | [ n j i g ij = = G в которой диагональные элементы рассчитаны в соответствии с формулой (5.4). Начальные вероятности на момент времени 0 = t заданы в виде вектора )} 0 ( , ), 0 ( { 1 n p p P K = Определим вероятность ) (t p j того, что в момент времени 0 > t случайный процесс находится в состоянии j E Придадим времени t малое приращение t ∆ и найдем вероятность ) ( t t p j ∆ + того, что случайный процесс в момент времени ) ( t t ∆ + окажется в состоянии j E Случайный процесс может оказаться в состоянии j E в момент ) ( t t ∆ + двумя способами: 1) в момент времени t процесс находился в состоянии j E и в течение промежутка времени t ∆ не перешел в другое состояние; 2) в момент времени t процесс находился в состоянии i E ) ( j i ≠ и за время t ∆ совершил переход в состояние j E Вероятность первого способа ) ( ) 1 ( t t p j ∆ + найдем как произведение вероятности ) (t p j того, что в момент времени t случайный процесс находился в состоянии j E , на условную вероятность того, что, будучи в j E , процесс не перешел в другие состояния i E ) ,..., 1 , 1 ,..., 2 , 1 ( n j j i + − = Эта условная вероятность равна ∑ ≠ = ∆ − n j i i ji t g 1 1 Последнее выражение становится очевидным, если вспомнить, что произведение t g ji ∆ с точностью до бесконечно малых высших порядков 186 Раздел 5. Численное моделирование определяет вероятность перехода случайного процесса из состояния j E в состояние i E за промежуток времени t ∆ , а сумма этих вероятностей есть вероятность перехода из состояния j E в любое другое состояние, не совпадающее с j E . Вычитая эту сумму из единицы, получим требуемую вероятность противоположного события. Таким образом, вероятность первого способа с учетом выражения (5.4) равна ) , 1 ( ) 1 ( ) ( ) ( ) 1 ( n j t g t p t t p jj j j = ∆ + = ∆ + Аналогично определяется вероятность ) ( ) 2 ( t t p j ∆ + второго способа оказаться в состоянии j E в момент ) ( t t ∆ + : она равна вероятности ) (t p j того, что в момент времени t процесс находился в состоянии i E , умноженной на вероятность t g ij ∆ перехода за время t ∆ в состояние j E : t g t p ij i ∆ ) ( . Суммируя эти вероятности по всем возможным состояниям, исключая состояние j E , получим искомую вероятность: ∑ ≠ = = ∆ = ∆ + n j i i ij i n j t g t p t t p j 1 ) 2 ( ) , 1 ( ) ( ) ( Применив правило сложения вероятностей, получим вероятность на- хождения случайного процесса в состоянии j E в момент времени ) ( t t ∆ + : ∑ ≠ = ∆ + ∆ + = ∆ + + ∆ + = ∆ + n j i i ij i jj j j j j t g t p t g t p t t p t t p t t p 1 ) 2 ( ) 1 ( ) ( ) 1 ( ) ( ) ( ) ( ) ( или ∑ = = ∆ = − ∆ + n i ij i j j n j t g t p t p t t p 1 ) , 1 ( ) ( ) ( ) ( Разделим левую и правую части последнего выражения на t ∆ и перейдем к пределу при 0 → ∆ t : ∑ = → ∆ = = ∆ − ∆ + n i ij i j j t n j g t p t t p t t p 1 0 ) , 1 ( ) ( ) ( ) ( lim Левая часть полученного выражения представляет собой производную по времени от функции ) (t p j : ∑ = = = n i ij i j n j g t p dt t dp 1 ) , 1 ( ) ( ) ( . (5.14) Таким образом, получена система дифференциальных уравнений марковского случайного процесса, которая при заданных начальных условиях )} 0 ( , ), 0 ( { 1 n p p P K = позволяет выполнить исследование нестационарного (переходного) режима работы моделируемой системы Раздел 5. Численное моделирование 187 путем расчёта вероятностей состояний марковского процесса в произвольный момент времени 0 > t Для случайных процессов, обладающих эргодическим свойством, имеет место стационарный режим, для которого согласно (5.8) вероятности состояний при ∞ → t не зависят от начальных вероятностей и текущего момента времени t. Тогда производные 0 ) ( = dt t dp j , и система дифферен- циальных уравнений (5.14) преобразуется в систему линейных алгебраических уравнений (5.13). Пример . В качестве примера марковского процесса с непрерывным временем рассмотрим модель «гибели и размножения», которая часто встречается в разнообразных практических задачах. Своим названием эта модель обязана биологической задаче об изменении численности популя- ции и распространении эпидемий, которая формулируется следующим образом. Рассмотрим развитие некоторой популяции, особи которой могут рождаться и умирать. Положим, что при наличии i особей в популяции рождение новых особей происходит с интенсивностью i λ и с интенсив- ностью i µ – особи умирают. Пусть в любой момент времени может происходить рождение или гибель только одной особи, и интервалы времени между двумя моментами рождения и гибели распределены по экспоненциальному закону с параметрами i λ и i µ соответственно. Тогда процесс "гибели и размножения" может быть представлен марковским случайным процессом с непрерывным временем (рис.5.1,а), в котором состояние E i соответствует наличию i особей в популяции (i=0, 1, …), причем число состояний может быть конечным или бесконечным. Отметим, что состояние E 0 соответствует вырождению популяции. Таким образом, марковский процесс называется «процессом гибели и размножения», если её граф переходов имеет вид цепочки состояний, в которой каждое состояние (кроме крайних) связано с двумя соседними состояниями, а крайние состояния E 0 и E n (в случае конечного числа состояний) или только нулевое состояние E 0 (в случае бесконечного числа состояний) – только с одним соседним состоянием. n µ µ µ 2 1 а б Рис . 5.2. Графы состояний процесса гибели и размножения с бесконечным ( а ) и конечным ( б ) числом состояний 1 3 2 1 + i i µ µ µ µ µ 1 1 0 − n λ λ λ i i λ λ λ λ λ 1 2 1 0 − Е 0 Е 1 Е 2 Еi Е 0 Е 1 Е n … 188 Раздел 5. Численное моделирование Графу переходов процесса гибели и размножения с конечным числом состояний (рис.5.2,б) соответствует матрица интенсивностей переходов: n n n n n i n n n n µ µ λ µ λ µ λ µ λ µ λ µ λ λ − + − − + − + − − − = − − − 0 0 0 ) ( 0 0 0 1 0 0 ) ( 0 2 0 0 ) ( 1 0 0 0 0 1 2 1 0 1 1 1 2 2 2 1 1 1 1 0 0 E G Диагональные элементы матрицы определяются из условия (5.4) – сумма элементов каждой строки должна быть равна нулю Система линейных алгебраических уравнений для определения стационарных вероятностей может быть составлена по графу переходов или по матрице интенсивностей переходов Сформулируем правила составления уравнений для стационар - ных вероятностей состояний марковского процесса с непрерывным временем по графу переходов и по матрице интенсивностей переходов Правило__1_(_по_графу_переходов_).'>Правило 1 ( по графу переходов ). В левой части каждого уравнения записывается вероятность рассматриваемого состояния , умноженная на сумму интенсивностей переходов из данного состояния во все другие состояния Правая часть уравнения представляет собой сумму членов , число которых равно числу входящих в данное состояние дуг , и каждый такой член представляет собой произведение интенсивности перехода , соответствующей данной дуге , на вероятность состояния , из которого исходит эта дуга Для нашего примера применение правила 1 дает следующую систему линейных алгебраических уравнений : = + + + = + = + + = + = − − + + − − 1 ) ( ) ( 1 0 1 1 1 1 1 1 2 2 0 0 1 1 1 1 1 0 0 n n n n n k k k k k k k p p p p p p p p p p p p p λ µ µ λ µ λ µ λ µ λ µ λ , Раздел 5. Численное моделирование 189 где последнее уравнение представляет собой нормировочное условие (5.11). Правило 2 ( по матрице интенсивностей переходов ). Для каждого столбца матрицы интенсивностей переходов составляется соответствую- щее уравнение как сумма произведений интенсивностей переходов на стационарную вероятность состояния с номером соответствующей строки, приравненная нулю. Применение правила 2 для нашего примера дает следующую систему линейных алгебраических уравнений: = + + + = + − = + + + − = + + + − = + − − − + + − − 1 0 0 ) ( 0 ) ( 0 1 0 1 1 1 1 1 1 2 2 0 0 1 1 1 1 1 0 0 n n n n n k k k k k k k p p p p p p p p p p p p p λ µ µ λ µ λ µ λ µ λ µ λ Легко убедиться, что обе системы уравнений эквивалентны. Решая полученную систему уравнений аналитически или с примене- нием численных методов, можно определить значения n p p p ,..., , 1 0 стацио- нарных вероятностей состояний марковского процесса. Кроме того, могут быть рассчитаны другие характеристики исследуемой системы, в частно- сти, среднее число особей в популяции как математическое ожидание случайной величины: ∑ = = n k k kp M 1 5.4. Марковские модели систем массового обслуживания В данном параграфе в качестве примеров применения случайных процессов для изучения свойств систем с дискретным характером функци- онирования подробно рассматриваются марковские модели систем массо- вого обслуживания (СМО). Примеры представлены в порядке возрастания их сложности, начиная с простейшей одноканальной СМО с однородным потоком заявок без накопителя и заканчивая СМО с накопителями ограниченной ёмкости и приоритетным обслуживанием неоднородного потока заявок. В каждом примере приводится описание исследуемой системы, а также предположения и допущения , принятые при построении математи- ческой модели и необходимые для того, чтобы протекающий в системе случайный процесс был марковским. Разработка марковской модели исследуемой системы в терминах случайных процессов предполагает 190 Раздел 5. Численное моделирование выполнение следующих этапов: • кодирование состояний случайного процесса; • построение размеченного графа переходов ; • формирование матрицы интенсивностей переходов ; • составление системы линейных алгебраических уравнений для расчёта стационарных вероятностей состояний марковского процесса. Матрица интенсивностей переходов может использоваться для задания системы линейных алгебраических уравнений в матричном виде при компьютерном расчёте стационарных вероятностей. При исследовании различного рода реальных систем, моделями которых служат СМО, вряд ли кого-то интересуют вероятности состояний. Гораздо больший интерес представляют такие характеристики СМО, как длина очереди заявок перед обслуживающим прибором, время ожидания и время пребывания заявок в системе, загрузка и коэффициент простоя системы, доля потерянных заявок и т.д., значения которых могут быть рассчитаны по найденным значениям стационарных вероятностей состоя- ний. Поэтому ниже особое внимание уделяется математическим зависимо- стям, позволяющим рассчитать в каждом конкретном примере наиболее важные характеристики функционирования исследуемых систем. Макси- мально подробно процесс получения таких зависимостей изложен в нескольких первых рассматриваемых ниже примерах. На основе этих зависимостей в некоторых примерах проводится анализ свойств исследуе- мой системы. Для остальных примеров подобный анализ рекомендуется читателю выполнить самостоятельно. В первом примере (п.5.4.1) одноканальной СМО без накопителя представлена диаграмма функционирования исследуемой системы, с по- мощью которой показано, что протекающий в системе случайный процесс при сформулированных предположениях и допущениях (а это, прежде всего, экспоненциальный характер процессов поступления и обслуживания заявок) является марковским. Аналогично, и для остальных систем можно показать, что протекающие в них случайные процессы при сформулиро- ванных предположениях и допущениях являются марковскими. В некоторых случаях на основе марковских моделей могут быть получены математические выражения для расчёта стационарных вероятностей состояний в явном виде без применения методов численного анализа. В частности, такие результаты представлены ниже для однока- нальной и многоканальной СМО без накопителя (с отказами) и однока- нальной СМО с накопителем неограниченной и ограниченной ёмкости. |