Метод статистического моделирования (метод Монте-Карло)
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-го
вида
|
|
1
|
2
|
2
|
12
|
2
|
1
|
2
|
8
|
3
|
4
|
0
|
16
|
4
|
0
|
4
|
12
|
Прибыль от реализации продукции
первого вида составляет 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.
) Вводим зависимости для
ограничений по ресурсам: 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,529411765
|
0,470588235
|
7,058823525
|
1,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.