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

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

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 ден. ед./ед. [?] Сформируйте производственную программу выпуска продукции, обеспечивающую максимальную прибыль от ее реализации. Постройте экономико-математическую модель задачи, дайте необходимые комментарии к ее элементам и получите решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?

Решение:

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

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

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

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

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

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

х₁ ≥ 0, х₂ ≥ 0.

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

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

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

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

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

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

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

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

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

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

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

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

М =  = 1,411764705