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

Размещено на http://www.allbest.ru/

Имитационное моделирование представляет собой численный метод проведения на ЭВМ вычислительных экспериментов с математическими моделями, имитирующими поведение реальных объектов, процессов и систем во времени в течение заданного периода. При этом функционирование таких объектов и процессов разбивается на элементарные явления, подсистемы и модули. Функционирование этих элементарных явлений, подсистем и модулей описывается набором алгоритмов, которые имитируют элементарные явления с сохранением их логической структуры и последовательности. При исследовании сложных систем, подверженных случайным возмущениям используются вероятностные имитационные модели, в которых влияние случайных факторов учитывается с помощью задания вероятностных характеристик случайных процессов (законы распределения вероятностей, спектральные плотности или корреляционные функции). При этом результаты, полученные при воспроизведении на имитационной модели рассматриваемого процесса, являются случайными реализациями. Поэтому для нахождения объективных и устойчивых характеристик процесса требуется его многократное воспроизведение, с последующей статистической обработкой полученных данных. Именно поэтому исследование сложных процессов и систем, подверженных случайным возмущениям, с помощью имитационного моделирования принято называть статистическим моделированием. Статистическая модель случайного процесса - это алгоритм, с помощью которого имитируют работу сложной системы, подверженной случайным возмущениям; имитируют взаимодействие элементов системы, носящих вероятностный характер. Тогда статистическое моделирование можно определить как способ изучения сложных процессов и систем, подверженных случайным возмущениям, с помощью имитационных моделей. Методика статистического моделирования, который часто называют методом Моне-Карло, состоит из следующих этапов: 1. Моделирование на ЭВМ псевдослучайных последовательностей с заданной корреляцией и законом распределения вероятностей (метод Монте- Карло), имитирующих на ЭВМ случайные значения параметров при каждом испытании; 2. Использование полученных числовых последовательностей в имитационных математических моделях. 3. Статистическая обработка результатов моделирования.

Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений. Как правило, предполагается, что моделирование осуществляется с помощью электронных вычислительных машин (ЭВМ), хотя в некоторых случаях можно добиться успеха, используя приспособления типа рулетки, карандаша и бумаги. Термин "метод Монте-Карло" (предложенный Дж. Фон Нейманом и С. М. Уламу в 1940-х) относится к моделированию процессов с использованием генератора случайных чисел. Термин Монте-Карло (город, широко известный своими казино) произошел от того факта, что "число шансов" (методы моделирования Монте-Карло) было использовано с целью нахождения интегралов от сложных уравнений при разработке первых ядерных бомб (интегралы квантовой механики). С помощью формирования больших выборок случайных чисел из, например, нескольких распределений, интегралы этих (сложных) распределений могут быть аппроксимированы из (сгенерированных) данных.

Возникновение идеи использования случайных явлений в области приближенных вычислений принято относить к 1878 г., когда появилась с помощью случайных бросаний иглыработа Холла об определении чисел на разграфленную параллельными линиями бумагу. Существо дела заключается в том, чтобы экспериментально воспроизвести событие, , и приближенно оценить этувероятность которого выражается через число вероятность.

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

Метод Монте-Карло оказал и продолжает оказывать существенное влияние на развитие метода вычислительной математики (например, развитие методов численного интегрирования) и при решении многих задач успешно сочетается с другими вычислительными методами и дополняет их. Его применение оправдано в первую очередь в тех задачах, которые допускают теоретико-вероятностное описание. Это объясняется как естественностью получения ответа с некоторой заданной вероятностью в задачах с вероятным содержанием, так и существенным упрощением процедуры решения. В тех случаях, когда имеется теоретико-вероятностное описание задачи, использование метода Монте-Карло может существенно упростить упомянутые ее решение. Впрочем, как будет следовать из дальнейшего, во многих случаях полезно и для задач строго детерминированных строить вероятностную модель (рандомизовать исходную задачу) с тем, чтобы далее использовать метод Монте-Карло.

Задание 2 приближенный вычисление математика моделирование

Предприятие выпускает три вида изделий (И1, И2, И3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблицах. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков ресурсов. Найти решение задачи симплексным методом с представлением всех симплексных таблиц (промежуточных шагов решения) и проанализировать полученные результаты. Составить двойственную задачу. Определить двойственные оценки из последней симплексной таблицы и провести анализ последней симплексной таблицы.

Вариант 9



	И1	И2	И3	З
Р1	2	5	8	58
Р2	8	4	5	55
Р3	6	6	2	69
П	7	4	1

Решение:

1) Сформулируем экономико-математическую модель задачи

