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

  Такими  примерами СФ являются: колебания  напряжения в электрической цепи, скорость движения автомобиля на участке  дороги с ограничением скорости, шероховатость  поверхности детали на определенном участке и т.д.

  Как правило, считают, что если аргументом СФ является время, то такой процесс  называют случайным. Существует и другое, более близкое к теории принятия решений, определение СП. При этом под случайным процессом понимают процесс случайного изменения состояний  какой-либо физической или технической  системы по времени или какому-либо другому аргументу.

  Нетрудно  заметить, что если обозначить состояние  и изобразить зависимость , то такая зависимость и будет случайной функцией.

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

  Кроме указанных выше примеров классификации  СП существует еще одно важное свойство. Это свойство описывает вероятностную  связь между состояниями СП. Так, например, если в СП вероятность  перехода системы в каждое последующее  состояние зависит только от предыдущего  состояния, то такой процесс называется процессом без последействия (рис.1).

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

   (1)

  Рис. 1. Схема процесса без последействия

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

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

  Выше  мы совершили незаметный терминологический  переход от понятия СП к “марковской цепи”. Теперь эту неясность следует устранить. Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

  Если  случайная последовательность обладает марковским свойством, то она называется цепью Маркова.

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

  Марковский  СП называется однородным, если переходные вероятности  остаются постоянными в ходе процесса.

  Цепь  Маркова считается заданной, если заданы два условия.

  1. Имеется совокупность переходных  вероятностей в виде матрицы:

   . (2)

  2. Имеется вектор начальных вероятностей

   , ….. (3)

  описывающий начальное состояние системы.

  Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е  состояние за один шаг процесса. Переходная матрица (2) обладает следующими свойствами:

  a) , (3a)

  б) .

  Матрица, обладающая свойством (3a), называется стохастической. Кроме матричной формы модель марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 2).

  Рис. 2. Ориентированный  взвешенный граф

  Вершины графа обозначают состояние  , а дуги- переходные вероятности.

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

  1. Невозвратное множество (рис. 3).

  Рис. 3. Невозвратное множество 

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

  2. Возвратное множество (рис. 4).

  Рис. 4. Возвратное множество

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

  3. Эргодическое множество (рис. 5).

  Рис. 5. Эргодическое множество

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

  4. Поглощающее множество (рис. 6)

  Рис. 6. Поглощающее множество

  При попадании системы в это множество  процесс заканчивается.

  Кроме описанной выше классификации множеств различают состояния системы:

  а) существенное состояние (рис.7): возможны переходы из в и обратно.

  Рис. 7. Существенное состояние

  б) несущественное состояние (рис. 8): возможен переход из в , но невозможен обратный.

  Рис. 8. Несущественное состояние

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

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

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

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

  Рис. 9. Классификация  марковских процессов

4. Математический  аппарат дискретных марковских цепей

  В дальнейшем рассматриваются простые  однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:

   (4)

  и называется уравнением Колмогорова-Чепмена.

  Уравнение Колмогорова-Чепмена относится к  классу рекуррентных соотношений, позволяющих  вычислить вероятность состояний  марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.

  Дальнейшие  математические соотношения зависят  от конкретного вида марковской цепи.

4.1. Поглощающие  марковские цепи

  Как указывалось выше, у поглощающих  ДМЦ имеется множество, состоящее  из одного или нескольких поглощающих  состояний.

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

   (5)

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

   (6)

  

  Такая форма позволяет представить  матрицу (6) в каноническом виде:

   (6а)

  где - единичная матрица;

   - нулевая матрица; 

   - матрица, описывающая переходы  в системе из невозвратного  множества состояний в поглощающее  множество;

   - матрица, описывающая внутренние  переходы в системе в невозвратном  множестве состояний.

  На  основании канонической формы (6а) получена матрица, называемая фундаментальной:

   (7)

  В матрице (7) символ (-1) означает операцию обращения, то есть

   (8)

  После соответствующих преобразований матрица (7) примет вид:

   (7а)

  Каждый  элемент матрицы (7а) соответствует  среднему числу раз попадания  системы в то или иное состояние  до остановки процесса (поглощения).

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

   (8а)

  где .

  Для иллюстрации приведем конкретный числовой пример: пусть известны значения переходных вероятностей матрицы  с одним поглощающим состоянием: ; ; ; ; ; ; ; .

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

  

  В данном случае

   ; ; ;

  Проделаем необходимые вычисления:

   ;

   ;

   .

  В данном случае компоненты вектора  означают, что если процесс начинается с состояния , то общее среднее число шагов процесса до поглощения будет равно 3,34 и, соответственно, если процесс начинается с состояния , то - 2,26.

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

  Так, если задать в нашем примере время  пребывания в состоянии  , а в состоянии - , то общее время до поглощения будет равно:

  

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