Механики
 Скачать 4.29 Mb.
|
|
Интенсивность перехода ij g из состояния E i в состояние E j опреде- ляется как предел отношения вероятности перехода ) ( τ ∆ ij P системы за промежуток времени τ ∆ из E i в E j к длине этого промежутка: ). ; , 1 , ( ) ( lim 0 j i n j i P g ij ij ≠ = ∆ ∆ = → ∆ τ τ τ (5.3) Отсюда следует , что вероятность перехода за бесконечно малый промежуток времени τ ∆ равна : ) ( j i g ij ≠ ∆ τ Вероятность двух и более переходов за время τ ∆ имеет порядок ( τ ∆ ) 2 и выше и предполагается бесконечно малой величиной Если интенсивности переходов постоянны и не зависят от времени t, то есть от того , в какой момент начинается промежуток τ ∆ , то марков - ский процесс называется однородным Если интенсивности ij g представ - Раздел 5. Численное моделирование 179 ляют собой функции времени t, процесс называется неоднородным В дальнейшем будем рассматривать только однородные марковские процессы Интенсивности переходов задаются в виде квадратной матрицы ] , 1 , | [ n j i g ij = = G , называемой матрицей интенсивностей переходов , диагональные элементы которой определяются из условия : ), , 1 ( 0 1 n i g n j ij = = ∑ = откуда ). , 1 , ( 1 n j i g g n i j j ij ii = − = ∑ ≠ = (5.4) Матрица, в которой сумма элементов в каждой строке равна нулю, называется дифференциальной. Выше было показано, что в случае экспоненциального закона распределения времени нахождения случайного процесса в некотором состоянии вероятность перехода из одного состояния в другое за бесконечно малый интервал времени определяется выражением (5.1) и равно τ α τ ∆ = ∆ ij ij P ) ( . Отсюда следует, что интенсивность перехода представляет собой параметр экспоненциального распределения: ij ij ij P g α τ τ τ = ∆ ∆ = → ∆ ) ( lim 0 Начальные вероятности ) 0 ( , ), 0 ( 1 n p p K , где ) 0 ( i p – вероятность того , что в момент времени 0 = t система находится в состоянии E i ) , 1 ( n i K = , задают состояние системы в начальный момент времени 0 = t Начальные вероятности необходимы при изучении переходных процессов , когда исследуемая система работает в нестационарном режиме Если марковский процесс обладает эргодическим свойством , что означает работу моделируемой системы в установившемся режиме , то , как будет показано ниже , стационарные характеристики ( вероятности ) не зависят от начальных вероятностей и , следовательно , могут быть не заданы 5.2.2. Характеристики марковского случайного процесса Изучение случайных процессов заключается в определении вероят - ностей того , что в момент времени t система находится в том или ином состоянии Совокупность таких вероятностей , описывающих состояния системы в различные моменты времени , дают достаточно полную информацию о протекающем в системе случайном процессе Рассмотрим систему с конечным числом состояний : E 1 , …, E n Обозначим через ) (t p i вероятность того , что в момент времени t система 180 Раздел 5. Численное моделирование находится в состоянии E i : } ) ( Pr{ ) ( i i E t Z t p = = В любой момент времени t система может находиться в одном из n возможных состояний , то есть для любого момента времени t выполняется условие : , 1 ) ( 1 = ∑ = t p n i i (5.5) которое называется нормировочным Совокупность вероятностей ) (t p i может быть представлена вектором с числом координат , равным числу возможных состояний системы : { } , ) ( ),..., ( ) ( 1 t p t p t P n = причем ∑ = = ≤ ≤ n i i i t p t p 1 1 ) ( ; 1 ) ( 0 . (5.6) Вектор , обладающий свойствами (5.6), называется стохастическим Стохастический вектор называется вектором состояний , если его компоненты представляют собой вероятности состояний системы Вектор состояний { } ) ( ),..., ( ) ( 1 t p t p t P n = является основной характе - ристикой марковского случайного процесса На основе полученных значений вероятностей состояний случайного процесса , протекающего в исследуемой системе , могут быть рассчитаны представляющие интерес реальные характеристики системы , например для системы массового обслуживания могут быть рассчитаны длины очередей заявок 5.3. Методы расчета марковских моделей 5.3.1. Эргодическое свойство случайных процессов Если по истечении достаточно большого промежутка времени веро - ятности состояний стремятся к предельным значениям n p p , , 1 K , не зави - сящим от начальных вероятностей ) 0 ( , ), 0 ( 1 n p p K и от текущего момента времени t , то говорят , что случайный процесс обладает эргодическим свойством Таким образом , для процессов , обладающих эргодическим свойством : P = ∞ = ∞ → ) ( ) ( lim P t P t , где ) , , ( 1 n p p K = P – вектор вероятностей состояний системы , называемых стационарными вероятностями В системе , описываемой марковским случайным процессом , облада - ющим эргодическим свойством , при ∞ → t устанавливается некоторый предельный режим , при котором характеристики функционирования системы не зависят от времени В этом случае говорят , что система Раздел 5. Численное моделирование 181 работает в установившемся или стационарном режиме Если характеристики функционирования системы зависят от времени , то имеем неустановившийся режим Отметим , что для стационарных вероятностей i p должно выполняться нормировочное условие (5.5). При рассмотрении случайных процессов возникает вполне резонный вопрос : когда случайный процесс обладает эргодическим свойством ? Случайный процесс с дискретным временем обладает эргодическим свойством , если матрица вероятностей переходов не является периодической или разложимой Матрица является разложимой , если она может быть приведена к одному из следующих видов : 1) D 0 0 A , 2) D C 0 A , 3) D 0 B A , где A, B, C, D – ненулевые квадратные подматрицы ; 0 – нулевая квадратная подматрица В первом случае состояния , соответствующие подмножествам A и D , называются замкнутыми , так как система , находясь в каком - то состоянии одного из этих подмножеств , никогда не сможет перейти в какое - либо состояние другого подмножества Состояния , соответствующие подмноже - ству D во втором случае и подмножеству A в третьем случае , называются невозвратными , поскольку после того , как процесс покинет эти состоя - ния , невозможен обратный переход в эти состояния из состояний , соответствующих другим подмножествам Матрица является периодической , если она может быть приведена к виду : 0 C B 0 Случайный процесс в этом случае будет по очереди переходить из состояний , соответствующих B , в состояния , соответствующие С Итак , если матрица вероятностей переходов ], , 1 , | [ n j i q ij = = Q случайного процесса с дискретным временем не является периодической или разложимой , то процесс обладает эргодическим свойством : ) , 1 ( ) ( lim n i p k p i i k = = ∞ → . (5.7) Транзитивный случайный процесс с непрерывным временем и конечным числом состояний , среди которых нет невозвратных и поглощающих состояний , всегда обладает эргодическим свойством : ) , 1 ( ) ( lim n i p t p i i t = = ∞ → . (5.8) 182 Раздел 5. Численное моделирование 5.3.2. Марковские процессы с дискретным временем Для однородного марковского процесса с дискретным временем вероятности состояний на момент времени k t определяются на основе следующего рекуррентного выражения : ,...) 2 , 1 ; , 1 ( ) 1 ( ) ( 1 ∑ = = = − = n i ij i j k n j q k p k p (5.9) Если рассматриваемый марковский процесс обладает эргодическим свойством , то , согласно (5.7), при ∞ → k вероятности состояний ) (k p i стремятся к стационарным значениям i p , не зависящим от момента времени k t и начальных вероятностей ) 0 ( i p С учётом этого , выражение (5.9) может быть преобразовано к виду : ∑ = = = n i ij i j n j q p p 1 ) , 1 ( (5.10) а нормировочное условие (5.5) примет вид : 1 1 = ∑ = n i i p (5.11) Уравнения (5.10) с условием (5.11) образуют систему линейных алгебраических уравнений для расчёта стационарных вероятностей состояний марковского процесса , которая обладает единственным решением , если Q – эргодическая матрица Доказательство выражения (5.9). Рассмотрим однородный марковский процесс с дискретным временем , который может находиться в одном из n возможных состояний : Е 1 , …, Е n Вероятности переходов ij q заданы в виде матрицы переходов ] , 1 , | [ n j i q ij = = Q , а начальные вероятности на момент времени 0 0 = t в виде вектора )} 0 ( , ), 0 ( { 1 n p p P K = Найдем вероятности состояний марковского процесса после первого шага , то есть на момент времени 1 t . По формуле полной вероятности получим : + + + = + + + = + + + = , ) 0 ( ) 0 ( ) 0 ( ) 1 ( ; ) 0 ( ) 0 ( ) 0 ( ) 1 ( ; ) 0 ( ) 0 ( ) 0 ( ) 1 ( 2 2 1 1 2 22 2 12 1 2 1 21 2 11 1 1 nn n n n n n n n n q p q p q p p q p q p q p p q p q p q p p или в компактной форме : ) , 1 ( ) 0 ( ) 1 ( 1 n j q p p n i ij i j = = ∑ = Раздел 5. Численное моделирование 183 Вероятности состояний после второго шага на момент времени 2 t определяются аналогично : ) , 1 ( ) 1 ( ) 2 ( 1 n j q p p n i ij i j = = ∑ = После k- го шага на момент времени ,...) 2 , 1 ( = k t k вероятности состояний будут определяться как ) , 1 ( ) 1 ( ) ( 1 n j q k p k p n i ij i j = − = ∑ = , что и требовалось доказать Пример Рассмотрим систему , которая состоит из двух устройств У 1 и У 2 , каждое из которых может находиться в одном из двух состояний : 0 – выключено и 1 – включено В определённые моменты времени устройства могут включаться или выключаться Выделим возможные состояния системы : 1 1 0 0 1 0 1 0 2 1 3 2 1 0 У У i E E E E E Состояние 0 E соответствует простою системы , когда оба устройства выключены , а состояние 3 E соответствует случаю , когда оба устройства включены Положим , что заданы вероятности переходов в виде матрицы 0 6 , 0 4 , 0 0 5 , 0 0 0 5 , 0 4 , 0 1 , 0 0 5 , 0 3 , 0 5 , 0 2 , 0 0 3 2 1 0 3 2 1 0 E E E E E E E E Q = и начальные вероятности 0 ) 0 ( ; 0 ) 0 ( ; 2 , 0 ) 0 ( ; 8 , 0 ) 0 ( 3 2 1 0 = = = = p p p p Определим вероятности нахождения системы в том или ином состоянии на различные моменты времени Согласно выражению (5.9) вероятности состояний системы : • на момент времени 1 t : 1 , 0 ) 0 ( ) 0 ( ) 0 ( ) 0 ( ) 1 ( 30 3 20 2 10 1 00 0 0 = + + + = q p q p q p q p p ; 16 , 0 ) 0 ( ) 0 ( ) 0 ( ) 0 ( ) 1 ( 31 3 21 2 11 1 01 0 1 = + + + = q p q p q p q p p ; 42 , 0 ) 0 ( ) 0 ( ) 0 ( ) 0 ( ) 1 ( 32 3 22 2 12 1 02 0 2 = + + + = q p q p q p q p p ; 32 , 0 ) 0 ( ) 0 ( ) 0 ( ) 0 ( ) 1 ( 33 3 23 2 13 1 03 0 3 = + + + = q p q p q p q p p ; • на момент времени 2 t : 29 , 0 ) 1 ( ) 1 ( ) 1 ( ) 1 ( ) 2 ( 30 3 20 2 10 1 00 0 0 = + + + = q p q p q p q p p ; 184 Раздел 5. Численное моделирование 148 , 0 ) 1 ( ) 1 ( ) 1 ( ) 1 ( ) 2 ( 31 3 21 2 11 1 01 0 1 = + + + = q p q p q p q p p ; 258 , 0 ) 1 ( ) 1 ( ) 1 ( ) 1 ( ) 2 ( 32 3 22 2 12 1 02 0 2 = + + + = q p q p q p q p p ; 304 , 0 ) 1 ( ) 1 ( ) 1 ( ) 1 ( ) 2 ( 33 3 23 2 13 1 03 0 3 = + + + = q p q p q p q p p Аналогично вероятности состояний системы могут быть рассчитаны на моменты времени ,... , 4 3 t t Нетрудно убедиться , что сумма вероятностей состояний системы на каждый момент времени равна единице : 1 ) ( ) ( ) ( ) ( 3 2 1 0 = + + + k p k p k p k p для , 2 , 1 = k Матрица вероятностей переходов рассматриваемой системы – неразложимая и непериодическая , следовательно , случайный процесс обладает эргодическим свойством , и вероятности состояний системы для стационарного режима ( стационарные вероятности ) 3 2 1 0 , , , p p p p могут быть найдены из системы линейных алгебраических уравнений (5.10) с учётом нормировочного условия (5.11): = + + + + + = + + + = + + = + + + = + = + + + = + = + + + = 1 ; 5 , 0 4 , 0 3 , 0 ; 6 , 0 1 , 0 5 , 0 ; 4 , 0 2 , 0 ; 5 , 0 5 , 0 3 2 1 0 2 1 0 33 3 23 2 13 1 03 0 3 3 1 0 32 3 22 2 12 1 02 0 2 3 0 31 3 21 2 11 1 01 0 1 2 1 30 3 20 2 10 1 00 0 0 p p p p p p p q p q p q p q p p p p p q p q p q p q p p p p q p q p q p q p p p p q p q p q p q p p Решая систему уравнений, получим значения стационарных вероят- ностей: 236 , 0 55 13 0 ≈ = p , 164 , 0 55 9 1 ≈ = p , 309 , 0 55 17 2 ≈ = p , 291 , 0 55 16 3 ≈ = p Таким образом, система будет простаивать 23,6% времени, а более 76% времени система будет находиться в рабочем состоянии, причем почти 30% времени (точнее 29,1%) во включённом состоянии будут одновременно находиться оба устройства системы. Среднее число устройств, находящихся одновременно во включённом состоянии, будет равно: 055 , 1 2 3 2 1 = + + = p p p M , то есть во включённом состоянии нахо- дится в среднем одно устройство. |