Моделирование дискретных технологических процессов. Сети Петри.

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

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

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

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

Зарождение теории сетей Петри

Сети Петри разрабатывались специально для моделирования тех систем, которые содержат взаимодействующие параллельные компоненты. Впервые сети Петри предложил Карл Адам Петри. В своей докторской диссертации «Kommunikation mit Automaten» («Связь автоматов») Петри сформулировал основные понятия теории связи асинхронных компонент вычислительной системы. В частности, он подробно рассмотрел описание причинных связей между событиями. Его диссертация посвящена главным образом теоретической разработке основных понятий, с которых начали развитие сети Петри.

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

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

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

Структура сети Петри

Сеть Петри состоит из четырех элементов: множество позиций Р, множество переходов Т, входная функция I и выходная функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j), называемых входными позициями перехода. Выходная функция О отображает переход t_j в множество позиций O(t_j), называемых выходными позициями перехода.

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

Определение 1. Сеть Петри С является четверкой, С= (Р, Т, I, О). Р= {р₁, р₂, ..., р_n} – конечное множество позиций, n³0. Т={t₁, t₂, ..., t_m} – конечное множество переходов, m³0. Множество позиций и множество переходов не пересекаются, Р Ç Т = Æ. I: Т®Р является входной функцией – отображением из переходов в комплекты позиций. О: Т® Р есть выходная функция – отображение из переходов в комплекты позиций.

Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом р_i, i=1, ..., п, а произвольный элемент Т – символом t_j, j=1,..., m.

Позиция р_i является входной позицией перехода t_j в том случае, если p_iÎI(t_j), p_i является выходной позицией, если p_iÎO(t_j). Входы и выходы переходов представляют собой комплекты позиций. Комплект является обобщением множества, в которое включены многократно повторяющиеся элементы – тиражированные элементы. В приложении 1 содержится описание теории комплектов. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции быть кратным входом либо кратным ' выходом перехода. Кратность входной позиции p_i для перехода t_j есть число появлений позиции во входном комплекте перехода, #(p_i,I(t_j)). Аналогично кратность выходной позиции p_i для перехода t_j есть число появлений позиции в выходном комплекте перехода, #(p_i,O(t_j)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.

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

Определение 2. Определим расширенную входную функцию I и выходную функцию таким образом, что #(t_j, I(p_i)) = #(p_i, I(t_j)), #(t_j, O(p_i)) = # (p_i, I(t_j)).

Пример.

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

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

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

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

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

C = (P, T, I, O),

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

T={t₁, t₂, t₃, t₄}.

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

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

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

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

Рис.6.1. Структура сети Петри представлена в виде четверки, которая состоит из множества позиций (Р), множества переходов (Т), входной функции ( ) и выходной функции ( )

Графы сетей Петри

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

Структура сети Петри представляет собой совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя типами узлов. Кружок О является позицией, а планка ½ – переходом.

Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие – от переходов к позициям. Дуга, направленная от позиции p_i к переходу t_j определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.

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

Граф сети Петри, изображенный на рис.5.2, эквивалентен структуре сети Петри из выше приведенного примера.

Рис. 5.2

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

Рис. 5.3

Поиск по сайту: