Моделирования случайных процессов

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

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

Существуют два типа алгоритмов, при помощи которых на ЭВМ могут вырабатываться дискретные реализации случайного процесса Алгоритмы первого типа предусматривают вычисление дискретной последовательности значений т. е. значений реализаций процесса в совокупности заранее выбранных моментов времени Шаг дискретизации обычно принимается постоянным: тогда из стационарности процесса следует стационарность последовательности

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

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

или в виде рекуррентного уравнения типа

Вид корреляционной функции воспроизводимого при помощи соотношений (49), (50) случайного процесса определяет набор значений коэффициентов .

Ко второму типу относятся алгоритмы, основанные на представлении моделируемых процессов в виде разложений

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

формуле (51). Алгоритмы моделирования случайных векторов в рамках корреляцион ной теории можно найти, например, в .

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

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

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

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

а коэффициенты

Шаг дискретизации и число членов ряда выбираются из условия

где - допустимая погрешность;

Моделирование стационарных случайных процессов с дробно-рациональной спектральной плотностью. Для моделирования случайных процессов с дробно-рациональной спектральной плотностью (см. табл. 1, процессы № 3, 4, 7, 8) вида

где полиномы относительно порядка соответственно эффективным является алгоритм типа (50). Спектральная плотность последовательности

может быть приведена к виду

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

Моделирование случайных процессов с использованием канонического разложения. Для стационарных гауссовских случайных процессов справедливо разложение, аналогичное (19):

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

Здесь гауссовские случайные величины со следующими вероятностными характеристиками:

Число членов ряда (58) выбирается из условия

Наряду с (58) можно использовать разложение

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

Разложения (58) и (59) удобно использовать для получения дискретных реализаций случайных процессов в неравноотстоящих точках.

Другие методы моделирования случайных процессов. Во многих случаях эффективным оказывается метод моделирования, основанный на использовании разложения

Здесь случайные величины с совместной плотностью вероятности

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

Наряду с (60) можно использовать разложение

Здесь случайные величины с совместной плотностью вероятности

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

Здесь - случайные числа, равномерно распределенные на интервале (0,1), которые вырабатываются на ЭВМ с помощью программных датчиков. Моделирование реализаций выполняют одним из методов моделирования случайных величии с заданным законом распределения. Соответствующие алгоритмы можно найти, например, в .

В табл. 2 приведены наиболее распространенные типы корреляционных функций стационарных случайных процессов и соответствующие им моделирующие алгоритмы.

Методы скользящего суммирования для моделирования случайных полей. Алгоритмы этого типа связаны с преобразованием однородного дельта-коррелированного поля в поле с заданной корреляционной функцией Это преобразование имеет вид

Функция Грина находится из уравнения

(см. скан)

Дискретные реализации поля воспроизводятся при помощи формулы скользящего суммирования

Здесь - константа, определяемая выбором шага дискретизации; - дискретные значения поля реализации которого воспроизводятся по формуле типа (52).

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

В табл. 2.2 даны типы корреляционных функций и энергетических спектров моделируемых процессов и соответствующие им алгоритмы. Ниже даются необходимые пояснения.

№ по порядку	Корреляционная функция
	Аналитическое выражение

Таблица 2.2.

Энергетический спектр
Аналитическое выражение

Продолжение таблицы 2.2.

№ по порядку	Корреляционная функция
	Аналитическое выражение

Продолжение таблицы 2.2.

Энергетический спектр
Аналитическое выражение

Продолжение таблицы 2.2.

№ по порядку	Моделирующий алгоритм	Параметры алгоритма
		Целая часть числа , .

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

Случайные процессы с корреляционными функциями, помещенными в таблице под № 1-5, относятся к классу случайных процессов с рациональной спектральной плотностью. Для моделирования таких процессов наиболее удобным является применение разностных уравнений (§ 2.3), что приводит к алгоритмам, не имеющим методической погрешности и сводящимся к простым рекуррентным соотношениям. Алгоритмы № 1-5 получены этим способом.

