Моделирование случайных процессов.

Лабораторная работа №7

Моделирование случайных процессов.

Понятие «случайный» - одно их самых фундаментальных как в математике, так и в повседневной жизни. Моделирование случайных процессов – мощнейшее направление в современном математическом моделировании.

Событие называется случайным, если оно достоверно непредсказуемо.

В вероятностных моделях смена состояний моделируемой системы определяется случайными величинами.

Случайные величины могут применяться при подсчете точных значений. Одним из распространенных приближенных вычислительных способов решения задач является метод Монте-Карло (метод статистических испытаний и статистического моделирования).

Имитационное моделирование в математике.

Имитационное моделирование — это метод исследования, основанный на том, что изучаемая система заменяется имитатором и с ним проводятся эксперименты с целью получения информации об этой системе (суть явления постигается без к экспериментов на реальном объекте).

Вычисление площадей методом Монте-Карло.

С помощью этого метода можно найти площадь любой фигуры G, которая имеет сложный контур, который сложно описать аналитически или сложно проинтегрировать. Нужно вписать эту фигуру в фигуру известной площади, скажем в прямоугольник с вершинами A, B, C, D и бросать точку на эту фигуру. Вероятность попадания точки в G будет равна отношению площадей.

Число успешных попаданий S _фигуры_G

P ( вероятность попадания в G) = --------------------------------------- = -----------------

Общее число бросков S _АВСВ

S _фигуры_G = S _АВСВ * P

Кроме вычисления площадей и объемов с помощью метода Монте – Карло можно вычислять решать системы уравнений и приближённо вычислять значение числа p.

Задание 1. Вычисление числа p методом Монте – Карло.

Вычисление π сводится к нахождению площади круга, радиус которого равен единице, с центром в точке М(0, 0).

Мы знаем, что площадь круга с радиусом 1 равна π

Вычислим эту площадь методом Монте-Карло и проверим будет ли она равна числу π.

1) Строим окружность r = 1, с центром в точке (0, 0). Площадь окружности мы не знаем.

2) Заключаем окружность в квадрат. Площадь квадрата 2*2 = 4

3) Проводим 1000 испытаний:

· Бросаем точку случайным образом в правый верхний сектор квадрата (его площадь 4/4=1) т.е. генерируем пару случайных чисел x и y x, y Î [0, 1].

· Определяем куда попадет точка: если x²+y²≤ 1 (x²+y²=R – уравнение окружности радиуса R, с центром в начале координат), то точка попадет в круг, иначе не попадет.

· Считаем количество попаданий

· Вычисляем вероятность попадания точки в окружность

· Вычисляем площадь единичной окружности (она должна быть близка к числу π ).

Табличная модель.

СЛЧИС() - функция Excel, возвращающая равномерно распределенное случайное число большее либо равное 0 и меньшее 1. Чтобы получить случайное вещественное число между a и b, можно использовать следующую формулу: СЛЧИС()*(b-a)+a

x= СЛЧИС()

y= СЛЧИС()

Результат эксперимента: ЕСЛИ(x*x+y*y< =1; 1; 0)

x	y	Площадь 1/4 квадрата
		Количество попаданий
		Количество испытаний
		Вероятность попадания
		Пи

Проведите 1000, 5000, 10000 испытаний. Как будет зависеть точность вычисления числа p от количества испытаний.

Задание 2. Задача Бюффона (еще один способ вычисления числа p).

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

На листе бумаги начерчены параллельные прямые, находящиеся друг от друга на расстоянии L =1. На лист брошена игла длиной l = 0, 5 (l= L/2). Какова вероятность того, что игла пересечет одну из прямых?

С одной стороны эта вероятность определяется соотношением (найденным Ж.Бюффоном в VIII в):

, если L = 2 ∙ L, то

С другой стороны:

, где N - число бросаний, N₁ - число пересечений иглы с линией.

Имитационное моделирование проведем следующим образом.

