Программный комплекс по изучению теории графов, сетей Петри и применению их в различных предметных областях

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Программный комплекс по изучению теории графов, сетей Петри и применению их в различных предметных областях

Халимон В.И., Проститенко О.В., Рогов А.Ю.

The educational program complex in which the variety of tasks which can be formalized with use of the graf theory, is incorporated by the common user interface is developed. Such approach allows to make more clear transition from studying cleanly theoretical positions to use grafs at modelling parallel processes on Petri-networks, modelling of single-channel and multichannel systems of mass service, and also construction grafs for systems of automatic control and definition of transfer function by means of formula Maison.

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

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

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

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1 - Структурная схема взаимодействия подсистем программного комплекса

теория граф математический

Ядром программного комплекса является подсистема «Графы». Для построения графа достаточно знать состав элементов и связи между ними. Топологический анализ проходит в несколько этапов: анализ элементов; анализ путей и контуров в системе; анализ связанности структуры; определение обобщенных структурных характеристик системы; оценка быстродействия; проверка достижимости элементов; анализ надежности; определение степени централизации элементов.

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

1. Файловой подсистемы, которая осуществляет ввод/вывод графов в файл.

2. Подсистемы ввода и редактирования графов, которая реализует следующие операции:

? ввод, удаление, перемещение вершин и связей;

? ввод и изменение основного и вспомогательного веса вершин и связей;

? разметка графа;

? отрисовка графа в рабочей области оболочки;

? очистка рабочих областей при создании нового графа;

? изменение размера вершин;

? назначение комментариев вершинам и связям;

? изменение нумерации вершин;

? изменение вида вершин.

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

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

5. Подсистемы выбора методов обработки графов.

6. Справочной подсистемы, которая позволяет получать справочную информацию об оболочке.

Главное окно подсистемы показано на рисунке 2.

Рисунок 2 - Главное окно подсистемы «Graf, PetriNet, SMO»

Подсистема «Графы» позволяет проводить анализ структур сложных систем графовыми методами по следующим пунктам:

? выявление ошибок в структуре системы:

? анализ связей структуры:

? анализ быстродействия системы;

? анализ надежности системы.

Наглядность графовых представлений и графовых методов преобразования структурных схем [3] привела исследователей к созданию математического аппарата для нахождения неизвестных переменных непосредственно по графу системы.

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

Используя приведенные выше определения, можно записать общее выражение для формулы Мэзона:

, (1)

где K_jl - коэффициент передачи графа от некоторого источника j к l-й вершине графа;

D - общий определитель графа, аналогичный главному определителю системы уравнений;

- передача s-го сквозного пути от источника j к l-й вершине графа;

- алгебраическое дополнение к s- му сквозному пути.

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

(2)

Пример реализации расчета передаточной функции системы по формуле Мезон в подсистеме «Графы» приведен на рисунке 3.

Рисунок 3 - Пример реализации расчета передаточной функции

Одной из модификаций графов являются сети Петри[2]. Сеть Петри - наглядная и хорошо формализованная модель поведения параллельных систем с асинхронными взаимодействиями. Она в компактной форме отражает структуру взаимоотношений элементов системы и динамику изменения ее состояний при заданных начальных условиях. Уровень абстракции модели очень высокий - он соответствует описанию взаимодействий в системе в терминах всего лишь двух понятий: событий и условий.

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

Рисунок 4 - Способы задания сети Петри в программном комплексе.

Подсистема «Сети Петри» содержит параметры, которые позволяют настроить режим расчета сети Петри:

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

2. Безопасная сеть - расчет сети по правилам безопасной сети. При установленном флажке «Первоначальное представление» в процессе расчета сети будут использоваться правила срабатывания переходов, разработанные доктором Петри в 1962 году (для срабатывания перехода выходные позиции не должны содержать маркеров).

3. Управляющая сеть - расчет сети по правилам управляющей сети. Флажок «На основе безопасной сети» запрещает наличие кратных дуг и накопление маркеров в позициях. Флажок «На основе оценочной сети» разрешает кратные дуги и накопление маркеров.

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

Рисунок 5 - Результат анализа сети, изображенной на рисунке 4

Подсистема «Системы массового обслуживания» позволяет строить графы состояний одноканальных и многоканальных систем с заданием интенсивностей потоков в качестве весов дуг и расчетом финальных вероятностей по уравнениям Колмогорова, что и представлено на рисунке 6.

Рисунок 6 - Работа подсистемы «Системы массового обслуживания»

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

Литература

Нечепуренко, М.И. Алгоритмы и программя решения задач на графах и сетях [Текст] / М.И. Нечепуренко.- Новосибирск: Наука, 1990.- 515 с.

Васильев, В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем [Текст] / В.В. Васильев, В.В. Кузьмук. - Киев: Наук. думка, 1990. - 216с.

Мэзон, С. Электронные цепи, сигналы и системы [Текст] / С. Мэзон,

Г. Циммерман. - М.:Издательство иностранной литературы,1963. - 650 с.

Размещено на Allbest.ru