Обозначим через X1, X2, X3 количество изделий каждого типа

Целевая функция (ЦФ)

f(x)=7 +4+

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

2+5+8?58

8+4+5?55

6+6+2?69

,,?0

2) Поиск оптимального плана выпуска

Решение задачи выполним с помощью надстройки EXCEL Поиск решения. В нашей задаче оптимальные значения вектора X=(x1, x2, x3) будут помещены в ячейках B3:Е3, оптимальное значение ЦФ в ячейке Е6.

Введем исходные данные. Введем зависимость для целевой функции с помощью функции СУММПРОИЗВ.



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

Введем зависимость для левых частей ограничений. В Поиске решения введем значение ЦФ, адреса искомых переменных, добавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями. (Рис.2)



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

После ввода параметров для решения ЗЛП нажимаю кнопку "выполнить". На экране появилось сообщение, что решение найдено.

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



Полученное решение означает, что максимальный доход 52,75 единиц предприятие может получить при выпуске 2,25 единиц Изделия 1и 9,25 Изделия 2. При этом Ресурс 2 и Ресурс 3 будут использованы полностью, а из 58 единиц запаса Ресурса 3 будут использованы только 50,75.

Создам отчет по результатам поиска решения.

Рис.4 Содержание отчета по результатам

В отчете по результатам содержатся оптимальные значения переменных X1, X2, X3, которые соответственно равны 2,25; 9,25;0; значение ЦФ и левые части ограничений.

3) Сформулируем экономико-математическую модель двойственной задачи к исходной задаче.

В двойственной задаче будет 3 неизвестных, т.к. в исходной задаче три функциональных ограничения. Обозначим их через Y1,Y2,Y3.

ЦФ в двойственной задаче сформулирую на минимум.

Коэффициентами при неизвестных в ЦФ двойственной задачи являются свободные члены в системе ограничений исходной задачи.

g()=58+55+69>min

Введем ограничения двойственной задачи

2+8+6?7

5+4+6?4

8+5+2?1

,,?0

Проделаю те же операции с двойственной задачей, что и с исходной. Получу:

Рис.5 Решение двойственной задачи

Решение двойственной задачи нахожу в протоколе Поиска решений Отчет по устойчивости.



Рис.6 Содержание отчета по устойчивости

Двойственные оценки Y1=0; Y2=0,75; Y3=0,16666667

Проведем анализ полученного оптимального решения исходной задачи с помощью двойственных оценок

1) Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений второй теоремы двойственности

Ресурсы 2 и 3 имеют отличную от нуля оценки 3/4 и 1/6-эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции.

Ресурс 1 используется не полностью (50,75<58), поэтому имеет нулевую двойственную оценку. Этот ресурс не влияет на план выпуска продукции.

Общая стоимость используемых ресурсов при выпуске 2,25 единиц Ресурса 1и 9,25 единиц Ресурса 2 составит 52,75.

g()=58*y1+55*y2+69*y3=58*0+55*3/4+69*1/6=52,75

Задание3

Решить транспортную задачу методом потенциалов.

Имеются три поставщика продукции с соответствующими предложениями а1, а2 и а3 и три потребителя, спрос которых составляет в1, в2 и в3 соответственно. Стоимость перевозки единицы груза из каждого пункта отправления до каждого пункта назначения задается матрицей С.

Вариант 9

а1= 300, а2 = 100, а3 = 190

в1 = 213, в2 = 157, в3 = 130

Решение:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	Запасы
1	5	3	2	300
2	3	4	1	100
3	1	2	1	190
Потребности	213	157	130

Проверим необходимое и достаточное условие разрешимости задачи.

?a=300+100+190=590

?b=213+157+130=500

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 90 (500--590). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

1) Занесем исходные данные в распределительную таблицу.



Рис. 7 Ввод исходных данных

2) Введем граничные условия и назначим целевую функцию

Рис.8 Назначение ЦФ и ввод граничных условий

3) Осуществим ввод зависимостей и ограничений задачи с определенными параметрами



Рис.9 Ввод зависимостей, ограничений задачи

4) Получим решение

Рис.10 Решение задачи

В результате получен оптимальный план перевозок

Рис. 11 Оптимальный план перевозок

X12=157 единиц груза следует перевезти от первого поставщика второму потребителю;

X13=53 единицы груза следует перевезти от первого поставщика третьему потребителю;

X14=90 единиц груза следует перевезти от первого поставщика четвертому потребителю;

Х21=23 единицы груза следует перевезти от второго поставщика первому потребителю;