Проводим 1000 испытаний (бросков иглы), считаем количество испытаний, в которых игла пересекла ось Х, находим вероятность P пересечения иглой оси Х, и затем вычисляем значение числа p из соотношения:

Положение иглы на листе полностью определяется двумя независимыми случайными величинами:

· углом α (0 < α < π )

· координатой y0 центра иглы. В нашем примере L=1, l = 0, 5, поэтому (-0, 75 < y0 < 0, 75).

Таким образом, чтобы смоделировать одно выпадение иглы, нам необходимо сгенерировать две случайные величины α и y0.

Координаты концов иглы определяются по следующим формулам:

Как определить пересекла ли игла ось Х? Если игла пересекла ось Х, координаты ее концов будут иметь разные знаки (y₁∙ y₂≤ 0)

Табличная модель.

y0 = СЛЧИС()*(0, 75+0, 75)-0, 75

α = СЛЧИС()*ПИ()

Результат бросания: ЕСЛИ(y1*y2< =0; 1; 0)

y0	α	y1	y2	Длина иглы, l	0, 5
				Кол-во бросков, N
				Кол-во попаданий, N1
				Вероятность попадания, Р
				p

Проведите 1000, 5000, 10000 испытаний. Как будет зависеть точность вычисления числа p от количества испытаний.

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

Задание 3. Очередь к одному продавцу

Рассмотрим одну из простейших задач данного класса. Имеется магазин с одним продавцом, в который случайным образом входят покупатели. Если продавец свободен, он начинает обслуживать покупателя сразу, если покупателей несколько, выстраивается очередь.

Первая случайная величина в этой задаче - промежуток между приходами любой последовательной пары покупателей. Покупатели заходят в магазин с интервалом от 0 до 5 мин. Будем считать, что эта случайная величина равномерно распределена на интервале [0, 5] (чтобы была возможность использовать функцию СЛЧИС()). На самом деле распределение Пуассоновское

Вторая случайная величина – длительность обслуживания каждого покупателя. Обслуживание покупателя может занять у продавца от 0 до 10 минут. Также примем, что случайная величина равномерно распределена на интервале [0, 10].

При моделировании систем такого вида возникают следующие вопросы:

Каково среднее время ожидания покупателем в очереди?

Каково среднее время простоя продавца в ожидании покупателя?

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

Табличная модель.

a_i = СЛЧИС()*Т

b_i = СЛЧИС()*t

c₁ = 0, c_i+1=c_i+a_i+1

d₁ = 0, d_i+1=МАКС(c_i+1; e_i) e_i = d_i+b_i

f_i = e_i – c_i

g₁ = 0, g_i+1 = f_i+1 – b_i+1

h₁ = 0, h_i+1 = d_i+1 - e_i

Моделирование очереди к одному продавцу
Максимальный промежуток между приходами покупателей (Т), мин
Максимальное время обслуживания покупателя (t), мин
Среднее время ожидания покупателем в очереди
Среднее время простоя продавца в ожидании
A	B	C	D	E	F	G	H
Промежутки между приходами покупателей	Длительность обслуживания	Условное время прихода покупателя	Момент начала обслуживания	Момент окончания обслуживания	Время, проведенное покупателем в магазине	Время, проведенное покупателем в очереди	Время, проведенное продавцом в ожидании

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

Задание 5. Модель «пьяницы»

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

Табличная модель.

Модель " Пьяницы" - точка блуждает по горизонтальной линии

h max – макс шаг в сторону	=

p	h	x

Постройте с помощью диаграммы траекторию движения точки.

Задание 4. Реализация игры «Жизнь» в Excel

Клетки в исходной таблице Excel слишком велики для нашей задачи. Поэтому придадим им вид небольших квадратов. В качестве примера возьмем игровое поле 5x5.

1) Отведем для игры клетки В2: F6.

2) Если клетка жива, то в ячейку запишем 1, если мертва, то 0. Зададим произвольное начальное состояние

Далее нам понадобятся две вспомогательные таблицы. В ячейках Н2: L6 будет храниться " потенциал" клеток.

