Советов Б.Я., Яковлев С.А. Моделирование систем (2001) (1186219), страница 16
Текст из файла (страница 16)
2.6) и таблицей выходов:Z . . . . Zji2 . . . . zk_tzkУ . . . . ^,iу,г • • • у,к-\у,кВ этих таблицах рц — вероятность перехода Р-автомата из состояния г, в состояние Zj. При этом, как и ранее, £ p,j= 1.62Первую из этих таблиц можно представить в виде квадратной матрицыразмерности КхК, которую будем называть матрицей переходных вероятностейили просто матрицей переходов Р-автомата. В общем случае такая матрицапереходов имеет видРиРиPIE.PnPnPinРиРиРиР,=Таблица 2.6**4fc«1Л*1РиРиРиРиРчРч1*1-1нPi (Х-1)Pi (Г- 1)Pit.PlKPi (*-»РчкДля описания У-детерминированното Р-автомата необходимо задать начальное распределение вероятностей видаz2 . .
. . 1'ii*t-iD .rf,d2dK-iЗдесь dt — вероятность того, что в начале работы Р-автомат находится в состояниик. При этом £dk=\.Будем считать, что до начала работы (до нулевого такта времени) Р-автоматвсегда находится в состоянии z0 и в нулевой такт времени меняет состояние в соответствии с распределением D.
Дальнейшая смена состояний Р-автомата определяется матрицей переходов РР. Информацию о начальном состоянии Р-автомата удобно•нести в матрицу Рр, увеличив ее размерность до (АГ+1)х(ЛГ+1). При этом перваястрока такой матрицы, сопоставляемая состоянию г„, будет иметь вид (0, dlt d2, ...„., dK), а первый столбец будет нулевым.Описанный У-детермивированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги —возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода p,j, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.Пример US.
Пусть задан У-детерминированный Р-автоматО 0,50 0Л> =00,500 001,00 00 00,7500,250 00,4000,600001,00 0Z'У\г00*i02*о63На рис. 2.5 показан граф переходов этого автомата. Требуется оценить суммарные финальные вероятности пребывания этого Р-автомата в состояниях z2 в z,.При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определенияфинальных вероятностей.
При этом начальное состояние г0 можно не учитывать, таккак начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеемС=СО000,75 00,2500,40 00,601,00 01,00 00С — (c R ) = (Cj, с 2 , с3> с*)>0где с* — финальная вероятность пребывания Р-автомата в состоянии zk.Получаем систему уравненийс2=0,75с2+0,40с3,с4-=0,25с2-|-0,60сз.Добавим к этим уравнениям условие нормировки с1+с2 + с3+с4 = \. Тогда,решая систему уравнений, получим С! = 5/23, с2=8/23, с3 = 5/23, с4 = 5/23.
Такимобразом , с 2 +с э = 13/23=0,5652. Другими словами, при бесконечной работе заданного в этом примере У-детерминированного Раетомата на его выходе формируется двоичнаяпоследовательность с вероятностью появленияединицы, равной 0,5652.Рис. 2.5. Граф вероятностного автоматаПодобные Р-автоматы могут использоваться как генераторы марковскихпоследовательностей, которые необходимы при построении и реализации процессов функционирования систем S иливоздействий внешней среды Е.Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методомстатистического моделирования.2.5. НЕПРЕРЫВНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ(2-СХЕМЫ)Особенности непрерывно-стохастического подхода рассмотримна примере использования в качестве типовых математических схемсистем массового обслуживания (англ.
queueing system), которые64будем называть Q-схемами. Системы массового обслуживанияпредставляют собой класс математических схем, разработанныхв теории массового обслуживания и различных приложениях дляформализации процессов функционирования систем, которые посвоей сути являются процессами обслуживания [6, 13, 33, 37, 51].Основные соотношения.
В качестве процесса обслуживания могутбыть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий насборочном конвейере цеха, заявки на обработку информации ЭВМот удаленных терминалов и т. д. При этом характерным для работытаких объектов является случайное появление заявок (требований)на обслуживание и завершение обслуживания в случайные моментывремени, т. е.
стохастический характер процесса их функционирования. Остановимся на основных понятиях массового обслуживания,необходимых для использования Q-схем, как при аналитическом,так и при имитационном.В любом элементарном акте обслуживания можно выделить двеосновные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого /-го прибора обслуживания Д (рис. 2.6), состоящего изнакопителя заявок Н,, в котором может одновременно находиться/,=0, L(H заявок, где L,B — емкость i-го накопителя, и канала обслуживания заявок (или просто канала) К/. На каждый элементприбора обслуживания Д поступают потоки событий: в накопительHi — поток заявок w,, на канал Kt — поток обслуживании и,.Потоком событий называется последовательность событий,происходящих одно за другим в какие-то случайные моментывремени.
Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающимимоментами)изадаетсяпоследовательностью{r„} = {0<f 1 </ 2 ...</«<•••}, где tn— момент наступления и-го события — неотрицательное вещественное число. Однородный потоксобытий также может быть задан в виде последовательности промежутков времени между л-м и (и—1)-м событиями {т„}, котораяоднозначно связана с последовательностью вызывающих моментов {*„}, гдеr„ = tn-t„-t„..l,n^l,tQ= 0,T.e.Tl= t1.<•_'Потоком неоднородных событий называется последовательность \t„, /„), где .t„ — вызывающие моменты; /„ — наборпризнаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок могут быть"Рис 2 6 П р и б о р обслужи .вания заявок65заданы принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типомканала и т.
п.Рассмотрим поток, в котором события разделены интервалами времени xlt i2>—.... которые вообще являются случайными величинами. Пусть интервалы т„ т2, ...независимы между собой. Тогда поток событий называется потоком с ограниченнымпоследействием.Пример потока событий приведен на рис. 2.7, где обозначено Т, — интервалмежду событиями (случайная величина); Тя — время наблюдения, Тс — моментсовершения события.Интенсивность потока можно рассчитать экспериментально по формулег;где N—число событий, произошедших за время наблюдения Тж.
Если 7)««const илиопределено какой-либо формулой 7/»»/(2)_i), то поток называется детерминированным. Иначе поток называется случайным.Случайные потоки бывают:— ординарными, когда вероятность одновременного появления 2-х и болеесобытий равна нулю;— стационарными, когда частота появления событий постоянная;— без последействия, .когда вероятность не зависит от момента совершенияпредыдущих событий.Поток событий называется ординарным, если вероятность того, что на малыйинтервал времени At, примыкающий к моменту времени I, попадает больше одногособытия Р>, (I, Л/), пренебрежительно мала по сравнению с вероятностью того, чтона этот же интервал времени Лг попадает ровно одно событие Ру ft АО. т. е. PY ftД/)й>Р>1 (/, Лг)- Вели для любого интервала Дг событиеР 0 ft ДО+Р, ft Д0+*>1 ft ЛО-1fкак сумма вероятностей событий, образующих полную группу и несовместных, тодля ординарного потока событийР0 ft Д О + Л ft ДО* 1. Ki ft АО-0 (ДО,где О (ДО — величина, порядок малости которой выше, чем Д/, т.