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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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).

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

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

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

Основа этой задачи - случайный процесс прихода клиентов в систему обслуживания. Промежутки между приходами любой последовательной пары клиентов - независимые случайные события, распределенные по некоторому закону. Реальный характер этого закона может быть установлен лишь путем многочисленных наблюдений; в качестве простейшей модельной функции плотности вероятности можно взять равновероятное распределение в диапазоне времени от 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

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

Случайной функцией называют функцию неслучайного аргумен­та 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)

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

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

В табл. 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) запишется в виде