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

Двойственной к сети Петри С = (Р, Т, Х, 0) является сеть Петри С = (Т, Р, У, О), которая получается в результате перестановки позиций и переходов. Структура графа сохраняется, просто меняются местами кружки и планки (см. упражнение 6). На рис. 2.7 юа Рис. 2.7. Сета„двойственнаи и сети Петри, показанной на рис 2,4, Основные определения показана сеть, двойственная к сети Петри на рис.

2.4. Двойственность — обычно полезный прием в теории графов и кажется интересным понятием для сетей Петри. Однако никакой пользы извлечь из понятия двойственной сети Петри в исследовании этих сетей не представляется возможным. Это объясняется в основном трудностью определения сети, двойственной к маркированной сети Петри. Маркированные сети Петри мы обсудим позднее.

Упражнения 1. Постройте графы сетей Петри, двойственные к сетям Петри, показанным на рис. 2.5 и 2.6. 2. Постройте граф сети Петри для следующей структуры сети Петри: Р = (Рг. Рз, Ръ Рз), Т = (Фь йь гз, 1с), 7(1,) = ( ), О(1,) = «Р,), 7«тт) =(Рг). О«1з) = (Рз). Фз) = «рз Рз) О(1з) = (Рзз Рз) 7«1з) =( ). О(1з) = «Рз) ° » (» 5) (Рз) ° О(1з) — (Рз) ° 3. Изобразите граф сети Петри следующей структуры: Р = (р, р ), Т = (й, йь 1з), 7«1,) = «Рз), О(1з) = «Р, ° Р,), 1«1,) =- «Р,), О(1.) = (Р.), 7(1з) = «рз) О«1з) = ( )- 4. Покажите, что двойственная к двойственной сети Петри С есть сама сеть С. $. Определите класс сетей Петри, которые совпадают с двойственными к се- бе. Можете ли вы дать простую характеризацию этого класса сетей Петри3 а.

Если сеть, двойственная к сети Петри С = (Р, Т, У, О), определена как С = (Т, Р, 7, О), входные и выходные функции должны быть расширены дли отображения и Р, и Т. Почемуу Если С =- «Р, Т,(, О) имеет нерасширен- ные входные и выходные функции, дайте определение С = (Т, Р, 7', О') с нерасширеннымн входными и выходными функциямн. 7. Найдите структуру сети Петри, соответствующую графу сети Петри на Рис. 2.8.

Определите структуру сети Петри для графа на рис. 2.9. 8. ГРафы сети Петри являются мультиграфами. так как позиция может быть кратным входом илн выходом перехода, В графе зто показывается несколь- кими дугами между позицией и переходом. В то время как такой способ удов- летворигелен для дуг с малой кратностью (не более трек), он неудобен для дуг очень большой кратности. Таким образом, в качестве альтернативного пред- ставления структур с большой кратностью используется пучок дуг. Пучок— зто специальная дуга, которая рисуется жирной линией и помечается крат- ностью Рис 2.10 иллюстрирует переход с входной кратностью 7 и выходной кратно- стью 11. Нарисуйте граф сети Петри для следующей структуры: «Рт.

Рз, Рз, Р4), Т = «1ь 1з, 1з» 1с), Фз) =( )з О(1з) = (Рз» Рз» Рз» Рг» Рз)» 7(1) = «рз). ОЩ=(р~.р~.р~,р р,р ° р), »(1з) = (Рь Рг» Рг» Р». Р». Р»]» О(1з) = (Рз Рз Рз. Рз ° Ра. Р4)» Ж) =(Рз. Рз. Р., Р.). О«1з) =( ). Глава 2 >3 г>х Р> >4 Рнс. 2.9. Граф сети Петри. Рис. 2.8. Граф сети Петри. Рнс.