Алгоритмы № 1 и 2 для моделирования процессов с экспоненциальной и экспоненциально-косинусной корреляционными функциями уже рассматривались в § 2.3 и пояснений не требуют.

Алгоритмы № 2-5 одинаковы и отличаются лишь значениями параметров , нахождение которых в каждом конкретном случае сводится к вычислениям по формулам, приведенным в табл. 2.2. При выводе выражений для вычисления параметров рекуррентных формул в алгоритмах № 3-5 использовались преобразования, рассмотренные в § 2.3 на примере экспоненциально-косинусной корреляционной функции: спектральная плотность последовательности для каждого типа корреляционной функции записывалась согласно (2.51), суммирование соответствующих бесконечных в обе стороны рядов осуществлялось по таблицам односторонних дискретных преобразований Лапласа , а факторизация числителей полученных дробно-рациональных спектральных функций производилось путем разложения полиномов на множители (полиномы имели порядок не выше второго) с последующим использованием корней полиномов согласно выражениям (2.61) и (2.62). Знаменатели спектральных функций оказывались автоматически факторизованными.

Для моделирования случайных процессов № 6-8, которые не относятся к классу процессов с рациональной спектральной плотностью, был применен метод скользящего суммирования как наиболее эффективный в данном случае.

Согласно алгоритмам № 6-8 последовательность получается методом скользящего суммирования последовательности с весом . Выражения для весовых коэффициентов были получены путем интегрирования энергетических спектров процессов по формуле (2.12). При этом полагалось, что частота дискретизации для случайного процесса № 6 [процесс с равномерным в полосе спектром] больше или равна и . Относительно процессов № 7, 8 предполагалось, что частота дискретизации достаточно велика, так что верхний предел в интеграле (2.12) можно принять равным бесконечности. Поэтому выражения для коэффициентов в алгоритмах № 7, 8 следует применять при . Замена конечного предела бесконечным позволила в данном случае свести интегралы типа (2.12) к табличным .

Алгоритмы № 6-8 являются приближенными, однако при увеличении параметра методическая погрешность может быть сделана пренебрежимо малой. При выбранных значениях и погрешность метода легко оценивается путем свертки весовых коэффициентов. Пример вычисления коэффициентов и расчета погрешности метода для случайного процесса с корреляционной функцией № 8 был приведен ранее в § 2.2. В этом же параграфе дано описание алгоритма для моделирования случайного процесса № 9 [см. алгоритм (2.48)].

Алгоритмы, приведенные в табл. 2.2, были подвергнуты практической проверке. Проверка производилась путем выработки на ЦВМ реализаций моделируемых случайных процессов длиной в 1000 дискрет при и при заданных значениях параметров и . По этим реализациям вычислялись выборочные корреляционные функции, которые сравнивались с заданными корреляционными функциями. Исходные независимые случайные числа вырабатывались по стандартной программе датчика нормальных случайных чисел для ЦВМ М-20.

При выработке начальных значений реализаций случайных процессов № 1-5 в качестве брались выборочные значения независимых нормальных случайных чисел с параметрами (0, 1).

На рис. 2.5 показаны начальные участки реализаций длиной в 400 дискрет некоторых случайных процессов из табл. 2.2; для удобства реализации изображены непрерывной линией. Рядом с реализациями изображены заданные корреляционные функции (сплошная линия) вместе с корреляционными функциями, вычисленными на ЦВМ по этим реализациям (пунктир). Графики помечены теми же номерами, что и корреляционные функции в табл. 2.2. Значения параметров и . выбраны так, чтобы интервалы корреляции у всех моделируемых процессов были примерно одинаковыми. Из рисунка видно хорошее совпадение заданных и выборочных корреляционных функций.

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

Между реализациями № 2 и 3, а также между реализациями № 6, 7 можно заметить определенное сходство, которое объясняется тем, что реализации формировались на ЦВМ путем преобразования одной и той же дискретной реализации белого шума.

