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

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 (надстройка Поиск решения).

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

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

Решение:

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

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

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

f () = 2х₁+3х₂ > max.

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

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

х₁? 0, х₂? 0.

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

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

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

2x₁ +2x₂=12; х₁+2х₂=8; 4х₁=16; 4х₂=12.

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

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

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

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

Этот вектор показывает направление наискорейшего изменения целевой функции. Линия 2х₁+3х₂ = а (а — постоянная величина) перпендикулярна вектору-градиенту. Она называется линией уровня. Для максимизации целевой функции перемещаем линию уровня в направлении вектора-градиента до тех пор, пока она не покинет пределов ОДР. Предельная точка области при этом движении и является точкой максимума целевой функции, в нашей задаче это точка, А (Рис 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 выполняем следующие действия:

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

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

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

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

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

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

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

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

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

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

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

Задание 3.

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

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

Определите:

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

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

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

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

Решение:

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

Годовая потребность л = 70 000 шт.

Период Т = 300 дней Накладные расходы s = 600 руб.

Удельные издержки хранения: Н = 10 руб/шт.год (h = руб/шт.день) Время ожидания доставки t = 3 дня Для решения задачи применяем классическую модель управления запасами (модель Уилсона).

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

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

q=2898(руб.).

3. Период поставок равен ф = = = 12,42 12 (дней).

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

= t = = 700 (шин) Рис. 5 График поставок.

Задание 4.

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

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

Указание. Для исследования предлагаемой хозяйственной ситуации используйте методы теории массового обслуживания. При моделировании предполагается, что поток требований на обслуживание является простейшим (пуассоновским), а продолжительность обслуживания распределена по экспоненциальному (показательному) закону. Задачу решите с помощью средств 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:

Таблица 1.

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

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

Таблица 2.

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

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

В = 1 — Р_отк = 1 — Р₀.

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

А = лВ = 15· 0,470 588 235 = 7,58 823 525.

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

М = = 1,411 764 705.

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

Таблица 3.

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

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

5. На основании данных таблицы 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*(-½, 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. Орлова И. В., Половников В. А. Экономико-математические методы и модели: компьютерное моделирование: учебное пособие. — М.: Вузовский учебник, 2012.

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

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