Введение

Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений.

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

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

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

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

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

Все приборы первой группы можно разделить на две подгруппы. Одни определяют характеристики записанных случайных сигналов за достаточно большое время, намного превышающее время реализации самого случайного процесса. Другие (они в последнее время вызывают наибольший интерес) позволяют получать характеристики случайного процесса оперативно, в такт с поступлением информации при натурных испытаниях новых систем управления, так как, пользуясь их показаниями, можно непосредственно изменять процесс управления и в ходе эксперимента наблюдать за результатами этих изменений.[4 с 754]

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

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

Можно утверждать, что метод Монте-Карло остаётся чистым методом моделирования случайных процессов, чистым математическим экспериментом, в известном смысле лишённым ограничений, свойственным другим методам. Рассмотрим данный метод применительно к решению различных задач управления.

Общая характеристика метода Монте-Карло

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

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

Каждое значение случайной величины xi представляется в машине двоичным числом, которое поступает с выхода датчика случайных чисел на сумматор. Для статистического моделирования рассматриваемой задачи требуется N-кратное повторение решения.[5]

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

Этот метод широко применяется и для исследования дискретных систем управления, когда используются кибернетические модели в виде вероятностного графа (например, сетевое планирование с ?-распределением времени выполнением работ) или вероятностного автомата.

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

При решении алгебраических уравнений методом Монте-Карло число операций пропорционально числу уравнений, а при их решении детерминированными численными методами это число пропорционально кубу числа уравнений. Такое же приблизительно преимущество сохраняется вообще при выполнении различных вычислений с матрицами и особенно в операции обращения матрицы. Основной идеей, которая используется при решении детерминированных задач методом Монте-Карло, является замена детерминированной задачи эквивалентной статистической задачей, к которой можно применять этот метод. Естественно, что при такой замене вместо точного решения задачи получается приближённое решение, погрешность которого уменьшается с увеличением числа испытаний.[5]

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

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

Задача получения случайных чисел обычно разбивается на две. Вначале получают последовательность случайных чисел, имеющих равномерное распределение в интервале [0,1]. Затем из неё получают последовательность случайных чисел, имеющих произвольный закон распределения. Один из способов такого преобразования состоит в использовании нелинейных преобразований.

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

Преимущество метода Монте-Карло состоит в том, что он способен “сработать” там, где отказывают другие методы.

Аналитические методы исследования позволяют существенно уменьшить погрешность метода Монте-Карло и могут поднять его до уровня получения качественных закономерностей. Синтез аналитических и статистических методов может свести D к очень малой величине, следовательно, уменьшить погрешность.[9]

Приведем примеры задач, решаемых методом Монте-Карло:

- расчет системы массового обслуживания;

- расчет качества и надежности изделий;

- теория передачи сообщений;

- вычисление определенного интеграла;

- задачи вычислительной математики;

- задачи нейтронной физики и другие.

2. Примеры решения задач с помощью метода Монте-Карло

Отыскание возможных значений случайной величины Х (моделирование) называют «разыгрыванием случайной величины».

Рассмотрим пример, иллюстрирующий метод статистических испытаний:

Система контроля качества продукции состоит из трех приборов. Вероятность безотказной работы каждого из них в течение времени Т равна 5/6. Приборы выходят из строя независимо друг от друга. При отказе хотя бы одного прибора вся система перестает работать. Найти вероятность Ротк того, что система откажет за время Т.

Решим задачу аналитически и методом статистических испытаний.

Аналитическое решение. Событие А (выход из строя хотя бы одного из трех приборов за время Т) и событие А (ни один из трех приборов не выйдет из строя за время Т) - противоположные. Вероятность Р (А) =(5/6)3. Искомая вероятность

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

Для определения того, выйдет или не выйдет из строя за время Т отдельный прибор, будем подбрасывать игральную кость. Если выпадет одно очко, то будем считать, что прибор вышел из строя; если два, три, ..., шесть очков, то будем считать, что прибор работал безотказно. Вероятность того, что выпадет одно очко, так же как и вероятность выхода прибора из строя, равна 1/6, а вероятность того, что выпадет любое другое число очков, как и вероятность безотказной работы прибора, равна 5/6.[9]

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

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

II. Задача оптимизации

Условия задачи.

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

Таблица 1

Прибыль от реализации продукции первого вида составляет 2 ден. ед./ед., второго вида - 3 ден. ед./ед.

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

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

Решение

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

Переменные: х - первый вид продукции, у - второй вид продукции.

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

F(х)=2х+3у>max

Ограничения: Исходя из условий задачи получается следующие ограничения:

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

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

Рассмотрим ограничение х и у Получается, что решение находится в первой четверти.

Теперь рассмотрим ограничение . Координаты двух точек прямой 2х+2у=12 это (0;6) и (6;0). Выберем точку вне ограниченной прямой 2х+2у=12-(0;0). Точка (0;0) удовлетворяет неравенство , поэтому и точки, принадлежащие полуплоскости, в которой лежит точка (0;0) также будут удовлетворять это неравенство.

