|
|
| Использование сетей Петри в математическом моделировании |
родолжив построение далее, мы найдем, что минимальное время, за которое может быть поджарена яичница, - шесть временных периодов (предполагая, что каждая подзадача требует ровно один период времени), а максимальное требующееся число помощников - два:Период времени Помощник 1 Помощник 21. Взять яйцо Взять жир2. Разбить яйцо Положить жир на сковороду3. Растопить жир4. Вылить яйцо на сковороду5. Ждать, пока яичница не изжарится6. Снять яичницуАвтоматизируем процесс построения решения задачи, модифицируя алгоритм топологической сортировки, проиллюстрированный программой, следующим образом: while (Граф не пуст){Определить вершины, не имеющие предшественников.Распечатать эту группу узлов с указанием, что эти подзадачимогут быть выполнены параллельно в следующий момент времени.Удалить из графа данные вершины и инцидентные дуги}Программа. Применение топологической сортировки для решения простейших задач сетевого планирования.#include <iostream. h>typedef struct Leader *Lref; // Тип: указатель на заголовочный узел.typedef struct Trailer *Tref; // Тип: указатель на дуговой узел. // Описание типа заголовочного узла.typedef struct Leader{int Key; // Информационное поле.int Count; // Количество предшественников.Tref Trail;Lref Next;}; // Описание типа дугового узла.typedef struct Trailer{Lref Id;Tref Next;};class Spisok {private:Lref Head; // Указатель на список заголовочных узлов.Lref Tail; // Указатель на фиктивный элемент // в конце списка заголовочных узлов.int z; // Количество узлов, не имеющих предшественников.public:Spisok () { // Инициализация списка заголовочных узлов.Head = Tail = new (Leader); z = 0; };Lref L (int);void Poisk ();void Vyvod ();};void Spisok:: Poisk (){Lref p,q; // Рабочие указатели.p = Head; Head = NULL;while (p! =Tail){q = p; p = p->Next;if (q->Count==0){ q->Next = Head; Head = q; }}}Lref Spisok:: L (int w) // Функция возвращает указатель на ведущего с ключом w.{Lref h = Head;Tail->Key = w;while (h->Key! =w) h = h->Next;if (h==Tail) // В списке нет элемента с ключом w.{Tail = new (Leader); z++;h->Count = 0; h->Trail = NULL; h->Next = Tail;}return h;}void Spisok:: Vyvod (){Lref p,q; // Рабочие указатели.Lref S,U; // Рабочие указатели.Tref t;cout << endl;cout << "Результат... \n";q = Head;while (q! =NULL) // Вывод всех элементов с нулевым количеством предшественников.{S = q; cout << " (";while (S! =NULL){ cout << S->Key << " "; z--; S = S->Next; }cout << ")"; // - ------------------------------------------------ -U = NULL; // Указатель на очередной список элементов // с нулевым количеством предшественников.while (q! =NULL){t = q->Trail;while (t! =NULL){p = t->Id; p->Count--;if (p->Count==0) // Включение (*p) в список ведущих.{ p->Next = U; U = p; }t = t->Next;}q = q->Next;}q = U;}if (z! =0)cout << "\nМножество не является частично упорядоченным! \n";}void main (){Spisok A;Lref p,q; // Рабочие указатели.Tref t;int x,y; // Рабочие переменные. // Фаза ввода.cout << "Задайте отношение частичного порядка... \n";cout << "Элемент ";cin >> x;cout << " предшествует элементу ";while (x! =0){cin >> y;p = A. L (x); q = A. L (y);t = new (Trailer); t->Id = q; t->Next = p->Trail;p->Trail = t; q->Count += 1;cout << "Элемент ";cin >> x;cout << " предшествует элементу ";} // Поиск ведущих с нулевым количеством предшественников.A. Poisk (); // Фаза вывода.A. Vyvod ();} [11]§3. Математические модели с использованием сетей ПетриСети Петри являются эффективным инструментом дискретных процессов, в частности, функционирования станочных систем. Их особенность заключается в возможности отображения параллелизма, асинхронности и иерархичности.На рис.2 приводится пример сети Петри, где Р - конечное непустое множество позиций (состояний); Т - конечное непустое множество переходов (событий), причем p P и ti T; F: Р x Т - {0, 1, 2,... }; Н: Т x Р {0, 1, 2,... } - функции входных и выходных инциденций; м0: Р {0, 1, 2,... } - начальная маркировка. Вершины сети p P изображены кружками, а вершины ti T - черточками (баркерами). Дуги соответствуют функциям инцидентности позиций и переходов. Точки в кружочках означают заданную начальную маркировку. Число маркеров в позиции равно значению функции м: Р {0, 1, 2,... }. Переход от одной маркировки к другой осуществляется срабатыванием переходов. Переход t может сработать при маркировке м, если он является возбужденным: (1) Рис.2. Сеть ПетриДанное условие показывает, что в каждой входной позиции перехода t число маркеров не меньше веса дуги, соединяющей эту позицию с переходом. В результате срабатывания перехода t, удовлетворяющего условию (1), маркировку м заменяют маркировкой м' по следующему правилу: (2)По этому правилу в результате срабатывания из всех входных позиций перехода t изымается F (p,t) маркеров и в каждую выходную позицию добавляется H (t,p) маркеров. Это означает, что маркировка м' непосредственно достижима из маркировки м. Функционирование сети Петри - последовательная смена маркировок в результате срабатывания возбужденных переходов.Состояние сети в данный момент времени определяется ее текущей маркировкой. Важная характеристика сети Петри - граф достижимости, с помощью которого описываются возможные варианты функционирования сети. Такой граф имеет вершины, которые являются возможными маркировками. Маркировки м и м' соединяются в направлении t дугой, помеченной символами перехода t T или мt м'. Маркировка м' такая последовательность переходов: ф = t1, t2,..., tk является достижимой из маркировки м, если существует, что мt1м't2 ... м tk м.N = (Р, Т, F, Н, м0), где Р = {Р1, Р2, Р3, Р4, Р5},T = {t1, t2, t3, t4, t5}, м0 = (1, 1, 0, 0, 0).Функции F и Н заданы матрицами|
| | P1 | P2 | P3 | P4 | P5 | | H = | t1 | 0 | 0 | 1 | 2 | 0 | | | t2 | 1 | 0 | 0 | 0 | 1 | | | t3 | 1 | 1 | 0 | 0 | 0 | | | t4 | 0 | 0 | 0 | 1 | 0 | | | | t1 | t2 | t3 | t4 | | F = | P1 | 1 | 0 | 0 | 0 | | | P2 | 1 | 0 | 0 | 0 | | | P3 | 0 | 1 | 0 | 0 | | | P4 | 0 | 0 | 1 | 0 | | | P5 | 0 | 0 | 0 | 1 | | |
Фрагмент графа достижимости для сети Петри приведен на рис3. [6] рис. 3 §4. Построение динамической модели на основе сети Петри1. Проверка синтаксиса функциональной модели и вывод динамической модели.Динамическая модель строится на основании функциональной модели и синтезируется пакетом Design/IDEF автоматически во время проверки синтаксиса функциональной модели. Для того, чтобы проверка стала возможной, необходимо разрешить эмуляцию CPN-моделей. Это делается путем установки метки CPN в окне Edit-Set Options-Methodology-Simulations. После установки метки в строке меню главного окна появляется новое меню CPN.Для проверки синтаксиса необходимо вызвать команду "Check CPN Syntax" в данном меню и в появившемся окне указать параметры проверки. По окончании проверки появляется окно с отчетом, где указываются ошибки (если есть), а на функциональной модели появляются элементы сети Петри.2. Краткие теоретические сведения о сетях Петри.Сети Петри являются мощным инструментом исследования моделируемых систем благодаря их возможности описания многих классов дискретных, асинхронных, параллельных, распределенных, недетерминированных систем, благодаря наглядности представления их работы, развитому математическому и программному аппарату анализа.Она представляет собой разновидность ориентированного графа, включающего в себя вершины двух типов: позиции и переходы. Позиции символизируют состояния и обозначаются как pi, а переходы обозначают собой действия (переходы из одного состояния в другое) и обозначаются как tj. Позиции и переходы соединены направленными дугами fk, каждая из которых имеет свой вес wk. Дуги также можно разделить на два типа: дуги, направленные от позиции к переходам, (p-t) и дуги, направленные от переходов к позициям (t-p). Исходя из этого, сеть Петри может быть формально представлена как совокупность множеств:N = (P, T, F, W),где P = {p1, p2… pn} - множество всех позиций (n - количество позиций),T = {t1, t2… tm} - множество переходов (m - количество переходов),F = (Fp-t, Ft-p) - множество дуг сети:Fp-t = (pґt), Ft-p = (tґp) - множества дуг, ведущих соответственно от переходов к по-зициям и от позиций к переходам.W = {w1, w2… wk} - множество весов дуг (k - количество дуг).Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции pi, как mi, то маркировка всей сети: M = {m1, m2… mn}. Тогда полное определение сети Петри, включая данные о началь-ной маркировке, можно записать в виде:PN = (N, M0), где М0 - начальная маркировка сети.3. Отладка динамической модели.Если в результате проверки синтаксиса функциональной модели были обнаружены ошибки, то их список будет выведен в окне отчета. В процессе устранения ошибок удобно переходить от одной ошибки к другой с помощью команды "Next Reference"/"Previous Ref-erence" меню Select. Все ошибки показываются выделением.4. Надписывание позиций.Для надписывания какой-либо позиции сети Петри необходимо сначала создать метку (команда Create Label), затем ее выделить и вызвать команду "Place Name" меню CPN. После этого достаточно указать надписываемый объект.5. Надписывание переходов.Роль переходов сети Петри играют функциональные блоки. По умолчанию в качестве имени перехода используется название блока. Однако, имеется возможность дать ему другое имя. Надписывание перехода производится так же, как и надписывание позиции.После того, как переход подписан в левом нижнем углу блока появляется квадрат, который подтверждает, что блок подписан.Аналогичным образом устанавливаются для перехода защита, кодовый сегмент и задержка.Защита запрещает переход в соответствии с условиями на переменные, указанные в выражениях смежных дуг. Для ее установки требуется создать метку, содержащую выражение для защиты, затем командой "Guard" меню CPN она привязывается к переходу.Кодовый сегмент определяет сегмент в коде Standard ML, который выполняется в эмуляторе Design/CPN всякий раз, когда будет срабатывать переход.Задержка определяет время, которое характеризует продолжительность срабатывания перехода.6. Надписывание дуг.Каждая дуга может иметь свое имя и выражение, которые задаются как присоединяемые метки.Для указания имени дуги необходимо создать новую метку, затем вызвать команду "Place Name" меню CPN и указать на маленький невидимый квадратик, принадлежащий функциональному блоку и расположенный в месте соединения блока и дуги.Выражение дуги характеризует мультинабор фишек, которые двигаются по дуге при любом срабатывании перехода, являющегося входным для дуги. Присоединение осуществляется аналогично вызовом пункта "Arc Expression" меню CPN.7. Удаление и скрытие динамической модели.Для скрытия элементов динамической модели используется команда "Hide CPN De-tail" меню CPN. Чтобы сделать элементы снова видимыми требуется команда "Show CPN Detail". Чтобы полностью удалить позиции сети Петри используется команда "Discard CPN Places". [9]§5. Применение сетевых моделей для описания параллельных процессовПри анализе сети Петри основное внимание уделяется, как правило, трем направлениям.Проблема достижимости. В сети Петри с начальной разметкой М0 требуется определить, достижима ли принципиально некоторая разметка М' из М0. С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.
Страницы: 1, 2, 3
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
