Метод Монте-Карло

Размещено на http://www.allbest.ru/

Введение

Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений. Возникновение идеи использования случайных явлений в области приближённых вычислений принято относить к 1878 году, когда появилась работа Холла об определении числа p с помощью случайных бросаний иглы на разграфлённую параллельными линиями бумагу. Существо дела заключается в том, чтобы экспериментально воспроизвести событие, вероятность которого выражается через число p, и приближённо оценить эту вероятность. Отечественные работы по методу Монте-Карло появились в 1955-1956 годах. С того времени накопилась обширная библиография по методу Монте-Карло. Даже беглый просмотр названий работ позволяет сделать вывод о применимости метода Монте-Карло для решения прикладных задач из большого числа областей науки и техники.

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



1. Метод статистического моделирования (метод Монте-Карло)

Датой рождения метода Монте-Карло принято считать 1949 г., когда появилась статья под названием «The Monte Carlo method». Создателями этого метода считают американских математиков Дж. Неймана и С. Улама. В СССР первые статьи о методе Монте-Карло были опубликованы в 1955-1956 гг. Любопытно, что теоретическая основа метода была известна давно. Более того, некоторые задачи статистики рассчитывались иногда с помощью случайных выборок, т.е. фактически методом Монте-Карло. Однако до появления электронных вычислительных машин (ЭВМ) этот метод не мог найти сколько-нибудь широкого применения, ибо моделировать случайные величины вручную - очень трудоемкая работа. Таким образом, возникновение метода Монте-Карло как весьма универсального численного метода стало возможным только благодаря появлению ЭВМ. Само название «Монте-Карло» происходит от города Монте-Карло в княжестве Монако, знаменитого своим игорным домом. Идея метода чрезвычайно проста и состоит она в следующем. Вместо того, чтобы описывать процесс с помощью аналитического аппарата (дифференциальных или алгебраических уравнений), производится «розыгрыш» случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. В действительности конкретное осуществление случайного процесса складывается каждый раз по-иному; так же и в результате статистического моделирования мы получаем каждый раз новую, отличную от других реализацию исследуемого процесса. Что она может нам дать? Сама по себе ничего, так же как, скажем, один случай излечения больного с помощью какого-либо лекарства. Другое дело, если таких реализаций получено много. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки могут быть получены любые интересующие нас характеристики: вероятности событий, математические ожидания и дисперсии случайных величин и т.д. При моделировании случайных явлений методом Монте-Карло мы пользуемся самой случайностью как аппаратом исследования, заставляем ее «работать на нас». Нередко такой прием оказывается проще, чем попытки построить аналитическую модель. Для сложных операций, в которых участвует большое число элементов (машин, людей, организаций, подсобных средств), в которых случайные факторы сложно переплетены, где процесс - явно немарковскпй, метод статистического моделирования, как правило, оказывается проще аналитического (а нередко бывает и единственно возможным). В сущности, методом Монте-Карло может быть решена любая вероятностная задача, но оправданным он становится только тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета. Приведем пример, когда метод Монте-Карло возможен, но крайне неразумен. Пусть, например, по какой-то цели производится три независимых выстрела, из которых каждый попадает в цель с вероятностью 1/2. Требуется найти вероятность хотя бы одного попадания. Элементарный расчет дает нам вероятность хотя бы одного попадания равной 1 - (1/2)3 = 7/8. Ту же задачу можно решить и «розыгрышем», статистическим моделированием. Вместо «трех выстрелов» будем бросать «три монеты», считая, скажем, герб - за попадание, решку - за «промах». Опыт считается «удачным», если хотя бы на одной из монет выпадет герб. Произведем очень-очень много опытов, подсчитаем общее количество «удач» и разделим на число N произведенных опытов. Таким образом, мы получим частоту события, а она при большом числе опытов близка к вероятности. Ну, что же? Применить такой прием мог бы разве человек, вовсе не знающий теории вероятностей, тем не менее, в принципе, он возможен. Метод Монте-Карло- это численный метод решения математических задач при помощи моделирования случайных величин.



Две особенности метода Монте-Карло

Первая особенность метода - простая структура вычислительного алгоритма.

Вторая особенность метода - погрешность вычислений, как правило, пропорциональна D/N2, где D - некоторая постоянная, N - число испытаний. Отсюда видно, что для того, чтобы уменьшить погрешность в 10 раз (иначе говоря, чтобы получить в ответе еще один верный десятичный знак), нужно увеличить N (т. е. объем работы) в 100 раз. Ясно, что добиться высокой точности таким путем невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью (5-10%). Способ применения метода Монте-Карло по идее довольно прост. Чтобы получить искусственную случайную выборку из совокупности величин, описываемой некоторой функцией распределения вероятностей, следует:

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

2.С помощью генератора случайных чисел выбрать случайное десятичное число в пределах от 0 до 1 (с требуемым числом разрядов).

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

