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

 

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

Метод статистического моделирования, известный в литературе также под названием метода Монте-Карло, дает возможность конструировать для ряда важных задач алгоритмы, хорошо приспособленные к реализации на компьютерах. Возникновение метода Монте-Карло связывают обычно с именами Дж.Неймана, С.Улама, Н.Метрополиса, а также Г.Кана и Э.Ферми; все они в 40-х годах работали в Лос-Аламосе (США) над созданием первой атомной бомбы. Название "Монте-Карло" произошло от города Монте-Карло (княжество Монако), известного своими казино, ибо одним из простейших приборов для генерирования случайных чисел служит рулетка.

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

Продемонстрируем суть метода на простейшей задаче. Пусть требуется приближенно определить математическое ожидание MX с.в. X. Пусть x1, x2,...,xn ? значения величины X, полученные при n независимых испытаниях (измерениях) с.в. X. Тогда величина

(1)

где Xk, k = 1,..., n ? независимые с.в. с общим распределением, cсовпадающим с распределением с.в. X, в соответствии с центральной предельной теоремой распределена по закону, близкому к гауссовому с параметрами:

M, D

Поэтому имеет место оценка (с надежностью 0,997)

(2)

Таким образом, в этом случае "время" связано обратной зависимостью с достигаемой точностью ?

= (3)

Необходимо отметить одну особенность метода Монте-Карло, состоящую в том, что оценка погрешности вычислений имеет вероятностный характер. При этом методе нельзя утверждать, что ошибка не превысит какого-либо значения. Можно только указать границы, за которые ошибка не выйдет с вероятностью, близкой к единице. В частности, в оценке (2) эта вероятность равнялась 0,997. В соответствии с основной идеей метода Монте-Карло для приближенного вычисления величины a необходимо "придумать" такую с.в. X, чтобы MX = a. При этом сама величина X может быть функцией какой-то скалярной или векторной случайной величины, или даже функционалом от случайного процесса. Поэтому первоочередной задачей при использовании метода Монте-Карло является задача моделирования случайных величин или случайных процессов.

Задание 2

моделирование алгоритм линейный программирование

Решите графическим методом типовую задачу оптимизации. Осуществите проверку правильности решения с помощью средств MS Excel (надстройка Поиск решения).

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

РесурсНорма затрат ресурсов на производство единицы продукцииОбщее количество ресурса1-го вида2-го вида1221221283401640412

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

Решение:

. Построим экономико-математическую модель задачи:

Переменные: x1 - количество продукции 1-го вида и х2 - количество продукции 2-го вида.

Целевая функция: это прибыль от реализации обоих видов продукции, которую необходимо максимизировать

f() = 2х1+3х2 ? max.

Ограничения по ресурсам:

Ограничения по количеству продукции:

х1 ? 0, х2 ? 0.

. Решим полученную задачу линейного программирования графическим методом.

Построим ОДР задачи. Линейное неравенство описывает некоторую область на плоскости. Определим, какие полуплоскости описывают неравенства, заданные в системе неравенств ограничений по ресурсам.

Для этого строим прямые:

x1 +2x2=12 ; х1+2х2=8 ; 4х1=16 ; 4х2=12

Выберем точку начала координат (0;0), подставим в первое неравенство и получим 0?12. Данное утверждение является верным, следовательно, неравенству соответствует полуплоскость, содержащая начало координат. Аналогично определяем полуплоскости по другим ограничениям.

Условие неотрицательности количества продукции определяют полуплоскости с граничными прямыми х1=0 и х2=0 соответственно.

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

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

Этот вектор показывает направление наискорейшего изменения целевой функции. Линия 2х1+3х2 = а (а - постоянная величина) перпендикулярна вектору-градиенту . Она называется линией уровня. Для максимизации целевой функции перемещаем линию уровня в направлении вектора-градиента до тех пор, пока она не покинет пределов ОДР. Предельная точка области при этом движении и является точкой максимума целевой функции, в нашей задаче это точка А (Рис 1). Для нахождения координат этой точки достаточно решить систему из двух уравнений прямых, получаемую из соответствующих ограничений и дающих в пересечении точку максимума.

; ;

Значение целевой функции в этой точке равно:

f()= 2*4+3*2 = 14

3. Ответ: Для получения максимальной прибыли (14 ден. ед.) от реализации двух видов продукции необходимо произвести 4 ед. продукции 1-го вида и 2 ед. продукции 2-го вида.

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

min f() = 2*0+3*0 = 0

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

Рис 1. Графическое решение ЗЛП.

4. Проверка правильности решения с помощью средств MS Excel (надстройка Поиск решения).

На рабочем листе MS Excel выполняем следующие действия:

)Указываем адреса ячеек, в которые будут помещены результаты решения: В3-С3.

)Вводим исходные данные - коэффициенты для целевой функции В4-С4, нормы затрат ресурсов на производство обоих видов продукции A8- C11, ограничения по ресурсам: F8- F11.

)Вводим зависимость для целевой функции: D4.

)Вводим зависимости для ограничений по ресурсам: D8 - D11. Рис. 2

Рис. 2. Вводится функция для вычисления целевой функции.

)Запускаем надстройку Поиск решения.

)Назначаем целевую ячейку: D4, вводим ячейки переменных В3-С3; вводим условия ограничений по ресурсам. Рис. 3

Рис. 3 Введены условия задачи

)Нажав кнопку Найти решение, получаем Результаты поиска решения. Рис.4

Рис. 4 Решение найдено

)В результате решения задачи получили ответ: Целевая функция, определяющая максимальную прибыль, равна 14 ден.ед.; количество продукции 1-го вида равно 4 ед., количество продукции 2-го вида равно 2 ед.

Задание 3