Х23=77 единиц груза следует перевезти от второго поставщика третьему потребителю;

Х31=190 единиц груза следует перевезти от третьего поставщика первому потребителю;

Общая стоимость перевозок =913.

Задание4

Найти оптимальные стратегии и цену игры, заданной платежной матрицей.

Решение:

Рассмотрим игру двух лиц, интересы которых противоположны. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.

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

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	a = min(Ai)
A1	3	4	3
A2	2	3	2
A3	5	3	3
A4	4	2	2
b = max(Bi)	5	4

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 3, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min(bj) = 4.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 3 ? y ? 4. Находим решение игры в смешанных стратегиях.

2. Находим решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

3x1+2x2+5x3+4x4 ? 1

4x1+3x2+3x3+2x4 ? 1

F(x) = x1+x2+x3+x4 > min

найти максимум функции Ф(y) при ограничениях:

3y1+4y2 ? 1

2y1+3y2 ? 1

5y1+3y2 ? 1

4y1+2y2 ? 1

Ф(y) = y1+y2 > max

Решим эти системы в Excel.

Рис.12 Минимум функции F(x)

Рис.12 Максимум функции F(y)

Оптимальный план можно записать так:

x3 = 1/11

x1 = 2/11

F(x) = 1*1/11 + 1*2/11 = 3/11

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

pi = g*xi; qi = g*yi.

Цена игры: g = 1 : 3/11 = 32/3

p1 = 32/3 * 2/11 = 2/3

p2 = 32/3 * 0 = 0

p3 = 32/3 * 1/11 = 1/3

p4 = 32/3 * 0 = 0

Оптимальная смешанная стратегия игрока I:

P = (2/3; 0; 1/3; 0)

q1 = 32/3 * 1/11 = 1/3

q2 = 32/3 * 2/11 = 2/3

Оптимальная смешанная стратегия игрока II:

Q = (1/3; 2/3)

Цена игры: v=32/3

3. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?aijqj ? v

?aijpi ? v

M(P1;Q) = (3*1/3) + (4*2/3) = 3.667 = v

M(P2;Q) = (2*1/3) + (3*2/3) = 2.667 ? v

M(P3;Q) = (5*1/3) + (3*2/3) = 3.667 = v

M(P4;Q) = (4*1/3) + (2*2/3) = 2.667 ? v

M(P;Q1) = (3*2/3) + (2*0) + (5*1/3) + (4*0) = 3.667 = v

M(P;Q2) = (4*2/3) + (3*0) + (3*1/3) + (2*0) = 3.667 = v

Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Оптимальный план двойственной задачи равен:

y1 = 1/11

y2 = 2/11

F(y) = 1*1/11+1*2/11 = 3/11

Задание5

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

В приходной кассе работают С операторов-кассиров. Средняя продолжительность обслуживания одного клиента составляет D мин.

Определить характеристики работы приходной кассы как объекта СМО.

Значения коэффициентов условия задачи
№ варианта Значения	1	2	3	3	5	6	7	8	9	10
А	11	10	10	9	8	9	8	11	7	7
В	220	220	300	300	280	270	240	300	200	240
С	2	2	3	3	4	4	3	3	2	4
D	4	3	4	3	4	3	5	5	2	5

Решение:

Введем в ячейки рабочего листа исходные данные:



Интенсивность потока преобразуется из чел./день в чел./мин по формуле:

Рассчитаем значение :

Рассчитаем значение :

Приступаем к определению характеристик СМО.

1. Вероятность простоя каналов



2. Вероятность занятости всех каналов обслуживанием

3. Вероятность того, что заявка окажется в очереди

4. Среднее число заявок в очереди

5. Среднее время ожидания заявки в очереди

6. Среднее время пребывания заявки в очереди

7. Среднее число занятых обслуживанием каналов

8. Среднее число свободных каналов



9. Коэффициент занятости каналов обслуживания

10. Среднее число заявок



Список используемых источников

1. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - М.: Вузовский учебник, 2004. - 144 с.

2. Леоненков А. Решение задач оптимизации в среде MS Excel -СПб..БХВ- Петербург, 2005.- 704 с.. ил.

3. Сдвинков О.А. математика в MS Excel 2002- М… Солон-Пресс, 2004-192 с.. ил.

4. Калихман И.Л. Сборник задач по математическому программированию. Изд. 2-е, доп. И перераб. М., “Высшая школа”, 1975.-270 с.

5. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник.- М.. Издательско-торговая корпорация “Дашков и К°”, 2003.

Размещено на Allbest.ru

...