Метод статистического моделирования (метод Монте-Карло)
Изучение особенностей метода статистического моделирования, известного в литературе под названием метода Монте-Карло, который дает возможность конструировать алгоритмы для ряда важных задач. Решение задачи линейного программирования графическим методом.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.12.2014 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
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.
В ячейку С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 - Р0
Абсолютная пропускная способность равна:
А = лВ = 15·0,470588235 = 7,058823525
Среднее число занятых каналов равно:
М = = 1,411764705
Результаты вычислений приведены в таблице 3.
Таблица 3
|
Pотк |
В |
А |
М |
|
|
0,529411765 |
0,470588235 |
7,058823525 |
1,411764705 |
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*(-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. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: учебное пособие. - М.: Вузовский учебник, 2012.
4. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - 2-е изд., испр. и доп. - М.: Вузовский учебник : ИНФРА-М, 2012.
5. Кремер Н.Ш. Исследование операций в экономике. - 2-е изд., перераб. и доп. - М.: Юрайт, 2012.
Размещено на Allbest.ru
Подобные документы
Связь стохастических процессов и дифференциальных уравнений. Алгоритм Бюффона для определения числа Пи. Геометрический алгоритм Монте-Карло интегрирования. Применение метода Монте-Карло в логистике. Алгоритм Метрополиса, квантовый метод Монте-Карло.
курсовая работа [258,0 K], добавлен 26.12.2013Случайная выборка из генеральной совокупности. Сущность метода Монте-Карло. Определение адекватности принятой эконометрической модели. Линейная регрессионная модель вида. Система нормальных уравнений в матричной форме. Параметры регрессионной модели.
контрольная работа [323,5 K], добавлен 08.12.2010Понятие имитационного моделирования, применение его в экономике. Этапы процесса построения математической модели сложной системы, критерии ее адекватности. Дискретно-событийное моделирование. Метод Монте-Карло - разновидность имитационного моделирования.
контрольная работа [26,7 K], добавлен 23.12.2013Определение площади фигуры аналитическим методом (с помощью вычисления определенного интеграла) и методом статистических испытаний Монте-Карло. Построение графиков для наглядной демонстрации результатов эксперимента. Вычисление доверительного интервала.
лабораторная работа [211,9 K], добавлен 15.10.2013Характеристика метода Монте-Карло. Его преимущество и недостатки, области применения. Решение задач по оптимизации использования ресурсов, управлению запасами и системе массового обслуживания с помощью средств аналитического и имитационного моделирования.
контрольная работа [1,4 M], добавлен 22.11.2013Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Методи генерування послідовності рівномірно розподілених випадкових чисел. Перевірка якості псевдовипадкових чисел. Використання методу Монте-Карло в імітаційному моделюванні. Обчислення інтегралу методом Монте-Карло. Переваги програмного методу.
методичка [2,8 M], добавлен 29.01.2010Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Статистическая модель случайного процесса. Численный метод Монте-Карло. Типы имитации, ее достоинства и возможности. Простая имитационная модель системы обработки документов. Использование для моделирования языка Siman. Его основные моделирующие блоки.
презентация [1,6 M], добавлен 22.10.2014Изучение метода экспоненциального сглаживания - эффективного метода прогнозирования, который дает возможность получить оценку параметров тренда, характеризующих не средний уровень процесса, а тенденцию, сложившуюся к моменту последнего наблюдения.
лабораторная работа [28,7 K], добавлен 15.11.2010