4.Опустить из этой точки пересечения перпендикуляр на ось абсцисс.

5. Записать полученное значение х. Далее оно принимается как выборочное значение. б. Повторить шаги 2-5 для всех требуемых случайных переменных, следуя тому порядку, в котором они были записаны.



В задачах исследования операций метод Монте-Карло применяется в трех основных ролях:

1) при моделировании сложных, комплексных операций, где присутствует много взаимодействующих случайных факторов;

2) при проверке применимости более простых, аналитических методов и выяснении условий их применимости;

3) в целях выработки поправок к аналитическим формулам типа «эмпирических формул» в технике.

Основным недостатком аналитических моделей является то, что они неизбежно требуют каких-то допущений, в частности, о «марковости» процесса.

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



2. Задача 1

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

Ресурсы	Норма затрат ресурсов на товары	Общее количество ресурсов
	1-го вида	2-го вида
1 2 3 4	2 1 4 0	2 2 0 4	12 8 16 12

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

Решение:

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

Ограничения по использованию ресурсов имеют вид:

Ресурс 1 -



Ресурс 2 -

Ресурс 3 -

Ресурс 4 -

Экономико-математическая модель задачи имеет вид:

Для получения решения графическим методом строим прямые:

	0	6			0	8
	6	0			4	0

Рис. 1 - Область допустимых решений: ОАВС



Строим прямую:

	0	-3
	0	2

И вектор (2;3)

Максимум ищем в точке области допустимых решений наиболее удаленной от прямой по направлению вектора . Он достигается либо в точке А, либо в точке В. Найдем их координаты:

А (0; 4)	В (4; 2)

Теперь найдем значение целевой функции в каждой точке:

Таким образом, максимум функции достигается в точке В. Для того, чтобы получить максимум прибыли 14 ден.ед. необходимо произвести 4 ед. продукции первого вида и 3 ед. продукции второго вида. Если решать задачу на минимум, то необходимо найти такое решение, при котором предприятие получит наименьшую функцию. Минимум функции необходимо искать в точке области допустимых решений самой близкой к прямой по направлению вектора . Очевидно, что он достигается либо в точке О (0; 0). Тогда полученная прибыль будет равна 0.

Значит, для того, чтобы получить минимально возможную прибыль (в данном случае вообще не получить ее) необходимо не производить продукцию.

3. Задача 2

Годовая потребность машиностроительного завода в шинах марки Bridgestone В250 (175/70 R13 82H) составляет 70 000 шт., расходы на один заказ - 600 руб., издержки по содержанию запасов - 10 руб. за шт. в год. Завод работает 300 дней в году. Доставка заказа осуществляется в течение трех дней.

Определите:

а) оптимальный размер поставки;

б) годовые расходы на хранение запасов;

в) период поставок;

г) точку заказа.

Решение:

Дано:

М =70000 шт.- годовой спрос

t = 3 дня - время поставки

К = 600 руб. - стоимость заказа (накладные расходы)

h = 10 руб. - затраты на хранение одной упаковки (удельные издержки хранения)

Т = 300 дней - количество рабочих дней в году

а) Оптимальный объем поставки составит:



б) Годовые расходы на хранение составят:

в) Период поставки равен:

или

0,0414 *300 = 12.42=12 дней

г) Точка заказа равна:

4. Задача 3

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

Вариант, задачи	Параметр	Параметр Тср = 1/м
4.9	15	12

Оцените основные характеристики работы данной бухгалтерии как СМО с отказами (указание руководства не допускать непроизводительных потерь рабочего времени!). Определите, сколько бухгалтеров должно работать в бухгалтерии в отведенные дни с сотрудниками, чтобы вероятность обслуживания сотрудников была выше 85%.

Решение:

1. Рассчитаем вероятность отказа в обслуживании по формуле:

Ротк=Рn=Р0 ,

P0=;

- нагрузка на систему.

2. Расчет нагрузки на систему (рис. 2);

Рис. 2 - Расчет нагрузки на систему

3. Расчет вероятности Р0 ячейке С6 без степени -1, для 1 числа канала получаем в ячейки В5 данные =1+($F$1^A5/ФАКТР(A5)), дальше заполняем ячейку В6 чтоб там получились данные =B5+($F$1^A6/ФАКТР(A6)) и протягиваем её до В14, получаем таблицу:



4. Рассчитаем вероятность Р0 в ячейке С5 ставя ячейку В5 в степень -1, чтоб там получились данные =B5^-1, и скопируем формулу в ячейки С6:С14, получиться таблица:

5. Рассчитаем вероятность Ротк чтобы в ячейке D5 получились данные =C5*$F$1^A5/ФАКТР(A5), и скопируем формулу в ячейки D6:D14, получится таблица:



