1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 58
Текст из файла (страница 58)
В случае й равно- вероятных исходов можно взять различные значения вектора из первых г знаков,где 2" '( . 16 ( 2", а в случае появления незакодированной 1 г-граммы повторить испытание (например, исполь- 0 ( 6) зовав следующие г знаков). Универсальный способ оолучения реализации слу- чайной величины $ с 0 та=)6(ер) х функцией распределения Г(х) по ю состоит в следующем. Пусть ф(е) = ийп (х: Р(х) ) ю).
1 Если функция у = =16(х) непрерывна н строго возрастает в любой точке, в которой опа больше О и меньше 1, то ф(х) — функция, обратная к Р(,),~ 302 ГЛ. 6. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ Тогда $=~>(ю) — случайная величина с функцией распределения Р(х). Действительно, события (ю <Р(х)) и Ц(в)<х) эквивалентны (рис. 7); остается заметить, что Р(ю(Р(х)) = Р(х). Пусть $ =До ..., $„) — н-мерный случайный вектор.
Распределение $ можно задать функциями распределения Р» (х), Р»э1» (х(хг), ..., Р» (» д (х(хм ..., х 1), где Р» (х) — функция распределения $О Р»э~», » (х) хм ...,ха,) — условная функция распределения $, при условии ~,=х;, »~ й. Случайную величину $, реализуют, как н в одномерном случае, используя для этого случайное число ю,.
Когда эо ..., $,, реализованы, то $, определяется тем же способом при Р (х) = =Р»,р,,...,»,,( )ь ° . 5,,). П р и м е р. Пусть случайный вектор До Э,) имеет плотность р(х, у), равную 2 при х > О, у ) О, х+ у (1, и равную О в противном случае. Тогда Р» (х) = 2х — х', 0 ( х ~ 1; Р; (» (х(р) = х/(1 — р), 0(х(1 — у.
Отсюда Помимо описанного способа, используются многие другие. Например, пусть  — случайная величина с плотностью р(х), причем р (х) дх = 1, р(х) -"- =с. Рассмотрим последовательность пар а (юо ии), (юн ю,), ... Пусть (ю,„-о ю.,„) — первая пара, для которой р(а+(Ь вЂ” а) ю,„,)» сон . Тогда положим $ = а+ +(Ь вЂ” а)ю,„-о Среднее число пар случайных чисел в расчете на одну реализацию $ равно (Ь вЂ” а)с. Суп»естэуют специальные приемы реализации наиболее употребительных распределений. Так, реализация величины $ с распределением, близким к нормальному, получается суммированием некоторого числа равномерных случайных чисел (используется центральная предельная теорема). Из экспоненциальной велиЧнны ( с плотностью †. е "М х ) О, и независимой от нее ю поз лучим две независимые величины $е $, со стандартным нормальным распределением по формуле $,=1~усоз2лю, $,=»(з1п2ню.
Эрланговская случайная величина реализуется как сумма независимых экспоненцпальных. Если Р(т) = Х р;Р; (х), где З б.и НЕКОТОРЫЕ КЛАССЫ СЛУЧАЙНЫХ ПРОЦГССОВ зоз ш ) (), Р,(х) — функции распределения, то можно либо вначале с помощью случайпого числа юа реализовать испытание, при гхм исходе которого перейти к реализации величины с распределением Р',(х) с помощью юаа либо проверить условие (за +...
+ Ра-а ~ юа ( Ра +... + Ра)а прп выполнении которого делается то же, что п в первом случае, г использованием того же ю,: юз = — (ю, — р, —... — р; т). Р, 3. Моделирование однородной цепи Маркова, Пусть Р = аар„.!а— матрица перехода цепи Маркова(тю п ) 0): РП = Р (у (ю1 =- г); (Р; ) — начальное распределение. Согласно и. 1 для каждоао а составляется подпрограмма моделирования случайной велишпы, распределение которой задается ~-й строкой матрицы Р. Назовем эту подпрограмму А,. Кроме того, составляется подпрограмма Асо моделирования случайной величины с распределением (р; ). На нулевом шаге вызывается подпрограмма А (о) Оа з результате выполнения которой получаем уа.
После этого вызываем Аа с г = Та. Результат выполнения данной подпрограммы СхтЬ у,. ЗатЕМ ВЫЗЫВаЕМ Аа С ~ =та, ПОЛуЧаЕМ уа И т. д. ДВОИЧНОЕ кодирование состояний цепи Маркова создает удобство при программировании описанных условных переходов. Данный алгоритм моделирования универсален, однако при моделировании практически встречающихся цепей Маркова необходимо использовать специфику задачи для экономии памяти ЭВМ в связи с тем, что состояний цепи Маркова бывает очень иного; в таких случаях становится невозможным записать не только элементы матрицы Р, но и сами состояния. Укажем два практических приема. Т1асто цепь Маркова представляет собой ограниченное случайное блуждание в т-мерном пространстве, и тогда переход от г„ = (у „ ..., у„ ) к у +, осуществляется в два этапа; вначале определяется р =т + ц„, где ц„— независимый от предыдущего случайный вектор с известным распределением.
После этого проверяется условие положительности всех компонент д„. Если это Условие выполнено, то У„за = Р„; в пРотивном слУчае Ц +, опРеделяется по н„более слоигным образом (возможно, на основании реализации новых случайных величин). Мы видим, что один и тот же алгоритм позволяет реализовать переходы для многих разлпчньтх исходных состояний.
Этот процесс можно продолжить, попользовав однородность переходов по компонентам н„т )ж Л, если эти компоненты оказались положительными. Второй прием связан с тем, что компоненты вектора у обычно отображают состояния различных объектов, входящих в систему обслуживания (источников требований, приборов, логических устройств). Каждый переход от та к У„+а связан с изменением состояния ограниченного числа объектов (часто одного- ЗО4 ГЛ.
К СТАТИСТИЧЕСКОЕ МОДЕЛИРОЭАНИЕ СИСТЕМ двух) . Таким образом, достаточно задать алгоритм случайного выбора объекта, инициирующего изменение состояния, н затем алгоритм соответствующих локальных прообразований. При этом часто процесс облегчается однородностью объектов и связей между ними: в таком случае в алгоритме преобразования будет переменной лишь адресная часть. 4. Моделирование марковского процесса с конечным множеством состояний. Такой процесс обычно задается начальным распределением (р[ ), матрицей интенсивностей перехода Л($) = =))Ле(У) ~), где Ле(Ю) при у Ф) есть мгновенная интенсивность перехода из ) в у в момент г, Лм(г) = — ~ Лц.
(у) = — Л;()). Общим во всех методах является реализация начального случайного состояния и пошаговое построение траектории процесса, т. е. продолжение ее на интервалы [О, у,), [го у,), [ум г,) и т. д. Различие — в методе реализации моментов у„: они могут быть как детерминированными, так и случайными.
Метод уху. В этом случае гху=г — у -) — постоянная величина )А; у„= пй, и ~1. Постоянную )Л выбирают таким образом, чтобы возможностью двух или большего числа переходов за время )Л можно было пренебречь. Тогда вместо траектории т(~) моделируется цепь Маркова (т.), где т. аппрокснмирует т(пух). Вероятности перехода (ц„) задаются приближенной формулой (и+1)А Р (тд.ь) = У ) тп —— У) = [ Лц (г) г(т, У'~1; пА Ш+1)А (. (- ) 1,(), где в случае непрерывных функций Ле(г) чаще всего заменяют интеграл значением функции в точке пух+)А/2. Если зто существенно для исследования требуемой характеристики процесса, то в случае т А,ты момент перехода приближенно представляют случайной величиной, равномерно распределенной в интервале (пй, (и+1)Л).
Данный метод прост в реализации, так как переходы за малое время обычно довольно просты. Однако этот метод не всегда удобен: при слишком большом значении )А искажается характер процесса, при слишком малом вычислительная реализация затягивается медлснным продвижением вдоль траектории. При моделировании системы обслуживания, когда т(г)=' =(т~(г), ..., т (г)), где т,(у) — состояние у-го объекта в момент у, можно использовать одну из двух разновидностей метода )Лг, хорошо илл)острируемых следующим примером. Пусть т;(г) = т, если гъй прибор обслуживает требование; т)(г) = О, если он свобо- 5 з.х нвкотОРыв клАссы случАнпых пРОцлссов 305 дев.
Длительность обслуживания еъго требования показательно распределена с параметром дн Можно сделать случайное испытание для каждого в в отдельности. При успехе (с вероятностью р;Л) е-й прибор освобождается. После этого анализируем ситуацпак какие приборы освободились за время Л, и формируем новое состояние цепи Маркова. При альтернативном подходе производится единственное испытание с вероятностью успеха дй, где д = т~ (~) )ве +... + т (Г) д . Успех этого испытания означает, что за время ев закончилась еще одна операция. Номер освободившегося прибора выбирается по случайному закону с вероятностями, пропорциональными аО(~) до В случае сложных систем, состоящих пз однотипных объектов, второй из указанных методов часто предпочтительнее первого.
Метод у аловых моментов. Назовем узловым моментом любой момент изменения состояния процесса о(г). Последовательность узловых моментов обозначим ~„, п ~ 0; ~е = О. Полоя2им ч„= ч(2 ), считая процесс ч(2) непрерывныве справа с вероятностью Е Тогда ((з„, г ), и ~ 0) — однородная цепь Маркова. Пусть ч„= а, ~ =д Плотность вероятности случайной величины х о„— г р х не О *е( — )х Не ~е (.а о приняла значение л, то следующее состояние равно / с вероятностью Хн(1+ в)/Х;(2+ л) (~' Ф 2). Особенно удобен этот метод в случае однородного марковского процесса: интервалы между узловыми моментами распределены по показательному аакону с параметром, зависящим от текущего состояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