Рассчитайте параметры моделей экономически выгодных размеров заказываемых партий.

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

Определите:

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

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

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

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

Решение:

Введем обозначения для данных:

Годовая потребность ? = 70000 шт.

Период Т = 300 дней

Накладные расходы s = 600 руб.

Удельные издержки хранения: Н = 10 руб/шт.год (h = руб/шт.день)

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

Для решения задачи применяем классическую модель управления запасами (модель Уилсона).

.Согласно формуле Уилсона, оптимальный размер поставки равен

2.Годовые расходы на хранение запасов составят

q=2898(руб.)

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

? = = = 12,42 12 (дней)

.Точка заказа равна

= t = = 700 (шин)

Рис. 5 График поставок.

Задание 4

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

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

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

Решение:

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

,

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

? = 15 - средняя интенсивность входящего потока заявок;

? = 5 - средняя интенсивность обслуживания.

Получаем нагрузка ? = 3.

Рассчитаем по приведенным выше формулам основные показатели системы для нашей задачи. Воспользуемся средствами MS Excel.

. На рабочем листе MS Excel «СМО с отказами» выполняем следующие действия:

) Создаем таблицу, содержащую столбцы: Число каналов, Вероятность Р0, Вероятность Ротк, а также сумму (1+?+?^2/2!+?+?^n/n!) = ; то есть в ячейках С5-С14 будем рассчитывать значения Вероятности Р0 без степени -1.

В ячейку С5 вводим значение 4, рассчитанное как 1+(для одного канала обслуживания n=1); далее в ячейке С6 вводим формулу: =C5+(3^B6/ФАКТР(B6)) и копируем формулу в ячейки С7-С14. Получаем таблицу 1:

Таблица 1

) Рассчитываем в ячейке D5 значение Вероятности Р0 по формуле: =С5^-1 и копируем формулу в ячейки D6-D14.

Затем в ячейке Е5 рассчитываем значение вероятности отказа в обслуживании Вероятности Ротк по формуле: =D5*(3^B5/ФАКТР(B5)) и копируем формулу в ячейки Е6-Е14. Результаты приведены в таблице 2:

Таблица 2

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

Относительная пропускная способность (вероятность того, что сотрудник будет обслужен):

В = 1 - Ротк = 1 - Р0

Абсолютная пропускная способность равна:

А = ?В = 15·0,470588235 = 7,058823525

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

М = = 1,411764705

Результаты вычислений приведены в таблице 3.

Таблица 3

PоткВАМ0,5294117650,4705882357,0588235251,411764705

4. В результате проведенных расчетов можно сделать следующие выводы:

СМО функционирует с перегрузкой: из двух бухгалтеров, обслуживающих работников, занято в среднем около 1,5. При этом почти 53% сотрудников уходят необслуженными.

.На основании данных таблицы 2 с помощью мастера диаграмм MS Excel построим график зависимости вероятности отказа в обслуживании от числа каналов (Рис.6)

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

Из графика видно, что для того, чтобы вероятность обслуживания сотрудников была выше 85% (Ротк < 0,15), в бухгалтерии в отведенные дни с сотрудниками должно работать n = 5 бухгалтеров.

Задание 5

Статистический анализ показал, что случайная величина Х (длительность обслуживания клиента в парикмахерской) следует показательному закону распределения с параметром µ =1,1 ; а число клиентов, поступающих в единицу времени (случайная величина Y), - закону Пуассона с параметром ? = 2,4.

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

Решение:

На рабочем листе MS Excel вводим исходные данные и создаем таблицу для расчета случайных величин X; Y. Вводим значения параметров данных законов распределения µ =1,1 и ? = 2,4 в ячейки F1 и D1 (Рис. 7).

Рис.7 15 реализаций случайных величин Х и Y.

Согласно условию задачи, случайная величина X (длительность обслуживания клиента) следует показательному закону распределения:

Хi = ? ;

где Рi - случайные числа с равномерным их распределением в интервале от 0 до 1.

Получим Рi с помощью функции =СЛЧИС() Мастера функций (категория Mатематические). Для этого в ячейку С4 вставим функцию

=СЛЧИС() и копируем ее в ячейки С4:Q4 (Рис. 8).

Рис.8 Использование функции =СЛЧИС()

Получим 15 реализаций случайной величины Х (длительность обслуживания клиента в парикмахерской, мин.). Для этого:

В ячейку C5 вводим формулу: =60*(-1/1,1)*LN(C4). Копируем эту формулу в ячейки С5:Q5.

Получим 15 реализаций случайной величины Y (время между приходом в парикмахерскую двух клиентов, мин.). Для этого:

В ячейку С6 вводим формулу: =60*(-1/2,4)*LN(С4). Копируем эту формулу в ячейки С6:Q6.

Введем учет времени прихода в парикмахерскую клиентов (Время поступления требования, мин.). Для этого:

В ячейку С7 вводим формулу: =С6 (время прихода 1-го клиента).

В ячейку D7 вводим формулу: =C7+D6 (время прихода 2-го клиента).

Копируем последнюю формулу в ячейки E7:Q7 (время прихода следующих клиентов). Получаем зафиксированное кумулятивным образом на временной оси (0;Т) время (i=1,2,3…15) поступления требований в минутах (с округлением).

Литература

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

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

. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: учебное пособие. - М.: Вузовский учебник, 2012.

. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - 2-е изд., испр. и доп. - М.: Вузовский учебник : ИНФРА-М, 2012.

. Кремер Н.Ш. Исследование операций в экономике. - 2-е изд., перераб. и доп. - М.: Юрайт, 2012.

1. Метод статистического моделирования (метод Монте-Карло) Метод статистического моделирования, известный в литературе также под названием метода Монте-К

Больше работ по теме: