7. Агрегативное описание систем

Вид материалаДокументы

Содержание


7.2. Процесс функционирования агрегата
7.2.2. Функционирование СМО как агрегата
Агрегативная система
Виды связей между агрегатами
Подобный материал:
7. Агрегативное описание систем


7.1. Понятие «агрегат» в теории систем


Пусть T – фиксированное подмножество действительных чисел (множество рассматриваемых моментов времени), X,U,Y,Z – множества любой природы. Элементы указанных множеств назовем: tÎ T – моментом времени; xÎ X; входным сигналом; uÎ U- управляющим сигналом; yÎ Y – выходным сигналом; zÎ Zсостоянием. Состояния, входные, управляющие и выходные сигналы, рассматриваемые как функции времени, обозначим z(t), x(t), u(t) и y(t).

Под агрегатом будем понимать объект (7.1), где H,G – операторы (вообще говоря, случайные). Операторы переходов и выходов H и Gреализуют функции z(t) и y(t). Структура этих операторов собственно и выделяет агрегаты среди прочих систем. Рассмотрим подробнее вид этих операторов. При этом будем считать справедливым следующее предположение.

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

Операторы переходов. Наряду с состоянием z(t) будем рассматривать также точки z(t+0). Договоримся считать, что для любого t1>tмомент (t+0) Î (t,t 1]. Вид оператора переходов H зависит от того, содержит ли рассматриваемый интервал времени моменты т.н. особых состояний агрегата или не содержит. Под особыми состояниями будем понимать его состояния в момент получения входного либо управляющего сигналов или выдачи выходного сигнала. Все остальные состояния агрегата будем называть неособыми.

Предположение 2. Из особых состояний агрегат может переходить в новое состояние скачком.

Пусть z(t*) – некоторое особое состояние агрегата, а us – последний управляющий сигнал usÎ U. Примем следующие обозначения для операторов, являющихся частными видами оператора Hи определяющих состояние агрегата в момент t*+0. Если t* - момент поступления входного сигнала x, то

z(t*+0)=V¢ [z(t*),x,us] (7.2)

Аналогично, если t* - момент поступления управляющего сигнала u, то

z(t*+0)=V¢¢ [z(t*),u] (7.3)

При одновременном поступлении x и u

z(t*+0)=V [z(t*),x,u] (7.4)

Наконец, если t* - момент выдачи выходного сигнала y, то

z(t*+0)=W[z(t*),us] (7.5)

В интервале между особыми состояниями, значение z(t) определяется при помощи операторов U, вид которых в общем случае зависит от особого состояния, являющегося для данного интервала времени начальным состоянием:

z(t*+0)=[t,z(t*+0),us] (7.6)

Здесь t* - момент особого состояния, являющегося исходным для данного интервала времени. Естественно, замечания о том, что H является случайным оператором, без изменений переносится на его частные виды U,V¢ ,V¢¢ ,V и W.

Оператор выходов. Во множестве Z состояний z(t) агрегата выделим класс подмножеств {Zy }, обладающих следующими свойствами. Выходной сигнал yвыдается в момент t¢ в тех случаях, когда: 1) z(t¢ )Î Zy ; z(t¢ -0)Ï Zy и 2) z(t¢ +0)Î Zy , но z(t’)Ï Zy . Тогда, оператор Gможно представить в виде совокупности 2 операторов: G¢ , вырабатывающего выходной сигнал

y=G ¢ [z(t¢ ),us] (7.7)

и G ¢¢ , проверяющего для каждого tпринадлежность z(t) к одному из подмножеств Zy . Заметим, что в общем случае, оператор G¢ является случайным оператором. Это значит, что данным t,z(t),uставится в соответствие не одно определенное значение выходного сигнала, а некоторое множество значений yс соответствующим распределением вероятностей, задаваемых оператором G¢ .

В некоторых случаях в качестве одной составляющих z(t), например z1(t), можно рассматривать время, оставшееся до выдачи выходного сигнала. Тогда оператор G¢¢ проверяет неравенство z1(t)>0.


^ 7.2. Процесс функционирования агрегата

7.2.1. Функционирование агрегата общего вида

Агрегат функционирует следующим образом. В начальный момент времени t0 заданы начальное состояние агрегата z0 и начальное значение управляющего сигнала u0.

Пусть t1 и t2 – моменты поступления первого x1 и второго x2 входных сигналов, t1 – момент поступления первого управляющего сигнала u1 и, для определенности t112. Рассмотрим полуинтервал (t0,t1]. Состояния агрегата изменяются с течением времени по закону

z(t)=[t,z0,u0] (t01) (7.8)

до тех пор (оператор G¢¢), пока в момент t¢ (пусть t¢1) состояние z(t¢) не окажется принадлежащим подмножеству Z¢y, хотя состояние z(t¢-0) не принадлежало подмножеству Z¢y. В этом случае в момент t¢ выдается выходной сигнал y(1), вырабатываемый оператором G¢. Вместе с тем закон изменения состояний (7.6) нарушается и

z(t¢+0)=W[z(t¢),u0]. (7.9)