6. Относительная пропускная способность В, т.е. вероятность того, что заявка будет обслужена,

статистическое моделирование поставка запас

7. Абсолютная пропускная способность А получим, умножая интенсивность потока заявок ?? на В,

.

8. Среднее число занятых каналов ;

.



Рис. 2 - График вероятности отказа в обслуживании

Расчет характеристик системы массового обслуживания:



Вывод. Из графика видно, что минимальное число каналов обслуживания, при котором вероятность обслуживания работника будет выше 85%, равно n=7.

5. Задача 4

Статистический анализ показал, что случайная величина Х (длительность обслуживания клиента в парикмахерской) следует показательному закону распределения с параметром м, а число клиентов, поступающих в единицу времени (случайная величина Y), - закону Пуассона с параметром . Значения параметров и м по вариантам приведены в таблице.

Вариант, задача	Параметр	Параметр м
5.9	2.4	1.1

Организуйте датчики псевдослучайных чисел для целей статистического моделирования (использования метода Монте-Карло). Получите средствами MS Excel 15 реализаций случайной величины Х и 15 реализаций случайной величины Y.

Решение:

Для получение случайных чисел с показательным законом распределения использовано соотношение

1.Получим случайные числа от 0 до 1 в ячейках $С$3:$Q$3. При использовании функции =СЛЧИС()



Случайные данные.

2.Расчитаем время между очередными поступлениями в ячейках $C$4:$Q$4. Для их получения используем следующие функцию =-1/$D$1*LN(C3)

Расчет времени между поступлениями.

3.Расчитаем время обслуживания округленное (в строках 7 и 9) с помощью формулы =60*(-1/$F$1)*LN(СЛЧИС())

Расчет времени обслуживании по работнику 1 и 2

4.Расчитаем время окончания обслуживания работника 1 строчку 6 складываем со строкой 7 и работника 2 строку 6 складываем со строкой 9.

Расчет окончания обслуживания первого и второго работника.

5.Далее последовательно сравниваются время окончания обслуживания каналами (строки 8 и 10) и время поступления требований (строка 6); соответственно, в счетчике отказов (строка 11) фиксируется 0 (требование принято к обслуживанию) или 1 (требование отказано в обслуживании) .

Первое требование выполняется первым мастером => C11=0 - требование принято.

Вторая заявка поступает в время D6=12. Проверяем: первый мастер еще работает (время окончания обслуживания C8=36.8 > времени поступления новой заявки D6=12). Второй мастер свободен, значит ему и обрабатывать эту заявку => D11=0 - требование принято.

Третья заявка поступает в время Е6=14. Проверяем: первый мастер занят (время окончания обслуживания C8=39 >времени поступления новой заявки Е6=14), второй тоже не может D10=53.9. Требование не будет выполнено => E11=1.

Четвертая заявка поступает в время F6=18. Проверяем: первый мастер закончил работу (время окончания обслуживания C8=7.6<времени поступления новой заявки F6=18). Заявка будет выполнена.

Пятая заявка поступает в G6=19. Проверяем: первый мастер занят (время окончания обслуживания F8=58.8 >времени поступления новой заявки G6=19), второй тоже не может D10=124.5. Требование не будет выполнено => G11=1.

С 6 по 9 заявку не будет выполнена, так как время окончания обслуживания >времени поступления новой заявки.

Десятая заявка поступает в время L6=36. Проверяем: первый мастер еще работает (время окончания обслуживания F8=97.6> времени поступления новой заявки L6=36), у второго мастера время окончания обслуживания D10=23.5<времени поступления новой заявки L6=36 => L11=0 - требование принято.

Одиннадцатая заявка поступает в время М6=38. Проверяем: первый мастер закончил работу (время окончания обслуживания F8=37.2<времени поступления новой заявки M6=38). Заявка будет выполнена.

Время поступления остальных заявок раньше, чем освободятся мастера, таким образом, остальные заявки не будут выполнены (по условию очереди нет). => строка 11 далее заполняется 1.

В соответствии со счетчиком отказов (в ячейках $C$11:$Q$11) зафиксировано 10 отказов, а требований 15 => статистическая оценка вероятности отказав данной системы массового обслуживания при N=15 равна (10/15)=0,67.



Заключение

Метод Монте-Карло используется очень часто, порой некритично и неэффективным образом. Он имеет некоторые очевидные преимущества:

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

б) Он приводит к выполнимой процедуре даже в многомерном случае, когда численное интегрирование неприменимо, например, при числе измерений, большим 10.

в) Его легко применять при малых ограничениях или без предварительного анализа задачи.

Он обладает, однако, некоторыми недостатками, а именно:

а) Границы ошибки не определены точно, но включают некую случайность. Это, однако, более психологическая, чем реальная, трудность.

б) Статическая погрешность убывает медленно.

в) Необходимость иметь случайные числа.

Размещено на Allbest.ru