Механики
 Скачать 4.29 Mb.
|
|
Раздел 5. ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ (МОДЕЛИ СЛУЧАЙНЫХ ПРОЦЕССОВ) «В задаче из N уравнений всегда будет N+1 неизвестная» (Уравнения Снэйфу) При изучении сложных систем со стохастическим характером функ- ционирования полезной математической моделью является случайный процесс, который развивается в зависимости от ряда случайных факторов. Примерами случайных процессов могут служить процессы поступления и передачи данных в телекоммуникационной сети, процессы выполнения задач и обмена данными с внешними устройствами в вычислительной системе и т.п. Большинство моделей дискретных систем со стохастическим харак- тером функционирования строится на основе моделей массового обслужи- вания, процессы в которых являются случайным и, во многих случаях, марковскими или некоторым образом связанные с марковскими процесс- сами. Поэтому для решения таких задач теории массового обслуживания может использоваться математический аппарат теории марковских процессов. Применение марковских процессов оказывается особенно эффективным и результативным при исследовании систем и сетей массового обслуживания с накопителями ограниченной ёмкости. Математическое описание марковских процессов обычно представ- ляется в виде систем дифференциальных (в случае нестационарного режи- ма) или алгебраических (для стационарного режима) уравнений, решение которых, в общем случае, получить в явном виде не удается. Это обуслов- ливает необходимость применения численных методов решения систем дифференциальных или алгебраических уравнений. 5.1. Понятие случайного процесса Основными для случайных процессов являются понятия состояния и перехода из одного состояния в другое. Случайный процесс находится в некотором состоянии, если он полностью описывается значениями переменных, которые задают это состояние. Процесс совершает переход из одного состояния в другое, если описывающие ее переменные изменяются от значений, задающих одно состояние, на значения, которые определяют другое состояние. Случайный процесс состоит в том, что с течением времени процесс переходит из одного состояния в другое заранее не известное состояние. Понятия «состояние» и «переход» используются как для описания случайного процесса, так и системы, в которой этот процесс протекает. Поэтому при моделировании реальных систем часто говорят о состоянии системы и переходе системы из одного состояния в другое. Если множество состояний, в которых может находиться процесс 174 Раздел 5. Численное моделирование счётное, то есть все возможные состояния могут быть пронумерованы, то соответствующий процесс называется случайным процессом с дискрет- ными состояниями или просто дискретным случайным процессом. В этом случае переменные, описывающие состояния случайного процесса, принимают либо целочисленные значения, либо вполне конкретные отде- лённые друг от друга дискретные значения. Обычно состояния дискретно- го случайного процесса определяются таким образом, чтобы каждое воз- можное состояние могло быть обозначено порядковым номером, при этом число возможных состояний системы может быть конечным: n E E E ,..., , 2 1 или бесконечным : ,... ,..., , 2 1 n E E E ( иногда состояния нумеруются , начиная с нуля : ,... ,..., , 1 0 n E E E ). Для случайного процесса с дискретными состояния - ми характерен скачкообразный переход из одного состояния в другое ( рис .5.1, а ). Например , случайный процесс , протекающий в простейшей СМО с однородным потоком заявок , может быть представлен количеством заявок , находящихся в системе в произвольный момент времени Тогда состояние k E случайного процесса и , следовательно , самой системы будет означать , что в СМО находится ровно , 2 , 1 , 0 = k заявок Если множество состояний не может быть пронумеровано , то имеем случайный процесс с непрерывными состояниями или просто непрерывный случайный процесс , для которого характерен плавный пере - ход из состояния в состояние и который задаётся в виде непрерывной ункции времени : ) (t E ( рис .5.1, б ). Например , процесс изменения темпера - туры некоторого объекта может рассматриваться как случайный процесс с непрерывными состояниями Поскольку модели массового обслуживания относятся к классу дискретных систем , то в дальнейшем будут рассматриваться только случайные процессы с дискретными состояниями При описании дискретных систем в терминах случайных процессов одним из основных этапов является этап кодирования состояний , заклю - чающийся в определении состава переменных и их значений , используе - мых для описания состояний Состав переменных в значительной мере Е 1 Е 2 Е 3 Е 4 Е 5 Е 6 t 0 t 1 t 2 t 3 t 4 t 5 Рис .5.1. Процессы с дискретными ( а ) и непрерывными ( б ) состояниями Е (t) t 0 t а ) б ) Раздел 5. Численное моделирование 175 определяется назначением разрабатываемой модели , зависящим от целей исследований 5.1.1. Случайные процессы с дискретными состояниями Предположим , что система может находиться в одном из состояний E 1 , E 2 , ... ( часто состояния обозначаются просто номерами 1, 2,...). Пусть состояние системы меняется скачкообразно в зависимости от некоторого параметра t, причем переход из состояния в состояние является случай - ным Будем называть параметр t – временем и считать , что t пробегает либо целые , либо действительные числа Обозначим через ) (t Z случайный процесс , описывающий состояние системы в момент времени t. Случайный процесс ) (t Z называется случайным процессом с дискретным временем, если переходы из состояния в состояние возможны только в строго определенные заранее фиксированные моменты времени, которые можно пронумеровать: K , , 2 1 t t Если промежуток времени между переходами из состояния в состояние является случайным и переход возможен в любой заранее не известный момент времени t , то процесс называется случайным процессом с непрерывным временем. Процесс с дискретным временем имеет место либо когда структура системы такова, что ее состояния могут изменяться только в заранее определенные моменты времени, либо когда предполагается, что для описания процесса достаточно знать состояние системы в отдельные моменты времени. Тогда эти моменты можно пронумеровать и говорить о состоянии E i в момент k t или просто в момент k ( , 2 , 1 , 0 = k ). Процессы с дискретным временем называются стохастическими последовательностями или случайными цепями. Случайные процессы с дискретными состояниями могут изображать- ся в виде графа переходов (состояний), в котором вершины соответствуют состояниям, а ориентированные дуги – переходам из одного состояния в другое. Граф переходов называется размеченным, если на дугах графа указаны условия перехода в виде вероятностей переходов (для процессов с дискретным временем) или интенсивностей переходов (для процессов с непрерывным временем). Состояния E i могут быть: • невозвратными, если процесс после какого-то числа переходов непременно покидает их; • поглощающими, если случайный процесс, достигнув этих состояний прекращается. Случайный процесс называется транзитивным, если из любого состояния можно перейти за то или иное число шагов в любое другое 176 Раздел 5. Численное моделирование состояние и вернуться в исходное. 5.1.2. Понятие марковского случайного процесса Случайный процесс называется марковским, если вероятность любо- го состояния в будущем зависит только от его состояния в настоящем и не зависит от того, когда и каким образом процесс оказался в этом состоянии. Описывающий поведение системы процесс ) (t Z называется цепью Маркова. Для того чтобы случайный процесс с непрерывным временем был марковским, необходимо, чтобы интервалы времени между соседними переходами из состояния в состояние были распределены по экспонен - циальному закону. Для доказательства последнего утверждения восполь- зуемся следующими рассуждениями. Пусть время нахождения случайного процесса в некотором состоянии E i до его перехода в другое состояние E j распределено по экспоненциальному закону с функцией распределения τ α τ ij e F ij − − = 1 ) ( , где ij α - параметр распределения , характеризующий частоту перехода из состояния E i в состояние E j и определяемый как величина , обратная среднему времени нахождения случайного процесса в состоянии E i до момента его перехода в состояние E j Вычислим вероятность того , что случайный процесс перейдет в состояние E j в течение интервала времени τ ∆ при условии , что в состоянии E i процесс уже находится в течение времени 0 τ Эта условная вероятность равна τ α τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ ∆ − − = − − ∆ + = ≥ ∆ + ≤ ≤ = = ≥ ∆ + ≤ ≤ = ≥ ∆ ij e F F F P ij 1 ) ( 1 ) ( ) ( ) Pr( ) Pr( ) Pr( ) ( 0 0 0 0 0 0 0 0 0 0 Из последнего выражения следует, что вероятность перехода из одного состояния в другое зависит только от исходного состояния E i и не зависит от интервала времени 0 τ , то есть от того, как долго находился процесс в состоянии E i , а также от того, какие состояния предшествовали состоянию E i . Другими словами, поведение случайного процесса не зависит от предыстории и определяется только его состоянием в настоящий момент, то есть процесс является марковским. Еще одно замечательное свойство экспоненциального распределе - ния вытекает из полученного выражения, а именно: если время нахожде- ния случайного процесса в некотором состоянии E i до его перехода в другое состояние E j распределено по экспоненциальному закону с параме- тром ij α , то интервал времени от любого случайного момента времени до момента перехода в состояние E j имеет такое же экспоненциальное распределение с тем же параметром ij α . Эта особенность является след- ствием отсутствия последействия, присущего всем процессам с экспонен- Раздел 5. Численное моделирование 177 циальным распределением времени нахождения в том или ином состоянии. Таким образом, безусловная ) ( τ ∆ ij P и условная ) ( 0 τ τ τ ≥ ∆ ij P вероятности перехода в другое состояние за время τ ∆ для марковского процесса одинаковы и равны τ α τ τ τ τ ∆ − − = ≥ ∆ = ∆ ij e P P ij ij 1 ) ( ) ( 0 Пусть интервал времени τ ∆ достаточно мал. Тогда, разлагая τ α ∆ − ij e в ряд по степеням τ α ∆ ij при 0 → ∆ τ и пренебрегая величинами высшего порядка малости, получим вероятность перехода из одного состояния в другое за бесконечно малый интервал времени: τ α τ α τ ∆ = ∆ − − = ∆ ij ij ij P ) 1 ( 1 ) ( . (5.1) 5.2. Параметры и характеристики марковского случайного процесса 5.2.1. Параметры марковского случайного процесса Для описания марковского случайного процесса с дискретными состояниями используется следующая совокупность параметров: • перечень состояний n E E ,..., 1 , в которых может находиться случайный процесс; • матрица переходов, описывающая переходы случайного процесса между состояниями в виде: матрицы вероятностей переходов Q для процессов с дискретным временем; матрицы интенсивностей переходов G для процессов с непрерывным временем; • начальные вероятности ) 0 ( , ), 0 ( 1 n p p K Для определения перечня состояний случайного процесса необхо- димо корректно решить задачу кодирования состояний, которое зависит от смысла, вкладываемого в понятие «состояние» для каждой конкретной системы. Так, например, состояние некоторой системы массового обслу- живания (а, следовательно, и случайного процесса, протекающего в ней) может быть задано числом заявок, находящихся в системе в данный момент времени, а состояние сети массового обслуживания – распределе- нием числа заявок по всем узлам сети. Для случайных процессов с дискретным временем изменения состояний происходят только в определенные моменты времени K K , , , , 2 1 k t t t . Переходы между состояниями описываются вероятно - стями переходов. Если непосредственный переход из одного состояния в другое невозможен, то вероятность, соответствующая данному переходу, равна нулю. Обозначим через ij q условную вероятность того, что в момент 178 Раздел 5. Численное моделирование времени 1 + k t случайный процесс перейдет в состояние E j при условии, что в момент k t процесс находился в состоянии E i . Если переход из состояния E i в E j зависит только от этих двух состояний, то есть условная вероят- ность ij q не изменяется при дополнительной информации о поведении процесса до момента t k , получим цепь Маркова. Цепь Маркова называется однородной, если вероятности переходов не зависят от момента времени k t , и неоднородной, если вероятности переходов являются функциями k t , то есть ) ( k q q ij ij = Вероятности переходов задаются в виде квадратной матрицы вероятностей переходов ], , 1 , | [ n j i q ij = = Q элементы которой удовлетво- ряют условиям: ) , 1 , ( 1 ; 1 0 1 n j i q q n j ij ij = = ≤ ≤ ∑ = . (5.2) Матрица, элементы которой удовлетворяют указанным условиям, называется стохастической. Последнее условие в виде суммы элементов каждой строки матрицы вероятностей переходов, равной единице, означает, что в момент времени k t случайный процесс с вероятностью единица выполнит переход в одно из n возможных состояний, включая то же самое состояние, из которого этот переход осуществляется, то есть процесс может остаться в том же состоянии. Для случайных процессов с непрерывным временем время между переходами из одного состояния в другое случайно. Это означает, что вероятность перехода из одного состояния в другое не может быть задана, поскольку вероятность такого перехода точно в произвольный момент времени t равна нулю. Для описания переходов между состояниями случайного процесса с непрерывным временем вместо вероятностей переходов вводится параметр, называемый интенсивностью перехода. |