Прежде чем рассматривать дальнейшие изменения состояний агрегата во времени, необходимо проверить (оператор G¢¢), не удовлетворяет ли состояние z(t¢+0) условиям выдачи выходного сигнала, или, другими словами, не принадлежит ли (в смысле условий 1) и 2), упомянутых выше) состояние z(t¢+0) некоторому новому подмножеству Z¢¢y). Если состояние z(t¢+0) удовлетворяет условиям выдачи выходного сигнала (принадлежит подмножеству Z¢¢y), то в момент t¢¢ выдается второй выходной сигнал y(2) (оператор G¢), а состояние агрегата описывается соотношением

z(t¢+0+0)=W[z(t¢+0),u0]=W{W[z(t¢),u0],u0} (7.10)

и т.д. В силу принятого соглашения в любой интервал времени может быть выдано лишь конечное множество выходных сигналов. Это свойство агрегата является ограничением, накладываемым на структуру подмножеств Zy и оператор W. Предположим теперь, что z(t¢+0) не принадлежит никакому из подмножеств Zy. Поэтому далее состояние агрегата изменяется в соответствии с законом

z(t)=ut¢[t,z(t¢+0),u0]=ut¢{t,W[z(t¢),u0],u0}. (7.11)

Пусть теперь в момент t1 поступает входной сигнал x1. Проследим поведение агрегата в момент t1 при различных вариантах возможных событий.

Если при достаточно малых e>0 в момент t1-e состояние агрегата не принадлежало подмножеству Z*y, а в момент t1 z(t1) принадлежит Z*y, то условимся, что в момент t1 выдается выходной сигнал y*, а состояние агрегата есть

z(t1+0)=W[z(t1),u0] . (7.12)

Вместе с тем действие входного сигнала x1 приводит к тому, что

z(t1+0+0)=V¢[z(t1+0),x1,u0]=V’{W[z(t1),u0],x1,u1} . (7.13)

Очевидно, что состояние z(t1+0+0) должно быть проверено (оператором G¢¢) по отношению к условиям выдачи выходного сигнала. Предположим теперь, что в момент t1 не было оснований для выдачи выходного сигнала y*. Тогда вместо (7.12 и 7.13) в силу действия входного сигнала x1 состояние агрегата имеет вид

z(t1+0)=V¢[z(t1),x1,u0], (7.14)

а в дальнейшем, если состояние (7.14) не соответствует выдаче выходного сигнала:

z(t)={t,V¢[z(t1),x1,u0],u0} (11.13) t11,t] (7.15)

Пусть в момент t1 в агрегат поступает управляющий сигнал u1. Тогда состояние агрегата имеет вид

z(t1+0)=V¢¢[z(t1),u1], (7.16)

если в момент t1 не происходит выдача выходного сигнала, или

z(t1+0+0)=V¢¢{[W[z(t1),u0]]u1,b}, (7.17)

если в момент t1 выдается выходной сигнал.

Необходимо отметить, что управляющий сигнал u в общем случае является параметром, определяющим операторы V¢,V¢¢,W,U,G¢,G¢¢. Поэтому в дальнейшем вместо начального значения управляющего сигнала u0 в этих операторах должно использоваться значение u1 до тех пор, пока не поступит следующий управляющий сигнал u2. Например, в полуинтервале (t1, t2], если нет оснований для выдачи выходного сигнала

z(t)=z(t1+0),u1] t12 (7.18)

В частном случае, операторы H и G могут оставаться неизменными при поступлении очередного управляющего сигнала. Аналогично, оператор U может быть одним и тем же при любых выходных сигналах (при попадании z(t) в любые подмножества Zy).

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


^ 7.2.2. Функционирование СМО как агрегата

В качестве примера представления систем в виде агрегатов рассмотрим однолинейную СМО следующего вида. В моменты времени tj, представляющие собой случайный поток однородных событий с заданным законом распределения, в систему поступают заявки, каждая из которых характеризуется параметром aj. Величина aj является случайной величиной с условным законом распределения f(a/t) при условии, что tj=t. Если линия обслуживания занята, заявка попадает в очередь и может находиться там (ждать) не более, чем

tk(ж)=j(aj,bi) (7.19)

Величина bi является случайной величиной с условным законом распределения f(b/t) при условии, что tk=t. Величины tk образуют случайный поток однородных событий с заданным законом распределения, не зависимый от tj. Заявка должна быть принята к обслуживанию не позднее, чем в момент времени tj+tk(ж), в противном случае она получит отказ.

Время обслуживания заявки или время занятости линии

tk(з)=y(aj,bi) (7.20)

Представим эту СМО в виде агрегата. Состояние агрегата будем характеризовать вектором z(t)ÎZ со следующими компонентами:

z1(t) – время, оставшееся до конца обслуживания заявки (для заявки, которая находится на обслуживании);

z2(t) – значение величины bi;

z3(t) – количеств заявок в очереди;

z4(t) – оставшееся время ожидания первой заявки из очереди (время до момента отказа);

z5(t) – оставшееся время ожидания второй заявки из очереди (время до момента отказа);

zk(t) – оставшееся время ожидания последней заявки из очереди (время до момента отказа).

Входной сигнал xj поступает в момент tj и несет с собой информацию об aj, т.е. xj=aj. Управляющий сигнал gi поступает в момент ti и несет с собой информацию о величине bi, т.е. gi=bi.

Рассмотрим подмножества Zy и соответствующие им выходные сигналы y, операторы W и U.

Подмножество Zy(1). Пусть в момент времени t1:

z1(t1)=0; zl(t)>0; l=3,4,…,k.