В начале реализаций № 2, 3 видны довольно большие отрицательные выбросы. Эти выбросы являются результатом искажения начальных участков моделируемых процессов из-за переходного процесса. Действительно, начальные условия выбраны так, что только случайные процессы № 1 и № 5-9 являются с самого начала стационарными.

Для того чтобы избавиться от переходного процесса при моделировании случайных процессов № 2-4, нужно при вычислении их начальных значений в качестве вместо независимых случайных чисел, как это было принято выше, взять четырехмерный случайный вектор с корреляционной матрицей

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

Известно, например, что при суммировании нескольких независимых стационарных нормальных случайных процессов образуется стационарный нормальный случайный процесс, корреляционная функция которого равна сумме корреляционных функций слагаемых. Отсюда, если корреляционная функция процесса является суммой двух или более корреляционных функций из табл. 2.2, то дискретные реализации этого процесса можно формировать путем суммирования двух или более независимых реализаций, получаемых по приведенным алгоритмам. Если, например, корреляционная функция моделируемого процесса имеет вид

то алгоритм для формирования его дискретных реализаций запишется в виде

То случайный процесс

где , преобразовать реализации и в реализацию случайного процесса с корреляционной функцией (2.83).

Для вычисления дискретных тригонометрических функций и целесообразно воспользоваться рекуррентным алгоритмом (1.3), тогда алгоритм (2.84) запишется в виде

Моделирование случайных процессов - мощнейшее направление в современном математическом моделировании.

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

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

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

Метод имитационного моделирования: моделирование систем массового обслуживания, задачи АСУ, АСУП и АСУТП, задачи защиты информации, моделирование сложных игровых ситуаций и динамических систем.

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

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

Другие методы: вероятностные методы распознавания образов, модели адаптации, обучения и самообучения.

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

Для не слишком требовательного пользователя обычно достаточны возможности датчика (генератора) случайных чисел, встроенного в большинство языков программирования. Так, в языке Паскаль есть функция random, значения которой - случайные числа из диапазона . Ее использованию обычно предшествует использование процедуры randomize, служащей для начальной "настройки" датчика, т.е. получения при каждом из обращений к датчику разных последовательностей случайных чисел. Для задач, Решение которых требует очень длинных некоррелированных последовательностей, вопрос осложняется и требует нестандартных

1. Особенности имитационного моделирования производственных систем

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

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

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

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

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

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

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

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

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

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

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

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

Дальнейшие пути имитации

Имитировать – значит приближаться к реальным объектам с конкретными (реальными) законами поведения, добавляя в процесс случайность.

Дифференциальные уравнения все усредняют начисто. Дифференциальные уравнения принципиально детерминированы. Они очень хороши, потому что дают интегральную характеристику (в целом).

Но это лишь первый шаг на пути исследования реальных систем. В реальной системе исследователя интересуют частности.

1-й путь. Переход к разностным уравнениям (этот способ активно использовался для разработки численных методов решения ДУ). Метод называется дискретизация процесса.

Имеем систему ДУ

.

Заменяем

бесконечно малый промежуток на малый.

Вычисляем каждое следующее значение через предыдущие.

Здесь надо иметь в виду, что коэффициенты уже имеют другую размерность (и смысл) и зависят от размера промежутка времени, через которые производится пересчет значений.

Реализация дискретного процесса в среде MVS – использование узла с пустым поведением и дуг циклического перехода.

Рис. 1. Реализация дискретного процесса

Временн"ая диаграмма дискретного процесса имеет вид кусочно-постоянной функции со скачками (разрывами) в точках t i пересчета значений.

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

2-й путь. Описание локальных законов поведения

Разделим закон изменения количества продукта на два поведения: закон убыли продукта, закон роста продукта

Аналогично для ресурса

Рис. 2. Структурная модель с локальными законами

