книги / Моделирование систем

зации времени при этом подходе остается аналогич­ ной рассмотренным в § 2.3 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (сгохастическиих) автома­ тах.

Основные соотношения. В общем виде вероятностный автомат (англ, probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирова­ ние которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически.

Применение схем вероятностных автоматов (P-схем) имеет важ­ ное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное пове­ дение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворящих заданным ограничениям.

Введем математическое понятие Р-автомата, используя поня­ тия, введенные для F-автомата. Рассмотрим множество G, элемен­ тами которого являются всевозможные пары (*,, zs), где xt и zs — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции <р и ф, то с их помощью осуществляются отображения G->Z и G-*Y, то говорят, что F= <Z, X , Y, <pt ф} определяет автомат детерминиро­ ванного типа.

Введем в рассмотрение более общую математическую схему. Пусть Ф — множество всевозможных пар вида (zk, yj), где — элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:

КJ

При этом £ £ bkj= \, где bkJ— вероятности перехода автома-

k - 1 j - l

та в состояние zk и появления на выходе сигнала yjt если он был в состоянии zs н на его вход в этот момент времени поступил сигнал xh Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P=<Z, X, У, В} называ­ ется вероятностным автоматом (Р-автоматом).

Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, что можно представить соответственно в виде:

61

да P-автомата в состояние z* и появления выходного сигнала укпри условии, что P-автомат находился в состоянии zs и на его вход поступил входной сигнал х х.

Если для всех к и j имеет место соотношение qkZi=bkji то такой P-автомат называется вероятностным автоматом Мили. Это тре­ бование означает выполнение условия независимости распределе­ ний для нового состояния Р-автомата и его выходного сигнала.

Пусть теперь определение выходного сигнала P-автомата зави­ сит лишь от того состояния, в котором находится автомат в данном такте работы. Другими словами, пусть каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:

I

Здесь YJ ‘S«= 1J где st — вероятность появления выходного сиг-

нала yt при условии, что P-автомат находился в состоянии zk. Возможные приложения. Если для всех к и i имеет место соот­

ношение zkSi=bki, то такой P-автомат называется вероятностным автоматом Мура. Понятие P-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым P=<Z , X, Y, (р, фу. Частным случаем P-автомата, задаваемого как P=< Z , X, Y, В}, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал P-автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятност­ ным автоматом. Аналогично, Z -детерминированным вероятност­ ным автоматом называется P-автомат, у которого выбор нового состояния является детерминированным.

Пример 2.4. Рассмотрим У-детерминированный P-автомат, который задан таб­ лицей переходов (табл. 2.6) и таблицей выходов:

В этих таблицах ру — вероятность перехода P-автомата из состояния г,- в состо­

яние zj. При этом, как и ранее, £ ру= 1.

У-1

62

На рис. 2.5 показан граф переходов этого автомата. Требуется оценить суммар­ ные финальные вероятности пребывания этого Р-автомата в состояниях z2 и z3.

При использовании аналитического подхода можно записать известные соот­ ношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние z0 можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероят­ ностей. Тогда имеем

где су. — финальная вероятность пребывания P-автомата в состоянии zy. Получаем систему уравнений

ci —С4»

с2= 0,75с2+0,40е3,

СЭ = С1»

с*— =0,25с2+ 0,60сэ.

Добавим к этим уравнениям условие нормировки с1+ с2+ с3+с4.=1. Тогда, решая систему уравнений, получим сх= 5/23, с2= 8/23, с3= 5/23, с4=5/23. Таким образом , с2+ с3 = 13/23=0,5652. Другими словами, при бесконечной работе задан­ ного в этом примере У-детерминированного Р- автомата на его выходе формируется двоичная последовательность с вероятностью появления

единицы, равной 0,5652.

2.5. НЕПРЕРЫВНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (б-СХЕМЫ)

Особенности непрерывно-стохастического подхода рассмотрим на примере использования в качестве типовых математических схем систем массового обслуживания (англ, queueing system), которые

64

будем называть Q-схемами. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые но своей сути являются процессами обслуживания [6, 13, 33, 37, 51].

