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

Краткие сведения

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

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

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

Такое распределение, конечно, малореалистично; реально для большинства процессов массового обслуживания функция распределения растет от t = 0, имеет при некотором значении t = τ максимум и быстро спадает при больших t, т.е. имеет вид, изображенный на рис. 7.6.

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

где λ - некоторая постоянная, п - произвольное целое.

Функции (35) имеют максимум при х = п/λ и нормированы.

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

Для примера в таблице в колонке А записаны случайные числа - промежутки между приходами клиентов (в минутах), в колонке В - случайные числа - длительности обслуживания (в минутах). Для определенности взято а max = 10 и b max = 5.

Рис. .6. Схематическое изображение плотности вероятности распределения времени между появлениями клиентов в системе массового обслуживания

Из этой короткой таблицы, разумеется, невозможно установить, какие законы распределения приняты для величин А и В. Остальные колонки предусмотрены для удобства анализа; входящие в них числа находятся путем элементарного расчета. В колонке С представлено условное время прихода клиента; D - момент начала обслуживания; Е - момент конца обслуживания; F - длительность времени, про­веденного клиентом в системе в целом; G - время, проведенное в очереди в ожидании обслуживания; Н - время, проведенное системой в ожидании клиентов (если их нет). Таблицу удобно заполнять по горизонтали, переходя от строчки к строчке. Так как начало обслуживания очередного клиента определяется либо временем его прихода, если система не занята, либо временем ухода предыдущего клиента, приведем для удобства соответствующие формулы (в них i = 1, 2, 3, ...):

с 1 = 0, с i+1 = с i + а i+1 ; d 1 = 0, d i+1 = max(c i+l , e i); (36a)

e 1 = b 1 e i = d i + b i ; f i = e i + c i ; g 1 = 0; g i+1 = f i+1 + b i+1 h 1 = 0; h i+1 = d i+1 - e i (36б)

Таким образом, при данных случайных наборах чисел в колонках А и В клиентам приходилось стоять в очереди (колонка G), и система простаивала в ожидании клиента (колонка Н).

При моделировании систем такого вида прежде всего возникает вопрос, какое среднее время приходится стоять в очереди? Ответить на него, кажется, несложно - надо найти

(37)

в некоторой серии испытаний. Аналогично можно найти среднее значение величины h. Труднее ответить на вопрос о достоверности полученных результатов; для этого надо провести несколько серий испытаний и использовать стандартные методы математической статистики (часто уместна обработка с помощью распределения Стьюдента).

Более сложный вопрос - каково распределение случайных величин G и Н при заданных распределениях случайных величин A и В? Качественный ответ на него можно попытаться получить, построив соответствующие гистограммы по результатам моделирования. Затем делается некоторая гипотеза о виде распределения и используются один или несколько статистических критериев проверки достоверности этой гипотезы.

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

Контрольные вопросы

1. Что такое «случайный процесс»?

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

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

4. Что такое «система массового обслуживания»? Приведите примеры.

5. В чем заключается метод Монте-Карло вычисления площадей плоских фигур? объемов тел?

6. Какие примеры случайных процессов Вы можете привести?

Темы для рефератов

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

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

Тема семинарских занятий

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

Лабораторная работа

1. При выполнении данной работы необходима генерация длинных последова­тельностей псевдослучайных чисел с заданным законом распределения вероятностей. Ее можно основывать на стандартном датчике равномерно распределенных случайных чисел, встроенном в применяемую систему программирования, с использованием одной из процедур пересчета данной последовательности в последовательность с нужным законом распределения (например, процедуру «отбор - отказ»).

2. Одна из центральных задач при моделировании случайных процессов - нахождение характеристик случайных величин, являющихся объектом моделирования. Главная такая характеристика - функция распределения. Ее вид можно качественно оценить по гистограмме, построенной в ходе моделирования, а гипотезу о функциональной форме проверить с помощью одного из стандартных критериев, используемых в математической статистике (например, критерия % 2). Однако это не всегда целесообразно, особенно если в задаче требуется определить лишь неко­торые характеристики случайной величины - чаще всего среднее значение и дисперсию. Их можно найти без моделирования самой функции распределения. При этом статистическая оценка достоверности результатов является обязательной.

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

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

