Т а б л и ц а 3.7

Т а б л и ц а 3.6

Таблица переходов Y –детерминированного вероятностного автомата

zj zi.	zj
z0	z1	z2	z3	z4
z0 z1 z2 z3 z4		0.5	0.75 0.4		0.5 0.25 0.6

Таблица выходов Y –детерминированного вероятностного автомата

Z	z0	z1	z2	z3	z4
Y

Для рассматриваемого P –автомата матрица соединений и вектор выходов имеют вид

; . (3.36)

В матрице соединений Y –детерминированного вероятностного автомата элемент c_ij = p_ij определяется вероятностью перехода P –автомата в состояние z_j из состояния z_i при поступлении входного сигнала, а выход описывается вектором выходов, i -я компонента которого – выходной сигнал, отмечающий состояние z_i.

Описанный Y –детерминированный P –автомат можно задать в виде ориентированного графа (рис.3.38), вершины которого сопоставляются состояниям автомата, а дуги – возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода p_ij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.

Рис. 3.38. Граф Y –детерминированного вероятностного автомата

Оценим суммарную финальную вероятность пребывания этого P –автомата в состояниях z₂ и z₃. При этом начальное состояние z₀ можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда матрица вероятностей перехода автомата будет иметь вид

,

откуда получаем систему уравнений, определяющих вероятности финального пребывания автомата в состояниях p_j ()

.

Добавим к этим уравнениям условие нормировки p₁ + p₂ + p₃ + p₄ = 1.

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

Для оценки различных характеристик исследуемых систем, представленных в виде P – схем, кроме рассмотренного случая аналитических моделей, можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.

3.4. Непрерывно-стохастические модели (Q- схемы)

Использование Q – схем позволяет формализовать процессы функционирования систем, которые, по своей сути, являются процессами обслуживания.

Q –схемы применяются в качестве типовых математических схем систем массового обслуживания (англ. Queueing System) [8].

В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например: потоки поставок продукции предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удалённых терминалов и т.д. Характерным для работы подобных объектов является стохастический характер процесса их функционирования, проявляющийся:

– в случайном появлении заявок (требований) на обслуживание;

– в завершении обслуживания в случайные моменты времени.

Рассмотрим основные понятия систем массового обслуживания (СМО), необходимые для использования Q –схем, как при аналитическом, так и при имитационном подходе.

Элементы СМО. В СМО фигурируют:

1. Средства обслуживания – обслуживающие аппараты (ОА) или каналы обслуживания (К). Средства обслуживания являются статическими элементами Q –схем.

2. Обслуживаемые заявки – транзакты. Являются динамическими элементами Q –схем.

3. Очереди.

Состояние СМО характеризуется:

1. Состояниями всех обслуживающих аппаратов, каждый из которых может находиться в состоянии “занят” или “свободен”.

2. Состояниями всех транзактов, каждый из которых может находиться в состоянии “обслуживание” или “ожидание”.

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

Переменные СМО. Переменные величины разделяются на независимые и системные.

Независимые величины СМО характеризуются двумя случайными переменными:

а) интервал прибытия – интервал времени между последовательными моментами прибытия заявок в систему;

б) время обслуживания – время, требуемое обслуживающему аппарату для выполнения обслуживания.

Системные величины СМО являются предметом исследования системы и назначаются исследователем, например:

а) число заявок, прибывших на обслуживание за заданный промежуток времени;

б) число заявок, которые попали на обслуживание сразу же по прибытии;

в) среднее время пребывания заявок в очереди;

г) средние длины очередей;

д) максимальная длина очереди;

е) нагрузка обслуживающего аппарата, являющаяся функцией времени, которое потрачено ОА на обслуживание в течение заданного промежутка времени и т.д.

На рис.3.39 приведён пример системы обслуживания одним обслуживающим аппаратом и очередью. Система функционирует следующим образом. Заявка из источника заявок приходит на обслуживание. Если обслуживающий аппарат свободен, то заявка занимает его, и начинается процесс обслуживания. Если обслуживающий аппарат занят, то заявка поступает в очередь, где ожидает окончания обслуживания предыдущей заявки. Обслуженная заявка освобождает обслуживающий аппарат и покидает систему. Заявки, приходящие на обслуживание, образуют поток заявок; заявки, поступающие на обслуживание, образуют поток обслуживания; а заявки, покидающие систему по окончании обслуживания, образуют выходной поток. Эти потоки характеризуются интенсивностью l прихода заявок на обслуживание, интенсивностью m обслуживания и интенсивностью h ухода заявок из системы.