Основные соотношения. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процес­ сы функционирования экономических, производственных, техничес­ ких и других систем, например потоки поставок продукции некото­ рому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удаленных терминалов и т. д. При этом характерным для работы таких объектов является случайное появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т. е. стохастический характер процесса их функционирова­ ния. Остановимся на основных понятиях массового обслуживания, необходимых для использования Q-схем, как при аналитическом, так и при имитационном.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и со­ бственно обслуживание заявки. Это можно изобразить в виде неко­ торого /-го прибора обслуживания Д (рис. 2.6), состоящего из накопителя заявок Д , в котором может одновременно находиться

4=0, LiB заявок, где L B — емкость z-го накопителя, и канала об­ служивания заявок (или просто канала) Kh На каждый элемент прибора обслуживания Д поступают потоки событий: в накопитель Д — поток заявок wh на канал JTf — поток обслуживаний и,.

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных собы­ тий. Поток событий называется однородным, если он характеризу­ ется только моментами поступления этих событий (вызываю­

тия— неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности про­ межутков времени между w-м и (и—1)-м событиями {т„}, которая однозначно связана с последовательно­ стью вызывающих моментов {/„), где

I

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

Рассмотрим поток, в котором события разделены интервалами времени хх, т2,...

..., которые вообще являются случайными величинами. Пусть интервалы т1} х2, ...

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

Пример потока событий приведен на рис. 2.7, где обозначено 7) — интервал между событиями (случайная величина); Тж— время наблюдения, Гс — момент совершения события.

Интенсивность потока можно рассчитать экспериментально по формуле

где N — число событий, произошедших за время наблюдения Тп. Если 7}=const или определено какой-либо формулой Tj= f(Tj_l), то поток называется детерминирован­

ным. Иначе поток называется случайным. Случайные потоки бывают:

—ординарными, когда вероятность одновременного появления 2-х и более событий равна нулю;

—стационарными, когда частота появления событий постоянная;

—без последействия, когда вероятность не зависит от момента ‘ совершения

предыдущих событий.

