48. Сети Петри. Ограниченность, безопасность, сохраняемость, достижимость, живость. Моделирование на сетях Петри.

Основные свойства сети Петри

• Ограниченность — число меток в любой позиции сети не может превысить некоторого значения K.

• Безопасность — частный случай ограниченности, K=1.

• Сохраняемость — постоянство загрузки ресурсов, постоянна. Где Ni — число маркеров в i-той позиции, Ai — весовой коэффициент.

• Достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое.

• Живость — возможностью срабатывания любого перехода при функционировании моделируемого объекта.

• Эквивалентность и включение

Под ограниченностью понимают свойство сети не допускать превышения количества фишек в конкретной или произвольной позиции некоторого фиксированного числа.

Если ни в одной позиции сети при любой последовательности срабатываний переходов количество фишек не превышает некоторого K, то такую сеть называют K-ограниченной.

Примеры ограниченной и неограниченной сетей

Место р называется безопасным, если для любой разметки сети M количество фишек M(p) £ 1; соответственно, сеть безопасна, если все ее места безопасны. Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1.

Сохраняемость – свойство сети, характеризующее невозможность возникновения или уничтожения ресурсов в моделируемом объекте.

Активность

Переход сети Петри называют тупиковым, если в процессе функционирования сеть может оказаться в состоянии, в котором этот переход заблокирован. Нетупиковый переход называют активным.

• активность уровня 0, если он никогда не может быть активирован (пассивный переход);

• активность уровня 1, если существует состояние (достижимое из начального), в котором он активирован;

• активность уровня 2, если для всякого целого n существует последовательность срабатывания переходов, в которой данный переход присутствует по крайней мере n раз;

• активность уровня 3, если существует бесконечная последовательность срабатывания переходов, в которой данный переход присутствует неограниченно часто;

• активность уровня 4, если для любого достижимого состояния существует последовательность срабатываний, приводящая в такое состояние, в котором этот переход активирован (активный переход).

Достижимость и покрываемость

Состояние S достижимо в сети Петри, если существует цепочка срабатываний переходов, ведущая из начального состояния в S. Состояние S'=(P1'...Pn') покрывает состояние S"=(P1"...Pn"), если для каждого i=1, ...,n имеет место Pi' >= Pi", т.е. имеет место S' >= S".

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

Эквивалентность и включение

Сети Петри эквивалентны, если они имеют одинаковое поведение, определяемое множеством достижимых состояний или множеством реализуемых последовательностей переходов.

Сеть СП1, включается в сеть СП2, если поведение СП1 является подмножеством поведения СП2.

Два метода анализа СП

• построение покрывающего дерева,

• решением матричных уравнений.

Анализ сети Петри на основе ее дерева достижимости

Алгоритм построения дерева достижимости:

Пусть So= (P1,..,Pn) граничная вершина дерева (состояние сети Петри), не являющаяся тупиковой или дублирующей. Тогда для каждого перехода tj, активированного в S, создается новая вершина S' =(Pi',..,Pn'), в которой состояние позиций Рi', i=1,...,n, определяется следующим образом:

• ЕСЛИ Pi=So, ТО Р i ' = ω

• ЕСЛИ на пути от корневой вершины к S существует вершина S"=(Р1",..,Рn"), такая что S'>S" (Рi'>Рi"), ТО Рi'= ω

• В противном случае значение Рi' определяется на основе срабатывания перехода tj из состояния S

Вершина S переопределяется как внутренняя, вершина S' становится граничной. Алгоритм заканчивает работу, когда все вершины дерева тупиковые, дублирующие или внутренние.

Проверка свойств сети Петри по дереву достижимости

• Сеть Петри является ограниченной тогда и только тогда, когда в её дереве достижимости отсутствует символ ω. Если сеть Петри ограничена, то по её дереву можно определить емкость каждой позиции как максимальное значение соответствующей компоненты состояния сети. Даже если сеть Петри не ограничена, то емкость можно определить для позиций, в которых отсутствует ω.

• Проверка сети Петри на тупиковые состояния по дереву достижимости не требует пояснений (неконечные состояния не должны быть тупиковыми).

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

Примеры синтеза сетевых моделей: процесс возникновения и развития инсульта (апоплексии)

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

При атеросклерозе это будут следующие события:

а.1 прорыв стенки сосуда;

а.2 развитие очага кровоизлияния;

а.3 поражение центра головного мозга;

а.4 апоплексический удар.

При тромбозе это будут события:

б.1 закупорка сосуда головного мозга;

б.2 развитие очага некроза;

б.3 поражение центра головного мозга;

б.4 апоплексический удар.

Виды сетей Петри

• Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).