Это означает, что обслуживание заявки закончилось. Выходной сигнал y1=(y1(1),y1(2)). Здесь y1(1) признак «заявка обслужена», y1(2)=y1(2)(aj,bi,t1) – выходной параметр заявки, зависящий от aj и bi. Заметим, что случайный характер оператора G¢ может проявляться в том, что y12 (aj,bi,t1) представляет собой случайную функцию aj,bi,t1. Оператор W, определяющий состояние агрегата в момент t1+0, задается следующим образом. Из всех zl(t1), где l=4,5,..k=z3(t), выбирается наименьшее и соответствующая заявка, например номер m, m£k принимается к обслуживанию со временем обслуживания (занятости канала) t(3)m=y(am,bi). Поэтому

(7.21)

Количество заявок в очереди уменьшится на 1: z3(t1+0)=z3(t1)-1 (7.22), а величина zm(t1+0) не определяется. Все остальные zl(t1+0) при l=4,5,..(за исключением zm)

zl(t1+0)= zl(t1) (7.23)

Оператор U, определяющий состояния агрегата для моментов времени t>t1 (до последующего особого состояния) имеет вид

z1(t)=z1(t1+0)-(t-t1)

z2(t)=z2(t1+0)=const

z3(t)=z3(t1+0)=const (7.24)

z4(t)=z4(t1+0)-(t-t1)

............…………

zk(t)=zk(t1+0)-(t-t1)


Подмножество . Пусть в момент времени t2:

z1(t2)>0; z3(t2)>0, zm(t2)=0, 4£m£k

Это означает, что время ожидания одной из заявок в очереди истекло. Поскольку заявка до момента t2 не была принята к обслуживанию, она получает отказ. Выходной сигнал y2=(y2(1),y2(2)). Здесь y2(1) представляет собой признак «заявка получила отказ», y2(2)= y2(2)(aj,bi,t2) – выходной параметр заявки. Оператор W в момент t2+0 описывается соотношениями:

z1(t2+0)=z1(t2)

z2(t2+0)=z2(t2

z3(t2+0)=z3(t2)-1 (7.25)

............…………

zl(t2+0)=zl(t2) l=4,5,..k m


Величина zm(t2+0) не определяется. Оператор U() для моментов времени t>t2 определяется равенствами.

z1(t)=z1(t2+0)-(t-t2)

z2(t)=z2(t2+0)=const

z3(t)=z3(t2+0)=const (7.26)

............…………

zl(t)=zl(t2+0)-(t-t2) ) l=4,5,..k m


Подмножество . В момент времени t3: z1(t3)=0, z3(t3)=0. Это значит, что очередь заявок отсутствует, и обслуживание закончилось в момент t3. Выходной сигнал y3=(y3(1),y3(2)). Здесь y3(1) – признак «система свободна», а y3(2)=t3 показывает момент освобождения системы. Оператор W: z1(t3+0)=0; z3(t3+0)=0; другие zl не определяются. Оператор для всех t>t3 задается соотношениями: z1(t)=0, z3(t)=0; zl(t) при l>3 не определяются (до следующего особого состояния).

Пусть теперь в момент tj поступает входной сигнал xj=aj (заявка с параметром aj). Оператор V¢ имеет следующий вид. Если входной сигнал поступил после выходного сигнала y3 (действовал оператор ) , то это означает, что система была свободной, и заявка сразу поступила на обслуживание с tj(З)=y(aj,bi). Поэтому

z1(tj+0)= tj(3)=y(aj,bi) (7.27)

z3(tj+0)=0

…………………………….

Величины zl(tj+0) для l>3 не определяются. Если входной сигнал поступил после выходных сигналов y1 и y2, то заявка попадает в очередь, т.е.

z1(tj+0)=z1(tj)

z2(tj+0)=z2(tj)

z3(tj+0)=z3(tj)+1

…………………. (7.28)

zl(tj+0)=zl(tj); l=4,5,..k

………………….

zk+1(tj+0)=tj(ж)=j (aj,bi)


В дальнейшем (оператор ) состояния z(t) определяются аналогично (7.24)

Пусть теперь в момент ti поступает управляющий сигнал gi=bi+1. При этом изменится только значение z2(t): вместо прежнего значения bi должно быть z2(t)=bi+1. остальные zl(t) не зависят от bi+1. Из этого легко усмотреть содержание операторов W и U.

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


7.3. Моделирование процесса функционирования агрегата


Целью моделирования в любом случае является получение характеристик, определяемых состояниями системы. Для этого необходимо фиксировать в процессе моделирования достаточно полную информацию о состояниях системы в соответствующие моменты модельного времени. Применительно к агрегату это означает, что необходимо получать значения состояний z(t) для некоторых моментов времени интервала исследования (0,T). Выше было показано, что вид оператора H, решающего эту задачу, зависит от того, поступают или нет входные и управляющие сигналы в течение рассматриваемого интервала времени. Моменты поступления x и uиграют значительную роль с точки зрения построения моделирующего алгоритма. В частности, мы будем рассматривать моделирование как последовательную цепь переходов из одного особого состояния агрегата в другое, причисляя условно к особым состояниям и z(0). Вид моделирующего алгоритма существенно зависит от того, известны ли заранее моменты поступления xи u и вообще моменты последующих особых состояний. С этой точки зрения следует иметь в виду два случая. Первый связан с рассмотрением агрегата, для которого законы поступления входных и управляющих сигналов заданы. В этом случае, очевидно, для моделирования агрегата, кроме описания самого агрегата, необходимо иметь исчерпывающее описание входных и управляющих сигналов, как воздействий внешней среды. Второй случай - рассмотрение агрегата, для которого входные и управляющие сигналы вырабатываются в процессе моделирования как выходные сигналы других агрегатов. Рассмотрим более подробно первый случай.

