Непрерывно-стохастические модели 2 страница

Формально сеть Петри (N-схема)задается четверкой вида

N=<B, D, I, O>,

где В — конечное множество символов, называемых позициями, ; D — конечное множество символов, называемых перехода­ми, , ; I — входная функция (прямая функция ин­цидентности), I: ; О — выходная функция (обратная функция инцидентности), О: . Таким образом, входная функция I отображает переход в множество входных позиций ,а выходная функция О отображает переход в множество выходных позиций .Для каждого перехода можно определить множество входных позиций перехода и выходных позиций перехода как

Аналогично, для каждого перехода вводятся определения множества входных переходов позиции и множества выходных переходов позиции :

Графически N-схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 2.8). Как видно из этого рисунка, граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые 0 и 1 соответственно. Ориен­тировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или пере­хода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существова­ние кратных дуг от одной вершины к другой.

 

Пример 2.7. Представим формально N-схему,показанную в виде графа на рис 2.7:

 

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

Маркированная (размеченная) N-схема может быть описана в виде пятерки и является совокупностью сети Петри и маркировки М [28, 30].

Функционирование N-схемы отражается путем перехода от раз­метки к разметке. Начальная разметка обозначается как . Смена разметок происходит в результате срабатывания

 

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

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

т. е. переход изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных пози­ций. Для изображения смены разметки М на М’ применяют обозна­чение .

 

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

 

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

 

Пример 2.9. Для некоторой заданной размеченной N-схемы (рис. 2.8) с начальной маркировкой (рис. 2.10, а)разрешенным является только переход , а остальные переходы , и — запрещен­ные. В результате выполнения этого перехода получим новую размеченную N-схему (рис.2.10, б). Теперь разрешены переходы и ;в результате их запуска получим новую раз­меченную N-схему. Переходы и нахо­дятся в конфликте, так как запущен может быть только один из них. Например, при запуске получим сеть, показанную на рис. 2.10, в. Теперь разрешен только переход и получим новую размеченную сеть (рис. 2.10, г). Теперь разрешено два перехода: и (в конфликте). Запустим переход (рис. 2.10, д).Теперь ни один переход не может быть запушен и выполнение сети прекращается.

 

Важной особенностью моделей процесса функционирования систем с использованием типовых N-схем является простота построения ие­рархических конструкций модели. С одной стороны, каждая N-схема может рассматриваться как макро­переход или макропозиция модели более высокого уровня. С другой стороны, переход, или позиция N-схемы, может детализироваться в форме отдельной подсети для бо­лее углубленного исследования про­цессов в моделируемой системе S. Отсюда вытекает возможность эф­фективного использования N-схем для моделирования параллельных и конкурирующих процессов в различных системах.

Типовые N-схемы на основе обычных размеченных сетей Петри пригодны для описания в моделируемой системе S событий произ­вольной длительности. В этом случае модель, построенная с ис­пользованием таких N-схем, отражает только порядок наступления событий в исследуемой системе S. Для отражения временных пара­метров процесса функционирования моделируемой системы S на базе N-схем используется расширение аппарата сетей Петри: вре­менные сети, E -сети, сети Мерлина и т. д. [19]. Детально вопросы, связанные с имитационным моделированием с использованием N-схем,будут рассмотрены далее.

 

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

 

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

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

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

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

В качестве элемента А-схемы выступает агрегат, а связь между агрегатами (внутри системы S и с внешней средой Е) осуществляет­ся с помощью оператора сопряжения R. Очевидно, что агрегат сам может рассматриваться как А-схема,т. е. может разбиваться на элементы (агрегаты) следующего уровня.

Любой агрегат характеризуется следующими множествами: мо­ментов времени T, входных X и выходных Y сигналов, состояний Z в каждый момент времени t. Состояние агрегата в момент времени обозначается как , а входные и выходные сигналы — как и соответственно [4].

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

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

Обозначим полуинтервал времени как , а полуин­тервал — как . Если интервал времени не содержит ни одного момента поступления сигналов, то для состояние агрегата определяется случайным оператором U в соответствии с соотношением