Ограничение . Координаты двух точек прямой это (8;0) и (0;4). Выберем точку вне ограниченной прямой -(0;0). Точка (0;0) удовлетворяет неравенство, поэтому и точки, принадлежащие полуплоскости, в которой лежит точка (0;0) также будут удовлетворять это неравенство.

Теперь рассмотрим неравенство .Оно соответствует прямой .

Рассмотрим неравенство . Оно соответствует прямой у=3.

В результате пересечения построенных четырех полуплоскостей получаем многоугольник ABCDE-область допустимых значений.

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

F(х)=2х+3у.

Оно представляет собой уравнение прямой линии, а также скалярное произведение двух векторов: =(х;у) и нормального вектора прямой (перпендикуляра) =(2;3).

Полученный график представлен на рисунке 1.

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

Полученные значения будут равны х=4 и у=2. Тогда целевая функция будет равняться Zmax=2*4+3*2=14

Теперь осуществим проверку правильности решения с помощью средств MS Excel.

Для этого сначала введем исходные данные, как показано на рисунке 2.

Рисунок 2

Теперь, используя Мастер функций, воспользуемся Математической формулой СУММПРОИЗВ. В ячейку F20 введем Массив1 C8:D8 и Массив 2 C20:D20.

В ячейку E14 введем формулу СУММПРОИЗВ с Массивом 1 $C$8:$D$8 и Массивом 2 C14:D14. И протянем это формулу до Е17 , получится, как показано на рисунке 3.

Рисунок 3

Теперь используя надстройку Поиск решений, найдем оптимальный метод решения данной задачи. В диалоговом окне «Поиск решений», необходимо ввести следующие данные, представленные на рисунке 4,для решения задачи.

Рисунок 4

Задача решена, и на экране мы видим решение, которое представлено на рисунке 5.

Рисунок 5

Таким образом, мы видим полученные результаты. Они соответствуют нашему решению графическим способом.

Таким образом, получается, что максимально полученная прибыль предприятием в 14 ден.единиц может быть достигнута при производстве 4 Х-продукции и 2 У-продукции. При данном оптимальном плане выпуска продукции используется первый ресурс (2*4+2*2=12); максимально используется второй ресурс (4+2*2=8); максимально используется третий ресурс (4*4=16); однако четвертый ресурс используется на 4 единицы меньше чем есть (4*2<12).

Таким образом, получается, что был найден оптимальный план решения задачи.

Если задачу решать на минимум с помощью надстройки Поиск решений, то получиться следующее решение, указанное на рисунке 6.

Рисунок 6

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

III. Задача управление запасами

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

Определите:

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

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

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

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

Решение

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

Со(расходы на один заказ)=600 рублей

Сh(издержки по содержанию запасов)=10 рублей

D(годовой спрос на изделия)=70000 штук

Т(количество рабочих дней)=300 дней

h(ежедневная стоимость хранения товара)=Ch/Т=10/300=0,033руб

а) оптимальный объем заказа

q= 2898,27 то есть чтоб не было дефицита на одну единицу, необходимо поставить 2898 единиц.

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

TC=+,

тогда получается что TC=+ = 28983

Именно такая сумма будет потрачена на управление запасами в год .

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

t= = 15,6 дней. Таким образом, получается что период доставки будет составлять 15,6 дней

г) Поскольку среднесуточный спрос равен 70000/300 дней = 233,33 шин, то получается, что точка заказа будет равна 233,33* 15.6 = 3499.95 = 3500 единиц

IV. Задача СМО с помощью аналитического моделирования

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

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

Решение

Эту задачу решим с помощью средств MS Excel.

Подготовим следующие исходные данные, представленные на рисунке 7.

Рисунок 7

Мю равняется 5, поскольку находиться как 60 минут/Т ср.мин. Следовательно 60/12=5. Чтоб найти Альфу введем в ячейку Е9 формулу Е6/Е8. То есть Лябма /Ню. Получаем 3.

Теперь будем заполнять таблицу. Для того чтобы посчитать вероятность отказа в обслуживании, нам необходимо произвести промежуточные расчеты, для чего в исходных данных у нас есть столбец скобки () и столбец Р0. В первую ячейку столбца Скобки(), необходимую для дальнейших вычислений, а именно в С12, забьем формулу =E9^B12/ФАКТР(B12). В ячейке С13 будет уже формула =C12+$E$9^B13/ФАКТР(B13).Её мы можем протянуть до ячейки С22. Теперь, совершив это действие, посчитаем Р0. Для этого в ячейку D12 забьем формулу =1/С12. То есть по сути считаем 1/промежуточный, полученный до этого результат. И протягиваем эту формулу до D22. Теперь мы можем посчитать вероятность отказа в обслуживании. В свою очередь это равняется частному между произведением промежуточного полученного значения Р0, время обслуживания в среднем в степени количество каналов на факториал количества каналов. Таким образом, получается, что нам необходимо забить в ячейку Е12 следующую формулу: =D12*$E$9^B12/ФАКТР(B12). И эту формулу необходимо протянуть до Е22. И теперь осталось найти пропускную способность. Она равняется 1минус Вероятность отказа в облуживании. Поэтому в ячейку F12 мы забиваем формулу =1-Е12 и опять же протягиваем её до F22. Итак, у нас получается таблицу со следующими данными, представленными на рисунке 8.

