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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ УГЛЯ И УГЛЕХИМИИ

На правах рукописи Милевский Владислав Анатольевич

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ТЕХНОЛОГИЧЕСКИХ СХЕМ С ИСПОЛЬЗОВАНИЕМ ФОРМАЛЬНЫХ СВОЙСТВ СЕТЕЙ ПЕТРИ (НА ПРИМЕРАХ СИСТЕМ КАРЬЕРНОГО ТРАНСПОРТА И ПРОВЕТРИВАНИЯ УГОЛЬНОЙ ШАХТЫ)

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях (по отраслям наук)

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель кандидат технических наук Тайлаков О.В.

КЕМЕРОВО -1999

ОГЛАВЛЕНИЕ

Введение . 4 Глава 1.Методы математического моделирования

процессов горного дела 10

1.1 .Применение теории графов для моделирования технологических

процессов угольной промышленности 10

1.2.Развитие методов математического моделирования в горном деле с использованием вычислительных возможностей компьютерной техники 15

1.3.Использование сетей Петри для моделирования

технологических процессов 19

1.3.1.Развития теории сетей Петри 22

1.3.2.Моделирующие возможности сетей Петри 23

1.3.3.Применение сетей Петри в горном деле 25

1.4.Выводы 27 Глава 2.Интегрированная система моделирования и формального

анализа свойств сетей Петри 28

2.1 .Основные понятия теории сетей Петри. Классификация 28

2.2.Алгоритмические основы построения системы моделирования 46 2.2. КПоведенческие свойства. Алгоритм построения* '

дерева достижимых состояний 46

2.2.2.Структурные свойства. Векторный анализ уравнения состояния 49 2.3.Общая структура и функциональные возможности

интегрированной системы 55

2.4.Особенности реализации модулей анализа сети Петри 63

2.5.Выводы 67 Глава 3.Анализ функционирования транспортной системы карьера 69 3.1 .Упрощенная модель транспортного потока 69

3.2.Методика проведения имитационных экспериментов 79

3.3.Моделирование работы карьера 82

3.4.Выводы 99

Глава 4.Математическое моделирование воздухораспределения

шахтной вентиляционной системы сетью Петри 101

4.1.Представление вентиляционной схемы сетью Петри 103

4.2.Математическое описание метода решения системы

воздухораспределения. Постановка задачи 104

4.3.Алгоритм построения системы независимых контуров 106

4.4.Примеры расчета реальных вентиляционных схем 109

4.5.Выводы 115 Заключение 117 Литература 120

Введение

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

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

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

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

последовательности действий; достижимость - установить возможность или невозможность некоторой ситуации в системе.

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

Работа выполнялась в соответствии с заданием задание «Структурные и информационные модели систем угледобычи и процессов функционирования сложных объектов» к плану НИР Института угля и углехимии СО РАН на 1998-2000 годы, проект «Математическое моделирование систем и процессов угледобычи»; Федеральной целевой программой «Государственная поддержка интеграции высшего образования и фундаментальной науки на 1997-2000 годы».

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

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

Задачи исследований:

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

- установить соответствие структуры, кратности дуг и маркирования позиций сетей Петри структуре производственных систем, параметрам процессов угледобычи, на примерах систем карьерного транспорта и управления вентиляцией угольной шахты;

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

- построить модель сети Петри вентиляционной системы угольной шахты и установить характерные структурные свойства построенной сети;

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

Методы исследований:

- алгоритмизация и программная реализация методов теории сетей Петри при разработке интегрированной системы моделирования и анализа формальных свойств сетей Петри в инструментальной среде программирования Borland Delphi 1.0 под управлением операционной системы MS Windows',

- принципы модульности и структурного подобия теории сетей Петри для моделирования элементов транспортной системы;

- методы векторной алгебры для анализа поведенческих и структурных свойств построенных моделей;

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

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

Научные положения, защищаемые автором

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

- кратностям дуг сети Петри изоморфны статические и времязависимые параметры оборудования (грузоподъемность, время выполнения операций) транспортной системы карьера;

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

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

реализуется инвариантная состоянию системы последовательность срабатывания переходов;

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

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

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

Научная новизна работы состоит

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

- в установлении соответствия понятий сетей Петри (кратности дуг, маркированию позиций) технологическим параметрам углепотоков транспортной системы карьера и вентиляционной схеме угольной шахты;

