Федеральное Государственное Образовательное Учреждение Высшего Профессионального Образования Ставропольский Государственный Аграрный Университет Лекция 5 на тему «Метод Монте-Карло» по дисциплине «Имитационное моделирование экономических процессов»

Вопросы: 1. Вводные замечания 2. Общая схема метода Монте-Карло 3. Пример расчета системы массового обслуживания методом Монте-Карло 4. Генерация последовательности случайных чисел 5. Моделирование случайных воздействий на системы Контрольные вопросы

1. Вводные замечания Метод статистического моделирования на ЭВМ - основной метод получения результатов с помощью имитационных моделей стохастических систем, использующий в качестве теоретической базы предельные теоремы теории вероятностей. Основа - метод статистических испытаний Монте-Карло. Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений.

Термин "метод Монте-Карло" (предложенный Дж. Фон Нейманом и С. М. Уламу в 1940-х) относится к моделированию процессов с использованием генератора случайных чисел. Термин Монте-Карло (город, широко известный своими казино) произошел от того факта, что "число шансов" (методы моделирования Монте-Карло) было использовано с целью нахождения интегралов от сложных уравнений при разработке первых ядерных бомб (интегралы квантовой механики). С помощью формирования больших выборок случайных чисел из, например, нескольких распределений, интегралы этих (сложных) распределений могут быть аппроксимированы из (сгенерированных) данных. Возникновение идеи использования случайных явлений в области приближенных вычислений принято относить к 1878 г., когда появилась работа Холла об определении чисел с помощью случайных бросаний иглы на разграфленную параллельными линиями бумагу.

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

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

2. Общая схема метода Монте-Карло Предположим, что нам требуется вычислить некоторую неизвестную величину m, и мы хотим сделать это, рассматривая случайную величину такую, что ее математическое ожидание М, = m. Пусть при этом дисперсия данной случайной величины D = b. Рассмотрим N случайных независимых величин,,…, распределения которых совпадают с распределением рассматриваемой случайной величины ξ. Согласно центральной предельной теореме теории вероятностей, распределение суммы =ξ1+ ξ2+…+ξN будет приблизительно нормальным со средним, равным μ= Nm, и дисперсией σ2 = Nb2. Согласно «правилу трех сигма», каковы бы ни были m и s,

Р{μ - Зσ< ρN< μ+ Зσ} = 0.997, т. е. Последнее соотношение можно переписать в виде Полученная формула дает метод расчета т и оценку погрешности этого метода. Сущность применения метода Монте-Карло заключается в определении результатов на основании статистики, полу чаемой к моменту принятия некоторого решения.

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

Равномерно распределенные случайные числа заключены в интервале от 0 до 1 и выбираются случайным образом в соответствии с функцией распределения F(x) = Рr{Х< х} = х, При этом распределении одинаково правдоподобно по явление любых значений случайной величины в интервале (0, 1). Здесь Рг{Х< х} вероятность того, что случайная величина X примет значение меньше х. Основным методом получения случайных чисел является их генерация по модулю. Пусть m, a, с, х0 целые числа, такие, что m > х0 и а, с, х0 > 0. Псевдослучайное число хi из последовательности {хi} получается с помощью рекуррентного соотношения xi = а xi-1 + с (mod m).

Стохастические характеристики генерируемых чисел решающим образом зависят от выбора m, а и с. Их неудачный выбор приводит к ошибочным результатам при моделировании методом Монте-Карло. Для численного моделирования часто требуется большое количество случайных чисел. Следовательно, период последовательности генерируемых случайных чисел, после которого последовательность начинает повторяться, должен быть достаточно большим. Он должен быть существенно больше требуемого для моделирования количества случайных чисел, иначе получаемые результаты будут искажены. Большинство компьютеров и программных оболочек содержат генератор случайных чисел. Однако большинство статистических тестов показывает коррелированность между получаемыми случайными числами.

Существует быстрый тест, с помощью которого необходимо проверять каждый генератор. Качество генератора случайных чисел можно продемонстрировать, заполняя полностью d-мерную решетку (например, двух- или трехмерную). Хороший генератор должен заполнить все пространство гиперкуба. Другой приближенный способ проверки равномерности распределения N случайных чисел хi состоит в вычислении их математического ожидания и дисперсии. Согласно этому критерию, для равномерного распределения должны выполняться условия