Рис. 3.39. Система обслуживания одним обслуживающим аппаратом и очередью

Для графического изображения СМО введена символика Q –схем. Для начертания Q –схем используются следующие основные элементы.

1. Источник заявок;

2. Материальные потоки (движение транзактов);

3. Информационные потоки (управляющие сигналы);

4. Клапан;

5. Накопитель;

6. Канал обслуживания;

7. Узел − правило, в соответствии с которым

направляются транзакты.

В качестве примера графического изображения Q –схемы на рис.3.40 приведена система обслуживания со страховым заделом.

Движение заявок через Q –схему представляет собой материальные потоки. А для управления системы обслуживания используются информационные потоки.

Рис. 3.40. Система обслуживания со страховым заделом:

И – источник заявок; Н1 и Н2 – накопители; К – канал обслуживания;

1, 2, 3 – клапаны

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

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

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

Поток неоднородных событий – это последовательность { t_n, f_n }, где t_n – вызывающие моменты; f_n – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Поток с ограниченным последействием – это поток, в котором интервалы прибытия t₁, t₂, … являются случайными величинами, независимыми между собой.

Ординарный поток событий – это поток, для которого вероятность того, что на малый интервал времени Dt, примыкающий к моменту времени t, попадает больше одного события P_>1 (t, Dt), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени Dt попадает ровно одно событие P₁ (t, Dt), т.е. P₁ (t, Dt) >> P_>1 (t, Dt).

Стационарный поток событий – поток, для которого вероятность появления того или иного числа событий на интервале времени t зависит лишь от длины этого интервала и не зависит от того, где на оси времени взят этот интервал. Для стационарного потока его интенсивность не зависит от времени и представляет собой постоянное значение, равное среднему числу событий, поступающих в единицу времени l(t) = l = const.

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

Q = < W, U, Y, H, Z, R, A >, (3.37)

где W – поток заявок;

U – поток обслуживания;

Y – выходной поток;

H – собственные параметры;

Z – внутреннее состояние;

R – оператор сопряжения;

A – оператор алгоритмов поведения заявок.

Поток заявок w_i Î W, т.е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе системы, образует множество неуправляемых переменных.

Поток обслуживания u_i Î U, т.е. интервалы времени между началом и окончанием обслуживания заявок обслуживающими аппаратами системы, образует множество управляемых переменных.

Выходной поток y_i Î Y, т.е. интервалы времени между моментами выхода заявок из системы, образует множество выходных переменных. Выходной поток составляют обслуженные заявки и заявки, покинувшие систему по различным причинам необслуженными (например, из-за переполнения накопителей).

Внутреннее состояние z_i Î Z определяется множеством состояний всех элементов, образующих систему. Процесс функционирования системы обслуживания можно представить как процесс изменения состояний его элементов во времени z_i (t). Переход в новое состояние для элемента системы означает изменение количества заявок, которые в нём находятся (в канале K_i и в накопителе H_i). Таким образом, состояние для элемента системы имеет вид , где – состояние накопителя H_i ( = 0 – накопитель пуст, = 1 – в накопителе имеется одна заявка, …, = – накопитель полностью заполнен); – ёмкость накопителя H_i, измеряемая числом заявок, которые в нём могут поместиться; – состояние канала K_i ( = 0 – канал свободен, = 1 – канал занят и т.д.).

Оператор сопряжения R отражает взаимосвязь элементов структуры системы (каналов и накопителей) между собой. Q –схемы образуются композицией многих обслуживающих аппаратов. Если каналы обслуживания соединены параллельно (рис.3.41), то имеет место многоканальное обслуживание (многоканальная Q – схема).

Рис. 3.41. Схема параллельного соединения каналов обслуживания:

а – с общей очередью; б – с раздельными очередями

Если каналы обслуживания соединены последовательно (рис.3.42), то имеет место многофазное обслуживание (многофазная Q – схема).

Рис. 3.42. Схема последовательного соединения каналов обслуживания

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

Собственные (внутренние) параметры H Q –схемы включают:

– количество фаз L_Ф;

– количество каналов в каждой фазе L_Kj ();

– количество накопителей каждой фазы L_Hk ();

– ёмкость i -го накопителя .

Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию для системы массового обслуживания:

– система с потерями ( = 0, т.е. накопитель у обслуживающего аппарата отсутствует, а имеется только канал обслуживания K_i);