- в разработке базисного набора математических моделей основных элементов транспортной системы: входной поток, выходной поток, буфер; механизма их композиции и структурной синхронизации;

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

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

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

Личный вклад автора состоит

- в разработке интегрированной системы моделирования и анализа формаль-

V и и 1 и 1

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

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

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

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

- в установлении тождественности системы независимых позиционных инвариантов и путей движения воздуха вентиляционной сети;

- в разработке метода построения системы независимых контуров вентиляционной сети.

Практическая ценность. Использование разработанной системы моделирования и анализа формальных свойств сетей Петри позволяет:

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

- описывать различные технологические процессы угледобычи структурно синхронизированными сетями Петри, в частности процесс транспортировки угля при добыче открытым способом;

- выбирать параметры оборудования, обеспечивающие стационарный режим функционирования транспортной системы карьера;

- графически отображать динамику работы системы;

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

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

Реализация работы. На основании полученных результатов разработаны методические рекомендации «Интегрированная система моделирования на основе сетей Петри», утвержденные методической комиссией механико-машиностроительного факультета КузГТУ и используемой в учебном процессе на кафедре автомобильных перевозок; учебное пособие «Построение и анализ формальных свойств сетей Петри с использованием интегрированной системы моделирования», утвержденное методической комиссией математического факультета КемГУ и используемой в учебном процессе на кафедре автоматизации исследований и технической кибернетики.

Апробация работы. Основные научные положения и практические результаты работы обсуждались и получили одобрение на II Международной научно-практической конференции «Безопасность жизнедеятельности предприятий в угольных регионах» (Кемерово, 1998 г.), на Международной научно-практической конференции «Наукоемкие технологии угледобычи и углепереработки» (Кемерово, 6-9 октября 1998 г.), на Международной конференции «Экологические проблемы угледобывающей отрасли в регионе при переходе к устойчивому развитию» (Кемерово, 24-25 февраля 1999 г.), на научном семинаре Кемеровского государственного университета (Кемерово, 1999 г.), на научном семинаре Кузбасского государственного технического университета (Кемерово, 1999 г.), на научном семинаре Института угля и углехимии СО РАН (Кемерово, 1999 г.).

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

Объем работы. Диссертация состоит из введения, 4 глав и заключения на 116 стр., содержит 3 таблицы, 32 рисунка, список литературы из 112 наименований.

Глава 1. Методы математического моделирования

процессов горного дела

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

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

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

Методы теории графов позволяют решать экстремальные задачи на составленном графе и можно рассматривать их как развитие методов вариантов [19]. Предположим, что задан граф С(Х, V) с множеством вершин {X} и множеством дуг {V}. Длина каждой дуги графа есть неотрицательное число 1(и)>0. На графе находится некоторый путь ¡х~{хо, X], х2, ..., хт}, для которого справедливо хт>х1>хо при 0<г<т и х(еХ.

Длина некоторого выделенного на графе пути ¡л определяется как

/(/;)=!>), (и)

и &]

где и - множество дуг пути р..

Если длину / дуг представить в виде какого-либо критерия, характеризующего отношения элементов и всего графа, то задача будет состоять в том, чтобы на графе определить путь из х0 в хт с наименьшей (или наибольшей) длиной, т. е. определить

UM = min l(f-i); jueM, (1.2)

где М - множество возможных путей из начальной вершины графа Хо в конечную вершину хт.

Таким образом, математически постановку задачи на графе можно свести к следующей модели, представляющей целевую функцию и систему ограничений:

G(X Y); 1(и) > 0;

/Л {Xq, X], х2,,

хт > х,1 0 </'</// ;

Г (13)

х0 <x,.j х,. eJ;

иШ

С (/0 = min /(//).

Задача (1.3) ставилась Е.И. Роговым, С.С. Банкиным и Е.Я. Рясковым [76] для определения вентиляционной системы обеспечивающей требуемое, относительно критериев надежности, воздухораспределение. На основе схемы вентиляции шахты строится граф надежности, дугами которого являются элементы этих подсистем: выработки, вентиляционные сооружения, средства автоматики, главные вентиляторы. Каждая дуга характеризуется двумя показателями -коэффициентом готовности Кг и средним временем восстановления Тв соответствующего элемента вентиляционной системы. Задача оценки надежности вентиляционной системы сводится к задаче нахождения на графе надежности пути

/.1ц, имеющего минимальный из всех возможных путей //г коэффициент готовности. Равенство (1.1) в этом случае принимает вид:

/(