и Существует множество статистических критериев, которые можно использовать для проверки того, будет ли последовательность случайной. Наиболее точным считается спектральный критерий. На практике главной проблемой является построение простого и надежного генератора случайных чисел, который можно использовать в своих программах. Для этого предлагается следующая процедура. В начале программы целой переменной X присваивается некоторое значение Х0. Затем случайные числа генерируются по правилу X = (аХ + с) mod m.

Выбор параметров следует осуществлять, пользуясь следующими основными принципами: 1. Начальное число Х0 можно выбрать произвольно. Если программа используется несколько раз и каждый раз требуются различные источники случайных чисел, можно, например, присвоить Х0 значение X, полученное последним на предыдущем прогоне. 2. Число m должно быть большим, например, 230 (поскольку именно это число определяет период генерируемой псевдослучайной последовательности). 3. Если m степень двойки, выбирают а таким, чтобы amod8 = 5. Если m степень десяти, выбирают а таким, чтобы amod10 = 21. Такой выбор гарантирует, что генератор случайных чисел будет вырабатывать все m возможных значений, прежде чем они начнут повторяться.

4. Множитель а предпочтительнее выбирать лежащим между 0.01m и 0.99m, и его двоичные или десятичные цифры не должны иметь простую регулярную структуру. Множитель должен пройти спектральный критерий и, желательно, еще несколько критериев. 5. Если a хороший множитель, значение с не существен но, за исключением того, что с не должно иметь общего множителя с m, если m размер компьютерного слова. Можно, например, выбрать с = 1 или с = а. 6. Можно генерировать не больше m/1000 случайных чисел. После этого должна использоваться новая схема, например, новый множитель а.

Перечисленные правила, главным образом, относятся к машинному языку программирования. Для языка программирования высокого уровня, например С++, часто используют другой вариант (1): выбирается простое число m, близкое к наибольшему легко вычисляемому целому числу, значение а полагается равным первообразному корню из m, а с берется равным нулю. Например, можно принять a = и т =

3. Пример расчета системы массового обслуживания методом Монте-Карло Рассмотрим простейшую систему массового обслуживания (СМО), которая состоит из n линий (иначе называемых каналами или пунктами обслуживания). В случайные моменты времени в систему поступают заявки. Каждая заявка поступает на линию 1. Если в момент поступления за явки Тк эта линия свободна, заявка обслуживается время t3 (время занятости линии). Если линия занята, заявка мгновенно передается на линию 2 и т. д. Если все n линий в данный момент заняты, то система выдает отказ. Естественной является задача определения характеристик данной системы, по которым можно оценить ее эффективность: среднее время ожидания обслуживания, доля времени простоя системы, среднюю длину очереди и т. д.

Будем считать, что промежуток времени между двумя последовательными заявками есть случайная величина с показательным распределением, плотность которого имеет вид Математическое ожидание такого распределения равно. Из сказанного выше ясно, что значение можно рассчитывать по формуле =- ln (2) где случайная величина распределена равномерно. Каждой линии ставится в соответствие ячейка ЭВМ, в которую записывается момент освобождения линии. Пусть в момент времени Т1, который мы примем за начало чета, все линии свободны. За время окончания расчета примем Ткон = Т 1+ Т.

Первая заявка поступает на линию 1 и тут же обслуживается, поскольку линия свободна. Следовательно, в течение времени t3 эта линия будет занята. Поэтому заменяем t1 на новое значение: t1 Т1 + t3 и добавляем 1 к счетчику выполненных заявок. Затем переходим к рассмотрению следующей заявки. Для этого генерируем значение, равномерно распределенное на [0, 1], и по формуле (2) вычисляем очередное значение = 2. Вычисляем момент поступления второй заявки: T2=T1+ 2. Проверяем, свободна ли в этот момент первая линия, т.е. выполнено ли условие t1 T2. Если это условие выполнено, линия свободна и приступает к обслуживанию второй заявки. Заменяем t1 на Т2 + t3, добавляем 1 к счетчику выполненных заявок и переходим к рассмотрению следующей заявки.

