Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 6

й. Сети Петри со своими фишками н правиламн запусков во многом напоминают игры, имеющие игровое поле: шашки, трик-тракф, ним, го в др. Можно В Нарды. — Прим. рвд. Глооа 3 Рис. 2.2х2. Игровое поле. придумать игру для одного — четырех человек, состоящую нз нгроаого поля (и качестае такого поля используется сеть Петри) н набора пластиковых фишек. Фишки распределены по позициям ости Петри, и игроки по очереди выбирают разрешенные переходы и запускают нх. Для разнообразия игра может быть сделана иа двадцати различных сагах Петри. Используя зти идея, придумайте правила, предусматривающие следующее: а) Как определено начальное распахал~ение фишекг (Каждый игрок начинает игРу, имея одну фип1ку в едоннкез; каждый лгрок получает «лз фишек на веем поле по желанию и г.

д.) б) (такова цель нгрыг (Захаатнть фишки своего противника; получить нан. большее количество фишек; как можно скорее избавиться от своих фишек н т. д.) в) Не нужно ли раскрасить фишки для разных игроков? (В соотиетстаин с этим определите правила запуска.) г) Не стоит лн присвоить очки различным переходам) Тогда очки игрока оп.

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

2.Ь. аалътернетивные формы определения сетей Петри Теория сетей Петри разрабатывалась рядом авторов. У них были различные мотивы и предпосылки. Вследствие такого разнообразия многие фундаментальные понятия были определены по-разному. Дадим некоторые из этих альтернативных определений, чтобы показать, что между ними нет существенных различий, и чтобы подготовить читателя к тем разнообразньпи представлениям, которые могут встретиться в литературе.

Например, оригинальные сети Петри (24Ц не разрешают существование кратных дуг между позициями и переходами. Это эквивалентно определению входов и выходов переходов как множеств (а не как комплектов) позиций. Далее, правило запуска было ограничено следующим требованием: фишка есть в каждой входной псвнции для перехода, и нет ни одной фишки в выходных позициях. Переход запускается путем удаления фишек из его входов (которые теперь становятся пустыми) и размещением фишек в (ранее пустых) выходах (которые теперь заполняются). Переход не может быть запущен, если фишка уже принадлежит выходной позиции.

Таким образом, маркировка каждой позиции присваивает либо О фишек, либо 1 фишку, )т: Р— н (О, 1). Теперь становится очевидным тот факт, что сеть с и позициями имеет точно 2" возможных маркировок, т. е конечное число состоянии. Ранние разработки Хольта по проекту теории информационных систем 11281 использовали эти же определения, но по мере продвижения исследований была обнаружена ограниченность такой модели. В работе Хольта н Коммонера, представленной на конференции в Вудс Холле [127), класс маркировок и правила запуска распространены на произвольные маркировки, рл Р— +- (О, 1, 2, ...). Таким образом была создана базовая модель сетей Петри атом виде, в каком она определена сегодня (за исключением возможности кратных дуг).

Многие из первых исследователей не давали формального определения своих моделей, а описывали неформально относящиеся к их работе компоненты, такие, как позиции, переходы, фишки и правило запуска. Одно из первых формальных определений было дано Патилом 123Ц в его докторской диссертации, в которой сеть Петри определялась в виде четверки (Т, Р, А, В), где Т вЂ” множество переходов, А — множество дуг„Р— множество позиций и В— начальная маркировка.

Дуги множества А соединяли либо позицию с переходом, либо переход с позицией. Таким образом, А'= ы (Р л' ,Т) Ь (Т х Р), Многие статьи по сетям Петри основывают- 2 562 Тливо 2 ся на этом определении н оиредечяют сеть Петри как тройку (Р, Т. Л) с выделенной функцией маркировки. Преобразование нз формы (Р, Т, Л) к определению с выделением входной и выходной функциями сравнительно просто. Мнознество дуг Л разбиваечся на множество входных дуг ((ры (у) ~ (рь У)) Р Л) и выходных дУг ((1;, Рг) ) ((л Рч) б Л). Эта фоРма непосРедственно приводит к обобщению, допускакпцему кратные входы и выходы. Необходимо только указывать кратность для каждой входной н выходной дупч. Хэк 11161 в конце концов остановччлся на определении сетей Петри в виде четверки (Р, Т, Г, В), где, как обычно, Р— множество позиций, Т вЂ” множество переходов, Р и  — функции, ставюцие в соответствие позициям и переходам количество фишек, необходимых для входа (Г) илн сбразованных для выхода (В).

