Н.В. Золотова, Р.С. Исмагилов
8
Из сказанного следует, что любая маркировка, достижимая из
начальной маркировки, представляется в виде линейной комбинации
векторов –
a
i
(
k
)
+
b
i
(
k
)
с целыми неотрицательными коэффициентами.
Обратное утверждение может оказаться неверным (из-за неравенств
k
a
i
(
k
)
для всех
i
).
Итак, анализ сети Петри сводится к действиям над векторами.
Хотя указанные действия над векторами весьма просты, полное опи-
сание графа маркировок для произвольной сети Петри оказывается
сложной задачей, связанной с проблемами алгоритмической разре-
шимости (подробнее см. [5, 9]). Эти вопросы рассматривались во
многих работах; они продолжают интересовать исследователей.
В заключение этого раздела вернемся к задаче описания графа
маркировок для сети из рис. 3 с начальной маркировкой
= (1, 0, 0).
Эта задача была поставлена в конце разд. 4. Легко видеть, что пози-
циям
t
1
,
t
2
,
t
3
соответствуют векторы
a
1
=
(1, 0, 0),
a
2
=
(1, 0, 0),
a
3
=
=
(0, 1, 1)
и
b
1
=
(1, 1, 0),
b
2
=
(0, 1, 0),
b
3
=
(0, 0, 1)
соответственно.
Используя их и начальную маркировку
=
(1, 0, 0), находим даль-
нейшие маркировки по формуле (2). Изобразив полученные точки
геометрически и проведя необходимые ребра, получаем граф, изоб-
раженный на рис. 14.
6. Приложения сетей Петри.
Область применения сетей Петри
обширна; ограничимся одним примером. Пусть некоторое изделие
обрабатывается автоматами
M
1
, … (на некоторых этапах работы не-
сколько автоматов могут действовать совместно). Построим сеть
Петри, описывающую процесс. В качестве переходов выступают
действия: подать изделие на обработку; удалить готовое изделие из
системы; автоматам
M
i
1
,
M
i
2
, … начать обработку; автоматам
M
i
1
,
M
i
2
, … закончить обработку. В качестве позиций выступают состоя-
ния системы: изделие ждет начала обработки автоматами
M
i
1
,
M
i
2
, …;
готовое изделие ждет отправления на выход; идет работа автоматов
M
i
1
,
M
i
2
, …; автомат
M
i
свободен. Наконец, ребра описывают после-
довательность действий. Вот простой пример.
Пример 3.
Изделие обрабатывается сначала автоматом
M
1
, затем —
автоматом
M
2
; готовое изделие удаляется из системы. Опишем позиции
и переходы.
Позиции (состояния):
а) изделие ждет обработки автоматом
M
1
;
б)
M
1
свободен;
в)
M
1
работает над изделием;
г) изделие, уже обработанное автоматом
M
1
, ждет обработки ав-
томатом
M
2
;
д)
M
2
свободен;
e)
M
2
работает над изделием;
ж) готовое изделие ждет отправления на выход.