3-й путь. Добавление случайности

Чтобы ввести случайность, будем на каждой итерации вычислять новые значения коэффициентов как некие случайные числа, распределенные, в первом приближении, по нормальному закону с заданными средним (мат. ожиданием) и дисперсией.

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

И за счет вероятностей мы сможем настраивать и исследовать эту модель.

Таким образом, основные пути приближения модели к реальной системе:

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

Комбинация всех этих способов – и есть имитационное моделирование (самое настоящее).

Сейчас используют другое современное название – агентное моделирование . На самом деле это классическое статистическое моделирование.

Есть два подхода к моделированию.

Первый: от объекта к модели (определяем состояние реальной системы в начальный момент времени и моделируем, что будет дальше).

Может быть обратная ситуация: от модели к объекту (строим модель, исследуем, при каких вероятностях и начальных значениях картина будет устойчивой или неустойчивой, и выдаем рекомендации)

Таким образом имеет место цикл Данные Модель Обработка Новые данные.

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

На 1-м такте есть первоначальное случайное распределение вероятности нахождения элемента в том или ином состоянии.

Циклически повторяем процесс. Вот это называется агентное или имитационное моделирование.

При этом мы получаем дискретные (кусочно-постоянные) функции.

Моделирование случайных процессов

Процессы Маркова

Функция Х(t) называется случайной , если ее значение при любом аргументе является случайной величиной.

Случайная функция Х(t) , аргументом которой является время, называется случайным процессом .

Случайный процесс, протекающий в какой-либо системе S , называется марковским (или процессом без последействия), если он обладает следующим свойством: для любого момента времени t 0 , вероятность любого состояния системы в будущем (при t > t 0 ) зависит только от ее состояния в настоящем (при t = t 0 ) и не зависит от того, когда и каким образом система S пришла в это состояние.

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

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

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

Классификация марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции Х(t) и параметра t .

Различают следующие основные виды марковских случайных процессов:

• с дискретными состояниями и дискретным временем (цепь Маркова);
• с непрерывными состояниями и дискретным временем (марковские последовательности);
• с дискретными состояниями и непрерывным временем (непрерывная цепь Маркова);
• с непрерывным состоянием и непрерывным временем.

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

Граф состояний

Марковские процессы с дискретными состояниями удобно иллюстрировать с помощью так называемого графа состояний, где кружками обозначены состояния S i системы S , а стрелками – возможные переходы из состояния в состояние. На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные задержки в прежнем состоянии изображают «петлей», т. е. стрелкой, направленной из данного состояния в него же.

Рис. 3. Граф состаояний

Состояний может быть конечное число или бесконечное, но счетное.

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью . Для такого процесса моменты t 1 , t 2 , …. когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t, а номер шага 1, 2,...,k ,... Случайный процесс в этом случае характеризуется последовательностью состояний S(0), S(1), S(2),..., S(k),. .., где S(0) - начальное состояние системы (перед первым шагом); S(1) – состояние системы после первого шага; S(k) – состояние системы после k-го шага...

Последовательность состояний S(1), S(2),..., S(k) можно рассматривать как последовательность случайных событий.

Обозначим вероятность находиться после k -го шага в состоянии S k . Тогда

Практический интерес представляют системы с конечным числом состояний S i (i =1,…, n).

Примеры конечных цепей Маркова

Пример 1. Модель 4 «Гараж»

Автомобили в гараже могут находиться в двух состояниях: рабочее (1) и ремонт (2).

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

• автомобиль был исправен и остался исправным;
• автомобиль был неисправен и стал исправным;
• автомобиль был исправен и стал неисправным;
• автомобиль был неисправен и остался неисправным.

Нарисуем граф состояний и переходов этой системы

Рис. 4

p 11 , p 12 , p 21 , p 22 , – вероятности переходов из состояния в состояние.

Если тип автомобилей одинаковый, то все вероятности будут одинаковы для всех автомобилей.