Следовательно, переход 1) можно запустить только в том случае, если по краИ- ней мере Р(1ач р;) фишек находятся в каждой позиции р; Е Р. Переход запускается путем удаления Р(1в рч) фишек нз каждой входной позиции н помещения В((в рч) фйшек в каждую выходную позицию. Функции Р и В могут быть представлены матрицами. Питерсон в своей диссертации 12361 попытался объединить переходы и их входы и выходы, определяя переход как упорядоченную пару комплектов позиций: 1; Е Р х Р .

Первая компонента пары — комплект входов перехода; вторая — комплект выходов перехода. Это сводит множество примитивных понятий теории к позициям и фишкам, так как переходы являются структурами, составленными из позиций. Такой подход особенно полезен для простого определения переходов при построении сети Петри. Эти определения отличаются от представленных здесь тглчько разницей в обозначениях. В большинстве работ по сетям Петри именно это имеет место: различие в определениях проявляется только в обозначениях. Однако в некоторых случаял определения могут ограничивать класс сетей Петри тем, что не допускаются кратные входные н выходные дуги нли сугцествует ограничение на форму переходов, т.

е. требуется, чтобы переходы имели непустые множества входных и выходных позиций нлп входные и выходные позиции перехода не должны совпадать (без петель). Но, как мы покажем в гл. 5, даже эти различия не имеют большого значения. Упражнения $. Дайте эквивалентное со андартное определение через Р, Т, Ц О) д эя сети Петри, определенной как (Р, Т, Р, О). Дайте определение через (Р, Т, Г, о) для сети Петри, заданной как (Р, Т, ), О). ун Почему некоторые нсследовэтсэп предпочитают определение через (Р. Т, А), которое ойзединяет входные н ващодныс взаимосвязи в множеств. дуг А, в то времн как другие отдают предночтенпе (Р, Т, т, О)) Покажите преимущество и недостатки каждого. Основные опредезснлл 2.7.

Замечания к литературе Для дальнейшего знакомства с сетями Петри, вероятно, лучше всего начать с обзоров 120, 238( в Сошрц(!щ 8пгтеуз. Почти в любой работе несколько первых разделов посвящены основным определениям и обюзначенпям, гюэтому, чтобы найти различия в определешгях, дос1з1 очно бегло просмотреть начала некоторых из перечисленных в биб;шографип. Например: !128, 127, 111, 115, 116, 152, 201, 208, 2901. 2.8. Темы для дальнейшего изучения 1. Разработайте теорию сетей Петри, разрешающую существование окрашенных фишек. Рассмотрите различия в определениях разрешенных переходов и запусков переходов.

Существует по меньшей мере трн разумных способа обобщения сетей Петри в случае окрашенных фишек. Укажите те, которые вы сможете предложить, и оцените степень их полезности. 2. Разработайте представление теории сети Петри для научных работников, це связанных с вычислительной техникой. Сравните ваше представление с предс1авлением Хольта !1231 и Мельдмана !184, 185!. 3. Постройте систему моделирования на ЭВМ для выполнения сети Петри. Для удобного интерфейса пользователя с программой используйзе стирающий графический дисплей (с электронно-лучевой трубкой пли плазменный) для изображения запусков переходов и последовательного передвижения фишек.

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

СЕ1И ПЕ1РИ ДЛЯ МОДЕЛИРОВАНИЯ Сети Петри были разработаны н используются н основном ддя моделироннння. С нх помощью могут быть промоделнровзны многие системы, н особенности системы с независимыми компонентами, например аппаратное н и ограммное обеспечение ЭВМ, физические системы, сопнальные н др. Сети «трн применяются для моделирования нозннкнонення рззлнчных событий н системе. В частности, сегн Петри могут моделировать поток ннформзпнн нлн другие ресурсы системы. В зтой главе мы прин«нем прнмеры енсге»ь моделнру«мых прн помощи сетей Петри.

Этн примеры дадуг прндсганленне о большом классе систем, которые можно моделнронзть сетямн Петри. об использующемся методе моделнровання и о снойстннх, которыми должны обладать моделируемые системы. 3.1. События и условия Простое представление системы сетью Петри основана на двух основополагающих понятиях: собпипиях и условиях. Сабытия— это действия, имеющие место в системе. Возникновением событий управляет состояние системы.