Лекции по курсу имитационное моделирование экономических процессов составитель ст преп каф. Итим нохрина Г. Л. 2
 Скачать 1.44 Mb.
|
|
т, то есть наименьшее целое число l, для которого а l - 1 де- лится на т, составляет l = т - 1 [Knuth, 1998a, р. 20]. Если таким образом выбрать значения т и а, то можно получить каждое целое число 1, 2, ..., п - 1 один раз в каждом цикле, так что Z o мо- жет быть любым целым числом от 1 до т - 1, а в результате все равно будет получен период т - 1. Такие генераторы называются мультипликативными ЛКГ с простым модулем Мультипликативный конгруэнтный метод (метод вычетов) В основе лежит следующее рекуррентное соотношение: – множитель, M – модуль, – стартовое значение. Рекомендуемые значе- ния для 64-разрядной сетки: Тогда период Для 32-разрядной: Тогда период Как раз этот датчик случайных чисел не удовлетворяет статистическим требованиям. Линейные смешанные формулы. p – порядок, стартовые значения: . Период Частный случай. Датчик Терпугова. Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 18 function Rand (var y: Integer): Double; const b=843314861; c=453816693; m2=1073741824; {M/2} begin {$O-,$R-} {Optimization- & Range Check-} y:=y*b+c; if y<0 then y:=(y+m2)+m2; Result:=Double(y)*0.4656613E-09; end; Причем тогда и только тогда, когда Существуют и другие методы моделирования базовых датчиков. Генерация случайных событий 1. Пусть имеется некоторое случайное событие А, наступающее с вероятностью р(А). Тогда ( – числа, генерируемые базовым датчиком). Следовательно, генератор 1 случайного события: ,где 2. Полная группа попарно несовместимых событий . Пусть Идея: Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 19 ГЕНЕРАЦИЯ ДИСКРЕТНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН При возникновении в процессе моделирования каких-либо случайных факторов следует прибегнуть к выборке, или генерированию, случайных величин из распределений вероятностей. Как и в главе 7, выражение «генерирова- ние случайных величин» мы используем для обозначения действий, направленных на получение наблюдений по случайным переменным (или для реализации случайных величин) из искомого распределения. Форма распределе- ния подбирается специально, в результате для сбора данных могут использоваться, например, экспоненциальное распределение, гамма-распределение или распределение Пуассона (см. главу 6). В данной главе мы склонны допустить, что распределение уже было некоторым образом определено (в том числе и значения его парамет- ров), и рассматриваем только вопрос о возможности генерировать случайные величины с этим распределением для выполнения прогона имитационной модели. Например, для моделей систем массового обслуживания (см. раздел 1.4 и главу 2) требуется генерировать время между поступлениями и время обслуживания для обеспече- ния продвижения модельного времени, а для модели системы управления запасами (из раздела 1.5) нужно гене- рировать объем спроса в моменты его возникновения. Как мы убедимся, ознакомившись с этой главой, основной составляющей, необходимой для каждого ме- тода генерирования случайных величин из любого распределения или случайного процесса, является источник не- зависимых и одинаково распределенных случайных величин с распределением U(0, 1). Вот почему очень важно наличие надежного генератора случайных чисел с распределением U(0, 1). В большинстве компьютерных про- грамм и пакетов имитационного моделирования имеются удобные генераторы случайных чисел, но некоторые из них (особенно старые версии) не адекватны уровню современных требований (см. главу 7). Без надлежащего гене- ратора случайных чисел невозможно правильно генерировать случайные величины из любого распределения. По- этому будем исходить из предположения, что у нас имеется надежный источник случайных чисел Пусть имеется дискретная случайная величина с рядом распределения. x p , Т.о. задача сводится к генерации полной группы попарно несовместимых событий. Т.е., если наступило , Программная реализация Специальные методы генерации некоторых дискретных случайных величин 1. Равномерное распределение x 0 1 n p Тогда Док-во. Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 20 x удовлетворяет равномерному распределению. 2. Геометрическое распределение x = 0,1,2,... до Док-во. 3. Отрицательное биномиальное распределение. х=0,1,2,... до Параметры: , и Для это распределение совпадает с геометрическим, поэтому можно представить , где - независимые случайные величины, распределенные по геометрическому закону. Т.о. (базовый датчик должен выдать r чисел для генерации одного х). 4. Биномиальное распределение (теорема об опытах – вероятность наступления m событий A в n опытах). Введем (функция Хэвисайда). Тогда наступило 1 события сумма дает кол-во событий наступивших в n опытах биномиальное распределение). Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 21 5. Пуассоновское распределение Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 22 ГЕНЕРАЦИЯ НЕПРЕРЫВНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН Непрерывная случайная величина характеризуется плотностью или функцией рас- пределения 1. Метод обратной функции Основная идея: представим и попробуем найти Допустим, что мы разрешили относительно : . И потребуем, чтобы . Тогда Т.к. равномерно распределена в [0,1), то и равномерно распределена там же, следовательно, можно записать и так Метод обратной функции применяется редко, т.к. обычно найти очень трудно. Примеры. 1. Экспоненциальное распределение: 2. Непрерывные случайные величины с заданной гистограммой: Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 23 Общая площадь Функция распределения: или Чтобы найти формулу, решим уравнение 1. .Отнимаем от него , затем и т.д. до тех пор, пока не по- лучим отрицательное значе- ние: 2. Ясно, что . Следовательно, 2. Метод суперпозиции Применим в случае, если , где , и Тогда моделирование производится следующим образом: 1. Генерируется дискретная случайная величина с рядом 2. Генерируется непрерывная случайная величина с плотностью Пример. Гиперэкспоненциальное распределение. Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 24 Моделирование: , где - смоделирована как дискретная случайная величина с рядом 3. Метод исключения Пусть некоторая функция удовлетворяет условиям: 1. 2. Теорема. Пусть некоторая двумерная случайная величина имеет следующую совместную плотность распределения Тогда СВ имеет плотность распределения Док-во. Т.о., если требуется моделировать случайную величину с плотностью , то принима- ем , тогда .Т.е. достаточно генерировать двумерную , равномерно рас- пределенную в области под , и тогда будет иметь распределение Осталось научиться равномерно попадать под кривую (область ). Оказывается, это очень просто: достаточно равномерно попадать в некоторую и рассматривать только те точки, которые - они будут равномерно распределены в Например, если , , то легче всего взять и Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 25 Далее применяем метод исключения, т.е результатом моделирования считаем только те , для ко- торых , остальные пропускаем: 4. Нормальные случайные величины Нормальная случайная величина: : Стандартная нормальная случайная величина: Любая нормальная случайная величина: , где Таким образом достаточно получить датчик стандартной нормальной случайной величины. Методы: 1. Метод суммирования /* ЦПТ: Для независимых случайных величин произвольным распределением .*/ Пусть ясно, что , . Тогда Если взять , то получим Существуют более точные формулы, типа . В частности, для : 2. Метод обратной функции - интеграл вероятностей или функция Лапласа. Свойство: Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 26 3. Метод обратной функции: Очевидно, что Т. о. заменяют аппроксимациями, например: где (Погрешность=0.003). Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 27 УПРАВЛЕНИЕ МОДЕЛЬНЫМ ВРЕМЕНЕМ Виды представления времени в модели Приступая к изучению механизмов управления модельным временем, уместно поговорить о том, какую роль вообще играет время в имитационном моделировании. При знакомстве с имитацион- ным экспериментом мы отмечали, что он представляет собой наблюдение за поведением системы в тече- ние некоторого промежутка времени. Конечно, далеко не во всех статистических испытаниях фактор вре- мени t играет ведущую роль, а в некоторых и вообще может не рассматриваться. Вспомните, например,, задачу о вычислении площади круга: полученный результат не зависел от того, сколь долго мы «бом- били» квадрат случайными точками (речь в данном случае не идет о количестве этих точек). Но значи- тельно больше задач, в которых оценка эффективности моделируемой системы напрямую связана с временными характеристиками ее функционирования. К ним относятся упоминавшиеся уже задачи по оценке производительности, некоторые задачи по оценке надежности, качества распределения ресурсов, а также все задачи, связанные с исследованием эффективности процессов обслуживания. Характерной особенностью большинства практических задач является то, что скорость протекания рас- сматриваемых в них процессов значительно ниже скорости реализации модельного эксперимента. Например, если моделируется работа вычислительного центра в течение недели, вряд ли кому-то придет в голову воспроизводить этот процесс в модели в таком же масштабе времени. С другой сторо- ны, даже те имитационные эксперименты, в которых временные параметры работы системы не учи- тываются, требуют для своей реализации определенных затрат времени работы компьютера. В связи с этим при разработке практически любой имитационной модели и планировании проведе- ния модельных экспериментов необходимо соотносить между собой три представления времени: 1. реальное время, в котором происходит функционирование имитируемой системы; 2. модельное (или, как его еще называют, системное) время, в масштабе которого организуется работа модели; 3. машинное время, отражающее затраты времени ЭВМ на проведение имитации. С помощью механизма модельного времени решаются следующие задачи: отображается переход моделируемой системы из одного состояния в другое; производится синхронизация работы компонент модели; изменяется масштаб времени «жизни» (функционирования) исследуемой системы; производится управление ходом модельного эксперимента; моделируется квазипараллельная реализация событий в модели. Приставка «квази» в данном случае отражает последовательный характер обработки событий (про- цессов) в ИМ, которые в реальной системе возникают (протекают) одновременно. Необходимость решения последней задачи связана с тем, что в распоряжении исследователя нахо- дится, как правило, однопроцессорная вычислительная система, а модель может содержать значительно большее число одновременно работающих подсистем. Поэтому действительно параллельная (одновре- менная) реализация всех компонент модели невозможна. Даже если используется так называемая распре- деленная модель, реализуемая на нескольких узлах вычислительной сети, совсем не обязательно, что число узлов будет совпадать с числом одновременно работающих компонент модели. Немного забегая вперед, следует отметить, что реализация квазипараллельной работы компонент модели является доста- точно сложной технической задачей. Некоторые возможные методы ее решения рассматриваются в сле- дующей лекции. Существуют два метода реализации механизма модельного времени — с постоянным шагом и по особым состояниям. Выбор метода реализации механизма модельного времени зависит от назначения модели, ее сложности, характера исследуемых процессов, требуемой точности результатов и т. д. Изменение времени с постоянным шагом При использовании данного метода отсчет системного времени ведется через фиксированные, вы- бранные исследователем интервалы времени. События в модели считаются наступившими в момент Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 28 окончания этого интервала. Погрешность в измерении временных характеристик системы в этом слу- чае зависит от величины шага моделирования Δt. Метод постоянного шага целесообразно использовать в том случае, если: события появляются регулярно, их распределение во времени достаточно равно-| мерно; число событий велико и моменты их появления близки; невозможно заранее определить моменты появления событий. Данный метод управления модельным временем достаточно просто реализовать в том случае, ко- гда условия появления событий всех типов в модели можно представить как функцию времени. Пусть, например, событие состоит в том, что летящий самолет пересекает некоторый воздушный рубеж, расстояние до которого равно R. Если самолет движется по прямой с постоянной скоростью V, можно вычислять путь, пройденный самолетом, с интервалом времени Δt: S=S+V-At. Соответственно, со- бытие считается наступившим, если выполняется условие S>R, а момент времени наступления события принимается равным n-Δt, где n — номер шага моделирования, на котором условие стало истинным. В общем виде алгоритм моделирования с постоянным шагом представлен на рис. 1 ( M t — текущее значение модельного времени, M T — заданный интервал моделирования), а для рассмотренного выше примера с самолетом — на рис. 2. Обратите внимание на то, что в отличие от обобщенного алгоритма, в приведенном примере моделирование завершается не по истечении заданного интервала времени, а при наступлении интересующего нас события. В связи с этим необходимо еще раз подчеркнуть, что при моде- лировании с постоянным шагом результат моделирования напрямую зависит от величины этого шага. Причем, если шаг будет слишком большим, то результат, скорее всего, будет неверным: момент окончания очередного шага очень редко будет совпадать с реальным моментом пересечения самолетом заданного рубежа. Та- кая ситуация показана на рис. 3. Рис . 1. Алгоритм моделирования с постоянным шагом. Рис . 2. Пример моделирования с постоянным шагом. Лекции по курсу ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Составитель – ст.преп.каф. ИТиМ Нохрина Г.Л. 29 Рис . 3. Зависимость результата эксперимента от шага модельного времени На рисунке использованы следующие обозначения: t m1 —ось модельного времени при использовании шага Δt 1 ; t m2 —ось модельного времени при использовании шага Δt 2 t p — ось реального времени; Т R — реальный момент пересечения самолетом рубежа; ; Т R1 , T R2 — моменты пересечения рубежа, полученные для соответствующих величин Δt. Приведенный пример призван обратить внимание на то, что выбор величины шага моделирова- ния является нелегким и очень важным делом. Универсальной методики решения этой проблемы не существует, но во многих случаях можно использовать один из следующих подходов: принимать величину шага равной средней интенсивности возникновения событий раз- личных типов; выбирать величину шага равной среднему интервалу между наиболее частым (или наиболее важными) событиями. Изменение времени по особым состояниям При моделировании по особым состояниям системное время каждый раз изменяется на величи- ну, строго соответствующую интервалу времени до момента наступления очередного события. В этом случае события обрабатываются в порядке их наступления, а одновременно наступившими считаются только те, которые являются одновременными в действительности. Для реализации моделирования по особым состояниям требуется разработка специальной процедуры планирования событий (так называемого календаря событий). Если известен закон распре- деления интервалов между событиями, то такое прогнозирование труда не составляет: достаточно к текущему значению модельного времени добавить величину интервала, полученную с помощью соот- ветствующего датчика. Пусть, например, за летящим самолетом, фигурировавшем при описании моделирования с посто- янным шагом, наблюдает диспетчер. Он вводит информацию о самолёте, причем интервалы между вводом двух соседних сообщений являются случайными величинами, распределенными по нормаль- ному закону с заданными параметрами Иллюстрация к такой ситуации приведена на рис. 4 (Т с — мо- мент ввода очередного сообщения, Δt—случайный интервал). Рис . 4. Изменение модельного времени по особым состояниям. Если же момент наступления события определяется некоторыми логическими условиями, то необходимо сформулировать эти условия и проверять их истинность для каждого последующего шага моделирования. Практика показывает, что сложности в реализации механизма изменения вре- |