Примерное время выполнения 16 часов.

Задание к лабораторной работе

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

Варианты заданий

Вариант 1

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

Вариант 2

Провести то же моделирование при пуассоновских законах распределения вероятностей входных событий: прихода покупателей и длительности обслуживания (при некотором фиксированном наборе параметров).

Вариант 3

Провести то же моделирование при нормальном законе распределения вероятностей входных событий: прихода покупателей и длительности обслуживания (при некотором фиксированном наборе параметров).

Вариант 4

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

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

Вариант 5

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

Вариант 6

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

Вариант 7

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

Вариант 8

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

Вариант 9

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

Вариант 10

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

Вариант 11

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

Вариант 12

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

Вариант 13

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

Вариант 14

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

Эта задача дала способ имитационному определению числа п. Действительно, если L = 2l, то . В ходе моделирования выполнить этот расчет.

Вариант 15

Разработать модель случайного одномерного блуждания (модель «пьяницы»). Блуждание задается по правилу: если случайное число из отрезка меньше 0,5, то делается шаг вправо на расстояние h , в противном случае - влево. Распределение случайных чисел принять равновероятным.

Решить задачу: какова вероятность при таком блуждании удалиться от начальной точки на п шагов?

Вариант 16

В условиях задачи из предыдущего варианта получить ответ на вопрос: какова вероятность «пьянице» вернуться через п шагов в начальную точку?

Вариант 17

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

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

Вариант 18

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

Вариант 19

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

Вариант 20

Реализовать модель плоского броуновского движения п частиц в прямоугольнике. Частицы считать шариками конечного размера. Удары частиц друг о друга и о стенки моделировать как абсолютно упругие. Определить в этой модели зависимость давления газа на стенки от числа частиц.

Вариант 21

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

Вариант 22

Реализовать имитационную модель системы «хищник - жертва» по следующей схеме.

«Остров» размером 20x20 заселен дикими кроликами, волками и волчицами. Имеется по несколько представителей каждого вида. Кролики в каждый момент времени с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов (за исключением участков, ограниченных береговой линией) или просто сидят неподвижно. Каждый кролик с вероятностью 0,2 превращается в двух кроликов. Каждая волчица передвигается случайным образом, пока в одном из соседних восьми квадратов не окажется кролик, за которым она охотится. Если волчица и кролик оказываются в одном квадрате, волчица съедает кролика и по­лучает одно очко. В противном случае она теряет 0,1 очка.

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

Если волк и волчица окажутся в одном квадрате и там нет кролика, которого можно съесть, они производят потомство случайного пола.

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

Вариант 23

Промоделировать процесс распространения инфекции стригущего лишая по участку кожи размером п x п (п - нечетное) клеток.

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

Проследить, как сказываются на результатах моделирования изменение разме­ров поля и вероятность заражения.

Вариант 24

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

Дополнительная литература

1. Бейли Н. Статистические методы в биологии: Пер. с англ. - М.: ИЛ, 1962.

2. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. - М.: Наука, 1966.

3. Саати Т. Элементы теории массового обслуживания и ее приложения: Пер. с англ. - М.: Сов. радио, 1991.

4. Шеннон Р. Имитационное моделирование систем - искусство и наука: Пер. с англ. - М.: Мир, 1978.

Тесты к главе 7

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

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

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

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

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

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

Вид корреляционной функции воспроизводимого при помощи соотношений (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).

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

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

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

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

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 года обучения (бакалавриат). Выделим следующие состояния

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

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