Итак, изучаем процесс функционирования агрегата в интервале времени (0, Т). Совокупности входных и управляющих сигналов, поступающих в агрегат в течение интервала времени (0, Т), считаем известными. Весьма важным является вопрос о способах ввода в модель входных и управляющих сигналов. Возможные варианты:

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

2. Генерирование сигналов при помощи случайных чисел. Моменты поступления сигналов в агрегат представляются в виде потока однородных событий, задаваемого соответствующим законом распределения интервалов времени между последовательными моментами. Другие параметры сигнала следует при этом задавать условным законом распределения при условии, что момент поступления сигнала задан. Тогда моделирование совокупности сигналов сводится к моделированию потока однородных событий и реализаций случайного вектора, заданного условным законом распределения.

Существенные особенности возникают лишь в том случае, когда входной (или управляющий) сигнал приходит от нескольких источников. Чтобы учесть такого рода обстоятельства, необходимо к подалгоритмам модели, формирующей входные и управляющие сигналы, построить дополнительный подалгоритм – сортировщик, который будет располагать сигналы, вырабатываемые различными источниками, в единую последовательность по времени. Перейдем к рассмотрению структуры моделирующего алгоритма. Введем следующие операторы:

Ф1 – формирование очередного момента τiпоступления в агрегат управляющего сигнала;

Р2 – проверка условия τi ≤ Т, где Т – граница интервала (0, Т) изучения агрегата;

F3 – подстановка вместо τi величины Т+b (b>0);

А4 – запоминание величины τi ;

Р5 – проверка условия i > 1;

Р6 – проверка условия tj< τi, где tj – момент поступления входного сигнала, и определение tвх = min (τ i, tj);

Ф7 – формирование очередного момента tj поступления в агрегат входного сигнала;

Р8 – проверка условия tj < Т;

А9 – запоминание величины tj;

F10 – подстановка вместо tj величины Т+b (b>0);

F11 – формирование признака μ = 0 – «ближайшим сигналом будет управляющий сигнал», tвх = τi;

F12 – формирование признака μ = 1 – «ближайшим сигналом будет входной сигнал», t вх = tj ;

Ф13 – формирование оператора Ut 0 для определения состояний z(t) агрегата в промежутках между особыми состояниями;