Поток событий называется ординарным, если вероятность того, что на малый интервал времени At, примыкающий к моменту времени /, попадает больше одного события Р>1 (i, At), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени At попадает ровно одно событие Рг (/, АО, т. е. Рх (/, ДО »-Р>;1 (/, АОЕсли для любого интервала At событие

Р0 (г, Д О +Л (*, Д0+Р>1 (I, Д О -1

как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий

Р0 (t, At)+Px (I, Дг)»1, Р >i (<, Д О -0 (ДО,

где О (ДО — величина, порядок малости которой выше, чем At, т. е.

lim [0 (Д0/Дг]=0.

Д|-*0

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

Рассмотрим на оси времени 0/ ординарный поток событии и найдем среднее число событий, наступающих на интервале времени At, примыкающем к моменту времени t. Получим

66

A/)/Af]= А(/). Интенсивность потока может быть любой неотрицательной функцией времени, имеющей размерность, обратную размерности времени. Для стационар­ ного потока его интенсивность не зависит от времени и представляет собой постоян­ ное значение, равное среднему числу событий, наступающих в единицу времени A(f)=A=const.

Возможные приложения. Обычно в приложениях при моделиро­ вании различных систем применительно к элементарному каналу обслуживания JT* можно считать, что поток заявок w{eW , т. е. интервалы времени между моментами появления заявок (вызыва­ ющие моменты) на входе К„ образует подмножество неуправля­ емых переменных, а поток обслуживания ще U, т. е. интервалы времени между началом и окончанием обслуживания заявки, об­ разует подмножество управляемых переменных.

Заявки, обслуженные каналом Ki} и заявки, покинувшие прибор

Дпо различным причинам необслуженными (например, из-за

переполнения накопителя Д ), образуют выходной поток Y, т. е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Процесс функционирования прибора обслуживания Д можно представить как процесс изменения состояний его элементов во времени z, (/). Переход в новое состояние для Д означает изменение количества заявок, которые в нем находятся (в канале Kt и в накопи­

теле Щ . Таким образом, вектор состояний для Д имеет вид z,=(z,fl, z*), где z® — состояние накопителя Д (z®=0 — накопитель пуст, z,H= 1 — в накопителе имеется одна заявка, ..., — накопи­ тель полностью заполнен); L® — емкость накопителя Д , измеря­ емая числом заявок, которые в нем могут поместиться; z* — состо­ яние канала Kt (z* =0 — канал свободен, z*= 1 — канал занят

ит. д.).

Впрактике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации ис­

пользуются не отдельные приборы обслуживания, а Q-схемы, об­ разуемые композицией многих элементарных приборов обслужива­ ния Д (сети массового обслуживания). Если каналы К{ различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы Д и их параллельные композиции соединены последовате­ льно, то имеет место многофазное обслуживание (многофазная Q-схема). Таким образом, для задания Q-схемы необходимо ис­ пользовать оператор сопряжения R, отражающий взаимосвязь эле­ ментов структуры (каналов и накопителей) между собой.

Связи между элементами Q-схемы изображают в виде стрелок (линий потока, отражающих направление движения заявок). Раз­ личают разомкнутые и замкнутые Q-схемы. В разомкнутой Q-схеме выходной поток обслуженных заявок не может снова поступить на какой-либо элемент, т. е. обратная связь отсутствует, а в замкнутых

Q-схемах имеются обратные связи, по которым заявки двигаются в направлении, обратном движению вход-выход.

Собственными (внутренними) параметрами Q-схемы будут яв­ ляться количество фаз 2,ф, количество каналов в каждой фазе Lkj,

j= l, I ? , количество накопителей каждой фазы к = \, Х,ф, ем­ кость z-ro накопителя L,H. Следует отметить, что в теории мас­ сового обслуживания в зависимости от емкости накопителя приме­ няют следующую терминологию для систем массового обслужива­ ния: системы с потерями (Ь,Б=0, т. е. накопитель в приборе Д отсутствует, а имеется только канал обслуживания Kt), системы

с ожиданием (£,я -»оо, т. е. накопитель Д имеет бесконечную ем­ кость и очередь заявок не ограничивается) и системы смешанного типа (с ограниченной емкостью накопителя Д ). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.

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

В зависимости от динамики приоритетов в Q-схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т. е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при модели­ ровании в зависимости от возникающих ситуаций. Исходя из пра­ вил выбора заявок из накопителя Д на обслуживание каналом Кь можно выделить относительные и абсолютные приоритеты. От­ носительный приоритет означает, что заявка с более высоким при­ оритетом, поступившая в накопитель Д , ожидает окончания об­ служивания предшествующей заявки каналом Kt и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Д , пре­ рывает обслуживание каналом JT; заявки с более низким приорите­ том и сама занимает канал (при этом вытесненная из К, заявка может либо покинуть систему, либо может быть снова записана на какое-то место в щ .

При рассмотрении алгоритмов функционирования приборов об­ служивания Д (каналов и накопителей Д ) необходимо также задать набор правил, по которым заявки покидают Д и К{. для Д — либо правила переполнения, по которым заявки в зависимо­ сти от заполнения Д покидают систему, либо правила ухода,

68

связанные с истечением времени ожидания заявки в Ни для К{— правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале Kt или не допускаются до обслуживания каналом Kh т. е. правила блокировок канала. При этом различают блокировки К§по выходу и по входу. Такие блокировки отражают наличие управля­ ющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведе­ ния заявок в Q-схеме можно представить в виде некоторого опера­ тора алгоритмов поведения заявок А.

Таким образом, Q-схема, описывающая процесс функциониро­ вания системы массового обслуживания любой сложности, одно­ значно задается в виде Q = (W , U, Н, Z, R, А ).

При ряде упрощающих предположений относително подмно­ жеств входящих потоков W и потоков обслуживания U (выполнение условий стационарности, ординарности и ограниченного последей­ ствия) оператора сопряжения элементов структуры R (однофазное одноканальное обслуживание в разомкнутой системе), подмножест­ ва собственных параметров Н (обслуживание с бесконечной ем­ костью накопителя), оператора алгоритмов обслуживания заявок А (бесприоритетное обслуживание без прерываний и блокировок) для оценки вероятностно-временных характеристик можно исполь­ зовать аналитический аппарат, разработанный в теории массового обслуживания. При принятых предположениях в обозначениях Д. Кендалла будет иметь место классическая система обслуживания типа М/М/1 (одноканальная система с марковским входящим пото­ ком заявок и марковским потоком обслуживания). Рассмотрим на примере основные аналитические соотношения для такой элемен­ тарной Q-схемы [6, 24, 37].

Пример 2.6. Допустим, что процесс обслуживания начинается при отсутствии заявок в накопителе. Тогда состояния системы массового обслуживания описыва­ ются следующей системой уравнений:

(Р„ (t+At)=P„ (0 [l-(A +/z)A /]+P„_, (ОЛДг+ P R+I (t)fiAt, п> 1, V o (t+ At)= P0 (О (1 -М О + Л № A t,

где Р„ (/) — вероятность нахождения системы в состоянии zn (t)eZ в момент време­ ни f, т. е. когда в ней имеется п заявок.

Эти уравнения следуют из того, что вероятность нахождения в системе п заявок

вмомент времени (/+ At) равна вероятности нахождения в системе п заявок в момент /, умноженной на вероятность того, что за время At в систему не поступит ни одной заявки и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (л—1) заявок в момент t, умноженная на вероятность того, что за время At поступит одна заявка и ни одна заявка не будет обслужена, плюс вероятность нахождения

всистеме (л +1) заявок в момент /, умноженная на вероятность того, что за время At одна заявка покинет систему и не поступит ни одной заявки. Вероятность того, что за время At не поступит ни одной заявки и ни одна заявка не покинет систему, равна

(1—ЯД/) (1—fiAt). Член, содержащий (Д/)2> при составлении дифференциального уравнения опускается. Следовательно, можно записать 1 — (A+n)At. Относительно остальных двух членов первого уравнения заметим, что

69

ЯДг (1—/|Д|)«ДД|, pAt (1-XAt)& pAt.

Перенеся Р„ (/) влево н устремив At к нулю, получим систему дифференциальных уравнений

fdP„ (t)ldt=-(X+ti)P„(t)+*Pn-i (O + A + i (0» n > h

W o (t)/dt= -XPQ(0 + р Л (О-

Найдем выражение для математического ожидания числа заявок, находящихся в накопителе, и среднего времени ожидания заявок в накопителе для стационарного состояния p=Xjp<\. Приравняв нулю производные по времени и исключив, таким образом, время t из уравнений, получим систему алгебраических уравнений

Пусть в первом уравнении л=1. Тогда (1 +p)pj =Р2 +РРо* Подставив сюда

значение р г из второго уравнения, находим р2—РгРо> Повторяя эти операции,

«

л-0

в системе нет ни одной заявки, имеется одна заявка, две заявки и т. д. Сумма этих

вероятностей должна быть равна единице, так как рассматриваются все возможные

00

состояния системы. Поэтому £ р р0=1,

я-0

во со

или Е РоР =Ро Е р =Ро/(1-р)=1> откуда р0- 1 - р . Следовательно, рп= р (1 —р).

я-0 л-0

Полученное выражение представляет собой геометрическое распределение. Математическое ожидание числа заявок, находящихся в системе (приборе),

А.= Е «Рл=(1- Р ) Е лр " = р (1—Р)«

л-0 л-0

Отметим, что 1„— среднее значение и возможны колебания числа заявок, ожида­ ющих обслуживания, что можно оценить с помощью дисперсии:

D Ы " Е 0 » -4 )* Л - Е ^ Р п - Ь /а - р )] 2.

л-0

При этом

Е «2рл= ( 1 - р> Е « V = p /(i-p )+ 2 p 2/(i~ p )2.

л-0 л-0

Следовательно,

D И = Р /(1 -р )+ 2 р 2/(1 -р )2-

Математическое ожидание числа заявок, находящихся в накопителе,

00

\ = Е (л- 1)Рл=1.- Р =р/(1 - р ) - Р = р2/(1 - р).

Л—1

Среднее время ожидания заявок в накопителе

'н='/вД = я 1/и (1 -р)].

70