Введем следующие обозначения: Х(t) - случайный процесс; x i (t) - i-ая реализация процесса X(t); x i (t j) - мгновенное значение процесса Х(t), соответствующее i-ой реализации в j-ый момент времени. Совокупность мгновенных значений, соответству­ющих значениям различных реализаций в один и тот же момент времени t j , назовем j-ой последовательностью процесса Х(t) и обозначим х(t j). Из сказанного следует, что в качестве аргу­ментов случайного процесса могут выступать время и номер реа­лизации. В связи с этим правомерны два подхода к изучению свойств случайного процесса: первый основан на анализе мно­жества реализаций, второй оперирует множеством последователь­ностей - временных сечений. Наличие или отсутствие зависимости значений вероятностных характеристик случайного процесса от времени или номера реализации определяет такие фундаментальные свойства процесса, как стационарность и эргодичность. Стацио­нарным называется процесс, вероятностные характеристики кото­рого не зависят от времени. Эргодическим называется процесс, вероятностные характеристики которого не зависят от номера ре­ализации.

Случайный процесс называется нормальным (или гауссовским) процессом, если одномерные и двумерные законы распределения любых его сечений нормальны. Исчерпывающими характеристиками нормального случайного процесса является его математическое ожидание и корреляционная функция. У стационарного нормального случайного процесса МОЖ постоянно, а корреляционная функция зависит только от разности моментов времени, для которых взяты ординаты случайного процесса ( =t 2 -t 1). Для стационарного слу­чайного процесса при достаточно большом отклонение ординаты случайного процесса Х(t 2) от ее математического ожидания m x в момент времени t 2 становится практически независимым от значе­ния этого отклонения в момент времени t 1 . В этом случае корре­ляционная функция К(t), дающая значение момента связи между Х(t 2) и Х(t 1), при будет стремится к нулю. Поэтому К() может или монотонно убывать, как это изображено на рис.2.2, или иметь вид, представленный на рис.2.3. Функция ви­да (рис.2.2.), как правило, аппроксимируется выражениями:

(2.38)

а функция вида (рис.2.3.) - выражениями:

Рис.2.2. Рис.2.3.

Устойчивость стационарного случайного процесса во времени позволяет заменить аргумент - время - некоторой вспомогатель­ной переменной, которая во многих приложениях имеет размер­ность частоты. Такая замена позволяет значительно упростить выкладки и добиться большей наглядности результатов. Получае­мая функция (S()) называется спектральной плотностью стацио­нарного случайного процесса и связана с корреляционной функци­ей взаимно обратными преобразованиями Фурье:

(2.42)

(2.43)

Существуют и другие нормировки спектральной плотности, например:

(2.44)

На основе преобразований Фурье нетрудно получить, напри­мер, для случайного процесса с K(t) вида (2.38):

(2.45)

Стационарный случайный процесс, спектральная плотность которого постоянна (S(w)=S=const), называется стационарным бе­лым шумом . Корреляционная функция стационарного белого шума равна нулю при всех , что означает некоррелированность лю­бых двух его сечений.

Задача моделирования стационарного нормального случайного процесса (СНСП) может быть сформулирована как задача нахожде­ния алгоритма, позволяющего получить на ЭВМ дискретные реали­зации этого процесса. Процесс X(t) заменяется с заданной точ­ностью соответствующим процессом X(nDt) с дискретным временем t n = nDt (Dt- шаг дискретизации процесса, n- целочисленный ар­гумент). В результате случайному процессу x(t) будут поставле­ны в соответствие случайные последовательности:

x k [n]=x k (nDt), (2.46)

где k - номер реализации.

Очевидно, что произвольный член случайной последователь­ности x(nDt) можно рассматривать как случайную функцию его но­мера, т.е. целочисленного аргумента n и, таким образом, исклю­чить из рассмотрения Dt, что и учтено при записи (2.46). Кроме того, чтобы отличить целочисленный аргумент от непрерывноизме­няющегося, его заключают в квадратные скобки.

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

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

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

(2.47)

(2.48)

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