А14 – определение ближайшего момента t вых выдачи выходного сигнала (реализация оператора G");

Р15 – проверка условия tвых ≤ tвх, где под tвх понимается меньшее из τ iи t j ;

Ф16 – определение состояния агрегата в момент t вых (реализация оператора Ut0);

Ф17 – формирование выходного сигнала у (реализация оператора G');

Ф18 – формирование состояния z( t вых + 0) после выдачи выходного сигнала (реализация оператора W);

Р19 – проверка принадлежности состояния z( t вых + 0) подмножеству Zy (реализация оператора G");

Р20 – проверка условия t вх < T;

Ф21 – определение состояния агрегата z( t вх) в момент tвх(реализация оператора Ut0);

Р22 – проверка условия μ > 0 (ближайшим сигналом является входной сигнал);

Ф23 – формирование управляющего сигнала g;

Ф24 – определение состояния z(τ i + 0) агрегата после управляющего сигнала (реализация оператора V");

Р25 – проверка принадлежности состояния z(τ i + 0) подмножеству Zy (реализация оператора G");

Ф26 – формирование входного сигнала х;

Ф27 – определение состояния z(t j + 0) агрегата после входного сигнала (реализация оператора V');

Р28 – проверка принадлежности состояния z(t j + 0) подмножеству Zy (реализация оператора G");

F29 – подстановка вместо t0 момента t ос последнего особого состояния (tвх, tвых или t=0);

Ф30 – определение состояния агрегата z(Т) в момент Т окончания моделирования (реализация оператора Ut0);

А31 – фиксация результатов, полученных при моделировании данной реализации процесса;

К32 – счетчик количества N реализаций (выполняет операцию N= N+1);

Р33 – проверка условия N
F 34 - переход к моделированию очередной реализации;

А25 – обработка результатов моделирования;

Я36 – выдача.

При перечислении операторов использованы следующие обозначения:

А – вычислительные операторы;

Ф – операторы формирования реализаций случайных процессов;

F – операторы формирования неслучайных величин;

Р – логические операторы;

Я – оператор, означающий окончание вычислений.

Схема алгоритма приведена на рис.10. Работа моделирующего алгоритма протекает следующим образом. Группа операторов Ф1-F12 предназначена для формирования моментов поступления входных и управляющих сигналов и определения момента поступления ближайшего сигнала. Операторы Ф1 и Ф 7 вырабатывают моменты τ i и tj соответственно. Операторы Р 2 и Р8 определяют, находятся ли эти моменты в пределах интервала моделирования агрегата. Если это условие выполнено, то моменты τi (оператор А 4) и tj(оператор А 9) запоминаются. Если же моменты τi и t j находятся вне интервала (0, Т), то вместо них подставляется граничное значение времени t=Т (операторы F3 и F10 ) . Оператор Р6 сравнивает τi и t j и определяет ближайший момент t вxпоступления в агрегат внешнего сигнала. Результаты сравнения фиксируются операторами F11 и F12; если μ = 0 – ближайшим будет управляющий сигнал, если μ = 1 – входной сигнал. Группа операторов Ф 13 – Р19 моделирует процесс функционирования агрегата в интервале времени между последовательными моментами поступления внешнего сигнала. В этом интервале состояния агрегата определяются оператором Ut0 (оператор Ф13). Единственным видом особых состояний агрегата в этом случае являются состояния выдачи выходных сигналов или, другими словами, состояния, принадлежащие подмножествам Zy. Задача оператора А14 состоит в том, чтобы путем совместного моделирования состояний z(t) и условий, определяющих подмножества Zy, определить моменты ty выдачи выходных сигналов (оператор G" агрегата) и найти наименьший из них. Пути решения этой задачи (реализация оператора А14) зависят от свойств агрегата и способа задания оператора G". В наиболее простых случаях задача сводится к проверке неравенств вида t вых - t > 0 или к совместному решению уравнений (неравенств), описывающих состояния z(t) агрегата и подмножества Z y.

Могут быть и более сложные подходы. В худшем случае приходится «прощупывать» состояния агрегата через малые интервалы времени ∆t и проверять принадлежность их подмножествам Zy на каждом шаге. Выбор минимального t у, т.е. tвых = min t у, обычно не представляет собой проблемы. Если момент t вых выходит за пределы интервала моделирования (0, Т) или не существует, то tвых принимается равным Т + b, где b > 0.

Если момент t вых оказывается внутри интервала между внешними сигналами (оператор Р15), то выходной сигнал у должен быть фактически выдан. Поэтому необходимо найти z( t вых) (оператор Ф16) и сформировать сам сигнал у (оператор Ф17). Обычно при моделировании оператора G' его расчленяют на две части:

  1. формирование для заданного Z y закона распределения случайного выходного сигнала у;
  2. выбор самого сигнала по жребию в соответствии с этим законом распределения.

Затем, поскольку агрегат находится в особом состоянии z( t вых), необходимо определить его состояние z(tвых + 0) (оператор Ф18) и проверить (оператор Р19), не принадлежит ли z(tвых + 0) одному из подмножеств Zy. Если это условие выполнено, то управление передается опять Ф17 для формирования второго выходного сигнала, выдаваемого в момент t вых и т.д. Если же z( t вых + 0) Zy, то через оператор F29 управление передается операторам Ф13 и А14 для формирования новых моментов tвых. Возвратимся к оператору Р 15. Если условие, проверяемое оператором Р15, не выполнено, т.е. t вх ≤ tвых, то переходим к рассмотрению поведения агрегата под воздействием внешнего сигнала. Будем считать, что t вх< Т (оператор Р20). В противном случае наступает конец интервала моделирования и мы переходим к определению состояния z(Т) (оператор А30). Оператор А21 вычисляет состояние агрегата z( t вх), а Р22 определяет тип внешнего сигнала (входной, управляющий). Группа операторов Ф23 – Р25 моделирует прием управляющего сигнала в момент τi, а группа Ф 26 – Р28 - прием входного сигнала в момент tj . Работа этих групп аналогична работе рассмотренной выше группы Ф17 – Р19. Заметим только, что z( t вх + 0) сразу может принадлежать одному из подмножеств Zy. Это условие проверяется операторами Р25 и Р28 соответственно. Если условие справедливо, то управление передается оператору Ф17 для формирования выходного сигнала. Если нет, управление передается оператору Ф1 7) для формирования очередного момента поступления управляющего (входного) сигнала.

Сложность машинной реализации рассмотренного моделирующего алгоритма зависит, в основном, от сложности реализации операторов, определяющих функционирование агрегата.




Рис. 7.1. Схема алгоритма функционирования агрегата общего вида






7.4. Кусочно-линейные агрегаты


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


7.4.1. Понятие о кусочно-линейном агрегате.


Для поставленных здесь задач достаточно считать, что на агрегат не поступают управляющие сигналы u, а поступают лишь входные сигналы x (не ограничивает общности, в качестве x можно рассматривать входной сигнал в широком смысле ()). Итак, мы рассматриваем агрегат как объект, который в каждый момент времени t характеризуется внутренним состоянием z(t), имеет вход и выход. На вход агрегат в изолированные моменты времени могут поступать сигналы, с выхода могут сниматься выходные сигналы. Класс кусочно-линейных агрегатов выделяется с помощью конкретизации структуры множеств Z,X,Y а также операторов H и G. Опишем данную конкретизацию.

Рассмотрим некоторое конечное или счетное множество I. Для определенности предположим, что I={0,1,2,…}, хотя в конкретных задачах I может иметь и другой вид. Назовем I-множеством основных состояний, а элементы nÎI – основными состояниями. Каждому основному состоянию nÎI поставим в соответствие некоторое целое неотрицательное число ||n||, которое назовем рангом основного состояния. Кроме того, каждому nÎI поставим в соответствие выпуклый многогранник Z(n) в евклидовом пространстве размерности ||n||. Будем считать, что Z=UZ(n), т.е. пространство состояний Z можно представить состоящим из всевозможных пар вида (), где nÎI, а z(n) является вектором размерности ||n|| и принимает значения из многогранника Z(n). Вектор z(n) будем называть вектором дополнительных координат. Если ||n||=0 для некоторого nÎI, то это означает, что в данном состоянии n дополнительные координаты не определяются.


7.4.2. Процесс функционирования КЛА.


Опишем сначала динамику КЛА, т.е. процесс изменения внутренних состояний во времени, в предположении отсутствия поступления x. В предыдущей терминологии, определим действия оператора U. Пусть в начальный момент времени t0 агрегат находится в состоянии z(t0)=(n,z(n)(0)), где z(n)(0)- внутренняя точка многогранника Z(n). Тогда при t>t0 точка z(n)(t) перемещается внутри многогранника Z(n) до тех пор, пока не достигнет его границы. Пусть это произойдет в момент t1, который назовем «опорным». Тогда при t01, Dt=t-t0 «движение» агрегата описывается следующими законами:

n(t)=n=const (7.29),

данному значению n соответствует вектор a(n) размерности ||n|| и

z(n)(t)=z(n)(0)+Dt×a(n). (7.30)

Значение опорного момента t1 определяется траекторией z(t), вернее её некоторыми параметрами и может быть найдено из соотношения

t1=inf{t:z(n)(0)+(t-t0)a(n)ÏZ(n), t>t0}, (7.31)

поскольку Z(n) многогранник, то нахождение t1 по (7.31) сводится к следующему. Пусть - j-тая грань многогранника Z(n) (предположим, что Z(n) содержит m(n) граней). Эти грани могут быть заданы линейными уравнениями:

j=1,… m(n) , (7.32)

где zi(n) – компоненты вектора z(n), i=1.. ||n||. Легко понять, что (7.32) может быть записано в виде

или



Обозначим , j=1,…m(n) (7.34)

Пусть t=min{tj;tj>0} (7.35)

Тогда из (7.33-7.35) следует, что t1=t0+t (7.36)

В момент t1 состояние рассматриваемого кусочно-линейного агрегата изменяется скачкообразно. Значение z(t1+0) является случайным, задаваемым распределением P1, которое зависит лишь от состояния z(t1). В момент t1 может выдаваться выходной сигнал (см. оператор G). Содержание (и необходимость выдачи) y зависит от состояния z(t1). Подмножество Zy, введенное в общем определении агрегата, в данном случае совпадает с . Для нас важно, указать, что множество Y имеет структуру, аналогичную Z, т.е. выходные сигналы y представляются y=(l,y(l)), где l-элемент некоторого не более чем счетного множества, y(l) – вектор, принимающий значения из евклидова пространства размером, зависящим от l. При t>t1 движение агрегата вновь происходит в соответствии с формулами (7.29) и (7.30) до очередного «особого» момента t2, где под Dt нужно понимать теперь t-t1 и т.д. Обратимся теперь к случаю поступления входного сигнала. Подчеркнем, что для КЛА множество X структурно аналогично множествам Z и Y, т.е. x=(m,x(m)), где m-элемент конечного или счетного множества, а x(m)- действительный вектор, размерность которого зависит от m. Следующее описание поведения КЛА можно рассматривать как раскрытие действия оператора V.

Пусть в рассматриваемый момент t состояние агрегата z(t)=(n,z(n)) и пусть в этот момент поступает входной сигнал x=(m,x(m)). При этом состояние агрегата меняется скачкообразно. Значение z(t+0) является случайным, задаваемым распределением P2, которое, вообще говоря, зависит от z(t) и x. Будем считать, что в рассматриваемый момент может выдаваться выходной сигнал, содержание и необходимость выдачи которого зависит не только от состояния z(t) (и, быть может, z(t+0)), но и от содержания поступившего входного сигнала x. После рассматриваемого момента времени t движение агрегата происходит в соответствии с формулами (7.29) и (7.30) до следующего момента поступления входного сигнала или выхода вектора состояния на границу допустимых значений.

Динамика КЛА описана полностью. В виде КЛА могут быть формализованы многие реальные процессы: процессы передачи и обмена данными в сетях связи, системы массового обслуживания и материально-технического снабжения, процессы автомобильного движения на дорогах, разнообразные дискретные производственные процессы, вычислительные системы и т.д. При этом всюду основные состояния агрегата указывают на качественно различные состояния моделируемых объектов. Дополнительные же координаты характеризуют происходящие количественные изменения и часто носят сугубо вспомогательный характер, «вбирая» в себя необходимую информацию о предыстории модели. Следует отметить, что представление реальных систем в форме КЛА неоднозначно, поскольку неоднозначно могут быть выбраны состояния агрегатов. Выбор же состояний определяется как целями исследования, так и стремлением уменьшить размерность задачи. При этом всегда приходится идти на компромисс между точностью описания и полнотой получаемой информации с одной стороны и простотой модели – с другой.


7.4.3. Примеры представления систем в виде КЛА.


Пример 1. Вероятностный автомат. Рассмотрим конечный асинхронный вероятностный автомат Мура, т.е. такой, который не имеет «жесткой» тактности, а изменяет свое состояние всякий раз, когда поступает входной сигнал. Синхронный автомат получается, если потребовать, чтобы входные сигналы поступали в моменты t=1,2,… Пусть Za – конечное множество внутренних состояний автомата, Xa – его входной (конечный) алфавит, Ya – его выходной (конечный) алфавит. Для определенности будем считать, что

Za={1,2,…N}, Xa={1,2,..K}, Ya={1,2,..M}.

Динамика автомата описывается следующим образом. Если в момент t состояние автомата za(t)=i и поступил входной сигнал, xa(t)=k, то состояние za(t+0)=j выбирается случайно с вероятностью , ³0, при любом k, 1£k£K. Выходной сигнал yaÎYa, выдаваемый в этот момент, является однозначной функцией «нового» состояния j: ya=m=Ф(j), где Ф- некоторая детерминированная функция с областью определения Za и множеством значений Ya. Представим этот автомат в виде кусочно-линейного агрегата. В качестве множества входных сигналов X КЛА возьмем Xa, а в качестве выходных сигналов Y – множество Ya. За множество I основных состояний КЛА выберем Za и будем считать ||n||=0 при всех nÎI, т.е. вектор дополнительных координат z(n) не определяется. При таком выборе состояния КЛА не определяются многогранники Z(n), отпадают вопросы о движении внутри многогранника, выходе на границу и связанного с ним распределения P1.

Все движение рассматриваемого КЛА состоит из скачков состояния при поступлении входных сигналов, причем ввиду отсутствия вектора дополнительных. координат речь идет лишь о скачках основного состояния n. Т.о., требуется задать лишь распределение P2. Оно совпадает с рассмотренным выше распределением . Содержание же выходного сигнала, выдаваемого в момент поступления входного, определяется только функцией Ф. Вообще, если предположить, что ||n||=0, ||l||=0, ||m||=0 " n,a,m, то легко видеть, что КЛА превращается в вероятностный автомат весьма общего вида.

Пример 2. Система массового обслуживания. Пусть на обслуживающий прибор поступает ординарный поток требований, причем i-е по счету требование характеризуется параметром qi, который представляет собой предельно допустимое время ожидания i-м требованием начала обслуживания. Время обслуживания i-того требования равно zi, причем {zi} – последовательность независимых одинаково распределенных случайных величин с общей функцией распределения B(x). Искомыми являются вероятностные характеристики длины очереди и времени ожидания.

Представим данный процесс в виде КЛА. За состояние агрегата выберем вектор z=(n,z(n)), где n- число требований, находящихся в системе в текущий момент времени, которые дождутся (или дождались) начала обслуживания, ||n||=n, а z(n) – вектор, координаты которого определяются только при n>0 и имеют следующий смысл: z1(n) – время, оставшееся до окончания обслуживания требования, находящегося на приборе, а zi(n) (1<i£n) – длительности обслуживания требований, которые стоят в очереди и будут впоследствии обслужены. В соответствие с этим вектор a(n) скоростей изменения дополнительных координат имеет компоненты a1(n)=-1, ai(n)=0 (1<i£n), многогранник Z(n) при каждом n>0 совпадает с первым октантом эвклидова пространства размерности n:

Z(n)={z(n): zi(n)³0, i=1,2,.. n} и имеет m(n)=n ограничивающих координатных гиперплоскостей

Zj(n) ={z(n):zj(n)=0} j=1,..n.

В качестве входного сигнала рассмотрим пару (1,q), где символ 1 просто указывает на факт поступления требования (и, таким образом, дискретная компонента m принимает лишь одно значение 1), а величина q равна допустимому времени ожидания поступающего требования (т.е. ||m||=1).

Рассмотрим динамику данного агрегата. Поскольку между моментами поступления входных сигналов изменяется лишь первая дополнительная координата (если n³1), то нет необходимости рассматривать случаи выхода дополнительных координат на гиперплоскости Zj(n), j>1 (мы считаем, что zi>0 с вероятностью 1). Пусть в момент t* выполнено z(t*)ÎZ1(n). Тогда с необходимостью

z(t*)=(n, 0, z2(n),..zn(n)), где n>0 (7.37)

Физически это означает, что момент t* является моментом окончания обслуживания и, следовательно, обслуженное требование должно покинуть систему, а его место занимает требование стоящее первым в очереди (если очередь не пуста). Следовательно, из состояния (7.37) агрегат перейдет в состояние



z(t*+0)= (7.38)


Т.о. распределение P1 является вырожденным и приписывает вероятность 1 состоянию вида (7.38) (если предыдущее состояние имело вид (7.37) и вероятность 0 любому множеству состояний, не содержащему (7.38). Будем считать, что в рассматриваемый момент t* выходной сигнал не выдается.

Рассмотрим теперь случай поступления входного сигнала (1,q) в момент t**. Пусть при этом состояние агрегата было z(t**)=(n,z(n)), где n³0. Физически поступление рассматриваемого входного сигнала означает приход требования, обладающего предельным временем ожидания q, в систему обслуживания. Рассмотрим 2 случая: n=0 и n>0. В первом из них требование поступает в пустую систему, а во втором – в занятую обслуживанием. При n=0 состояние z(t**+0) должно отражать тот факт, что поступившее требование сразу принято к обслуживанию и ему случайным образом назначено время обслуживания (с распределением B), т.е.

z(t**+0)=(1,z), (7.39)

где z - случайная величина, имеющая распределение B(x). При n>0 состояние z(t**+0) должно отражать тот факт, что требование будет принято к обслуживанию тогда и только тогда, когда его предельное время ожидания q превосходит реальное (т.е. q>) и в случае, если оно принято, ему назначается случайное время обслуживание с распределением B(x).



z(t**+0)= ( (7.40)


, где z(x) – случайная величина с распределением B(x). Соотношения (7.39) и (7.40) конструктивно задают распределение P2.

Будем считать, что в момент t** выдается входной сигнал, фиксирующий имеющуюся длину очереди, время ожидания и факт принятия или непринятия поступающего требования. В соответствии с этим предположим, что y=(l,y(l)), где l=(l1,l2), l1 – число требований, находящихся в системе в момент t**. l2=0 или 1, если поступающее требование не принимается или принимается соответственно к обслуживанию, ||l||=l2, y(l)=время ожидания принятым требованиям начала обслуживания.

В данном случае l представляет собой вектор размерности 2 с целочисленными компонентами. Из сказанного следует, что имеют место зависимости:

l1=n



l2=


y(l)=(координата определяется лишь при l2=1)

На этом описание данной системы массового обслуживания в виде КЛА закончено.


7.5. Агрегативные системы


Рассмотрим класс сложных систем, представляющих собой конструкции из агрегатов, обладающих следующим свойством: существует такое (в общем случае неоднозначное) расчленение системы на элементы, при котором каждый полученный элемент представляет собой агрегат. Такого рода сложные системы будем называть агрегативными или А-системами. Каждый элемент А-системы, будучи в общем случае агрегатом, не обязательно должен обладать полным комплектом свойств агрегата: он может быть и более простым объектом, представляющим собой частный случай агрегата. Вместе с тем среди элементов А-системы не может быть ни одного элемента, который не являлся бы агрегатом (с полным или частичным комплектом свойств). Другими словами, среди элементов А-системы не могут содержаться объекты более общего характера, чем агрегат.

Вся информация, циркулирующая в А-системе, делится на внешнюю (поступающую извне от объектов, не являющихся элементами данной системы) и внутреннюю, вырабатываемую агрегатами самой системы. Обмен информацией между А-системой и внешней средой происходит через агрегаты, называемые полюсами системы. Так имеются входные полюса, представляющие собой агрегаты, для которых вводимая информация, поступающая в виде x-сообщений, является полностью или частично внешней (A1 и A4 на рис. 11). Управляющие полюса (A1,A3,A6). Заметим, что А1 является одновременно входным и управляющим полюсом системы. Выходные полюса (A3,A7). Агрегаты, не являющиеся полюсами, называются внутренними агрегатами. В частном случае А-система может не содержать внутренних агрегатов, а состоять только из полюсов. Могут быть также случаи, когда в А-системе отсутствуют входные и управляющие полюсы. Наконец, А-система может состоять лишь из одного агрегата. Этот агрегат одновременно может быть входным, управляющим и выходным полюсом А-системы.



g2

(x)

(x)

(g)

(g)

(g)


Рис. 11. ^ Агрегативная система


Передача информации в А-системе происходит мгновенно (см 3.2), т.е. момент t¢ выдачи каким-нибудь из агрегатов является также моментом поступления входной или управляющей информации в некоторый агрегат системы или, наконец, моментом выдачи информации выходным полюсом системы. Такое предположение не является стеснительным ограничением. Если в реальной системе передача информации между ее элементами происходит с задержкой по времени, то соответствующая линия передачи представляется как самостоятельный агрегат, осуществляющий задержку. Тогда в формализованной схеме передача информации между элементами будет происходить мгновенно.

^ Виды связей между агрегатами. Свойства А-системы определяются не только свойствами составляющих агрегатов, но также и ее структурой. Рассмотрение структуры начнем с определения соотношений взаимодействия между агрегатами.

Два агрегата B и C называются непосредственно связанными, если между ними осуществляется прямая передача информации, т.е. выходная информация агрегата B является входной или управляющей для агрегата C, или наоборот. Будем также рассматривать просто связанные агрегаты. Агрегаты B и С называются связанными, если существует такая совокупность агрегатов B,D1,D2,…,DS,C, что каждые два соседних агрегата B,D1,D2,…,DS,C непосредственно связаны (в противном случае, несвязанные агрегаты). Рассмотрим некоторые виды связей между агрегатами. Будем говорить, что агрегат С непосредственно следует за агрегатом B (агрегат B непосредственно предшествует агрегату С), если некоторая часть выходной информации агрегата B является частью входной информации агрегата C. Очевидно, что данный агрегат, если даже он является полюсом A-системы, может непосредственно следовать за несколькими (непосредственно предшествовать нескольким) агрегатами А-системы. Аналогичные отношения можно ввести для связанных агрегатов. Будем говорить, что агрегат C следует за агрегатом B (агрегат B предшествует агрегату C), если существует такая совокупность агрегатов B,D1,D2,…,DS,C, каждый из которых непосредственно следует за предыдущим.

Аналогично будем говорить, что агрегат B непосредственно управляет агрегатом C (агрегат С непосредственно подчинен агрегату B), если некоторая часть управляющей информации агрегата С представляет собой часть выходной информации агрегата B. Данный агрегат может непосредственно управлять несколькими агрегатами или быть непосредственно подчинен нескольким агрегатам А-системы. Агрегат B управляет агрегатом С (агрегат С подчинен агрегату B), если существует такая совокупность B,D1,D2,…,DS,C, что каждый из них непосредственно управляет последующим агрегатом.