Представим вероятности в виде матрицы

Называется матрицей переходов .

Свойства матрицы переходов

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из i -го) состояния, в том числе и переход в самое себя.
2. Элементы столбцов показывают вероятности всех возможных переходов системы за один шаг в заданное (j -е) состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец – в состояние).
3. Сумма вероятностей каждой строки равна единице, т. к. переходы образуют полную группу несовместных событий.
4. По главной диагонали матрицы переходных вероятностей стоят вероятности P ii того, что система не выйдет из состояния i , а останется в нем.

Введем вектор – k =0,1,2,3…функция, которая вычисляет вероятность на каждом шаге (такте) оставаться в одном из двух состояний.

Вектор вероятностей начального состояния для каждой машины . Например, можно считать, что в начальном состоянии машина достоверно исправна, то .

Опишем этот процесс в виде дерева

Кроме этого на первом такте добавляется (задается) вероятность начального состояния.

Если зафиксировать k =const, то нам известны все конечные исходы системы. Если вероятности p ij =const, то этот процесс и есть цепь Маркова. В данной модели реализуется бесконечный процесс. При длительном функционировании системы может оказаться, что вероятности состояний стремятся к некоторому числу. Эти предельные вероятности называют вероятностями установившегося процесса . При моделировании бесконечных процессов интерес представляет вычисление вероятностей установившегося процесса.

Пример 2. Модель 5 «Кубик и монеты»

Есть две монеты А и Б и кубик К. У одной есть герб и решка, а у другой обе решки.

Игра: выбираем случайным образом монетку и кидаем. Если выпал герб бросаем кость, если выпала решка, бросаем ту же монетку снова.

Нарисуем граф состояний игры

Пространство исходов конечно. Все вероятности фиксированы. Это цепь Маркова. В данной модели видно, что процесс рано или поздно заканчивается, если случайным образом выбрана монета А. Если же была выбрана монета Б, то процесс бесконечный.

Задание для самостоятельной работы

Составить матрицу переходов для данной системы.

Пример 3. Модель 6 «Игра»

Имеется 5 состояний. В некоторый момент частица (шарик) находится в одном из состояний S i . За каждый шаг частица может перейти только в соседнее состояние: в S i-1 с вероятностью p , в S i+1 с вероятностью q . При этом (как известно) p + q =1. Если частица попадает в концевое состояние, то там остается навсегда. Вероятности фиксированы. В состояниях S i , i =2,3,4 частица не может остаться.

Построим матрицу P , в которой описаны вероятности перехода частицы из состояния S i в состояние S j .

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

Пример 4. Модель 7 «Обучение в вузе»

Процесс обучения в вузе 4 года обучения (бакалавриат). Выделим следующие состояния

6.1. ТЕХНИКА СТОХАСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

Понятие «случайный» - одно из самых фундаментальных как в математике, так и в повседневной жизни. Моделирование случайных процессов - мощнейшее направление в современном математическом моделировании.

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

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

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

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

Итак, пусть в функционале модели значения некоторых входных параметров определены лишь в вероятностном смысле. В этом случае значительно меняется сам стиль работы с моделью.

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

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

Рассмотрим вначале генерацию чисел равновероятно распределенных на некотором отрезке. Большинство программ - генераторов случайных чисел - выдают последовательность, в которой предыдущее число используется для нахождения последующего. Первое из них - начальное значение. Все генераторы случайных чисел дают последовательности, повторяющиеся после некоторого количества членов, называемого периодом, что связано с конечной длиной машинного слова. Самый простой и наиболее распространенный метод - метод вычетов, или линейный конгруэнтный метод, в котором очередное случайное число x n определяется «отображением»

