Файл: Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие.pdf

30 90 A=RND(1)
100 IF A>0.5 THEN X=X+10 ELSE X=X-10 110CIRCLE(320+X,175),2,I MOD 15 115 FOR I=0 TO 30000: NEXT
120 NEXT
130 PRINT X
140 NEXT
Задание на самостоятельную работу
Сравните точное и имитационное решение, совпадают ли они?
4.2. Двумерная модель 1 случайных блужданий [2]
Пусть вероятность того, что, начав с перекрестка, пьяница пой- дет на север, юг, восток или запад одинакова. Какова вероятность того, что пройдя 10 кварталов, пьяный окажется не далее двух кварталов от исходного места?
Обозначим местоположение пьяного на каждом перекрестке двумерным вектором (х, у), где х – направление с востока на запад, а у – направление с севера на юг. Каждое перемещение на восток дает +1 к х, а перемещение на запад дает –1 к х. Аналогично на се- вер +1 и на юг –1. За начальное положение возьмем начало коор- динат (0, 0). Если в конце прогулки протяженностью в 10 кварталов окажется, что сумма абсолютных значений х и у больше 2, то, сле- довательно, пьяный ушел от начальной точки дальше, чем на 2 квартала. На каждом перекрестке вероятность выбора любого направления равна 0,25. Поэтому для каждого перекрестка берем случайное двузначное число и условимся, что если получается чис- ло в интервале 00–24, то идем на восток (х+1), для 25–49 идем на запад (х–1), для 50–74 идем на север (у+1) и для 75–99 идем на юг
(у –1). Алгоритм программы приведен на рис. 6.

31
Рис. 6. Блок-схема модели поведения пьяного прохожего
Задание на самостоятельную работу
Напишите программу и определите вероятность.
4.3. Двумерная модель 2 случайных блужданий [7]
Рассмотрим блуждание пьяного на плоскости, каждый шаг ко- торого равновероятен в любую сторону и направлен под углом в 45 градусов к осям системы координат – х и у. Как далеко он будет от фонаря через n беспорядочных шагов, каково наиболее вероятное расстояние от фонаря после n шагов? Можно промоделировать кривую его движения с помощью генератора случайных чисел. По- сле моделирования большого числа таких опытов можно опреде- лить вероятное расстояние от исходной точки.

32 1. Будем считать, что фонарь расположен в начале системы ко- ординат х, у.
2. Примем, что первая цифра двузначного случайного числа означает +1 по оси х, если получается нуль или четное число и –1, если число нечётное.
3. Вторая цифра этого числа соответствует

1 по оси у анало- гичным способом.
4. Точка


,
n
n
x y
определяет положение пьяного после n шагов.
5. Расстояние пьяного от фонаря после n шагов определяется выражением
2 2
2
n
n
n
d
x
y


Рассмотрим пример, допустим, первые 5 случайных чисел ока- зались 36, 35, 68, 90 и 35. Построим табл. 1, предполагая, что пья- ница начинает двигаться с координаты (0, 0).
Таблица 1
Шаг Первая цифра Вторая цифра
Расположение точки


,
n
n
x y
1 3
6
(–1, 1)
2 3
5
(–2, 0)
3 6
8
(–1, 1)
4 9
0
(–2, 2)
5 3
5
(–3, 1)
То есть, после 5 шагов расстояние от центра будет


1 2 2
2 5
5 5
3,16
d
x
y



Перемещения пьяницы для первых пяти шагов показаны на рис. 7.
Рис. 7. Траектория случайного блуждания

33
Затем эта оценка усредняется по серии экспериментов. Сравните ее с аналитическим решением
 
1 2
n
d
a n

. То есть, наиболее вероят- ное расстояние от фонаря после n шагов равно длине шага а, умноженной на
 