Если линия занята, то проверяем, свободна ли вторая линия, и т. д. Если в какой-то момент времени заняты все линии, добавляем 1 в счетчик отказов и переходим к выполнению следующей заявки. После каждого вычисления Тk проверяем условие окончания опыта: Tk>Tкон. Если это условие выполнено, опыт заканчивается. Такой опыт повторяется N раз, и результаты всех опытов усредняются. Подобные расчеты могут быть полезны при решении вопроса об увеличении линий, необходимости повышения квалификации персонала и т. д.

4. Генерация последовательности случайных чисел Существует три способа генерации случайных чисел: Аппаратный - в основе лежит какой-либо физический эффект (например, шумы в электронных устройствах, случайные числа вырабатываются с помощью специального датчика. Этот способ не гарантирует качество последовательности случайных чисел непосредственно во время моделирования. С помощью этого способа нельзя получать одинаковые последовательности. Используется редко. Табличные - случайные числа оформлены в виде таблицы в оперативной памяти или на внешнем носителе. При этом способе запас чисел ограничен, вычислительные ресурсы используются неэффективно. Используется редко.

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

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

Для получения случайных чисел на ЭВМ используются алгоритмы, поэтому такие последовательности, являющиеся по сути детерминированными, называются псевдослучайными. ЭВМ оперирует n-разрядными числами, поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0,1) используют дискретную последовательность 2n случайных чисел того же интервала - закон распределения такой дискретной последовательности называется квазиравномерны распределением.

Требования к идеальному генератору случайных чисел: Последовательность должна состоять из квазиравномерно распределенных чисел; Числа должны быть независимыми; Последовательности случайных чисел должны быть воспроизводимыми; Последовательности должны иметь неповторяющиеся числа; Последовательности должны получаться с минимальными затратами вычислительных ресурсов. Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных числе находят алгоритмы вида: xi+1=Ф(xi), представляющие собой реккурентные соотношения первого порядка.

Большинство конгруэнтных процедур генерации случайных чисел основаны на следующей формуле: где - неотрицательные целые числа. По целым числам последовательности {Xi} можно построить последовательность {xi}={Xi/M} рациональных чисел из единичного интервала (0,1). Применяемые генераторы случайных чисел перед моделированием должны пройти тщательное предварительное тестирование на равномерность, стохастичность и независимость получаемых последовательностей случайных чисел.

Методы улучшения качества последовательностей случайных чисел: 1. Использование рекуррентных формул порядка r: Но применение этого способа приводит к увеличению затрат вычислительных ресурсов на получение чисел. 2. Метод возмущений:

5. Моделирование случайных воздействий на системы 1. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью p. Определим А как событие, состоящее в том, что выбранное значение xi равномерно распределенной на интервале (0,1) случайной величины удовлетворяет неравенству: xi =p, его вероятность равна 1-р.

2. Рассмотрим группу событий. Пусть А1, А2,..., Аs - полная группа событий, наступающих с вероятностями p1, p2,..., ps соответственно. Определим событие Аm как событие, состоящее в том, что выбранное значение xi случайной величины удовлетворяет неравенству Где Процедура моделирования испытаний в этом случае состоит в последовательном сравнении случайных чисел xi со значениями lr. Если условие выполняется, исходом испытания оказывается событие Аm. 3. Рассмотрим независимые события А и В с вероятностями наступления рА и рВ. Возможными исходами совместных испытаний в этом случае будут события АВ,

с вероятностями рАрВ, (1-рА)рВ, рА(1-рВ), (1- рА)(1-рВ). Для моделирования совместных испытаний можно использовать два варианта процедуры: Последовательное выполнение процедуры, рассмотренной в п.1. Определение одного из исходов АВ, по жребию с соответствующими вероятностями, т.е. процедура, рассмотренная в п.2. Первый вариант потребует двух чисел xi и двух сравнений. При втором варианте можно обойтись одним числом xi, но сравнений может потребоваться больше. С точки зрения удобства построения моделирующего алгоритма и экономии количества операций и памяти ЭВМ более предпочтителен первый вариант.

4. События А и В являются зависимыми и наступают с вероятностями pА и pВ. Обозначим через pА(В) условную вероятность наступления события В при условии, что событие А произошло.

Контрольные вопросы: Как можно определить метод Монте-Карло? Практическое значение метода Монте-Карло? Общая схема метода Монте-Карло? Пример расчета системы массового обслуживания методом Монте-Карло? Способы генерации случайных чисел? Каковы требования к идеальному генератору случайных чисел? Методы улучшения качества последовательностей случайных чисел?