|
Определение характеристик случайного процесса
При статистическом моделировании операций нередко приходится встречаться со случаем, когда моделируемый случайный процесс является стационарными протекает неограниченно долго, имея не зависящие от времени вероятностные характеристики.
Рис. 6.16
В качестве примера рассмотрим работу n-канальной системы массового обслуживания с m местами в очереди,
граф состояний которой показан на рис.
6.16. Предположим, что поток заявок, переводящий систему из состояния в состояние (слева направо),
— стационарный, но не пуассоновский, например поток Пальма с
произвольным законом распределения f(t) интервала времени Т между
заявками. Время обслуживания
одной заявки тоже распределено не по показательному закону, а по
произвольному закону Если речь идет об изучении начального, нестационарного периода функционирования системы, то моделирование производится обычным способом — разыгрывается множество реализаций процесса, и нужные нам вероятностные характеристики, например, вероятность отказа, среднее число занятых каналов, среднее число заявок в очереди и др., находятся обработкой «опытного» материала как статистические средние по множеству реализаций. Однако, когда речь идет об изучении не переходного,
начального периода, а
стационарного, установившегося режима, достигаемого при При этом интересующие нас вероятностные характеристики случайного процесса могут быть получены не как средние по множеству реализаций, а как средние по времени для одной достаточной длинной реализации.
Рис. 6.17
Строго говоря, одной стационарности процесса для этого
недостаточно. Процесс
должен обладать еще так называемым эргодическим свойством. В элементарном истолковании это свойство состоит в том, что предельный режим, устанавливающийся
в системе через некоторое время ее работы, независим, от того,
каковы были начальные условия и
первоначальный период работы системы — каждая отдельная реализация
является как бы «полномочным представителем» всего класса реализаций. Это значит, что какую бы мы реализацию ни выбрали, при Можно привести пример процесса стационарного, но не обладающего эргодическим свойством. Пусть, например, рассматривается система с графом состояний, показанным на рис. 8.23. Все потоки событий, переводящих систему из состояния в состояние, считаем стационарными. Пусть в начальный момент t =0 система находится в состоянии S0; из него она может перейти либо в состояние S1 либо в S3. Перейдя в состояние S1 , система начнет «циркулировать» по состояниям S1 и S2. Благодаря стационарности потоков событий, вызывающих эту циркуляцию, через достаточное время вероятности p1(t) и p2(t) состояний S1 и S2 станут постоянными, а процесс циркуляции—стационарным:
Если же из состояния S0 система перешла не в S1 , а в S3, то она будет циркулировать не по состояниям S1 ,S2, а по состояниям S3, S4; вероятности этих состояний тоже будут стремиться к постоянным:
но уже к другим, чем р1 и р2. Таким образом, в приведенном примере процесс, протекающий в системе, будет стационарным, но не эргодическим, и его вероятностные характеристики существенно зависят от начального периода (начального поведения системы). Ясно, что моделирование такого процесса с помощью одной (хотя бы и очень длинной) реализации недостаточно для получения его вероятностных характеристик. К счастью, эргодические случайные процессы на практике встречаются чаще, чем неэргодические и, как правило, моделирование одной реализации дает возможность получить все вероятностные характеристики. В частности, эргодическими оказываются процессы, протекающие в системах, граф состояний которых относится к схеме «гибели и размножения», как показано, например, на рис. 6.16. Здесь система может через какое-то число шагов перейти из каждого состояния в каждое другое и «расщепления» процесса, подобного происходящему в системе с графом рис. 6.17, не происходит. Если система имеет бесконечное множество возможных
состояний, то, мы знаем, даже при стационарности всех потоков событий,
предельного режима при Доказать существование предельного режима мы, строго говоря, можем только для марковской системы, а моделирование методом Монте-Карло применяется, как правило, к системам не-марковским. Однако с помощью косвенных рассуждений часто и в этом случае удается убедиться в существовании предельного режима. Для пояснения изложенного рассмотрим пример, относящийся к моделированию методом Монте-Карло работы не-марковской системы массового обслуживания с очередью. Пример. Имеется двухканальная (n
=2) СМО с очередью.
Число мест в очереди т
= 3; заявка, пришедшая в момент, когда все три места в очереди заняты, получает отказ
и покидает систему. Поток заявок —
пальмовский, т. е. интервалы времени между заявками представляют собой независимые случайные величины,
распределенные по одному и тому же (непоказательному) закону f(t) (рис. 6.18). Время обслуживания одной заявки — также случайная
величина, распределенная по непоказательному закону Требуется, моделируя работу СМО методом Монте-Карло и
располагая только одной
длинной реализацией, оценить приближенно предельные характеристики системы (при — вероятности состояний (вероятности того,
что будут заняты · среднее число занятых каналов; · среднее время ожидания заявки в очереди; дисперсию времени ожидания заявки в очереди; · вероятность отказа (того, что заявка покинет СМО необслуженной).
Рис. 6.18 Рис. 6.19
Построить схему моделирования и схему обработки его результатов. Решение. Граф состояний системы имеет вид, показанный на рис. 6.20. Число состояний конечно; из каждого состояния можно перейти в каждое; потоки событий, переводящие систему из состояния в состояние, стационарны (хотя и не пуассоновские); из этого заключаем, что система обладает эргодическим свойством и моделирование по одной реализации возможно.
Рис. 6.20
Предположим для простоты, что в начальный момент (t= 0) система находится в состоянии S0 (свободна). Начнем моделирование с того, что разыграем на оси 0t поток заявок, т. е. ряд случайных точек t1 t2 t3 ... — моментов прихода соответствующих заявок — первой, второй и т.п. (рис. 6.21), Розыгрыш потока заявок производится следующим образом. Строится функция распределения случайной величины Т — интервала между заявками:
и разыгрывается значение случайной величины Т1, как это описано в п.2: для этого берется функция, обратная F, от случайного числа R от 0 до 1: Т1=F- '(R).
Рис.6.21
Рис. 6.22
Расстояние T1 откладывается от Изобразим процедуру моделирования с помощью наглядной схемы (рис. 6.22). Вверху мы поместим ось времени (0) с отмеченными на ней моментами поступления заявок. Ниже ее мы поместим еще пять осей: (1), (2), (3), (4), (5). На осях (1) и (2) мы будем изображать состояния первого и второго каналов (жирная черта — «занят», тонкая — «свободен»). На осях (3), (4), (5) мы будем изображать состояния первого, второго и третьего мест в очереди (жирная черта — «занято», гонкая— «свободно»). Все пять осей имеют тот же отсчет времени, что и ось (0). До момента t1, — прихода первой заявки — все каналы и все места в очереди свободны. В момент t1 приходит первая заявка и занимает первый канал. Сколько времени он будет занят — решается розыгрышем. Для этого мы подвергнем случайное число R (разумеется, новое) преобразованию Ф-1(R), где Ф — функция распределения времени обслуживания:
Первое разыгранное значение времени обслуживания т
обозначаем тх
и откладываем на оси (1) от точки с абсциссой t1 , отмечая его жирной линией (рис. 6.22). В момент
прихода t2 второй
заявки первый канал еще занят; заявка занимает второй канал. Разыграем еще
одно значение т, обозначим его Заявка t3, пришедшая в момент, когда оба канала заняты,
становится в очередь,
занимает в ней первое место (ось (3)) и ждет до того момента, когда
освободится один из каналов, В нашем случае раньше освобождается канал (2) — в этот
момент точка с оси (3) перескакивает на ось (2) — и снова разыгрывается время обслуживания Не будем продолжать подробное описание процедуры розыгрыша реализации — она достаточно ясна из рис. 6.22. На этом рисунке против каждого участка занятости канала (места в очереди) для удобства обработки проставлен номер заявки, занимающей это место; можно проследить, как заявка «путешествует» с последних мест в очереди на первые, затем — на обслуживание. Заявка, получившая отказ, отмечается звездочкой (она покидает СМО необслуженной). Предположим, что моделирование реализации продолжено
нами достаточно долго (настолько долго, что
влияние начальных условий уже перестает
сказываться). Посмотрим, как по этой реализации определить интересующие нас вероятностные
характеристики работы СМО. Вероятности
Очевидно,
При большом Т вероятности р0, р1 и р2 будут приближенно равны отношениям соответствующих времен к общему времени:
Заметим, что участок Т целесообразно отсчитывать не с самого начала процесса, где еще сказывается влияние начальных условий, а от более удаленного по времени момента 0', где влияние начальных условий уже практически перестает сказываться. Найдем вероятности
Среднее число занятых каналов
Среднее время ожидания заявки в очереди
и для каждой из них непосредственно подсчитаем время
ожидания в очереди
Если нас интересует не просто среднее время ожидания, а условное среднее время, вычисленное при условии, что заявка была принята к обслуживанию, то среднее арифметическое времен ожидания вычисляется не для всех заявок, а только для тех, которые были обслужены. Дисперсия времени ожидания найдется аналогичным образом, как среднее арифметическое квадратов времен, ожидания минус квадрат среднего времени ожидания:
Наконец, вероятность отказа найдется на большом участке времени Т как отношение числа N* заявок, помеченных звездочкой (получивших отказ), к общему числу N заявок, поступивших за это время:
|