Совокупность случайных операторов V и U рассматривается как оператор переходов агрегата в новые состояния. При этом процесс функционирования агрегата состоит из скачков состояний в мо­менты поступления входных сигналов x (оператор V) и изменений состояний между этими моментами и (оператор U). На оператор U не накладывается никаких ограничений, поэтому до­пустимы скачки состояний в моменты времени, не являющиеся моментами поступления входных сигналов х. В дальнейшем момен­ты скачков будем называть особыми моментами времени , а состояния — особыми состояниями А-схемы. Для описания скачков состояний в особые моменты времени будем использо­вать случайный оператор W, представляющий собой частный слу­чай оператора U, т. е.

В множестве состояний выделяется такое подмножество , что если достигает ,то это состояние является моментом выдачи выходного сигнала, определяемого оператором выходов

Таким образом, под агрегатом будем понимать любой объект, определяемый упорядоченной совокупностью рассмотренных мно­жеств Т, Х, Y, Z, Н и случайных операторов V, U, W, G.

Последовательность входных сигналов, расположенных в по­рядке их поступления в А-схему, будем называть входным сообще­нием или x-сообщением. Последовательность выходных сигналов, упорядоченную относительно времени выдачи, назовем выходным сообщением или y-сообщением.

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

 

Пример 2.10. Рассмотрим А-схему, структура которой приведена на рис. 2.11. Функционирование А-схемы связано с переработкой информации, передача послед­ней на схеме показана стрелками. Вся информация, циркулирующая в А-схеме, делятся на внешнюю и внутреннюю. Внешняя информация поступает от внешней объектов, не являющихся элементами рассматриваемой схемы, а внутренняя инфор­мация вырабатывается агрегатами самой А-схемы. Обмен информацией между А-схемой и внешней средой Е происходит через агрегаты, которые называются полюсами А-схемы. При этом различают входные полюсы A-схемы, представляющие собой агрегаты, на которые поступают x -сообщения (агрегаты , , ),и выход­ные полюсы А-схемы, выходная информация которых является y -сообщениями (агрегаты , , , , , ).Агрегаты, не являющиеся полюсами, называются внутренними.

Каждый n -й агрегат А-схемы имеет входные контакты, на которые поступает совокупность элементарных сигналов , , одновременно возникающих на входе элемента, и выходные контакты, с которых снимается совокупность элементарных сиг­налов , . Таким образом, каждый агрегат А-схемы имеет входных и выходных контактов.

Описание отдельного агрегата уже рассмотрено, поэтому для построения формального понятия А-схемы остается выбрать достаточно удобные спосо­бы математического описа­ния взаимодействия между агрегатами. Для этого вве­дем ряд предположений о закономерностях функцио­нирования А-схем,хорошо согласующихся с опытом ис­следования реальных слож­ных систем [4]: 1) взаимодействие между А-схемой и вне­шней средой Е,а также меж­ду отдельными агрегатами внутри системы S осуществ­ляется при передаче сигна­лов, причем взаимные влия­ния, имеющие место вне ме­ханизма обмена сигналами, не учитываются; 2) для опи­сания сигнала достаточно некоторого конечного набора характеристик; 3)элементарные сигналы мгновенно передаются в А-схеме независимо друг от друга по элементарным каналам; 4) к входному контакту любого элемента А-схемы подключается не более чем один элементарный канал, к выходному контакту — любое конечное число элементар­ных каналов при условии, что ко входу одного и того же элемента А-схемы направляется не более чем один из упомянутых элементар­ных каналов.

Взаимодействие А-схемы с внешней средой Е рассматривается как обмен сигналами между внешней средой Е и элементами А-схемы. В соответствии с этим внешнюю среду Е можно представить в виде фиктивного элемента системы , вход которого содержит входных контактов , а выход — выходных контактов , . Сигнал, выдаваемый А-схемой во внешнюю среду Е,принимается элементом как входной сигнал, состоящий из эле­ментарных сигналов . Сигнал, поступа­ющий в А-схему из внешней среды Е, является выходным сигналом элемента и состоит из элементарных сигналов .

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

В силу предположения о независимости передачи сигналов каж­дому входному контакту

соответствует не более чем один выходной контакт

где — множество входных контактов всех элементов А-схемы и внешней среды Е; — множество выходных контактов всех элементов А-схемы и внешней среды Е,с которыми она связана элементарным каналом; k, .