Дискретно-стохастические модели (Р-схемы)

Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным выше конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.

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

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

Введем математическое понятие Р-автомата, используя понятия, введенные для F -автомата. Рассмотрим множество G, элементами которого являются всевозможные пары ,где и — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции и то с их помощью осуществляются отображения и , то говорят, что определяет автомат детерминированного типа.

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

Элементы из Ф	…	…		…
	…			…

6.3. ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ

(Р-СХЕМЫ)

Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным в § 2.3 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастическиих) автоматах.

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

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

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

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

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

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

При этом— вероятности перехода Р-автомата в состояние z_k и появления выходного сигнала у_к при условии, что Р-автомат находился в состоянии z, и на его вход поступил входной сигнал х,.

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

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

I

Здесь — вероятность появления выходного сигнала у, при условии, что Р-автомат находился в состоянии z_k.

Возможные приложения. Если для всех к и i имеет место соотношение z_kS_j=b_kh то такой Р-автомат называется вероятностным автоматом Мура. Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым P=<Z, X, Y, φ, ψ,>. Частным случаем Р-автомата, задаваемого как P=(Z,X, Y, B\ являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминировано.

Если выходной сигнал Р-автомата определяется детерминировано, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-demepминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

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

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

Будем считать, что до начала работы (до нулевого такта времени)
Р-автомат всегда находится в состоянии z₀ и в нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний Р-автомата определяется матрицей переходов Р_Р. Информацию о начальном состоянии Р-автомата удобно нести в матрицу Рр, увеличив ее размерность до (K+1)х(K+1). При этом первая строка такой матрицы, сопоставляемая состоянию z₀ , будет иметь вид (0, d₁ d₂,.. „., d_K), а первый столбец будет нулевым.

Описанный У-детермивированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги —возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода p_j, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.

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

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

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

Подобные Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е. Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.

6.4. НЕПРЕРЫВНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ

(Q-СХЕМЫ)

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

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

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

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

l_i =0, L_i^H заявок, где L_i^H — емкость i-го накопителя, и канала об­служивания заявок (или просто канала) K_i На каждый элемент прибора обслуживания П_i поступают потоки событий: в накопитель Hi — поток заявок w_i на канал Кi — поток обслуживании и_i.

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных собы­тий. Поток событий называется однородным, если он характеризу­ется только моментами поступления этих событий (вызываю­щими моментами) и задается последовательностью {t_n} = {0≤ t₁ ≤ t₂…≤ t_n≤ …}, где t_n — момент наступления n-го собы­тия — неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности про­межутков времени между n-м и (п— 1)-м событиями {τ_n}, которая однозначно связана с последовательно­стью вызывающих моментов { t_n }, где τ_n= t_n - t_n - t_n-1, n≥1, t₀ = 0. т. е. τ_n = t₁

Рис. 1. Прибор обслуживания заявок

Потоком неоднородных событий на­зывается последовательность {t_n, fn), где U, — вызывающие моменты; t_n — набор признаков события. Например, примени­тельно к процессу обслуживания для не­однородного потока заявок могут быть заданы принадлежность к тому или иному источнику заявок, нали­чие приоритета, возможность обслуживания тем или иным типом канала и т. п.

Рассмотрим поток, в котором события разделены интервалами временя τ₁, τ₂,.... которые вообще являются случайными величинами. Пусть интервалы τ₁, τ₂,... независимы между собой. Тогда поток событий называется потоком с ограниченным последействием.

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

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

Рис.2. Графическое изображение N-схемы

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

Случайные потоки бывают:

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

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

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

Поток событий называется ординарным, если вероятность того, что на малый интервал времени ∆t, примыкающий к моменту времени t, попадает больше одного события Р_>1 (t, ∆t), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени ∆t попадает ровно одно событие Р₁ (t, ∆t) т. е. P₁ (t, ∆t )»-P_>1 (t, ∆t). Вели для любого интервала ∆t событие

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

где 0 (∆t)— величина, порядок малости которой выше, чем ∆t т. е.

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

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

Тогда среднее число событий, наступающих научастке времени ∆t в единицу времени, составит [ Р₁ (t,∆t)]/∆t Рассмот­рим предел этого выражения при ∆t→0. Если этот предел существует, то она назы­вается интенсивностью (плотностью) ор­динарного потока событий

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

Возможные приложения. Обычно в приложениях при моделиро­вании различных систем применительно к элементарному каналу обслуживания Ж» можно считать, что поток заявок wiεW, т. е. интервалы времени между моментами появления заявок (вызыва­ющие моменты) на входе K_i образует подмножество неуправля­емых переменных, а поток обслуживания uiεU т. е. интервалы времени между началом и окончанием обслуживания заявки, об­разует подмножество управляемых переменных.

Заявки, обслуженные каналом К_ь и заявки, покинувшие прибор Пi по различным причинам необслуженными (например, из-за переполнения накопителя Нi), образуют выходной поток y_i ε Y, т. е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Процесс функционирования прибора обслуживания П_i можно представить как процесс изменения состояний его элементов во времени z, (t). Переход в новое состояние для П_i означает изменение количества заявок, которые в нем находятся (в канале К_i и в накопи­теле H_i. Таким образом, вектор состояний для П_i имеет вид z_i=(z_i^H, z_i^K), где z_t^H — состояние накопителя Н_I (z_I ^B=0 — накопитель пуст, z^B=l — в накопителе имеется одна заявка,..., z_i^H—L_i ^H — накопи­тель полностью заполнен); L_i ^H — емкость накопителя Нi измеря­емая числом заявок, которые в нем могут поместиться; z_i^K— состо­яние канала K_i( z_i^K =0 — канал свободен, z_i^K =l—канал занят и т. д.).

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

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

Собственными (внутренними) параметрами Q-схемы будут яв­ляться количество фаз Lф, количество каналов в каждой фазе L_KJ, j=l, L^Ф, количество накопителей каждой фазы L_Нк, к=l, L_ф ем­кость i-го накопителя L_I^H. Следует отметить, что в теории мас­сового обслуживания в зависимости от емкости накопителя приме­няют следующую терминологию для систем массового обслужива­ния: системы с потерями (L_I^H =0, т. е. накопитель в приборе П_i отсутствует, а имеется только канал обслуживания К_i), системы с ожиданием (L_I^H → ∞, т. е. накопитель H_i имеет бесконечную ем­кость и очередь заявок не ограничивается) и системы смешанного типа (с ограниченной емкостью накопителя H_i). Всю совокупность собственных параметров Q-схемы обозначим как подмножество H.

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

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

При рассмотрении алгоритмов функционирования приборов об­служивания П _i, (каналов K_i и накопителей H_i необходимо также задать набор правил, по которым заявки покидают H_i и K_i) для H_i — либо правила переполнения, по которым заявки в зависимо­сти от заполнения H_i покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в H_i для K_t — правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале K_i или не допускаются до обслуживания каналом К_i т. е. правила блокировок канала. При этом различают блокировки K_i по выходу и по входу. Такие блокировки отражают наличие управля­ющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведе­ния заявок в Q-схеме можно представить в виде некоторого опера­тора алгоритмов поведения заявок А.

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

Q=(W, U, H, Z, R, А)

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

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

где Р_n (t) — вероятность нахождения системы в состоянии z_n (t)εZ в момент времени t, т. е. когда в ней имеется n заявок.

Эти уравнения следуют из того, что вероятность нахождения в системе n заявок в момент времени (t+∆t)равна вероятности нахождения в системе n заявок в момент t, умноженной на вероятность того, что за время ∆t в систему не поступит ни одной Заявки и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (n - 1) заявок в момент t,умноженная на вероятность того, что за время ∆t поступит одна заявка и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе (n +1) заявок в момент t, умноженная на вероятность того, что за время ∆t одна заявка покинет систему и не поступит ни одной заявки. Вероятность того, что за время ∆t не поступит ни одной заявки и ни одна заявка не покинет систему, равна (1—λ∆t) (1-μ∆t). Член, содержащий (∆t)², при составлении дифференциального уравнения опускается. Следовательно, можно записать 1 -(λ+μ)∆t. Относительно остальных двух членов первого уравнения заметим, что

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

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

Пусть в первом уравнении n=1. Тогда (1+ρ)Р₁=Р₂+ρР₀. Поставив сюда значение Р₁ из второго уравнения, находим Р₂=ρ²Р₀. Повторяя эти операции, получаем Р_n=ρ²P₀, причем , так как эта сумма вероятностей того, что в системе нет ни одной заявки, имеется одна заявка, две заявки и т.д. Сумма этих вероятностей должна быть равна единице, так как рассматриваются все возможные состояния системы. Поэтому , или

, откуда Р₀=1-ρ. Следовательно, Р_n=ρⁿ(1-ρ).

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

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

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

При этом

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

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

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

Возможности оценки характеристик с использованием аналитических моделей теории массового обслуживания являются весьма ограниченными по сравнению с требованиями практики исследования и проектирования систем, формализуемых в виде Q-схем. Несравненно большими возможностями обладают имитационные модели, позволяющие исследовать Q-схему, задаваемую Q=‹W,U,H,Z,Y,R,A›, без ограничений. На работу с Q-схемами при машинной реализации моделей ориентированы многие языки имитационного моделирования, например SIMULA, SIMSCRIPT, GPSS и др.

6.5. КОМБИНИРОВАННЫЕ МОДЕЛИ (А-СХЕМЫ)

Наиболее известным общим подходом к формальному описанию

процессов функционирования систем является подход, предложенный

Н. П. Бусленко. Этот подход позволяет описывать поведение непрерывных и дискретных, детерминированных и стохастических систем, т. е. по сравнению с рассмотренными является обобщенным (универсальным) и базируется на понятии агрегативной системы (от англ. aggregate system), представляющей собой формальную схему общего вида, которую будем называть А-схемой.