Определение характеристик случайных параметров моделируемой системы.

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

методическое пособие для студентов

специальности «Прикладная информатика в

экономике»

Екатеринбург

2004 УДК 519.852

С 42

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

Методическое пособие «Имитационное моделирование» утверждено на заседании кафедры «Высшая математика» Уральского государственного университета путей сообщения (протокол № ** от **11. 2006г.).

Автор: П.П. Скачков, канд. физ.-мат. наук, доцент, УрГУПС

Рецензент: В.Е. Замыслов, канд. физ.-мат. наук, доцент

кафедры прикладной математики УрГУПС.

Ó Уральский государственный университет путей сообщения (УрГУПС), 2006

ОГЛАВЛЕНИЕ

1. Введение.

2. Случайные числа.

3. Метод Монте-Карло. Решение детерминированных задач. Моделирование задач имеющих стохастическую природу.

Вероятностно-статистические аспекты метода Монте-Карло и имитационного моделирования (ИМ),

Определение характеристик случайных параметров моделируемой системы.

5. ИМ Марковских процессов.

6. ИМ систем массового обслуживания.

7. Моделирование стоимости пакета акций в условиях случайных колебаний цен.

Приложение.

Введение.

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

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

Компьютерное ИМ предполагает выполнение ряда последовательных действий.

1) Описание реальной системы с выделением структуры, динамического взаимодействия элементов, факторов неопределенности и состояний системы, в которых она может находиться.

2) Создание блоковой схемы объекта с указанием состояний его элементов и возможных переходов между ними.

3) Построение моделирующей программы на специальном языке ИМ или общем языке программирования.

4) Проигрывание различных возможных ситуаций на модели.

5) Верификация модели и программы на основе анализа полученных результатов и их сравнения с теорией процесса и (или) информацией о функционировании реального объекта.

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

,

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

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

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

Область применения ИМ в настоящее время можно разделить на две основные части.

1. Теоретические задачи математики, математической физики, физики, химии…., в частности

¨ вычисление многомерных интегралов;

¨ обращение и псевдообращение матриц;

¨ вычисление констант;

¨ решение дифференциальных уравнений в частных производных;

¨ диффузия в смесях.

2. Практические задачи организации управления

¨ анализ производственных технологических процессов;

¨ планирование и прогнозирование инвестиционных проектов;

¨ задачи социально-психологического характера;

¨ разработка военной тактики и стратегии.

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

1. Метод Монте-Карло (МК).

ИМ можно считать развитием метода МК, разработанного в 50-х годах прошлого века. Основная идея этого метода состоит в использовании выборок для получения оценок искомых характеристик изучаемых объектов. Задача, при этом, формулируется таким образом, чтобы алгоритм решения использовал случайные числа соответствующих законов распределения. Достаточно сложно представить себе, как формализовать полностью детерминированную задачу (вычисление определенных интегралов, например) для решения ее с помощью выборок. (Существенное значение при этом имеют методы получения последовательностей случайных чисел). Этот вопрос детально рассматривается в следующей главе.

Соответствующие построения детально рассмотрены ниже.

Пример 1.1 Определение площади круга радиуса r=0.5 с центром в точке (0.5;0.5). Будем формировать пары псевдослучайных чисел и рассматривать их как координаты точек брошенных внутрь квадрата со стороной равной единице. Часть этих точек попадет внутрь вписанного круга, а часть нет. Исходя из понятия геометрической вероятности, можно сделать вывод − отношение вероятности попаданий в круг к полному числу точек равно отношению площади круга к площади квадрата (равного единице). Поэтому за оценку площади круга можно принять величину .

В качестве иллюстрации построим график (точки − реализации ).

Пример 1.2 Вычисление определенного интеграла. Пусть требуется найти интеграл от функции на отрезке [0,1]. Применяя тот же прием, что и в предыдущем примере получим

Другим способом вычисления является метод суммирования значений подынтегральной функции при случайных значениях аргумента и нахождением среднего

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

Пример 1.3 Приближенное решение задачи линейного программирования.

Метод аналогичен способу вычисления определенного интеграла. В прямоугольник, содержащий многогранник планов бросаются случайные точки (случайные планы задачи), вычисляется значения функции цели на этих планах. Размер прямоугольника определяет интервалы, на которых формируются последовательности случайных чисел. Точки, не попавшие в многоугольник решений, игнорируются. Сравнивая полученные значения функции цели на различных планах, выбирают наибольшее (наименьшее) из них и принимают соответствующий план как оптимальный. При этом координата x запоминается как элемент , координата y − , а функция цели .

Дана задача линейного программирования

Решение задачи легко получить обычными методами, тогда

. Приведем схему решения ММК.

Таким образом, .

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

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

Пусть проводится n независимых опытов, в каждом из которых событие А появляется с равной вероятностью р. Требуется найти вероятность появления события ровно k раз. Это задача Бернулли и ответ можно получить по формуле

При n=20, k=5, и p=0.2 0.1748. Построим моделирующую программу

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

Путь р=0.05, n=15, тогда искомая вероятность .

Моделирующая программа

дает результат .

Пример 1.6 В урне находится 5 белых и 20 черных шаров. Из урны последовательно (без возвращения) вынимают шары до появления белого. Найти вероятность того, что белый шар появится третьим. Решение задачи дает . Численный результат ИМ получим по программе

и P(A)= 0.1391 при длине прогона n =10000.

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

2. Случайные числа (СЧ) и методы их получения.

Моделирование систем требует учета стохастических воздействий на систему (случайных событий в случайные моменты времени). Случайные события и случайные промежутки времени можно моделировать с помощью случайных чисел. Методы формирования массивов СЧ можно разделить на физические (аппаратные), табличные и алгоритмические. В машинном статистическом эксперименте, как правило, используют алгоритмический метод. Во всех современных пакетах прикладных программ и языках программирования имеются встроенные функции позволяющие получать массивы СЧ с заданным законом распределения и заданными параметрами. Необходимо иметь в виду, что любая алгоритмическая процедура использует для вычисления СЧ некоторую формулу и, следовательно, получаемая последовательность полностью определена начальными значениями параметров (детерминирована). Такие числа называют псевдослучайными. При дискретном моделировании в качестве базовой выбирают последовательность случайных чисел , равномерно распределенных на интервале (0, 1). Непрерывная случайная величина X имеет равномерное распределение, если ее функция плотности и функция распределения имеют вид

математическое ожидание М(X)=1/2 и дисперсия D(X)=1/12.

Наиболее распространенным методом получения такой последовательности является мультипликативная конгруэнция (в различных модификациях). Два целых числа x и y называются конгруэнтными по модулю m (m –целое число), если |x–y| = km. Таким образом, y конгруэнтно x по модулю m, если |x–y| делиться на m без остатка. Например, при x = 12589 и m = 10, y = 9 конгруэнтно x по модулю 10, а при x = 1223 и m = 2, y = 1 конгруэнтно x по модулю 2. Метод состоит в получении последовательности по рекуррентной формуле

, k = 0,1,2,…

где входные параметры. Такой алгоритм приводит к повторению псевдослучайных чисел начиная с некоторого k. Можно доказать [1], что при

a = 100003, и – девятизначном целом нечетном числе не делящимся на 5, получится не повторяющихся случайных чисел. Очевидно, что при решении задачи необходимо, чтобы полученной последовательности было достаточно для прогона модели.

Продемонстрируем получение первых трех псевдослучайных чисел на примере,

пусть

Тогда, последовательно имеем

и т.д.

Здесь операция mod(Z,V) определяет остаток от деления Z на V.

Число неповторяющихся случайных чисел можно существенно увеличить следующим простым способом. После выбора вычисляются значения и вырезаются числа стоящие, например, в 11,12 и 13 разрядах. Пусть в этих разрядах оказались числа 2, 0, 7 тогда 0,207 следующее случайное число. Этот метод может использоваться и самостоятельно для небольших выборок. После этого находим , описанным выше способом мультипликативной конгруэнции, и получаем последующую серию из чисел. Угол α выбирается произвольно, но меньше 0,5 угловой секунды.

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

Тест на равномерность последовательности проводится по обычной схеме обработки опытных данных. Интервал (0;1) делится на k частей, определяются частоты и по критерию согласия (например, Пирсона) принимаем гипотезу о равномерном законе с некоторым уровнем значимости.

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

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

…aaabbbbaabaaabbbbbabab…

Так как случайные числа в этой последовательности предполагаются независимыми и равномерно распределенными на интервале (0, 1), то теоретическая вероятность появления серии длиной j в последовательности длиной L в N опытах определяется формулой Бернулли

.

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

Проверка независимости элементов последовательности псевдослучайных чисел {xi} проводится на основании вычисления корреляционного момента. Две случайные величины называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая величина. Введем в рассмотрение случайную величину , где τ − величина сдвига последовательности. Корреляционный момент двух случайных величин X и Y с реализациями и определяется по формуле

,

где − вероятность того, что величина (X,Y) примет значение . Если случайные числа независимы, то Фактически, при таком анализе, вычисляют коэффициент корреляции . При любом τ ≠ 0 и достаточно больших N , если эмпирическое значение , то с вероятностью β можно утверждать, что полученная последовательность чисел удовлетворяет гипотезе о корреляционной независимости.

Общим подходом построения последовательностей случайных чисел с произвольными законами распределения является метод обратной функции. Пусть требуется создать выборку СЧ, имеющих закон распределения . Если случайное число, из последовательности, имеющей равномерное распределение на интервале (0,1), то возможное значение непрерывной случайной величины X c заданной функцией распределения , является корнем уравнения

или .

Пример 1. Непрерывная случайная величина Х распределена по показательному закону, заданному функцией распределения

.

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

.

Пусть случайная величина R приняла значения , тогда, при

, получим числа распределенные по показательному закону с заданным параметром λ .

Пример 2. Непрерывная случайная величина Х распределена по закону равномерной плотности на интервале (a,b), заданному функцией распределения

.

Подставляя функцию в уравнение и разрешая его относительно , получим

.

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

,

где m и σ математическое ожидание, и среднее квадратичное отклонение получаемой случайной величины, − СЧ равномерно распределенные на интервале (0,1). Для практических целей достаточно просуммировать 12 таких чисел (n=12).

Задания для лабораторных работ по теме «Случайные числа».

1. Методом мультипликативной конгруэнции сформировать последовательность из n=100 случайных чисел, равномерно распределенных на интервале (0,1). В качестве взять число 3st5st937, где s − первая, а t − вторая цифра по номеру студента в журнале.

2. Провести проверку гипотезы о равномерном законе для полученной выборки (статистический тест).

3. Рассмотреть методом серий вопрос о стохастичности полученных случайных чисел (длина серии j для студента задается преподавателем).

4. Доказать независимость элементов полученной последовательности.

При выполнении лабораторной работы можно использовать примеры программ приводимых в Приложении.

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