Імітаційне моделювання
Машинна імітація випадковихпараметрів
Методичнівказівки
щодо виконаннялабораторної роботи
Зміст роботи
Методи генеруванняпослідовності рівномірно розподілених випадкових чисел
Завдання
Перевірка якостіпсевдовипадкових чисел
Завдання
Приклади використання методуМонте Карло в імітаційному моделюванні
Обчислення числа
Обчислення визначеногоінтегралу методом Монте-Карло
Методигенерування послідовності рівномірно розподілених випадкових чисел
Для построения последовательности равномернораспределенных случайных чисел используются следующие методы.
Мультипликативно-конгруэнтный метод, или метод степенных вычетов:
xi=axi-1 (mod m), i=l,2,...
x0=b. (1)
где a, m — неотрицательные целые числа.
Согласно (1) необходимо взять последнее случайноечисло, умножить его на a и взять модуль полученного числа по т (т.е.разделить на т и взять остаток в качестве следующего xi).Последовательность равномерно распределенных на отрезке [О, 1]псевдослучайных чисел получается при делении остатка на т.
В качестве модуля обычно выбирают 2Ь или 10d.
На основе конгруэнтной формулы было создано множествогенераторов.
Смешанные генераторы Томпсона основываются на следующейформуле
xi+1=axi + C (mod m)
Аддитивный конгруэнтный метод (Грин,Смит, Клем) используетрекуррентную формулу
xi+1=(xi + xi-1)C(mod m)
Примеры построения последовательности псевдослучайныхравномерно распределенных на отрезке [0; 1] чисел с помощью приведенныхалгоритмов.
Пусть а=111, т=256, b=10.
Тогда с помощью мультипликативно-конгруэнтного методаполучается
x0=b = 10, r0= = x0/m= 10/256=0,039.
Далее получается
x1=ax0(mod m) = 111*10 (mod256) = 1110 mod 256 = 86,
r1=x1/m=86/256=0,336
При тех же параметрах а, m и параметре С=347 с помощью смешанногогенератора Томпсона получаем:
x1=ax0+C(modm)= 111*10 +347 (mod 256) = 1457 mod 256 = 177,
r1=x1/m=177/256=0,691.
Наконец, аддитивно-когруэнтным методом при х0=100,x1=183 получаем
х2 =x0+xl(modm) = (100 + 183) (mod 256) =283 mod 256 = 27,
r2=x2/m=27/256= 0,105.
В табл. 1 приведены результаты расчетов для первых 10псевдослучайных чисел, полученных всеми перечисленными способами.
Переваги програмного методу:
— займає мало місця воперативній пам«яті (близько десяти команд);
— можна поворити спроби;
— забезпечується одноразовапервірка якості випадкових чисел;
— не потрібні зовнішніпристрої.
Недоліки програмного методу:
— швідкість утвореннявипадкових чисел відносно невелика;
— обмежений запас чисел.
Таблица 1
Последовательности псевдослучайных чисел
i Мультипликативно-конгруэнтный метод Смешанный генератор Томпсона Аддитивно — конгруэнтный метод
xi
ri
xi
ri
xi
ri 10 0,039 10 0,039 100 0,391 1 86 0,336 177 0,691 183 0,715 2 74 0,289 26 0,102 27 0,105 3 22 0,086 161 0,629 16 0,063 4 138 0,539 42 0,164 75 0,293 5 214 0,836 145 0,566 224 0,875 6 202 0,789 58 0,227 123 0,480 7 150 0,586 129 0,504 176 0,688 8 10 0,039 74 0,289 171 0,668 9 86 0,336 113 0,441 128 0,500 10 74 0,289 90 0,352 219 0,855
Завдання
Построить последовательности псевдослучайных чисел, используя табличныйпроцессор MS Excel. Получить таблицу, аналогичную таблице 1.
Для вычисления остатка от деления рекомендуется использовать функциюОСТАТ.
Выполнить форматирование.
Описание функции ОСТАТ
Назначение: Возвращает остаток от деления аргумента число на делитель.Результат имеет такой же знак, как и делитель.
Синтаксис
ОСТАТ(число;делитель)
Число — это число, остаток от деления которого определяется.
Делитель — это число, на которое нужно разделить (делитель). Еслиделитель равен 0, то функция ОСТАТ возвращает значение ошибки #ДЕЛ/0!
Замечания
Функция ОСТАТ может быть выражена через функцию ЦЕЛОЕ:
ОСТАТ(n; d) = n — d*ЦЕЛОЕ(n/d)Перевірка якостіпсевдовипадкових чисел
Застосовувати псевдовипадкові числа,утворювані з допомогою програмних генераторів РВП [0, 1], правомірно в томуразі, коли статистичні характеристики їх збігаються з властивостями чисел,породжених деяким ідеальним генератором, що вибирає значення на відрізку [0, 1]рівноймовірно і незалежно одне від одного згідно із законом при x1
Тому успішне застосування методуМонте-Карло можливе лише тоді, коли створювані генератором числа будуть випадковими,рівномірно розподіленими на відрізку [0, 1] і незалежними.Зрозуміло, що за своїми конструктивними особливостями програмні датчики неможуть відтворювати випадкові числа, які повністю задовольняють переліченівимоги. Проте для практичних цілей буває достатньо, щоб послідовність РВП [0,1] приблизно відповідала вимогам ідеального генератора. Таке припущенняперевіряється з допомогою спеціальних статистичних тестів. При цьомувиконуються дві передумови.
1.Генератор псевдовипадкових чиселвважається придатним для використання, якщо він витримує набір напередустановлених тестів.
2.Якість випадкових чисел перевіряєтьсялише один раз на попередньому етапі побудови імітаційної моделі.
Розроблено чимало тестів, котрі дають змогу оцінюватиякість випадкових чисел. Серед них є загальновідомі статистичні методиперевірки гіпотез (перевірка відповідності розподілів за критеріями Пірсона абоКолмогорова, виявлення кореляційної залежності між серіями випадкових чисел — автокореляції), а також і спеціально розроблені для методу Монте-Карло критерії.
Розглянемо кілька спеціальних тестів перевіркиякості випадкових чисел. Особливість їх застосування полягає в тому, щогенератор РВП [0,1] вважають за можливе використовувати лише в тому разі, коливін одночасно відповідає всім вибраним тестам (перевірка датчика припиняється,тільки-но він не відповідає черговому тесту). При цьому багато рішень щодовідповідності датчика тому чи іншому тесту експериментатор приймає наінтуїтивному рівні, спираючись на власний досвід таких досліджень.
Перевірка за моментами розподілу
Для ідеального генератора рівномернорозподілених випадкових чисел математичне сподівання їх дорівнює½, а дисперсія дорівнює 1/12.
Перевірка на рівномірність загистограмою
Розіб»ємо відрізок [0,1] на nрівних частин. Кожне з чисел xiпотрапить на один з таких відрізків. Нехай m1 – кількість випадковихчисел, що потрапили на перший відрізок, m1 – на другий і т.д. Прицьому
m1 +m2 +… +mn= N/
Обчислимо відносні частоти потрапляннявипадкових чисел на кожний із відрізків
p1=m1/N; p2=m2/N;… pn=mn/N,
а далі для перевірки рівномірностіпсевдовппадкових чисел будується гістограма.
Якщо випадкові числа рівномірні, то длядостатньо великих N гістограма (ламана лінія) має наближатися до теоретичноїпрямої у = 1/n.
Число розбиттів n має бути недуже малим, щоб можна було перевірити локальну рівномірність. Водночас і дужевелике n нас не задовольняє, оскільки потрібно буде багато випадковихчисел (N на два — три порядки більше за n). На практиці nберуть таким, що задовольняє нерівність 20 n
Перевірка зa посередніми ознаками
Дивись [1, с. 55].
Перевірка на періодичність
Якщо серед множини програмне утворюванихвипадкових чисел x0,x1,x2,....xl-1немає однакових, а xlзбігається з одним зі створених раніше чисел, то L називається відрізкомаперіодичності. Очевидно, що L
Перевірка на випадковість
Дивись [1, с. 57].
Перевірка генератора в«роботі»
Досить надійним методом установлення якостівипадкових чисел е перевірка генератора РВП [0,1] в «роботі». Згідно з цимметодом складають імітаційну модель, результат роботи якої може бутипередбачений теоретично. Порівнюючи експеріментальний, здобутий за допомогоюЕОМ, і теоретичний результати, можна зробити висновки щодо придатностігенератора випадкових чисел.
Для ілюстрації такого підходу перевірки якостівипадкових чисел розглянемо описану далі гру. Стрілець стріляє по мішені. Якшовін у неї влучить, то отримає виграш 9 грн., а якщо промахнеться — заплатитьштраф у розмірі 1 грн. Імовірність влучити в мішень становить 0,05.
Величина виграшу с випадковою величиною з такимрозподілом:Виграш 9 — 1 Імовірність 0,05 0,95
Математичне сподівання виграшу за один пострілподається у вигляді
mx=9*0,05 + (-1)*0,95=-0,5.
Перевіримо якість випадкових чисел, наведених утабл.Д1. ([3] Таблиця випадкових цифр). Для цього, склавши імітаційну модельгри, математичне сподівання виграшу оцінюватимемо за допомогою середньогоарифметичного значення виграшу 440 пострілів.
Умовимося, що влучення в ціль імітується відношенням x0,95. Із 440 пострілів(440 випадкових чисел таблиці) маємо 21 влучення. Середній виграш
xср=(21*9+(-1)*419)/440=230/440=-0,522.
Точність оцінки математичного сподівання e = 0,022 для такого відносноневеликого числа випробувань вважається задовільною. Звідси можна дійтивисновку, шо перевірений генератор випадкових чисел придатний длярозв'язування задач методом Монте-Карло.Завдання
1. Выполнить проверку правильности генерации случайныхчисел по тесту «Перевірка за моментами розподілу». Результатыпоместить в таблицу следующего вида. Проанализировать результаты. Сделатьвыводы.Количество испытаний Мультипликативно — конгруэнтный метод Смешанный генератор Томсона Математическое ожидание Дисперсия Математическое ожидание Дисперсия 10 50 100 200 300
3.
4.Выполнить проверку правильностигенерации случайных чисел по тесту «Перевірка на рівномірність загистограмою». Создать две гистограммы распределения РВП: длямультипликативно — конгруэнтного метода и для смешанного генератора Томсона.
Перед построением диаграмм рекомендуется создать дветаблицы следующего вида.Мультипликативно — конгруэнтный метод Смешанный генератор Томсона Карманы Частота Карманы Частота 0,05 0,05 0,10 0,10 0,15 0,15 0,20 0,20 0,25 0,25 0,30 0,30 0,35 0,35 0,40 0,40 0,45 0,45 0,50 0,50 0,55 0,55 0,60 0,60 0,65 0,65 0,70 0,70 0,75 0,75 0,80 0,80 0,85 0,85 0,90 0,90 0,95 0,95 1,00 1,00
Рекомендуется следующее оформление диаграммы.
/>
5.Выполнить проверку правильностигенерации случайных чисел также по гистограмме, используя программу на языкеПаскаль (Смотри Приложение 1).
С помощью программы построить три гистограммы.Проанилизировать результаты. Сделать выводы.
В отчет скопировать гистограммы и текст программы.
Прикладивикористання методу Монте Карло в имитационном моделировании
Цель работы — ознакомление с возможностямипрактического применения метода Монте-Карло (1949) – численного методамоделирования случайных величин.
Для примера взяты две задачи: вычислениечисла p и вычисление определённого интеграла. Обчислення числа p
Расчёт числа p проводится путём набрасывания случайных чисел на квадрат со сторонамиравными 1, в который вписана единичная окружность. Общее число случайных точек(на отрезке [0;1) принимается за N, а число точек, попавших в круг – за М.
Число p рассчитывается как:
/>
/>
Чем больше проводится экспериментов, тем точнееполучается результат.
Практическое задание
Провести моделирование с целью исследованиязависимости точности вычисляемого значения p от числа испытаний N.
Для моделирования разработать программное средство.Провести моделирование и результаты внести в таблицу. Проанализироватьрезультат. Сделать выводы.N 10 50 100 150 200 p
Для проведения моделирования студент должен создатьпрограмму на любом из алгоритмических языков или создать электроннную таблицу.Ниже предлагается один из возможных вариантов решения задачи в табличномпроцессоре. таблицу отформатировать. Снабдить комментариями.X Y X^2+Y^2
Попадание в круг
(1 или 0) Приближенное значение числа p 4*M/N
Вычисление
количества испытаний (N) Вычисление суммы попаданий (M) Обчислення визначенного інтегралуметодом Монте-Карло
Вычисление определенного интеграла вида
/>
производится по приближенной формуле:
/>,
где xi — случайная величина, xi =p/2×g, 0
Точность результата также зависит отколичества испытаний
Практическое задание
Провести моделирование с целью исследованиязависимости точности вычисляемого значения интеграла от числа испытаний N.
Для моделирования разработать программное средство.Провести моделирование и результаты внести в таблицу. Проанализироватьрезультат. Сделать выводы.N 10 50 100 150 200 S
Для проведения моделирования студент должен создатьпрограмму на любом из алгоритмических языков или создать электронную таблицу.Ниже предлагается один из возможных вариантов решения задачи в табличномпроцессоре. Таблицу отформатировать. Снабдить комментариями.гамма кси sin() Сумма Количество испытаний Интеграл 0,162 0,255 0,252 0,669 12 0,088
Литература
1. КурицкийБ.Я. Поиск оптимальных решений средствами Ехсеl 7.0. — СПб.: ВНV, 1997. — 384с.
2. Методическиерекомендации к выполнению практических заданий по курсу «Имитационноемоделирование» для студентов специальности 7.050102 заочной формы обучения/ Сост. О.Ю.Полякова. — Харьков: Изд. ХГЭУ, 2002. — 28с.
3. СитникВ.Ф., Орленко Н.С. Імітаційне моделювання.- К.: КНЕУ, 1998.- 232c.
4. Ж.-П.Ламуатье. Упражнения по программированию на Фортране IV. Пер. с франц., подред. Ю.М.Баяковского. – М.: Мир. 1978. с. 167.
5. Соболь И.М. Метод Монте-Карло. — 4-е изд. — М.: Наука. Главная редакцияфизико-математической литературы, 1985.— 80 с. — (Популярные лекции поматематике).
Контрольные вопросы:
1. В чемсущность метода статистического моделирования?
2. Предельныетеоремы теории вероятностей.
3. Какиеспособы генерации последовательностей случайных чисел используются прикомпьютерном моделировании?
4. Почемугенерируемые на компьютере последовательности чисел называютсяпсевдослучайными?
5. Что собойпредставляют конгруэнтные процедуры генерации последовательностей чисел?
6. Какиесуществуют методы проверки качества генераторов случайных чисел?
7. Какиесуществуют способы генерации последовательностей случайных чисел с заданнымзаконом распределения на компьютере?
8. Моделированиедискретных случайных величин.
9. Чемопределяется эффективность компьютерного моделирования систем?
10. Проблемымоделирования систем.
11. Особенностинепрерывно-детерминированного подхода к построению математических моделейсистем.
12. Особенностидискретно-детерминированного подхода к построению математических моделейсистем.
13. Особенностидискретно-стохастического подхода к построению математических моделей систем.
14. Особенностинепрерывно-стохастического подхода к построению математических моделей систем.
15. ПараметрыQ-схемы имитационного моделирования.
16. Определениеоднородного и неоднородного потоков событий.
17. Определениеодинарного и стационарного потоков событий.
18. Определениемногоканального и многофазного обслуживания.
Приложение 1
Анализ генератора случайных чисел
В системе Турбопаскаль имеется функция random, которая дает случайноечисло в интервале [0,1] в соответствии с равномерным законом распределения.Можно разделить этот интервал на р меньших интервалов одинаковой длины инайти, как случайные числа распределяются в этих р интервалах.
Рассмотрим конкретный пример. Пусть значения случайной величины находятсяв интервале: А=0; В=1. Этот интервал будем делить на 20 интервалов: р=20.Генерируются N=10 000 чисел.
Результат работы программы имеет вид гистограммы, где около каждогостолбца отображается номер интервала (кармана) и значение частоты.
Ниже приведен пример гистограммы.
Histogram
1 502 **************************************************
2 456 **********************************************
3 470 ***********************************************
4 528 *****************************************************
5 468 ***********************************************
6 498 **************************************************
7 528 *****************************************************
8 534 *****************************************************
9 476 ************************************************
10 521 ****************************************************
11 503 **************************************************
12 503 **************************************************
13 491 *************************************************
14 498 **************************************************
15 451 *********************************************
16 508 ***************************************************
17 516 ****************************************************
18 529 *****************************************************
19 525 *****************************************************
20 495 **************************************************
Замечание
Кроме рассматриваемого здесь теста «по гистограмме» известны идругие, более совершенные статистические тесты для проверки качества генератораслучайных чисел [*].
*) Кнут. искусство программирования. Т.2.
Пояснение к алгоритму
При составлении программы авторам [5, с. 103-107] предстояло преодолетьодно затруднение — определить, к какому интервалу относится получаемоеслучайное число.
Один из возможных методов состоит в выполнениипоследовательности проверок, которые позволяли бы определить, в какой интервалпопадает число. Этот метод легко программируется, но программа получаетсядлинной и медленной.
Самый быстрый метод заключается в определении целой переменнойJ,соответствующей номеру интервала, к которому относится число. Например, дляинтервала [0,1], разделенного на 20 классов длиной 0.05, можно получитьзначение J следующим образом:
J= целое (20 х) +1
х=0.03®целое(0.6)+1
х=0.06®целое(1.2)+2
Чтобы подсчитать число элементов в каждом классе, можно действоватьследующим образом:
1) получитьслучайное число х,
2) вычислитьJ,
3) установитьT(J)=T(J)+1, где Т – массив из р элементов и каждый элемент T(J) служит счетчикомдля класса J.
Программа
uses Crt;
Var
a,b,p,n,i,j: integer;
Var
t: array [1..20] of integer;
Var
h1,x:Real;
Var
rp,y:Real;
Var
aa: array [1..72] of string[1];
Var
k: integer;
Begin
clrscr;
randomize;
{ writeln('a=0,b=20');
readln(a,b);
writeln('p=20');
readln(p);
writeln('n=10000');
readln(n);}
a:=0;b:=20;p:=20;n:=10000;
for i:=1 to p do t[i]:=0;
h1:=p/(b-a);
for i:=1 to n do
begin
x:=random(b);
j:=trunc((x-a)*h1)+1;
t[j]:=t[j]+1
end;
clrscr;
for i:=1 to p do
writeln(i:3,t[i]:10);
readln;
rp:=p;
for i:=1 to p do t[i]:=0;
for i:=1 to n do
begin
y:=random;
j:=trunc(rp*y)+1;
t[j]:=t[j]+1;
end;
Clrscr;
Writeln('*******');
for i:=1 to p do writeln(i:3,t[i]:10);
readln;
Clrscr;
writeln('Histogram');
for i:=1 to 72 do aa[i]:='*';
for i:=1 to p do
begin
k:=trunc((t[i]+5)/10);
write(i:2,t[i]:4,' ');
{writeln ('k=',k:3);}
for j:=1 to k dowrite(aa[j]);writeln;
end;
readln
end.