где a , с , m - натуральные числа, mod - так называемая, функция деления по модулю (остаток от деления одного числа на другое по модулю). Наибольший возможный период датчика (7.69) равен т; однако, он зависит от а и с. Ясно, что чем больше период, тем лучше; однако реально наибольшее m ограничено разрядной сеткой ЭВМ. В любом случае используемая в конкретной задаче выборка случайных чисел должна быть короче периода, иначе задача будет решена неверно. Заметим, что обычно генераторы выдают отношение DIV_ADBLOCK304">

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

Рис. 7.54. Вид гистограммы для равномерно распределенных на отрезке чисел при достаточно большой выборке

Понятно, что при большом числе испытаний высоты столбиков должны быть почти одинаковыми. Однако, этот критерий является необходимым, но не достаточным; например, он «не замечает» даже очень короткой периодичности Для не слишком требовательного пользователя обычно достаточны возможности датчика (генератора) случайных чисел, встроенного в большинство языков программирования. Так, в PASCAL есть функция random, значения которой - случайные числа из диапазона , легко получить числа из произвольного интервала [а, b ].

X = a + (b - a)∙r.

Более сложные распределения часто строятся с помощью распределения равномерного. Упомянем здесь лишь один достаточно универсальный метод Неймана (часто называемый также методом отбора-отказа), в основе которого лежит простое геометрическое соображение. Допустим, что необходимо генерировать случайные числа с некоторой нормированной функцией распределения f(x) на интервале [а, b ]. Введем положительно определенную функцию сравнения w(x) такую, что w(x) = const и w(x) > f(x) на [а, b ] (обычно w(x) равно максимальному значению f(x) на [а, b ]). Поскольку площадь под кривой f(x) равна для интервала [х, х + dx ] вероятности попадания х в этот интервал, можно следовать процедуре проб и ошибок. Генерируем два случайных числа, определяющих равновероятные координаты в прямоугольнике A BCD с помощью датчика равномерно распределенных случайных чисел:

x = a + (b - a)∙r, y = w∙r

и если точка М(х, у) не попадает под кривую f(x) , мы ее отбрасываем, а если попадает - оставляем (рис. 7.55). При этом множество координат х оставленных точек оказывается распределенным в соответствии с плотностью вероятности f(x) .

Рис. 7.55. Метод отбора-отказа. Функция w(x) = f max

Этот метод для ряда распределений не самый эффективный, но он универсален, прост и понятен. Эффективен он тогда, когда функция сравнения w (x ) близка к f(х) . Заметим, что никто не заставляет нас брать w (x )= const на всем промежутке [а, b ]. Если f(x) имеет быстро спадающие «крылья», то разумнее взять w (x ) в виде ступенчатой функции.

6.2. МОДЕЛИРОВАНИЕ СЛУЧАЙНЫХ ПРОЦЕССОВ В СИСТЕМАХ МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

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

Типичная задача: очередь к одному «продавцу». Рассмотрим одну из простейших задач данного класса. Имеется магазин с одним продавцом, в который случайным образом входят покупатели. Если продавец свободен, он начинает обслуживать покупателя сразу, если покупателей несколько, выстраивается очередь.

Вот аналогичные задачи:

Ремонтная зона в автохозяйстве и автобусы, сошедшие с линии из-за поломки;

Травмопункт и больные, пришедшие на прием по случаю травмы (т. е. без системы предварительной записи);

Телефонная станция с одним входом (или одной телефонисткой) и абоненты, которых при занятом входе ставят в очередь (такая система иногда практикуется);

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

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

Итак, на входе этой задачи случайный процесс прихода покупателей в магазин. Он является «марковским», т. е. промежутки между приходами любой последовательной пары покупателей - независимые случайные события, распределенные по некоторому закону. Реальный характер этого закона может быть установлен лишь путем многочисленных наблюдений; в качестве простейшей модельной функции плотности вероятности можно взять равновероятное распределение в диапазоне времени от 0 до некоторого Т - максимально возможного промежутка между приходами двух последовательных покупателей. При этом распределении вероятность того, что между приходами двух покупателей пройдет 1 минута, 3 минуты или 8 минут одинакова (если T > 8).