Матричный анализ

Второй подход к анализу сетей Петри основан на матричном представлении сетей Петри. Альтернативным по отношению к опре­делению сети Петри в виде (Р, Т, I, О) является определение двух матриц D^- и D⁺, представляющих входную и выходную функции. Каждая матрица имеет m строк (по одной на пе­реход) и n столбцов (по одному на позицию). Определим D^-[j, i] = #(p_i, I(t_j)), a D⁺ [j, i] = #(p_i, O(t_j)). D^- определяет входы в переходы, D⁺ - выходы.

Матричная форма определения сети Петри (Р, Т, D^-, D⁺) экви­валентна стандартной форме, используемой нами, но позволяет дать определения в терминах векторов и матриц. Пусть e[j] - m-вектор, содержащий нули везде, за исключением j-й компоненты, равной единице. Переход t_j представляется m-вектором-строкой е[j].

Теперь переход t_j в маркировке µ разрешен, если µ > e[j] • D^-, а результат запуска перехода t_j в маркировке µ, записывается как:

δ(t_j) = µ - e[j] • D^- + e[j] • D⁺ = µ + e[j] • D

где D = D⁺ - D^- - составная матрица изменений.

Тогда для последовательности запуска переходов σ = t_j1, t_j2 , …, t_jk имеем:

δ(σ) = µ + e[j₁] • D + e[j₂] • D + … + e[j_k] • D =

= µ + (e[j₁] + e[j₂] + … + e[j_k])D • = µ + f(σ) • D

Вектор f(σ) = e[j₁] + e[j₂] +... + e[j_k] называется вектором за­пусков последовательности σ = t_j1, t_j2 , …, t_jk, f(σ)_jp - это число запусков перехода t_p в последовательности t_j1, t_j2 , …, t_jk. Вектор запусков f(σ), следовательно, является вектором с неотри­цательными целыми компонентами. (Вектор f(σ) - это отображение Париха последовательности σ = t_j1, t_j2 , …, t_jk).

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

Пусть w = (w₁,w₂, …, w_n) - вектор-столбец. Тог­да, если µ - начальная маркировка, а µ' - произвольная дости­жимая маркировка, т.е. µ' принадлежит R(C,µ), необходимо, чтобы µ • w = µ' • w. Теперь, поскольку µ' достижима, существует последовательность запусков переходов σ = t_j1, t_j2 , …, t_jk, которая переводит сеть из µ в µ'. Поэтому

µ' = µ + f(σ) • D

Следовательно,

µ • w = µ' • w = (µ + f(σ) • D) • w = µ • w + f(σ) • D • w, поэтому f(σ) • D • w = 0.

Поскольку это должно быть верно для всех f(σ), имеем D • w = 0.

Таким образом, сеть Петри является сохраняющей тогда и только тогда, когда существует такой положительный вектор w, что D • w = 0.

Это обеспечивает простой алгоритм проверки сохране­ния, а также позволяет получать вектор взвешивания w.

Развитая матричная теория сетей Петри является инструментом для решения проблемы достижимости. Предположим, что марки­ровка µ' достижима из маркировки µ. Тогда существует последо­вательность (возможно, пустая) запусков переходов σ, которая приводит из µ к µ'. Это означает, что f(σ) является неотрицатель­ным целым решением следующего матричного уравнения для х:

µ' = µ + x • D

Следовательно, если µ' достижима из µ, тогда данное уравнение имеет решение в неотрицательных целых; если данное уравнение не имеет решения, тогда µ' недостижима из µ.

Рассмотрим, например, маркированную сеть Петри, изображенную на рис.1:

Рис. 1. Сеть Петри, иллюстрирующая метод анализа, основанный на мат­ричных уравнениях

Матрицы D^- и D⁺ имеют вид:

t₁ t₂ t₃ t₁ t₂ t₃

p₁ 1 0 0 p₁ 1 0 0

D^- = p₂ 1 0 0 D⁺ = p₂ 0 2 0

p₃ 1 0 1 p₃ 0 1 0

