Советов Б.Я., Яковлев С.А. Моделирование систем (2001) (1186219), страница 18
Текст из файла (страница 18)
Несравненно большими возможностями обладают имитационные модели, позволяющие исследовать Q-схему, задаваемую Q=(W, U,H,Z, Y, R, А}, без ограничений. На работу с Q-схемами при машиннойреализации моделей ориентированы многие языки имитационногомоделирования, например SIMULA, SIMSCRIPT, GPSS и др. Детально вопросы, связанные с имитационным моделированием g-схем,будут рассмотрены далее.2.6.
СЕТЕВЫЕ МОДЕЛИ (JV-СХЕМЫ)В практике моделирования объектов часто приходится решатьзадачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременнопараллельно протекает несколько процессов. Самым распространенным в настоящее время формализмом, описывающим структуруи взаимодействие параллельных систем и процессов, являются сетиПетри (англ.
Petri Nets), предложенные К. Петри [28, 30].Основные соотношения. Теория сетей Петри развивается в нескольких направлениях: разработка математических основ, структурная теория сетей, различные приложения (параллельное программирование, дискретные динамические системы и т. д.).Формально сеть Петри (N-схема) задается четверкой видаN=(B,D,I,0),где В — конечное множество символов, называемых позициями,ВФ0\ D — конечное множество символов, называемых переходами, D^0, В[)рФ0\ I—входная функция (прямая функция инцидентности), I: BxD-*{0, 1}; О — выходная функция (обратнаяфункция инцидентности), О : Dx 2?-»{0,1}.
Таким образом, входнаяфункция / отображает переход d, в множество входных позицийbtel(dj), а выходная функция О отображает переход d, в множествовыходных позиций bteD(dj). Для каждого перехода djeD можноопределить множество входных позиций перехода 1(d) и выходныхпозиций перехода О (dj) какЩ)={Ь,еВ\[{Ьь4)=1},0(dJ)={bieB\0(dJ, £,) = !},i=T7n\j=\,m,n=\B\, m=\D\.Аналогично, для каждого перехода bteB вводятся определениямножества входных переходов позиции 1(b) и множества выходныхпереходов позиции О (£>,):711(Ьд={djeD\I(dj, Ь,)=1},O(bd={djeD\0(bh dj)=l}.Графически N-схема изображаетсяв виде двудольного ориентированногомультиграфа, представляющего собойРис. 2 8 .
Графическое изображе совокупность позиций и переходовние N-схемы(рис. 2.8). Как видно из этого рисунка,граф N-схемы имеет два типа узлов:позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждаядуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции).
ГрафN-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.Пример 2.7. Представим формально N-схему, показанную в виде графана рис. 2.7:N-(B, D, /, оу,В=*(Ьи Ьи *з> **• *з>>2>~<4, dt,•<*i.rf4>.'ttMM.0(d^{b2,/№Ы*а. К М.0(d2)~{b5},/№>-{*»}.0(d,)={6*},/«XU0{d^{bitb3, b,},b3}.Возможные приложения.
Приведенное представление N-схемыможет использоваться только для отражения статики моделируемой системы (взаимосвязи событий и условий), но не позволяетотразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводитсяфункция маркировки (разметки) М: 2*-»{0, 1, 2, ...}. МаркировкаМ есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток,соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутривершин-позиций соответствующего числа точек (когда количествоточек велико, ставят цифры).Маркированная (размеченная) N-схема может быть описанав виде пятерки NM = (B, D, I, О, М> и является совокупностью сетиПетри и маркировки М [28, 30].Функционирование N-схемы отражается путем перехода от разметки к разметке.
Начальная разметка обозначается как MQ : 2?-»{0,1, 2, ...}. Смена разметок происходит в результате срабатывания72Рис. 2.9. Пример функционирования размеченной N-схемыодного из переходов djSD сети. Необходимым условием срабатывания перехода dj является btel(dj) {М(Ы)^1}, где М{£><} — разметкапозиции bt. Переход dj, для которого вьшолняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.Срабатывание перехода dt изменяет разметку сети Мф)==(М(Ь1), М(Ь2), ..., М(Ья))г на разметку М'(Ь) по следующемуправилу:М'(Ь)=М(Ь)-1Ц) + 0(4),т. е.
переход d} изымает по одной метке из каждой своей входнойпозиции и добавляет по одной метке в каждую из выходных позиций. Для изображения смены разметки М на М' применяют обозначение М\1М'.73Пример 2.8. Рассмотрим размеченную N-схему с начальной разметкой Ма*>{1,О, 0, 0, 1, 0, 1}, которая приведена на рис.
2.9, а. При такой начальной разметкеN-схемы единственным готовым к срабатыванию является переход d2, срабатываниекоторого ведет к смене разметки М0 И Ми где М1 = {0,1, 1, 0, 1, 0, 1} (рис. 2.9, б).При разметке М^ возможно срабатывание переходов «/„ af, и i s . В зависимости оттого, какой переход сработал первым, получается одна из трех возможных новыхмаркировок (рис. Z9, в, г, д). Функционирование N-схемы продолжается до тех пор,пока существует хотя бы один возможный переход.Таким образом, N-схема выполняется путем запусков переходов под управлением количества меток и их распределения всети. Переход запускается удалением меток из его входных позиций и образованием новых меток, помещаемых в выходные позиции.
Переход может запускаться только тогда, когдаон разрешен. Переход называется разрешенным, если каждая изего входных позиций имеет число меток, по крайней мереравное числу дуг из позиции в переход.Пример 13. Для некоторой заданной размеченной N-схемы (рис. 2.8) с начальноймаркировкой Л/0=>{1, 2, 0, 0, 1} (рис. 2.10, а)разрешенным является только переход dltа остальные переходы d2, d3udt — запрещенные. В результате выполнения этого переходаполучим новую размеченную N-схему (ряс.2.10, б). Теперь разрешены переходы а2 и d3;в результате их запуска получим новую размеченную N-схему. Переходы d2 и d3 находятся в конфликте, так как запушен можетбыть только один из них. Например, призапуске d, получим сеть, показанную на рис.2.10, в.
Теперь разрешен только переход diи получим новую размеченную сеть (рис. 2.10,г). Теперь разрешено два перехода: d2 и d3 (вконфликте). Запустим переход d2 (ряс. 2.10, д).Теперь ни один переход не может быть запушен и выполнение сети прекращается.Рис. 2.10. Пример функциоюфования размеченной заданной JV-схемы74Важной особенностью моделейпроцесса функционирования системс использованием типовых N-схемявляется простота построения иерархических конструкций модели.С одной стороны, каждая N-схемаможет рассматриваться как макропереход или макропозиция моделиболее высокого уровня. С другойстороны, переход, или позиция Nсхемы, может детализироватьсяв форме отдельной подсети для более углубленного исследования процессов в моделируемой системе S.Отсюда вытекает возможность эффвКТИВНОГО использованияN-схемдля моделирования параллельных и конкурирующих процессовв различных системах.Типовые N-схемы на основе обычных размеченных сетей Петрипригодны для описания в моделируемой системе S событий произвольной длительности.
В этом случае модель, построенная с использованием таких N-схем, отражает только порядок наступлениясобытий в исследуемой системе S. Для отражения временных параметров процесса функционирования моделируемой системы 5 набазе N-схем используется расширение аппарата сетей Петри: временные сети, ЛГ-сети, сети Мерлина и т. д. [19]. Детально вопросы,связанные с имитационным моделированием с использованием Nсхем, будут рассмотрены далее.2.7. КОМБИНИРОВАННЫЕ МОДЕЛИ (Л-СХЕМЫ)Наиболее известным общим подходом к формальному описанию процессов функционирования систем является подход, предложенный Н. П.
Бусленко. Этот подход позволяет описывать поведение непрерывных и дискретных, детерминированных и стохастических систем, т. е. по сравнению с рассмотренными являетсяобобщенным (универсальным) и базируется на понятии агрегативной системы (от англ. aggregate system), представляющей собойформальную схему общего вида, которую будем называть А-схемойОсновные соотношения. Анализ существующих средств моделирования систем и задач, решаемых с помощью метода моделирования на ЭВМ, неизбежно приводит к выводу, что комплексное решение проблем, возникающих в процессе создания и машинной реализации модели, возможно лишь в случае, если моделирующиесистемы имеют в своей основе единую формальную математическую схему, т. е. А-схему.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