– система с ожиданием ( → ∞, т.е. накопитель H_i имеет бесконечную ёмкость и очередь заявок не ограничивается);

– система смешанного типа (с ограниченной ёмкостью накопителя H_i).

Вся совокупность собственных параметров Q –схемы образует множество H.

Оператор алгоритмов (дисциплин) поведения заявок A определяет набор правил поведения заявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе H_i и обслуживания заявок каналом K_i каждого обслуживающего аппарата Q –схемы. Неоднородность заявок, отражающая процесс в той или иной реальной системе, учитывается с помощью введения классов приоритетов.

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

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

Аналитическое решение Q –схемы, заданной Q = < W, U, Y, H, Z, R, A >, возможно только при следующих упрощениях:

– входные потоки W и потоки обслуживания U – стационарные, ординарные, ограниченного последействия;

– оператор сопряжения элементов структуры R – однофазное одноканальное обслуживание в разомкнутой системе;

– множество собственных параметров H – обслуживание с бесконечной ёмкостью накопителя;

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

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

3.5. Обобщённые модели (A –схемы)

Наиболее известным общим подходом к формальному описанию процессов функционирования систем является подход, предложенный Н.П.Бусленко. Этот подход позволяет описывать поведение непрерывных и дискретных, детерминированных и стохастических систем, т.е. по сравнению с рассмотренными является обобщённым (универсальным) и базируется на понятии агрегатной системы (англ. Aggregate System), представляющей собой формальную схему общего вида, которая называется A – схемой [8].

A – схемадолжна являться адекватным математическим описанием объекта моделирования, служить основой для построения алгоритмов и программ при компьютерной реализации модели, позволять в упрощенном варианте проводить аналитические исследования.

При агрегатном описании сложный объект (система) разбивается на конечное число N_A частей (подсистем), сохраняя при этом связи, обеспечивающие их взаимодействие. Если некоторые из полученных подсистем оказываются, в свою очередь, ещё достаточно сложными, то процесс их разбиения продолжается до тех пор, пока не образуются подсистемы, которые в условиях рассматриваемой задачи моделирования могут считаться удобными для математического описания. В результате такой декомпозиции сложная система представляется в виде многоуровневой конструкции из взаимосвязанных элементов, объединённых в подсистемы различных уровней [8].

В качестве элемента A – схемы выступает агрегат A, а связь между агрегатами (внутри системы и с внешней средой) осуществляется с помощью оператора сопряжения R элементов в A – схему.

Совокупность N_A агрегатов представляет агрегатную систему или A – схему. Для описания реальной системы в виде A – схемы необходимо получить по рассмотренным ранее методикам описание отдельных агрегатов A_n и связей между ними, задаваемых оператором сопряжения R. Взаимодействие A – схемы с внешней средой рассматривается как обмен сигналами между внешней средой и элементами A – схемы. В соответствии с этим внешняя среда представляется в виде фиктивного элемента системы A₀.

Для установления связей между агрегатами каждый как элемент A – схемы снабжается множеством входных (, I_n – число входов n –ого агрегата; , N_A – число агрегата в A – схеме) и множеством выходных (, J_n – число выходов n –ого агрегата) контактов, через которые осуществляется обмен сигналами между элементами A – схемы и внешней средой.

Введённая пара множеств , является математической моделью элемента A_n, используемого для формального описания сопряжения его с элементами A – схемы и внешней средой.

Оператор сопряжения R сопоставляет входному контакту n -ого агрегата выходной контакт k -ого агрегата, т.е. = R ().

Таким образом, совокупность множеств , и оператор сопряжения R образуют схему сопряжения элементов в систему.

Графически A –схема изображается в виде структурной схемы.

A –схемы отображают наши представления о взаимодействии реальных объектов в рамах механизма обмена сигналами.

Ниже приведён пример A – схемы, структура которой представлена на рис.3.43, а оператор сопряжения R задан таблично (табл. 3.8).

При табличном способе задания оператора сопряжения R A – схемы используется таблица, в которой на пересечении строк с номерами агрегатов n и столбцов с номерами входных контактов i располагаются пары чисел k,l, указывающие номер агрегата k и номер контакта l, с которым соединен контакт .

Таким образом, рассмотренные примеры использования типовых математических схем (D –, F –, P –, Q – и A – схем) позволяют формализовать достаточно широкий класс больших систем, с которыми приходится иметь дело в практике исследования и проектирования реальных объектов.

Рис. 3.43. Структура агрегатной системы

Дата добавления: 2014-11-20