Сети Петри. Основные понятия
Формализм теории сетей Петри основан на понятии комплекта, явл. обобщенным понятием мн-ва, а комплект ,подобно мн-ву, явл. набором элементов, но в отличии от него допускает кратные вхождения эл-тов. В случае мн-ва эл-т может входить или не входить во мн-во, в случае комплекта – эл-т может входить в него целое неотриц. число раз . Взаимосвязь между эл-тами и мн-вом определяется ф-цией членства, принимающей значения 0 или 1.
Взаимосвязь между эл-тами и комплектом определяется ф-цией числа вхождений, обозначающейся #(x,B).
Из определения следует, что #(x,B)>=0, если х принадлежит В, то #(x,B)>0, если х не принадлежит В, то #(x,B)=0.
Комплект явл. по определению пустым, если для всякого x -> #(x,B)=0
Мощностью комплекта В наз |В| общее число вхождений эл-тов в комплект В, т.е.
|В|= СУММА по х #(x,B)
А наз подкомплектом В, если всякий эл-т А некот кол-во раз входит в В. Комплекты наз равными #(x,А)= #(x,B) для всех х. Из определения следует, что А=В тогда и только тогда, когда А явл подкомплектом В и В явл подкомплектом А. Из рав-ва А=В следует, что мощность комплектов А и В равны, а из того, что А подкомплект В – мощность А меньше или равна мощности В.
Комплект А строго включен в В, если А явл подкомплектом В, А неравно В, мощность А строго меньше В, но необязательно, что #(x,A) <#(x,B).
Сети Петри включают 4 комплекта: <P,T,I,O>, где Р={p1,p2,…pn}-мн-во позиций, n>=0; T={t1,t2,..tm}-мн-во переходов,I-входная ф-ция отображения переходов в комплекты позиций и позиций в комплекты переходов I: T->Pв степени бесконесности, P:->T в степени бесконечности; О-выходная ф-ция отображения переходов комплекта позиций и позиций в комплекты переходов O:T->Р в степени бесконечность, Р-> T в степени бесконечность.
|
|
|
Позиция Pi явл. входной для перехода Tj, если Pi принадлежит I(tj), и выходной, если Pi принадлежит О(tj).
Вход и выход перехода- это комплекты позиций. Кратность входной позиции Pi для перехода Tj – это число вхождений позиции во входной комплект, т.е. #(Pi, I(tj)); аналогично кратность выходной позиции Pi для перехода tj - #(Pi, O(tj)) – число вхождений позиций Pi в ф-ции выхода tj.
Граф явл двудольным тогда и только тогда, когда все его циклы имеют четкую длину, или же G(V1,V2) наз граф, мн-во вершин кот разбивается на два непересекающихся подмножества V1 и V2так, что каждое ребро в G соединяет две вершины из разных подмн-в.
Графическим представлением сети Петри C=(P,T,I,O) явл двудольный граф, мн-ва вершин кот образуют объединение Р и Т, а смежность вершин задается ф-цией I или О, причем позиции обозначаются кружками, а переходы- вертикальными палочками. Дуга соединяет позицию и переход, если позиция явл входной для перехода, и переход с позицией, если позиция чвл выходной для перехода.
|
|
|
Сеть Петри случае явл ориентированным двудольным мультиграфом.
32. Маркировка сети Петри, выполнение сети Петри.
Маркировка мю сети Петри C=(P,T,I,O)- это ф-ция, отображающая мн-во позиций Р в мн-ве неотриц целых N.
Маркировка присваивает каждой позиции некот, быть может, нулевое кол-во фишек. В графе фишки изображаются точками внутри позиций.
Сеть Петри с определенной маркировкой наз маркированной.
Маркировку мю можно определить как n-мерный вектор: мю=(мю1, мю2,..мюn), n=|P|; мю i принадлежит N, N- число фишек в позиции Pi, или как комплект, включающий мюi-раз в комплект Pi
Под выполнением сети Петри понимается последовательность запусков переходов, в рез-те кот удаляются фишки из входных и появляются в выходных позициях переходов.
Разрешенным наз переход, имеющий в каждой входной позиции число фишек неменее, чем число дуг, идущих из позиции в переход, т.е. такой переход tj, для кот справедливо мю (Pi)>= #(Pi,I(tj)), Pi принадлежит P
Запуск перехода удаляет все разрешающие фишки из входных позиций по одной на каждую дугу и помещает фишки в выходные позиции снова по одной на каждую дугу.
В общем случае запуск перехода заменяет маркировку мю сети Петри на новую маркировку мю со штрихом.
|
|
|
Запуск перехода Tj приведет к маркировке мю со штрихом, определяющейся как мю со штрихом (Pi)=мю (Pi)-#(Pi, I(tj))+#(Pi,O(tj)), либо мю со штрихом = мю-I(tj)+O(tj), если рассматривать мю, мю со штрихом, I(tj),O(tj)-как комплекты.
Состояние сети Петри определяется ее текущей маркировкой, запуск перехода вызывает смену состояния. На мн-ве все маркировок сеть Петри с n-позициями определяется ф-цией дельта. Ф-ция перехода дельта для сети Петри C=(P,T,I,O) с маркировкой определенной только для тех переходов tj принадлежащих T, для кот I(tj)<= мю, если рассматривать мю и I(tj) как комплекты. Если дельта (мю, Tj) определяется, то мю со шрихом = дельта (мю, tj)=мю-I(tj)+O(tj)
С выполнением сети Петри связаны 2 последовательности маркировки мю0, мю1 и мю2 и последовательность переходов tj0, tj1,tj2, они взаимосвязаны взаимоотношением дельта (мю k,tk)=мю k=1, k=0,1,2,…По данной последовательности переходов U(мю0) можно легко получить последовательность маркировок, но не всегда по данной послед-ти можно получить послед-ть переходов.
Можно говорить, что маркировка мю со штрихом непосредственно достижима из маркировки мю, если для некот перехода tj принадлежащего T ф-ция маркировки мю со шрихом =дельта(мю, tj).
|
|
|
Использование сети Петри для решения задач планировщика.
Последовательность модулей с входными и выходными моделями наз сценарием, реализующим данный проект.
Сценарий проекта можно представить в виде модельного графа:
G=<V,U>, где U-связи между моделями и модулями
V=V1объединенное V2 , причем V1 пересечающееся V2=0
V1={vi1,vi2…vin}мн-во модулей
V2={vj1,vj2…vjh}мн-во моделей
Причем вершина vi принадлежащая V1, соединенная дугой (vj,vi) с вершиной vi, кот принадлежит V1,если модуль vi, в качестве входной модели имеет модель, соответствующую вершине vj.
Вершина vj принадлежащая V2, соединенная дугой (vi,vj) с вершиной vj, кот принадлежит V2,если модуль vi, в качестве выходной модели имеет модель, соответствующую вершине vi.
Предполагается, что в качестве выходной модели каждый модуль имеет только одну модель.
Для создания интеллектуального планировщика может быть использован аппарат сети Петри.
Каждому сценарию проекта, представленному в виде двудольного графа (j=VU) можно поставить в соответствие след сеть Петри C=(P,T,I,O):
P=V2=<vj1,vj2..vjh>-мн-во позиций, т.е.каждой позиции соответ модель
T=V1=<vi1,vi2…vin>- мн-во переходов, т.е. каждому переходу соответ модуль
Позиция Рi, явл эл-том мн-ва V2, явл входной позицией перехода Tj, кот явл эл-том V1, т.е. Pi принадлежит I(tj)
Если дуга (Pi tj) принадлежит U, то Pi, принадлежащее V2, явл выходной позицией перехода tj,принадлежащее V1, т.е. Pi=O(tj)
В соответствии с сетью Петри системы, процесс проектирования можно представить выполнением сети Петри системой, начальная маркировка определяется тем мн-вом входных моделей, кот заданы для проектирования, и процесс проектирования заканчивается при наличии хотя бы одной фишки в позициях, кот соответствуют выходным моделям проекта.
Дата добавления: 2018-04-04; просмотров: 635; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!