p₄ 0 1 0 p₄ 0 0 1

а матрица D:

В начальной маркировке µ = (1, 0, 1, 0) переход t₃ разрешен и приводит к маркировке µ' = (1, 0, 0,1).

µ' = µ + e[3] • D = (1, 0, 1, 0) + (0, 0, 1) • D =

= (1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).

Последовательность σ = t₃, t₂ , t₃, t₂ , t₁ представляется вектором запусков f(σ) = (1, 2, 2) и получает маркировку µ':

µ' = (1, 0, 1, 0) + (1, 2, 2) • D = (1, 0, 1, 0) + (0, 3, -1, 0) = (1, 3, 0, 0)

Для определения того, является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1,0, 1, 0), имеем уравнение:

(1, 8, 0, 1) = (1, 0, 1,0)+ x• D

которое имеет решение х = (0, 4, 5). Это соответствует последова­тельности σ = t₃, t₂ , t₃, t₂ , t₃,, t₂ , t₃ , t₂ , t₃

Далее мы можем показать, что маркировка (1, 7, 0, 1) недости­жима из маркировки (1, 0, 1, 0), поскольку матричное уравнение

(1, 7,0, 1)=(1, 0, 1, 0) + x• D

не имеет решения.

Матричный подход к анализу сетей Петри очень перспективен, но имеет и некоторые трудности. Заметим прежде всего, что мат­рица D сама по себе не полностью отражает структуру сети Петри. Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц D⁺ и D^-, но затем взаимно уничтожаются в матрице D = D⁺ - D^-. Это отражено в предыдущем примере позицией p₄, и переходом t₃.

Другая проблема — это отсутствие информации о последова­тельности в векторе запуска. Рассмотрим сеть Петри на рис. 2. Предположим, мы хотим определить, является ли маркировка (0, 0, 0, 0, 1) достижимой из (1, 0, 0, 0, 0). Тогда имеем уравнение