1 2
n
. Текст программы, реализующий это моде- лирование, приведен ниже.
5 CLS
10 SCREEN 9 20 X0=320:Y0=175 30 INPUT “ВВЕДИТЕ ЧИСЛО ШАГОВ”;N
35 RANDOMIZE
40 FOR I=1 TO N
50 A=INT(RND(1)*100)
60 X=A\10 70 Y=A MOD 10 80 X1=X0:Y1=Y0 90 IF X MOD 2=0 THEN X0=X0+10 ELSE X0=X0-10 100 IF Y MOD 2=0 THEN Y0=Y0+10 ELSE Y0=Y0-10 110 LINE (X1, Y1)-(X0, Y0), I MOD 15 115 FOR J=1 TO 30000:NEXT
120 NEXT
125 PRINT X0,Y0 127 CIRCLE(X0,Y0),5 130 PRINT”РАССТОЯНИЕ ОТ СТОЛБА”;SQRT(((X0-320)/10)^2+((Y0-
175)/10)^2)
140 PRINT”ТЕОРЕТИЧЕСКИ ПРЕДСКАЗЫВАЕМОЕ”;SQR(N)

34 1) как только автобус переходит в состояние А, так мы его ре- монтируем;
2) работает автобус до тех пор, пока не перейдет в состояние В и уже затем ремонтируется.
Лучшей стратегией считается та стратегия, которая дает наиболь- шее среднее число рейсов в день.
При моделировании формируется выборка случайного числа r и имитируется состояние, в котором находится автобус в конце каж- дого рейса. Сначала имитируется один рейс при стратегии 1, затем
– при стратегии 2. Затем подсчитывается среднее число рейсов в день, фактически выполненных при стратегиях 1 и 2 и их разность.
Графическое изображение имитации при стратегии 2 показано на рис. 8.
Рис. 8. Эксплуатационная стратегия 2
Рассмотрим более подробно процесс работы автобуса. Если ав- тобус уходит в рейс в состоянии Е, то имеется вероятность а закон- чить его в состоянии А и вероятность (1– а) остаться в состоянии Е.
Если рейс начинается в состоянии А , то имеется вероятность в за- кончить его в состоянии В и вероятность (1– b) остаться в состоя- нии А. С помощью теории марковских цепей получено аналитиче- ское решение для среднего числа рейсов при стратегиях 1 и 2.


 




2 1
1 1
1
N
N
a
a
a
a
 


 

,














2 2
2 1
1 1
1
N
N
a
b
b
a
ab a b
 
 

 

(29)
При моделировании производим выборку случайного числа r и с помощью табл. 2 имитируем состояние, в котором находится авто- бус в конце рейса.

35
Таблица 2
Автобус выезжает в состоянии
Выборка состояний автобуса в конце рейса.
Автобус приезжает в состоянии
Е
А
В
Е


1
a
r
 


0
r
a
 
–
A
–


1
b
r
 


0
r
b
 
Допустим автобус начинает рейс в состоянии
А
(это возможно только при стратегии 1). Если полученное значение
r
удовлетворя- ет неравенству
r
b

, то автобус заканчивает рейс в состоянии
А
При этом




1 1
P r
b
P r
b
b

 

 
. Блок-схема имитацион- ной модели приведена на рис. 9
В ней использованы следующие обозначения: SG1-логическая переменная «хорошее состояние Е» при первой стратегии, она при- нимает значение 1, если автобус в хорошем состоянии Е при стра- тегии 1 и значение 0, если автобус находится в состоянии А (то же при стратегии 1). SG2 – логическая переменная «хорошее состоя- ние» при стратегии 2: равна 1, если автобус в хорошем состоянии при стратегии 2, 0 – если автобус в состоянии А. SG2 – переменная
«состояние В» при стратегии 2, равна 1, если автобус в состоянии В при стратегии 2, в иных случаях = 0. DMAX – количество дней все- го, D – текущее число дней, RM – число моделируемых рейсов в день, включая отдельные рейсы. RA, RB – число действительно выполненных рейсов в течение дня при стратегиях 1 и 2, соответ- ственно. Z – разность между числом действительно выполненных рейсов при стратегиях 1 и 2 за определенный день, т.е.
Z = RA – RB
SZ – сумма значений Z за D дней. AVERA, AVERB – среднее число рейсов в день при стратегиях 1 и 2 соответственно после М дней.
AVERZ = AVERA – AVERB.

36
Рис. 9. Моделирование двух стратегий обслуживания
Часть блок-схемы между 2 и 3 используется только один раз за каждый моделируемый день, в начале каждого дня еще ни одного рейса не выполнено (RA=RB=0) или смоделировано (RM=0) и ав- тобус начинает рейс в хорошем состоянии Е при обеих стратегиях
(SG1=1, SG2=1, SB2=0).
После точки 3 RM сравнивается с N для проверки условия, не выполнено ли уже максимальное число рейсов в день. Если при стратегии 1 автобус начинает рейс в хорошем состоянии (SG1=1), то этот рейс выполняется (RA=RA+1) и производится выборка со- стояния в конце этого рейса, т.е. если
r
a

, то автобус уже не в

37 хорошем состоянии (SG1=0) , если
r
a

, то изменений нет, т.е. он в состоянии Е. Если же автобус сразу в состоянии А (SG1 = 0), то рейс отменяется (RA

RA + 1) и автобус ремонтируется (SG1=1).
В этом случае нет необходимости выборки числа. После ремонта автобус всегда в хорошем состоянии. Затем мы определяем по табл. 2, в каком состоянии он закончит рейс при стратегии 2. После имитации целого дня (RM = N) подсчитывается SRA, SRB, SZ и имитируется следующий день (D = D+1), если еще не достигнуто требуемое число имитируемых дней (DMAX). После имитации
DMAX дней подсчитывается среднее число рейсов в день при стра- тегиях 1 и 2 и их разность.
Текст программы приведен ниже.
10 INPUT”Введите a,b,n,dm”;A,B,N,DM
20 D=0:SA=0:SB=0:SZ=0 30 RA=0:RB=0:RM=0 40 S1=1:S2=1:S3=0 50 RM=RM+1 60 IF RM95 PRINT N/(1+A)+A*(1-(-A)^N)/(1+A)^2;(A*A*(1-B)^N)-B*B*
(1-(1-A)^N)/A/B/(A-B)
100 END
110 IF S1=1 THEN GOTO 130 120 S1=1:GOTO 150 130 RA=RA+1:Q=RND(1)
140 IF Q0 THEN GOTO 50 160 RB=RB+1:Q=RND(1)
170 IF S2=1 THEN GOTO 200 180 IF QПри
0,1
a

; b = 0.2, n = 60 и dm = 100 программа дает следую- щие данные: среднее количество рейсов при стратегии 1 равно

38 54,4; при стратегии 2–15,9; разница 39,5. Теоретические значения равны соответственно 54,6 и 15. Видно хорошее соответствие меж- ду данными.
Задачи для самостоятельного решения
1. Каждое утро Сэм играет в игру: подбрасывает монету до тех пор, пока разность между числом выпавших гербов и решек не ста- нет равной 3. За каждый бросок монеты платит 1 доллар, при удач- ном исходе получает 8 долларов. На игру он откладывает 10 долла- ров и играет в нее до тех пор, пока либо не проиграет все деньги, либо не выиграет. Определите результат игры за пять дней, будет ли он в выигрыше?
2. Вероятности перемещения пьяницы 50 % прямо, 20 % напра- во или налево и 10 % назад. Использовав 10 попыток, вычислите вероятность того, что он, пройдя 5 кварталов, закончит путь не да- лее чем в 2-х кварталах от исходного состояния.
3. На лист бумаги с параллельными линиями на расстоянии а
друг от друга бросают наугад иглу длиной l. Требуется определить вероятность того, что она пересечет 0,1,2,3 линии. Пусть х – рас- стояние по перпендикуляру от одного конца иглы до первой линии пересекаемой иглой, а

