link2960 link2961 link2962 link2963 link2964 link2965 link2966 link2967 link2968 link2969 link2970 link2971 link2972 link2973 link2974 link2975 link2976 link2977 link2978 link2979 link2980 link2981 link2982 link2983 link2984 link2985 link2986 link2987 link2988 link2989 link2990 link2991 link2992 link2993 link2994 link2995 link2996 link2997 link2998 link2999 link3000 link3001 link3002 link3003 link3004 link3005 link3006 link3007 link3008 link3009 link3010 link3011 link3012 link3013 link3014 link3015 link3016 link3017 link3018 link3019 link3020 link3021 link3022 link3023 link3024 link3025 link3026 link3027 link3028 link3029 link3030 link3031 link3032 link3033 link3034 link3035 link3036 link3037 link3038 link3039 link3040 link3041 link3042 link3043 link3044 link3045 link3046 link3047 link3048 link3049 link3050 link3051 link3052 link3053 link3054 link3055 link3056 link3057 link3058 link3059 link3060 link3061 link3062 link3063 link3064 link3065 link3066 link3067 link3068 link3069 link3070 link3071 link3072 link3073 link3074 link3075 link3076 link3077 link3078 link3079 link3080 link3081 link3082 link3083 link3084 link3085 link3086 link3087 link3088 link3089 link3090 link3091 link3092 link3093 link3094 link3095 link3096 link3097 link3098 link3099 link3100 link3101 link3102 link3103 link3104 link3105 link3106 link3107

Лекции по системному анализу в чрезвычайных ситуациях. Часть 4

ТЕМА 2.2.6.  Сети Петри


1. Основные понятия

2. Конечные разметки сети

3. Ограниченности сети Петри

4. Моделирование с помощью сетей Петри

1. Основные понятия

clip_image002[6]

Рис.1

Графы специального вида, получившие в дальнейшем название “Сети Петри” были впервые введены Карлом Петри в 60-х годах. В следующем десятилетии начался “бум” разработок в этом направлении. В настоящее время поисковые машины Интернет дают несколько десятков тысяч ссылок на использование этого термина.

Популярность сетей Петри вызвана удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделированию. Прекрасное изложение теории сетей Петри можно найти на русском языке в [1] и [2]. Формальное определение сетей Петри будет приведено ниже. Здесь же дать простое представление об этом математическом инструменте.

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

Либо начало дуги совпадает с позицией и тогда конец этой дуги совпадает с переходом, либо наоборот.

clip_image004[6]

Рис.2

На рис.1 приведены примеры, соответствующие этому ограничению, на рис.2 — недопустимые примеры.

clip_image006

Оригинальным понятием теории сетей Петри является понятие “фишка”. Фишки изображаются точками, расположенными внутри позиций. Таким образом, каждой позиции сети ставится в соответствие натуральное число, указывающее количество фишек в данной позиция. Это число называют разметкой позиции, а совокупность таких чисел для всех позиций сети называют разметкой сети. Замечу, что позиция может и не содержать фишек, т.е. иметь нулевую разметку.

Пример сети с разметкой приведен на рис.3.

Другое оригинальное понятие сети Петри — “срабатывание” переходов.

clip_image008

Рис.3

Назовем входными позициями некоторого конкретного перехода — те позиции, из которых исходят дуги, входящие в данный переход. Соответственно, выходными позициями назовем позиции, в которые входят дуги, исходящие из данного перехода.

Например, на рис.3 для перехода P1 входная позиция V1- выходная -V3.

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

Например, переход P1 на рис.3 при срабатывании изымает из позиции V1 одну фишку и увеличивает количество фишек в позиции V3 на одну.

Переход P2 изымает одну фишку из позиции V1 и помещает в позицию V2 две фишки.

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

Например, на рис.3. переход P3 не может сработать, ибо в позиции V3 находится только одна фишка, а дуг, связывающих V3 и P3 — две.

Как только введено понятие “срабатывание” перехода — появляется возможность говорить о функционировании сети и моделировании процессов, этапы которых связаны между собой причинно-следственной связью.

В самом деле, на рис.3 изображена сеть, в которой переход P3 не может сработать. Но если сработает переход P1, то количество фишек в позиции V3 — увеличится. Теперь P3 — сработает.

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

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

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

Вы здесь: Главная БЖД и Охрана труда Чрезвычайные ситуации Лекции по системному анализу в чрезвычайных ситуациях. Часть 4