(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + x• D

Рис. 2. Другая сеть Петри, служащая для иллюстрации матричного ана­лиза

Это уравнение не имеет однозначного решения, но сводится к мно­жеству решений {a\f(o) = (1, х₂, х₆— 1, 2х₆, х_е— 1, х₆)}. Оно определяет взаимосвязь между запусками переходов. Если поло­жим х₆ = 1 и х₂ = 1, то /(о) = (1, 1, 0, 2, 0, 1), но этому вектору запуска соответствуют как последовательность 44444. ^{так и п0-}следовательность 44444- Следовательно, хотя и известно число запусков переходов, порядок их запуска неизвестен.

Еще одна трудность заключается в том, что решение уравнения является необходимым для достижимости, но недостаточным. Рассмотрим простую сеть Петри, приведенную на рис. 3. Если мы хотим определить, является ли (0, 0, 0, 1) достижимым из (1, 0, 0, 0), необходимо решить уравнение

Рис. 3. Сеть Петри, показывающая, что решение матричного уравнения— необходимое, но недостаточное условие для решения задачи достижимости

Это уравнение имеет решение /(а) = (1, 1), соответствующее двум последовательностям: tit₂ и /₃/_t. Но ни одна из этих двух последо­вательностей переходов невозможна, поскольку в (1,0, 0, 0) ни t_it ни 4 не разрешены. Таким образом, решения уравнения не­достаточно для доказательства достижимости.

Контрольные вопросы и задания

1. Постройте граф сети Петри для следующей сети Петри:

P={p₁,p₂,p₃,p₄}, T={t₁,t₂,t₃,t₄,t₅},

I(t₁)={}, O(t₁)={p₁},

I(t₂)={p₁}, O(t₂)={p₂},

I(t₃)={p₂,p₂,p₄}, O(t₃)={p₁,p₃},

I(t₄)={}, O(t₄)={p₃},

I(t₅)={p₃}, O(t₅)={p₄,p₄}.

2. Постройте граф сети Петри для следующей сети Петри:

P={p₁,p₂,p₃,p₄}, T={t₁,t₂,t₃,t₄},

I(t₁)={}, O(t₁)={p₁,p₁,p₁,p₁,p₂},

I(t₂)={p₂}, O(t₂)={ p₁,p₁ p₁,p₁,p₁,p₁,p₃},

I(t₃)={p₁,p₁,p₁,p₁,p₁,p₁}, O(t₃)={ p₂,p₂ p₂,p₂ p₄,p₄},

I(t₄)={ p₂,p₃ p₄,p₄}, O(t₄)={p₃}.

3. Для сети Петри из упр.1 для маркировки m=(5,4,0,0) указать разрешенные переходы.

4. Для сети Петри из упр.2 для маркировки m=(7,12,2,1) указать разрешенные переходы.

5. Покажите, что ÈR(C,m)=Nⁿ, где mÎNⁿ.

6. Докажите, что если m‘Î R(C,m), то R(C,m‘)Í R(C,m).

7. Докажите, что m‘Î R(C,m) тогда и только тогда, когда R(C,m‘)Í R(C,m).

8. Постройте множество достижимости для сети Петри из упр.1.

9. Постройте множество достижимости для сети Петри из упр.2.

10. Сети Петри со своими фишками и правилами запусков во многом напоминают игры, имеющие игровое поле: шашки, нарды, ним, го и др. Можно придумать игру для одного - четырех человек, состоящую из игрового поля (в качестве поля используется сеть Петри) и набора фишек. Фишки распределены по позициям сети Петри, и игроки по очереди выбирают разрешенные переходы и запускают их. Определите правила игры, предусматривающие следующее:

a Как определено начальное расположение фишек? (Например, каждый игрок начинает игру, имея одну фишку в домике или каждый игрок получает n фишек на всем поле по желанию и т.д.).

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

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

d Не стоит ли присвоить очки различным переходам? (Тогда очки игрока определяются суммой переходов, запущенных им).

На основе этого опишите игру, приведите пример игры.

11. Разработайте программу, которая реализует игру из упр.10, где в качестве вашего противника выступает компьютер для заданной сети Петри.

12. Постройте систему моделирования для выполнения сети Петри. Запуск разрешенных переходов задается пользователем системы моделирования.

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

14.Построить сеть Петри, представляющую конечный автомат, вычисляющий дополнение до двух двоичного числа.

15.Построить сеть Петри, представляющую конечный автомат для определения четности входного двоичного числа.

16.Построить сеть Петри, представляющую конечный автомат, который определяет триггер со счетным входом.

17.Построить сеть Петри, представляющую конечный автомат, который определяет триггер с раздельными входами.

18.Разработать алгоритм моделирования блок-схем сетью Петри.

19.PERT-диаграмма является графическим представлением взаимосвязей между различными этапами, составляющими проект. Проект представляет собой совокупность большого числа работ, при этом работы должны завершиться прежде, чем начнут выполняться другие. Кроме того, на выполнение каждой работы требуется определенное количество времени. Работы графически представляются вершинами, а дуги используются для отображения причинно-следственных связей между ними. PETR - диаграмма есть направленный граф со взвешенными дугами. Задача состоит в том, чтобы определить минимальное время выполнения проекта. Разработать алгоритм моделирования PERT-диаграмм с помощью сетей Петри.

20.Разработайте модель, основанную на сетях Петри, для моделирования химических реакций.

21.Рассмотрите построение не дерева, а графа достижимости. Если вершина x порождает последующую вершину z с m[z]=m[y] для некоторой неграничной вершины y, вводится помеченная соответствующим образом дуга от x к y. Опишите алгоритм построения графа достижимости.

22.Покажите, что алгоритм построения графа достижимости сходится, и исследуйте его свойства, сравнивая его с алгоритмом построения дерева достижимости.

23.Дерево достижимости нельзя использовать для решения проблемы достижимости, т.к. теряется информация в связи с введением понятия символа w. Он вводится, когда приходим к маркировке m‘ и на пути от корня к m‘ имеется такая маркировка m, что m‘>m. В этом случае можно получить все маркировки вида m+n(m‘-m). Исследуйте возможность использования выражения a+bn_i вместо w, для того чтобы представить значения компонент. Если вы сможете определить дерево достижимости, в котором все векторы маркировок представляются выражениями, тогда решение задачи достижимости определяется просто решением системы уравнений.

24.Обобщите определение сохранения, разрешая отрицательные веса.Что можно было бы считать разумной интерпретацией отрицательного веса? Является ли разрешимой задача определения сохранения сети Петри, если разрешены отрицательные веса?

25.Разработайте с помощью матричного подхода к анализу алгоритм определения ограниченности сети Петри.

26.Разработайте алгоритм решения задачи равенства двух сетей Петри. Сеть Петри C₁=(P₁,T₁,I₁,O₁) с маркировкой m₁ равна сети Петри C₂=(P₂,T₂,I₂,O₂) с маркировкой m₂ , если R(C₁,m₁)= R(C₂,m₂).

27.Разработайте алгоритм решения задачи подмножества двух сетей Петри. Сеть Петри C₁=(P₂,T₂,I₂,O₂) с маркировкой m₂ есть подмножество сети Петри C₁=(P₁,T₁,I₁,O₁) с маркировкой m₁ , если R(C₁,m₁)Í R(C₂,m₂).

28.Разработайте алгоритм решения задачи достижимости. В сети Петри C=(P,T,I,O) с маркировкой m маркировка m‘ достижима из m, если m‘ÎR(C,m).

29.Разработайте алгоритм задачи достижимости подмаркировки. Для подмножества P’ Í P и маркировки m‘ существует ли m‘’ÎR(C,m), такая, что m‘’(p_i)=m‘(p_i) для всех p_iÎP’?.

30.Разработайте алгоритм задачи достижимости нуля. Выполняется ли m‘ÎR(C,m), где m‘(p_i)=0 для всех p_iÎP?

31.Разработайте алгоритм задачи достижимости нуля в одной позиции. Для данной позиции p_iÎP существует ли m‘ÎR(C,m) с m‘(p_i)=0?

32.Разработайте алгоритм решения задачи активности сети Петри. Активны ли все переходы t_jÎT?

33.Разработайте алгоритм решения задачи активности одного перехода. Активен ли данный переход t_jÎT?

34.Сеть Петри называется обратимой, если для каждого перехода t_jÎT найдется переход t_kÎT, такой, что

#(p_i,I(t_j))=#(p_i,O(t_k)), #(p_i,O(t_j))=#(p_i,I(t_k)),

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

35. Разработайте алгоритм решения задачи равенства для обратимых сетей Петри.

36.Задача о курильщиках. Каждый из трех курильщиков непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы табак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой - спички, третий - табак. Агент обладает бесконечными запасами бумаги, спичек и табака. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий ингредиент, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех ингредиентов, и цикл повторяется. Предложите активную сеть Петри, которая моделирует задачу о курильщиках.

37. Автоматная сеть Петри - это сеть Петри, в которой каждый переход может иметь точно один выход и один вход,т.е. для всех t_jÎT ½I(t_j)½=1 и ½O(t_j)½=1. Разработайте алгоритм построения конечного автомата, который эквивалентен заданной автоматной сети Петри.

38. Маркированный граф есть сеть Петри, в которой каждая позиция является входом для точно одного перехода и выходом точно одного перехода,т.е. для каждого перехода p_iÎP ½I(p_i)½=1 и ½O(p_i)½=1. Разработайте алгоритм решения задачи достижимости для маркированных графов.

39.Рассмотрите класс сетей Петри, которые являются и маркированными графами, и автоматными сетями Петри.

40.Постройте сеть Петри, моделирующую системы, описанные в приложении 8. Опишите события, происходящие в системе, и условия, которые описывают систему. Постройте дерево достижимости построенной сети Петри. Опишите состояния, в которых может находиться система.