– угол (рис. 10).
Подсчет числа пересечений линий дан в табл. 3.
Рис. 10. Расположение иголки на листе с линиями

39
Таблица 3 l

sin

по длине находится в пределах между
Количество пересечений
(x+а) и (х+2а)
2
(x) и (х+а)
1
(x–а) и (х)
0
(x–2а) и (х–а)
1
(x–3а) и (х–2а)
2
Все значения х в пределах от 0 до а равновероятны, равновероятны также все значения

в пределах от 0 до 2

. Функции распределе- ния для х и

выражаются формулами
1
F
x a

,
2 2
F
  
. Бросок иглы эквивалентен случайному выбору точки с координатами F
1
и
F
2
внутри квадрата со стороной 1. Области квадрата, соответству- ющие пересечениям 0,1,2, .. линий определяются кривыми
1 sin
x n a
   

(n =…–2,–1,0,1,2,...). Вероятности пересечения 0,
1, 2, 3 линий могут быть найдены аналитически или графически путем измерения соответствующих площадей на рис. 11. Для l = 3a
вид квадрата представлен на рис. 11 и результаты расчета приведе- ны в табл. 4.
Рис. 11. Кривые, характеризующие функцию распределения для разных n

40
Таблица 4
Количество пересечений
0 1
2 3
Вероятность
0,107 0,227 0,314 0,352
Проверьте данные расчета и проведите расчет для l = 4a.
4. Производится серия N раз по 10 выстрелов по мишени. Тре- буется оценить вероятность того, что число попаданий в мишень будет четным, т.е. 0, 2, 4, 6, 8, 10.
Вероятность попадания случайной величины в интервал (0, р), где
1
p

, равна длине этого отрезка, т.е.


i
P x
p
p


. Поэтому при каждом выстреле полученное случайное число x
i
сравнивается с заданной вероятностью р и при
i
x
p

регистрируется попадание в цель, иначе – нет.
 
1 1
N
j
i
P y
N
y



,
1
j
y

, если
h
j
– четное, иначе 0.
10 1
,
1... ,
i
i
i
h
h
j
N




а
1
i
h

, если
i
x
p

, иначе 0.
Блок-схема программы приведена на рис. 12.
Рис. 12. Блок-схема программы

41
Напишите программу и определите вероятность, сравните полу- ченное решение с аналитическим решением
 


5 10 2 2
2 10 0
1
k
k
k
k
P y
c p
p





, где


!
!
!
b
a
b
c
a b
a


5.
М
ОДЕЛИРОВАНИЕ СТОХАСТИЧЕСКИХ СИСТЕМ
5.1. Теория марковских цепей [5,9]
На планете Оз никогда не бывает двух ясных дней подряд. Если сегодня ясно, то завтра с вероятностью 1/2 будет лить дождь, либо идти снег. Если сегодня снег (или дождь), то с вероятностью 1/2 погода не изменится. Если она все же меняется, то в 1/2 случаев снег заменится дождем или наоборот и в 1/2 случаев на следующий день будет ясная погода. Определите вероятность ясной погоды на
3-й день, если сегодня дождь.
Математическая теория таких процессов была рассмотрена в
1907 году Марковым и получила название теории марковских це- пей. В общем случае она формулируется так: пусть система может находиться в множестве различных состояний
{S
1
, S
2
,…,S
n
}.
В каждый момент времени она находится в одном из таких состоя- ний. С течением времени система может переходить в другие со- стояния. Вероятность того, что система переходит из состояния S
i
в состояние
S
j
зависит только от состояния
S
i
и определена матрицей переходов
P
, в которой
p
ij
– есть вероятность перехода из
i
-го со- стояния в
j
-е. Также задано некое исходное состояние или вектор вероятностей его реализации. Это и есть марковская цепь. Запишем матрицу переходов для погоды на планете Оз.
1 2 1 4 1 4 1 2 0
1 2 1 4 1 4 1 2
дождь
ясно
снег
дождь
ясно
снег
P

Матрицу переходов можно изобразить графически (рис. 13).