Введение в компьютерное моделирование. Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие
 Скачать 1.03 Mb.
|
|
4.4. Модель автобусного обслуживания [8] Автобус должен делать в день N рейсов. Первый рейс всегда начинается в исправном состоянии Е, имеется вероятность а сло- маться во время рейса и перейти в состояние А. В этом состоянии он может выйти на следующий рейс. Необходимый ремонт для пе- ревода его в исходное состояние Е занял бы время равное времени одного рейса. Если он не ремонтируется и в состоянии А выходит на следующий рейс, то есть вероятность b, что он закончит рейс в состоянии В. Если он достигает состояния В, то он ремонтируется до следующего утра и все оставшиеся рейсы отменяются. Нужно выбрать одну из двух стратегий обслуживания: 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 RM (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). 42 Рис. 13. Графическое представление матрицы переходов В теории марковских цепей показано, что вероятность того, что система через n шагов перейдет в состояние a j из состояния a i определяется матрицей перехода 0 n P n n j n j j P a P f a P (30) В случае, если -вектор–строка, компоненты которого задают ве- роятности пребывания в соответствующих состояниях в данный момент, то P задает эти вероятности на следующем шаге, а n P – через n шагов. Тогда ответ на поставленный выше вопрос дается матрицей/ 3 0 26 64 13 64 25 64 13 32 6 32 13 32 25 64 13 64 26 64 дождь ясно снег дождь ясно снег P Из нее видно, что вероятность хорошей погоды через 3 дня после дождя равна 13/64. Для получения степеней матрицы Р можно ис- пользовать Mathcad. Задачи на самостоятельную работу 1. Эскадрилья истребителей имеет 4 самолета и получает боевое задание один раз в день утром. Если к концу дня число самолетов из-за потерь уменьшается до 0, 1, 2 самолетов, то она получает из резерва 1 самолет ночью. На следующий день, если в наличии 3 или 4 самолета, то задание дается, иначе – отменяется. Каждый са- 43 молет может быть выведен из строя с вероятностью р. Если на за- дание посылается n самолетов, то вероятность того, что k из них будут выведены из строя, задается биномиальным распределением ! ! ! k n k n p q k n k , (31) где 1 q p Матрица вероятностей переходов имеет вид 3 2 2 3 4 3 2 2 3 4 0 1 0 0 0 0 1 0 3 3 0 4 6 4 P p p q pq q p p q p q pq q Первая строка матрицы относится к случаю, когда в момент i име- ется один самолет, тогда в момент 1 i будет два самолета, так как ночью будет получено пополнение – один самолет и не будет вы- лета. Вторая строка – два самолета в момент i – нет вылета и три самолета в момент 1 i . Третья строка – в момент i имеется три самолета – будет вылет, вероятность того, что в момент 1 i будет один самолет соответствует случаю, что все три самолета будут сбиты, т.е. 3 31 p p . Вероятность того, что к моменту 1 i будет два самолета соответствует тому, что один самолет вернулся, т.е. 2 32 3 p p q . Вероятность того, что в момент 1 i будет три само- лета равна сумме вероятностей того, что вернулись два или три са- молета, т.е. 2 3 33 3 p pq q . Аналогичные рассуждения применя- ются и для четвертой строки. При рассуждениях имеется в виду тот факт, что число самолетов определяется утром после возможного пополнения по схеме Вылет на задание или отдых Пополнение Вылет на задание или отдых Пополнение Вылет на задание или отдых момент i момент 1 i Постройте график, представляющий матрицу переходов в этом случае. 44 2. В каждом заезде на скачках определенная лошадь выигрывает заезд с вероятностью 2/5, делит первое и второе место с вероятно- стью 1/5 и проигрывает с вероятностью 2/5 независимо от исхода любого предыдущего заезда. Постройте матрицы Р, Р 2 и Р 3 3. 80% сыновей выпускников Гарвардского университета посту- пают в Гарвард, остальные в Иелл, 40% выпускников Иеллского университета поступают в Иелл, остальные разделяются поровну между Гарвардом и Дортмундом и, наконец, 70% сыновей выпуск- ников Дортмундского университета поступают в Дортмунд, 20% в Гарвард и 10% в Иелл. Постройте матрицу Р. Определите вероят- ность, с которой внук выпускника Гарвардского университета по- ступает в Гарвард. 4. Рассмотрим процесс наследования признаков, когда признак определяется одной парой генов типа G и g. Каждый индивид мо- жет иметь генные признаки типа GG, gg, Gg. Для типов Gg и gG говорят, что ген G доминирует над геном g. Тип GG называется доминантным, gg называется рецессивным, Gg называется гибрид- ным. При скрещивании от потомков выбираются по одному гену случайным образом. Тогда GG + GG = GG, gg + gg = gg, GG+gg=Gg. При скрещивании типов GG+Gg от первого и от второго берется G с вероятностью 1/2 и g с вероятностью 1/2. Поэтому GG + Gg = 1/2GG + 1/2Gg. Аналогично gg+Gg=1/2Gg+1/2gg. Для Gg+Gg потомство с вероят- ностью 1/2 получает гены каждого типа от каждого из родителей, поэтому Gg+Gg = 1/4GG+1/2Gg+1/2gg. Определите матрицу Р для скрещивания индивидуума с неизвестными генными признаками и гибридным. Определите матрицы Р, Р 2 , Р 3 , если начинаем с гиб- рида. 5.2. Марковские цепи с поглощением [5] Рассмотрим следующую модель пьяницы: пьяница ходит только по прямой линии и с вероятностью 1/3 идет влево, либо 2/3 вправо. Всего он может сделать 4 шага, с обеих сторон от пьяного стоят полицейские. Как только он доходит до одного из них, так его за- бирают в участок. Обозначим состояние пьяного 0, 1, 2, 3, 4. Со- 45 стояние 0 и 4 называются поглощающими, так как, попав в них, пьяница уже не возвращается. Матрица переходов имеет вид: 0 1 2 3 4 0 1 2 3 4 1 0 0 0 0 1 3 0 2 3 0 0 0 1 3 0 2 3 0 0 0 1 3 0 2 3 0 0 0 0 1 Такие марковские цепи называются цепями с поглощением. Для них интересуются ответами на следующие вопросы: а) какова вероятность того, что процесс завершится переходом в конкретное поглощающее состояние; б) сколько в среднем шагов потребуется, чтобы попасть в по- глощающее состояние; в) сколько в среднем раз проходит процесс через каждое непо- глощающее состояние? Для ответа на эти вопросы приведем матрицу переходов в кано- нический вид, выписывая первыми поглощающие состояния 0 поглощение непоглощение поглощающее непоглощающее I P R Q где I – единичная матрица, 0 – нулевая, Q и R – неотрицательные матрицы. В теории марковских цепей показано, что процесс обяза- тельно попадет в поглощающее состояние, т.е. 0 n n Q и беско- нечный ряд 2 N I Q Q сходится к пределу, равному об- ратной матрице 1 I Q , т.е. 1 N I Q Матрица N называется фундаментальной матрицей. Тогда обо- значим 1 – вектор столбец из 1, – вектор сумм по строкам N мат- рицы, равный 1 N ij n дает среднее время пребывания в состоя- нии S j при начальном состоянии S i (где S i и S j – непоглощающие, t i – среднее число шагов до поглощения, при начальном S j , т.е. i-й элемент вектора ik b – вероятность того, что при начальном S i 46 процесс будет поглощен в состояние S k , равна ik-ому элементу матрицы B = NR). Для нашего примера канонический вид 0 4 1 2 3 0 4 1 2 3 1 0 0 0 0 0 1 0 0 0 1 3 0 0 2 3 0 0 0 1 3 0 2 3 0 2 3 0 1 3 0 P Тогда 1 1 1 2 3 0 7 5 6 5 4 5 1 3 1 2 3 3 5 4 5 6 5 0 1 3 1 5 3 5 7 5 N I Q , 7 5 6 5 4 5 1 17 5 1 3 5 4 5 6 5 1 18 5 1 5 3 5 7 5 1 11 5 N , 7 5 6 5 4 5 1 3 0 7 15 8 15 3 5 4 5 6 5 0 0 1 15 9 15 1 5 3 5 7 5 0 2 3 1 15 14 15 B N R Таким образом, среднее время пребывания в состоянии 2 при начальном состоянии 1 равно 7/5 согласно матрице N. Среднее число шагов до поглощения из состояния 1 равно 3 и вероятность поглощения из состояния 3 правым полицейским рав- на 14/15. |