Рисунок 8.

Теперь из этой таблицы мы легко может определить вероятность отказа в обслуживании и относительную пропускную способность для нашей двухканальной системы массового обслуживания. Вероятность отказа будет 0,53, а относительная пропускная способность 47 %. Таким образом, получается, что абсолютная пропускная способность будет 7,06. Это число мы можем найти, перемножив Лямбу на относительную пропускную способность для данной системы массового обслуживания. Среднее число занятых каналов получается 1,412. Это мы находим путем деления абсолютной пропускной способности на Ню.

Для того чтобы определить какое количество бухгалтеров должно работать чтоб пропускная способность была больше 85 %, необходимо также обратиться к таблице, представленной на рисунке 8. Мы видим, что пропускная способность больше 85%, а именно 89 %, у пятиканальной системы. Таким образом, получается, что для того, чтобы пропускная системы была больше 85 % необходимо 5 бухгалтера на производстве. Тогда вероятность отказа будет всего лишь 0,11, абсолютная пропускная способность 13,35, а среднее число занятых каналов 2,67.

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

V. Задача СМО с помощью имитационного моделирования

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

Лямба =2,4, а Мю=1,1

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

Решение

Имитационный эксперимент мы проведем в соответствии с заданием с помощью средств средствами MS Excel. Для этого подготовим следующие исходные данные, представленные на рисунке 9.

Рисунок 9.

В строку номер требования введем в ячейки соответственно числа от 1 до 15.

Альфа посчитаем путем деления Лямбы на Мю, получается Альфа= 2,181818

С помощью Мастер функций введем начиная в ячейки Случайное число(0-1) случайные числа. Для этого среди математических функций выберем функцию =СЛЧИС() и зафиксируем её в каждой ячейке нажав F9 на клавиатуре.

Далее нам необходимо подсчитать Время между заявками в минутах. Это делается путем того, что пишем формулу =-60*1/Лямба*Натуральный логарифм случайного числа. Соответственно в ячейку N15 мы вводим формулу

=-60*1/2,4*LN(N14). И так мы вводим эту же формулу во всю строку 9, подставляя только соответствующий натуральный логарифм.

И теперь осталось подсчитать время поступление требования системы в минутах. Соответственно по первому требованию время поступлении равняется времени между заявками в минутах. Второе же требование равняется время поступление по первому требованию и плюс время между заявками по второму требованию. И далее по строке соответственно. Таким образом, у нас получатся следующие датчики, представленные на рисунке 10.

Рисунок 10.

Заключение

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

Задачи, решаемые методом Монте-Карло: расчет системы массового обслуживания; расчет качества и надежности изделий; теория передачи сообщений; вычисление определенного интеграла; задачи вычислительной математики; задачи нейтронной физики; моделирования дискретных и непрерывных случайных величин; моделирования случайных процессов и полей; вычисления многомерных интегралов и другие.

А так же в работе были решены четыре задача. Задача по оптимизации использовании ресурсов была решена с помощью средств MS Excel, а также графическим способом. Кроме того, в данной задачи нашли не только решение задачи на максимуму, но и также решение задачи на минимум.

Вторая задача управления запасами. Здесь мы рассмотрели как найти оптимальный объем заказов, период поставок, точку заказа и затраты на управление заказами в год.

Третья задача это задача по системе массового обслуживания. Эту задачу мы решали с помощью средств аналитического моделирования. Кроме того, что мы определили показатели по задаче для заданного количества каналов, а именно 2, также было определено сколько каналов необходимо использовать чтоб относительная пропускная способность была более 85 %.

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

Список литературы

1. Основы теории игр: учебное пособие / Мар. гос. ун-т;Н.С. Садовин, Т.Н. Садовина. -- Йошкар-Ола, 2011. -- 119 с.

2.Основы высшей математики для юристов:Учебное пособие/Кафедра инфомационного oбеспечения ОВД РЮИ МВД России; Арбузов П.В., Гуде С.В., Герасименко В.Н., Медянцев Д.В..-2012.-234 с.

3. Бережная Е.В. Математические методы моделирования экономических систем / Е.В. Бережная, В.И. Бережной. -- М.: Финансы и статистика, 2003. -- 368 с.

4. Бригхем Ю. Финансовый менеджмент / Ю. Бригхем, М. Эрхардт. -- СПб.: Питер, 2007. -- 960 с.

5. Дубров А.М. Компонентный анализ и эффективность в экономике: учеб. пособие для вузов / А.М. Дубров. -- М.: Финансы и статистика, 2002. -- 352 с.

6. Федосеев В.В., Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров. -3-е изд., перераб. и доп. - М.: Юрайт, 2012.

7. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие. - М.: Вузовский учебник, 2012.