3) Для вычисления потенциала клетки В2 введем в ячейку Н2 следующую формулу:

= СУММ(A1: C3)-B2 (1)

В данном случае подсчитывается число живых клеток в окрестности клетки

4) Закончив ввод формулы (1) нажатием клавиши Enter, установим курсор на правый нижний угол клетки Н2 и размножим формулу сначала до ячейки L2, а затем вниз, заполнив всю таблицу Н2: L6.

Сложнее всего задать правило поведения клеточного автомата.

5) Запишем в ячейку В10 правило поведения автомата В2, используя логические функции:

=ЕСЛИ(ИЛИ(H2> 3; H2< 2); 0; ЕСЛИ(H2=3; 1; ЕСЛИ(H2=2; B2; -1))) (2)

Первое ЕСЛИ в функции (2) означает, что клетка будет мертва при потенциале Н2 = 0, 1, 4, 5, 6, 7; второе ЕСЛИ - что при потенциале 3 клетка будет живой, третье ЕСЛИ - что при потенциале 2 состояние автомата в клетке В2 не меняется. Наконец, выражение (-1) означает, что при невыполнении всех предыдущих условий в ячейку В10 будет записано значение (-1). (Заметим, что в данном случае этот вариант невозможен.)

6) Функция (2) записывается только в одну ячейку В10, далее она размножается вправо до ячейки F10, а затем вниз, заполняя всю таблицу B10: F14. Таким образом, если в таблице B2: F6 мы имеем состояние системы в момент t, то в таблице B10: F14 вычисляется состояние системы в следующий момент t + 1.

7) Теперь необходимо скопировать таблицу B10: F14 в таблицу B2: F6. Делается это следующим образом.

Шаг 1. Выделяем таблицу BIO: F14.

Шаг 2. В меню " Правка" выбираем команду " Копировать".

Шаг 3. Устанавливаем курсор в ячейку В2.

Шаг 4. В меню " Правка" выбираем команду " Специальная вставка". В раскрывшейся дополнительной вкладке следует из первого столбца " Вставить" выбрать строку " Значения" и нажать кнопку ОК.

В итоге в таблице B2: F6 появится картинка нового состояния системы.

Процедуру копирования можно существенно ускорить, если подготовить соответствующий макрос. Делается это очень просто.

1) В Excel 2000 в меню " Сервис" выбираем " Макрос", а затем команду " Начать запись".

2) В раскрывшейся вкладке можно дать имя макросу либо оставить предлагаемый вариант " Макрос 1".

3) Назначаем макросу клавишу быстрого вызова, например Ctrl + e.

4) Нажимаем ОК.

5) Появится таблица Excel, и на экране возникнет кнопка " Остановить макрос".

6) Выполним указанные выше операции (шаги 1-4) и нажмем кнопку " Остановить".

Запись макроса будет закончена.

Теперь переход к следующему временному такту будет происходить после каждого нажатия комбинации клавиш Ctrl + е и можно спокойно наблюдать за эволюцией системы.

Примеры структур для игры «Жизнь»:

1. Неизменяемые формы жизни (которые в следующие моменты времени остаются неизменными):

Block Boat

2. Осцилляторы (или переключатели):

Blincker Toad

3. Перемещающиеся (планеры, которые перемещаются по всей игровой площади):

Glider Lightweight spaceship

В каталоге «Практика» откройте файл Lifemodel.xls и посмотрите борьбу двух структур в игре «Жизнь»

Идеи для проектов можно найти в книге «Модели социальных процессов» (электронный вариант http: //bibl.tikva.ru)

Например, на странице 262 описана модель процесса расовой сегрегации. Клеточные автоматы (игра «Жизнь» относится к клеточным автоматам) используются как инструмент для изучения процессов социальной самоорганизации.

Лабораторная работа №7

Моделирование случайных процессов.

Событие называется случайным, если оно достоверно непредсказуемо.

В вероятностных моделях смена состояний моделируемой системы определяется случайными величинами.

12 3	Поделиться: