Сайт в помощь студенту Грамоте учиться – всегда пригодится


Скачать реферат полностью

6. Сети Петри
6.1. Основные определения
Сети Петри (СП) и их многочисленные модификации являются одним из классов моделей, неоспоримым достоинством которых является возможность адекватного представления не только структуры сложных организационно-технологических систем и комплексов, но также и логико-временных особенностей процессов их функционирования. Сети Петри представляют собой математическую модель для представления структуры и анализа динамики функционирования систем в терминах «условие-событие». Это модель может быть успешно использована для описания так называемых динамических дискретных систем различных классов, таких как: вычислительные процессы и программы, технологические процессы, информационные, экономические, биологические, социальные и технические системы.
Модели сетей Петри позволяют исследовать работоспособность моделируемых систем, оптимальность их структуры, эффективность процесса их функционирования, а также возможность достижения в процессе функционирования определенных состояний. Сети Петри и их обобщения являются удобным и мощным средством моделирования асинхронных, параллельных, распределенных и недетерминированных процессов, позволяют наглядно представить динамику функционирования систем и составляющих их элементов. Свойство иерархического вложения сетей Петри позволяют рассматривать модели различной степени детализации, обеспечивая тем самым необходимую композицию сложных систем и процессов.
Структура сети Петри. Сеть Петри С является четверкой: С = (Р, Т, I, О). Р— {p1, р2, ..., рn} — конечное множество позиций, n?  0. Т = (t 1, t 2, ..., t m} — конечное множество переходов, m ? 0. Множество позиций и множество переходов не пересекаются, Р ? Т  = O. I : T > Р? является входной функцией — отображением из переходов в комплекты позиций.
О: Т > Р?есть выходная функция — отображение из переходов в комплекты позиций.
Позиция рi  является входной позицией перехода tjв том случае, если piI I(tj); piявляется выходной позицией, если рiI O(tj). Входы и выходы переходов представляют собой комплекты позиций. Комплект является обобщением множества, в которое включены многократно повторяющиеся элементы — тиражированные элементы. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции быть кратным входом либо кратным выходом перехода. Кратность входной позиции piдля перехода tjесть число появлений позиции во входном комплекте перехода, #(pi, I(tj)). Аналогично кратность выходной позиции piдля перехода tjесть число появлений позиции в выходном комплекте перехода, #(pi, О(tj)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.
Существует и такой вариант определения входной и выходной функций переходов. I – входная функция переходов, которая определяется как отображение I: PTN0; O – выходная функция переходов, которое определяется как отображение O: TPN0, где N0 – множество натуральных чисел и ноль.
Пример. C = (P, T, I, O), P = {p1, p2, p3, p4, p5}, T = {t1, t2, t3, t4},

I ( t1) = {p1},                                  O(t1) = {p2, p3, p5},
I ( t2) = {p2, p3, p5},                       O(t2) = {p5},
I( t3) = {p3},                                   O(t 3) = {p4},
I( t4) = {p4},                                   O(t 4) = {p2, p3},

Графическое представление сети Петри. Структура сети Петри представляет собой совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя типами узлов. Кружок ? является позицией, а планка | - переходом.
Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие — от переходов к позициям. Дуга, направленная от позиции piк переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.
Граф G сети Петри есть двудольный ориентированный мультиграф, G = (V, А), где V= {v1, v2, ..., vs} — множество вершин, а А = {a1, a2, ..., ar} — комплект направленных дуг, аi = (vj, vk), где vj, vkI V. Множество Vможет быть разбито на два непересекающихся подмножества Р и Т, таких, что V = Р U Т, Р I Т = ? , и для любой направленной дуги aiI А, если ai= (vj, vk), тогда либо vjI Р и vkI T, либо vjI Т, а vkI P.


Рис. 6.1. Граф сети Петри
Матричное представление сети Петри. Альтернативным по отношению к определению сети Петри в виде (Р, Т, I, О) является определение двух матриц D-и D+, представляющих входную и выходную функции. Каждая матрица имеет mстрок (по одной на переход) и nстолбцов (по одному на позицию). Определим D- [j, i]= # (pi, I(tj)), a D+ [j, i] = #(pi, 0 (tj)). D -определяет входы в переходы, D+— выходы. Матричная форма определения сети Петри (Р, Т, D-, D+) эквивалентна стандартной форме, но позволяет дать определения в терминах векторов и матриц.
Маркировка сетей Петри. Маркировка ? есть присвоение фишек позициям сети Петри. Фишка — это примитивное понятие сетей Петри (подобно позициям и переходам). Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Петри могут изменяться. Фишки используются для определения выполнения сети Петри.
Маркировка ? сети Петри С = (Р, Т, I, О) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N  ? : Р > N. Маркировка ? может быть также определена как вектор ? = (? 1, ?2, … , ? n), где n = |Р| и каждое ?iI N, i = 1, ..... n. Вектор ? определяет для каждой позиции piсети Петри количество фишек в этой позиции. Количество фишек в позиции piесть ?i, i = 1, ..., n.