ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 145
Скачиваний: 0
где £ — случайная величина, равномерно распределенная |
на [0, 1], |
что приводит к вычислению обратной функции |
|
Л = F -' (|). |
(7) |
Из (6) и (7) следует простой способ получения чисел, распре деленных согласно F (x). Надо взять равномерно распределенные случайные числа £ и подставить их в обратную функцию F~k Это даст искомые случайные числа г), подчиненные закону F (х). Ил люстрацией данного преобразования является рис. 7.2.
Рис. 7.2. Схема получения случайных чисел г|. распределенных по произ вольному закону F(x), на основе чи сел £, равномерно распределенных на
[О, 1]
Для получения чисел, подчиненных экспоненциальному распре делению F ( x )~ 1—е-Ъг, надо пользоваться соотношением (7), что дает
л==_ J _ i n ( l _ g )
Л
или равносильное ему соотношение
1]= - у 1п£’
так как 1—£ тоже распределено равномерно на [0, 1]. Непосредст венно отсюда получаем простой метод моделирования нестацио нарного пуассоновского процесса с кусочно-постоянной интенсив ностью. На рис. 7.3 показан пример моделирования пуассоновско-
Рис. 7.3. Схема моделирования нестационарного пуассо новского процесса
го процесса с к — 2 в течение одной единицы времени и с 1 = 3 |
в |
течение второй единицы времени. Моделируем процесс с ^,= 1 |
в |
течение пяти единиц времени, а потом методом подобия отобража ем па две единицы с интенсивностями к = 2 и А.=3 соответственно.
141
Подобным образом можно моделировать процесс с любой функ
цией A,(t).
Кроме экспоненциального распределения с постоянными или зависящими от времени параметрами, встречаются также распре деления Эрланга с плотностью
чЛ ..ft—1«—X.v
р Л х , К ) = |
(А _ |
1)|------ . |
|
|
(8) |
где k — целое, |
положительное, А>0 |
н гиперэкспоненцнальное рас |
|||
пределение |
|
|
|
|
|
F (х) = Pie |
>M* + |
• • •+ pk е ^ |
, |
|
|
^ > 0 , х > 0 , рг > 0 |
|
|
О) |
||
|
|
1= 1 |
|
|
|
Для получения (8) надо брать сумму k чисел, |
каждое из которых |
||||
подчиняется распределению е~х х, а |
в случае |
(9) |
брать числа |
||
подчиненные е_ х х, с 'вероятностями ри i= 1, |
к. |
полученной на |
|||
В случае эмпирической функции распределения, |
|||||
основе статистических данных, вычисление обратной функции со
гласно (7) |
сводится к случайному выбору одного из табличных |
|||
значений. |
Например, пусть имеется эмпирическое |
распределение |
||
длительности обслуживания: |
|
|
|
|
Частота |
Длительность обслуживания |
|||
0,1 |
30 |
с |
|
|
0,25 |
45 |
» |
|
|
0,4 |
1 |
мин |
|
|
0,15 |
1 |
» |
1 5 с |
|
0,1 |
1 |
» |
30 |
» |
•Тогда при данном равномерно распределенном случайном чис ле имеем следующие правила выбора:
т)= 30 |
с |
|
> если |
0 < £ < 0 ,1 ; |
|
45 |
» |
|
> |
» |
0,1 < £ < 0 ,3 5 |
1 |
мин |
15 |
j |
» |
0,35<|<0,75 |
1 |
» |
с, |
» |
0,75 < | < 0 ,9; |
|
1 |
» |
30 |
», |
» |
0,9< | < 1 . |
Неудобством такого подхода является необходимость проверки последовательности логических условий. Во избежание этого мож но поступить следующим образом. Составим таблицу из двадцати строчек: в первых двух строчках запишем 30 с, в следующих пя ти 45 с, далее 8 раз 1 мин, 3 раза 1 мин 15 с и 2 раза 1 мин 30 с; равновероятным выбором одной из двадцати строчек получаем случайные числа о данным эмпирическим распределением. Недо статок метода — увеличение числового массива.
Такой же прием можно использовать, чтобы получить числа, ра спределенные согласно произвольной функции распределения F (x).
142
Во избежание необходимости многократно решать ур-нне (7) мож но заранее решить его для некоторого набора значений х и соста вить таблицу. Наиболее «простой вьибор из таблицы — равновероят ный, который описан выше. Чтобы составить таблицу из <N чисел, воспроизводящих распределение F (x ), надо выбрать такие лщ ..
л'ль при которых
X
X
7.3.АЛГОРИТМЫ МОДЕЛИРОВАНИЯ КОММУТАЦИОННЫХ СИСТЕМ
1.Три алгоритма моделирования полнодоступного пучка с потерями
Выбор алгоритмов моделирования связан с желанием удов летворить двум противоречивым требованиям: за минимальное ма шинное время получить статистические оценки максимальной точ ности. На практике, конечно, корректно поставить одно требование, например:' получить наиболее точные оценки характеристик си стемы за данное машинное время и построить доверительный ин тервал этих сценок.
Рассмотрим три подхода к статистическому моделированию си стем массового обслуживания на примере о-линейного полнодоступиого пучка с потерями и покажем, как на основе учета веро ятностных свойств системы можно упростить программу моделиро вания.
Моделирование истинного процесса обслуживания. Пусть на пучок поступает поток вызовов с ограниченным последействием, функцию распределения между двумя последовательными вызова ми обозначим через A (t). Пусть времена обслуживания являют ся взаимно независимыми случайными величинами с функцией ра спределения B (t). Требуется найти оценку среднего числа занятых линий.
Программа статистического моделирования такой системы со держит: подпрограммы реализации случайных величин согласно функциям распределения A (t) и B (t); одну ячейку для хранения текущего времени системы, которое растет случайными скачками согласно функции распределения A (t), и v ячеек для хранения по следнего момента освобождения каждой из v линий. Проиллюст рируем этот алгоритм на примере трехлинейного пучка (рис. 7.4). Через |i, £2, . . . обозначены расстояния между последующими вы
зовами, распределенные |
согласно A (t); длительности обслужива |
|
ния (разговора) тр, тр,. . . |
'подчинены закону В (t). Поясним работу |
|
алгоритма моделирования в момент поступления |
пятого вызова. |
|
В этот момент текущее |
время ^о='|1+ ? 2+ |з+ |4; |
при 'поиске сво- |
143
бодной литии с наименьшим номером (упорядоченный поиск) сра вниваем ближайший (последний) момент освобождения линии + i= 1, 2, 3, с. /0:
Hi = + (U + ^3 + + ^ ^о; ^2 = + Ч2 ^о’> ^3 =
=+ ^2 + Чз > По
следовательно, пятый вызов теряется. Шестой вызов занимает вто рую линию и т. д.
3-я линия |
|
|
Ь |
|
I |
|
|
|
|
L— ——р------------------------------ |
|
| |
|
|
|
|
|
|
|
|
|
|
|
2-ялиния----------- |
х//// / / / / / / / / / //////\ |
|
—J------------------ |
|
|||
|
|
|
|
|
I |
|
|
|
9, |
|
м |
т |
\Ъ |
п |
|
1-я линия V M W M 7m |
I |
|
|||||
|
|
|
|
|
№ |
4 4 |
|
|
|
|
|
|
I |
|
|
__________' |
| |
' |
| _____J------- |
4 |
1------------ |
||
о |
$} |
h |
*з |
4 / |
|
* |
|
ios Si+h + b + h
Рис. 7.4. Временная диаграмма работы трехлинейном системы
Моделирование марковского процесса (при экспоненциальных законах). Предположим, что
А (0 - e 'w, t > 0, B(t) = е- ', t> 0.
Тогда действие у-линейной системы с потерями описывается мар ковским процессом x(t) (его состояния принимают значения: 0, 1, 2, v). Почти всякая траектория марковского процесса устроена таким образом, что время пребывания gi в £-м состоянии подчиня ется экспоненциальному распределению с параметром X-j-i, т. е.
P {h < 0 = е- (Х+1) |
(10) |
В момент выхода из этого состояния осуществляется переход в со стояние £+1 с вероятностью
X
X “J- i |
( п ) |
|
и в состояние i— 1 с вероятностью
4t |
( 12) |
|
X+ / |
При i= v возможен переход только в состояние у— 1 с вероят ностью, равной 1 (рис. 7.5а). Отсюда следует, что при воспроиз
144
ведении действия системы надо моделировать два случайных ме ханизма: 1) время пребывания согласно (10) и 2) вероятности пе реходов согласно (И ) и (12). Следовательно, нужны: программа реализации случайных величин, подчиняющихся экспоненциально му распределению (10); программа получения равномерно распре деленных случайных чисел для выбора направления скачков по
а) |
|
А |
ю |
|
А_ |
|
|
'A+i |
i+1 ‘ |
|
|
i+1 |
|
i |
' A + i |
||
|
|
- |
|||
i |
|
|
|
|
|
Н |
|
1 |
L-1 |
|
L |
1 |
|
' A + i |
|||
|
A + i |
|
|
||
|
|
|
|
|
|
|
|
7 |
|
|
|
Рис. 7.5. Элементы траекторий марковского процесса: |
временами |
||||
а) |
со случайными и б) |
с детерминированными |
|||
пребывания в состояниях |
|
|
|
||
(11) и (12); ячейки для фиксации текущего времени системы, ко торое меняется скачками согласно случайным временам пребыва ния в последовательных состояниях, и v разрядов (а не v ячеек!) для записи номеров занятых линий или одна ячейка для записи числа занятых линий. Такой подход дает существенную экономию машинной памяти, что особенно важно при моделировании слож ных систем.
Моделирование вложенной цепи Маркова. Из анализа свойств траектории марковского процесса x(t) следует, что при вычисле нии оценки среднего числа занятых линий случайные времена пре бывания в отдельных состояниях можно заменить на их средние значения. Действительно, пусть взяли траекторию процесса x(t) до момента TN, т. е. до момента N-го скачка. Цель — вычислить
х1
Mf ( TN) = ^ ~ j f[x(t)]dt, |
(13) |
о
где
f[x(t)] = i, если x(t) = i, i = 0, 1, • ■ •, v.
Функционал (13) представляет собой случайную величину, завися щую от выборочной траектории процесса x(t). При замене — случайного времени пребывания в состоянии i на его среднее зна
чение — (см. рис. 7.5б), что следует из (10), среднее значение
функционала (13) сохраняется неизменным, а дисперсия его су щественно уменьшается, так как устраняется один из двух случай ных механизмов, порождающих траекторию x(t), а именно, слу чайные распределения (10). Уменьшение дисперсии является пер вым преимуществом такого подхода к статистическому моделиро-
145
ванию, а отсутствие необходимости моделировать случайные вре мена пребывания — вторым. Оба преимущества подтверждаются результатами вычислений, приведенными в [155].
2.Модифицированный марковский процесс
Вдальнейшем через x(t) обозначим модифицированный мар ковский процесс, получаемый из x(t) заменой Случайных времен пребывания в отдельных состояниях на их средние значения. Для
перехода к процессу x(,t) в общем случае необходимо, чтобы сис тема описывалась марковским процессом x(t) с непрерывным вре менем ,и дискретным множеством состояний. Пусть дан однород ный марковский процесс x(t) с дискретным множеством состояний
5, |
определяемый матрицей интенсивностей перехода Л = ||аг.у||, х, |
у £ |
S. Траектории процесса x(t) являются ступенчатыми функция |
ми и имеют простой вероятностный смысл. Если в момент t про цесс x(t) перешел |(или уже находится) в состояние х, то время пребывания в состоянии tx является случайной величиной, кото рая подчиняется экспоненциальному закону:
P{tx > z } = 7 ^ . |
(14) |
В момент выхода t-\-4x процесс переходит в состояние у |
с вероят |
ностью |
|
Рху = — — — , у ф х , y e S . |
(15) |
--- а хх
Величины рху являются переходными вероятностями вложенной цепи Маркова. Следовательно, на процесс x(t) можно смотреть как на марковскую цепь с присоединенными случайными величи нами. В состоянии х присоединенной случайной величиной считаем tx — случайное (время пребывания в этом состоянии.
Результатом моделирования обычно является среднее значение интеграла некоторой функции И х)> определенной над случайным процессом x (t):
|
т |
|
M,{T) = |
± r ^ j[x{t))dt. |
(16) |
|
о |
|
При переходе от x(t) « x(t), т. е. при замене случайных времен |
||
пребывания |
в состояниях tx их средними значениями— -— , |
ме- |
|
---аХХ |
|
няется распределение функционала (16). Если оцениваются такие величины, как среднее число занятых линий, среднее время пребы вания в каком-то состоянии, линейная комбинация средних вре мен пребывания по состояниям (оценка вероятности потерь по вре
мени), то при переходе от x(t) к x(t) сохраняется среднее значе ние оценки (16), но дисперсия оценки существенно понижается, т. е. повышается точность результатов моделирования, что под робно исследовано в [155].
J46