Ирина Эланс
Метод статистического моделирования (метод Монте-Карло). 2
Оглавление
1. Метод статистического моделирования (метод Монте-Карло)
Метод статистического моделирования, известный в литературе также
под названием метода Монте-Карло, дает возможность конструировать для
ряда важных задач алгоритмы, хорошо приспособленные к реализации на
компьютерах. Возникновение метода Монте-Карло связывают обычно с
именами Дж.Неймана, С.Улама, Н.Метрополиса, а также Г.Кана и Э.Ферми; все они в 40-х годах работали в Лос-Аламосе (США) над созданием первой
атомной бомбы. Название "Монте-Карло" произошло от города Монте-Карло
(княжество Монако), известного своими казино, ибо одним из простейших
приборов для генерирования случайных чисел служит рулетка.
Хотя общепринятого определения методов Монте-Карло не существует,
тем не менее под этим названием подразумевают численные методы решения
математических задач при помощи моделирования случайных величин и
процессов. Основная идея метода − связь между вероятностными
характеристиками различных случайных процессов (вероятностями случайных событий или математическими ожиданиями случайных величин) и величинами, являющимися решениями задач математического анализа (значениями интегралов, решениями дифференциальных уравнений и т.п.). Оказывается, что вместо вычисления ряда сложных аналитических выражений можно "экспериментально" определить значения соответствующих вероятностей и математических ожиданий. Этот метод получил широкое развитие в связи с новыми возможностями, которые дают быстродействующие электронные вычислительные машины.
Продемонстрируем суть метода на простейшей задаче. Пусть требуется
приближенно определить математическое ожидание MX с.в. X. Пусть x1, x2,
...,xn − значения величины X, полученные при n независимых испытаниях
(измерениях) с.в. X. Тогда величина
где Xk, k = 1, ..., n − независимые с.в. с общим распределением, cсовпадающим с распределением с.в. X, в соответствии с центральной предельной теоремой распределена по закону, близкому к гауссовому с параметрами:
Поэтому имеет место оценка (с надежностью 0,997)
Таким образом, в этом случае "время" связано обратной зависимостью с
достигаемой точностью ε
=
Необходимо отметить одну особенность метода Монте-Карло, состоящую
в том, что оценка погрешности вычислений имеет вероятностный характер. При этом методе нельзя утверждать, что ошибка не превысит какого-либо значения. Можно только указать границы, за которые ошибка не выйдет с вероятностью, близкой к единице. В частности, в оценке (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 ден. ед./ед.
[?] Сформируйте производственную
программу выпуска продукции, обеспечивающую
максимальную прибыль от ее
реализации. Постройте экономико-
Решение:
1. Построим экономико-
Переменные: x1 – количество продукции 1-го вида и х2 – количество продукции 2-го вида.
Целевая функция: это прибыль от реализации обоих видов продукции, которую необходимо максимизировать f() = 2х1+3х2 → max.
Ограничения по ресурсам:
Ограничения по количеству продукции: х1 ≥ 0, х2 ≥ 0.
2. Решим полученную задачу линейного программирования графическим методом.
Построим ОДР задачи. Линейное неравенство описывает некоторую область на плоскости. Определим, какие полуплоскости описывают неравенства, заданные в системе неравенств ограничений по ресурсам.
Для этого строим прямые:
2x1 +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). Для нахождения координат этой точки достаточно решить систему из двух уравнений прямых, получаемую из соответствующих ограничений и дающих в пересечении точку максимума.
; ;
Значение целевой функции в этой точке равно:
max 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
Рассчитайте параметры моделей экономически выгодных размеров заказываемых партий.
Годовая
потребность
Определите:
а) оптимальный размер поставки;
б) годовые расходы на хранение запасов;
в) период поставок;
г) точку заказа.
Решение:
Введем обозначения для данных:
Годовая потребность λ = 70000 шт.
Период Т = 300 дней
Накладные расходы s = 600 руб.
Удельные издержки хранения: Н = 10 руб/шт.год (h = руб/шт.день)
Время ожидания доставки t = 3 дня
Для решения задачи применяем классическую модель управления запасами (модель Уилсона).
Согласно формуле Уилсона, оптимальный размер поставки равен
Годовые расходы на хранение запасов составят
q=2898(руб.)
Период поставок равен
τ = = = 12,42 12 (дней)
Точка заказа равна
= t = = 700 (шин)
Рис. 5 График поставок.
Задание 4
В бухгалтерии организации в определенные дни непосредственно с сотрудниками работают два бухгалтера. Если сотрудник заходит в бухгалтерию для оформления документов (доверенностей, авансовых отчетов и пр.) в тот момент, когда оба бухгалтера заняты обслуживанием ранее обратившихся коллег, то он уходит из бухгалтерии, не ожидая обслуживания. Статистический анализ показал, что среднее число сотрудников, обращающихся в бухгалтерию в течение часа, λ = 15 , а среднее время, которое затрачивает бухгалтер на оформление документа, – Тср = 12 мин (параметр Тср = 1/µ = 1/5 (часа)).
[?] Оцените основные
У к а з а н и е. Для исследования предлагаемой хозяйственной ситуации используйте методы теории массового обслуживания. При моделировании предполагается, что поток требований на обслуживание является простейшим (пуассоновским), а продолжительность обслуживания распределена по экспоненциальному (показательному) закону. Задачу решите с помощью средств MS Excel.
Решение:
1. Рассчитаем вероятность
отказа в обслуживании по
,
где = ; - нагрузка на систему.
λ = 15 – средняя интенсивность входящего потока заявок;
μ = 5 – средняя интенсивность обслуживания.
Получаем нагрузка ∝ = 3.
Рассчитаем по приведенным выше формулам основные показатели системы для нашей задачи. Воспользуемся средствами MS Excel.
2. На рабочем листе MS Excel «СМО с отказами» выполняем следующие действия:
1) Создаем таблицу, содержащую столбцы: Число каналов, Вероятность Р0, Вероятность Ротк , а также сумму (1+∝+∝^2/2!+⋯+∝^n/n!) = ; то есть в ячейках С5-С14 будем рассчитывать значения Вероятности Р0 без степени -1.
В ячейку С5 вводим значение 4, рассчитанное как 1+(для одного канала обслуживания n=1); далее в ячейке С6 вводим формулу: =C5+(3^B6/ФАКТР(B6)) и копируем формулу в ячейки С7-С14. Получаем таблицу 1:
2) Рассчитываем в ячейке D5 значение Вероятности Р0 по формуле: =С5^-1 и копируем формулу в ячейки D6-D14.
Затем в ячейке Е5 рассчитываем значение вероятности отказа в обслуживании Вероятности Ротк по формуле: =D5*(3^B5/ФАКТР(B5)) и копируем формулу в ячейки Е6-Е14. Результаты приведены в таблице 2:
3. Проведем расчет относительной (В) и абсолютной (А) пропускной способности для нашей системы (n = 2), и среднего числа занятых каналов обслуживания (М).
Относительная пропускная способность (вероятность того, что сотрудник будет обслужен):
В = 1 – Ротк = 1 – Р0
Абсолютная пропускная способность равна:
А = λВ = 15·0,470588235 = 7,058823525
Среднее число занятых каналов равно:
М = = 1,411764705
Результаты вычислений приведены в таблице 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 вводим исходные данные и создаем таблицу для расчета случайных величин 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.
2. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие. – М.: Вузовский учебник, 2012.
3. Орлова И.В., Половников
В.А. Экономико-математические
4. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – 2-е изд., испр. и доп. – М.: Вузовский учебник : ИНФРА-М, 2012.
5. Кремер Н.Ш. Исследование операций в экономике. – 2-е изд., перераб. и доп. – М.: Юрайт, 2012.
