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

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 ден. ед./ед.

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

 

                          

 Решение:

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 выполняем следующие действия:

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 дней в году. Доставка заказа  осуществляется в течение трех  дней.

        Определите:

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

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

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

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

 

                           Решение:

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

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

Период Т = 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.