• Стохастическая сеть Петри — задержки являются случайными величинами.

• Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.

• Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.

• Ингибиторная сети Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой находится метка.

Три основных направления исследований в теории сетей Петри

• общая теория сетей, которая выделяет и формализует базовые понятия, изучает связь между различными классами сетей и классами реальных систем, обосновывает метод исследования сетей, устанавливает связь аппарата сетей с другими разделами математики;

• специальная теория сетей, которая изучает собственно сети Петри как математические объекты, их свойства, правила конструирования и преобразования

• приложения сетей к конкретным задачам анализа и синтеза дискретных систем

Преимущества использования сетей Петри в моделировании и анализе бизнес-систем

• большие  выразительные  способности в представлении параллельных асинхронных систем; 

• способность представления локального управления,  параллельных, конфликтных, недетерминированных и асинхронных событий;

• графическое представление сети;

• понятность модели и легкость ее изучения;

• возможность  иерархического  моделирования  на   их основе; 

• возможность описания системы на различных уровнях  абстракции; 

• возможность представления системной иерархии;

• возможность машинной поддержки в проектировании.

49. Потоки в сетях. Разделяющие множества. Сеть. Поток в сети. Классификация вершин по воздействию на поток. Величина потока. Разрез и поток через разрез. Теорема о максимальном потоке. Метод увеличивающих цепей. Алгоритм построения максимального потока.

Пусть G = (V, E) — связный граф и F  E — подмножество множества его ребер. При этом F называется разделяющим множеством тогда и только тогда, когда подграф G = (V, E – F) несвязен. Разделяющие множества всегда существуют (если граф имеет по меньшей мере две вершины), так как всегда можно положить F = E. Очевидно, что граф может быть разбит разделяющим множеством на более чем две компоненты.

Если задан связный граф G = (V, E) и множество его вершин разбито на два непустых подмножества W и множество ребер, соединяющих W с W, называется разрезом. Для любого множества W это множество ребер будет непусто в силу связности графа G, и следовательно, разрез определен. Для любого заданного графа совокупность разрезов, определенных различными множествами W, образует подкласс класса всех разделяющих множеств и, более того, любое разделяющее множество содержит, по крайней мере, один разрез в качестве своего подмножества.

Сеть - пара S = G, с, где G = V, E — произвольный ориентированный граф, а с: E  R — функция, которая каждой дуге u, v ставит в соответствие неотрицательное вещественное число с(и, v), называемое пропускной способностью этой дуги. Множества V и Е называются соответственно множеством вершин и множеством дуг сети S.

Под разрезом Р(А) сети S, соответствующим подмножеству А  V (А  , А  V), мы понимаем множество дуг u, v  Е, таких что u  А и v  V\A, т. е.

P(A) = E  (A  (V\A)).

Для произвольного потока f в сети S поток через разрез Р(А): .

Определим пропускную способность разреза Р(А) следующим образом: .

Под минимальным разрезом, разделяющим s и t, мы будем понимать произвольный разрез Р(А), s  А, t  V\A с минимальной пропускной способностью.

Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения.

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

Будем говорить, что дуга е сети S является допустимой дугой из и в v относительно потока f, если

е = <u, v> и f(e) < c(e) (1) или

е = < v, u > и f(e) > 0. (2)

В зависимости от того, какое из приведенных условий имеет место, первое или второе, будем говорить соответственно о согласованной или несогласованной допустимой дуге из и в v. Увеличивающей цепью (длины l) для данного потока f из s в t называется произвольная знакопеременная последовательность (попарно различных) вершин и дуг

v₀, e₁, v₁, e₂,v₂, …, v_l–1, e_l, v_l, (3)

такая что v₀ = s, v_l = t, и для каждого i  l дуга e_i допустима из v_i–1 в v_i относительно потока f.