2.10. Пучок дуг. Для графов с большой кратностью используется пучок дуг, помеченный числом кратности, а не изображение всех кратных дуг- 9. Инверсная сеть Петри — С для сети Петри С = (Р, Т; 1, 0) определяется перестановкой входной н выходной функций — С =' (Р, Т, О, I). Как зто повлияет на граф сети Петри? В чем отличие от двойственной сети Петри? Окажет ли влияние расширение входной н выходной функций? Изобразите инверсную сеть Петри для сети Петри, приведенной иа рнс. 2.7. 2.3. Маркировка сетей Петри Маркировка у, есть присвоение фишек позициям сети Петри. Фишка — это примитивное понятие сетей Петри (подобно позициям и переходам).

Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Петри могут изменяться Фишки используются для определения выполнения сети Петри. Определение 2.5. Маркировка р сети Петри С = (Р, Т, 1, 0) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел >т'. р,: Р-+-й~. Маркировка р может быть также определена как и-вектор р = = (р,„рх, ..., р„), где п = 1Р! и каждое р> е >ч', 1 = 1, ..., и. Век- Ослоанме онреоелекии Рис.

2.11. Маркированная сеть Петри. Структура сети Петри совпадает со структурами на рис. 2.1 и 2.4. Маркировка — (1, 2, О, О, !). Рис. 2.12. Маркированная сеть Петри. Структура аналогачна структуре, нвображенной на рнс. 2.11, но маркировка отличается. тор )ь определяет для каждой позиции р; сети Петри количество фишек в этой позиции. Количество фишек в позиции р, есть рь 4 = 1, ..., и. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением 1чр1) = 1ье Обозначение ее в виде функции является несколько более общим и поэтому употребляется гораздо чаще.

Маркированная сеть Петри М = (С, р) есть совокупность структуры сети Петри С = 1Р, Т, 1, 0) и маркировки 1ь и может быть записана в ниде М = Р, Т ~. О. Р) На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис. 2.11 и 2.12 приведены примеры графического представления маркированной сети Петри. Так как количество фишек которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри сущест- Глаза 2 24 г2 Ра Рис. 2.13. Граф сети Петри с очень большой маркир овкой (47„13, 7, 42). вует бесконечно много маркировок. Множество всех маркировок сети Петри, обладзющей и позициями, есть множество всех п-векторов, 1т'". Это множество, хотя и бесконечно, является счетным.

Упражнения 1. Для маркированной сети Петри (рис. 2.12) представьте маркировку как функцию и как вектор. 2. Для структуры сети Петри (рис. 2.2) изобразите граф сети Петри и укажите на графе маркировку р = (1, О, 1, 1, О, 0). 3, Количества фишек в сети Петри редко превышает 5 или 6. В атом случае их рисуют. Однако, когда маркировка имеет 10, 20 или сотни фишек, приписанных позиции, в кружках удобнее не рисовать фишки, а указывать их общее количество. как на рис.

2.!3. Используя зтот способ, изобразите маркировку р = (137, 22, 2, О, 14) для сети Петри на рнс. 2.12. ЗА. Правика выпеянения сетей Патри Выполнением сети Петри управляют количество и распределение фишек в сети. Фишки находятся в кружках и управляют выполнением переходов сети. Сеть Петри выполняется посредством запусков переходов. Переход запускается удалением фишек нз его входных позиций и образованием новых фишек, помещаемых в его выходные позиции. Переход может запускаться только в том случае, когда он разрешен.

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

Например, если позиции рг н рв служат входами для перехода 1», тогда г, разрешен, если р, н ра имеют хотя бы по одной фишке. Для перехода 7т с входным комплектом (р», р», р») позиция р» должна обладать по крайней мере тремя фишками, для того чтобы Ь, был разрешен. Основные определения Определение 2.6.

Переход 1; Е Т в маркированной сети Петри С = (Р, Т, 1, О) с маркировкой 14 разрешен, если для всех Р; ~ Р Р (М ~ +1 (Р * 1 М. Переход запуслаался удалением всех разрешающих фишек из его входных позиций н последующим помещением в каждую из его выходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг. Переход 1, с 1(1,) = (ре) и О(1 ) = (Р„Рсл) разрешен всякий раз, когда в Ре будет хотя бы одна фишка. Переход 14 запускается удалением одной фишки из позиции ре и помещением одной фишки в позицию рт н в рм (его выходы). Дополнительные фишки в позиции Рз не влияют на запуск (хотя они могут разрешать дополнительные запуски 14). Переход 1,, в котором 7[14) = (Раи рее) и О(14) = (рея, Рмн Рея), запускается удалением одной фишки из рм и одной фишки из Рея, при этом оДна фишка помешаетсЯ в Ре, н Две в — Рея (так как Рея имеет кРатность, равную двум).