Математическое и программное обеспечение систем принятия решений в посткатастрофических ситуациях тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Пащенко, Дмитрий Владимирович

• Пащенко, Дмитрий Владимирович
• кандидат технических наук
• 2003

Оглавление диссертации кандидат технических наук Пащенко, Дмитрий Владимирович

Введение

Глава 1 Анализ программ контроля и управления распределёнными объектами

1.1 Функциональные возможности информационных систем

1.2 Сравнительный анализ геоинформационных систем

1.3 Организация моделирования в геоинформационных системах

1.4 Региональные геоинформационные системы

1.5 Анализ свойств объекта исследования

1.6 Надёжность энергетических сетей

1.7 Выводы

Глава 2 Разработка и анализ алгоритмов планирования восстановления территориально распределённых систем

2.1 Организация моделирования территориально протяжённых объектов

2.2 Разработка модели энергетической сети

2.3 Разработка алгоритмов определения порядка восстановления ЛЭП

2.4 Адаптация алгоритма разложения графа в ширину применительно к модели энергосистемы

2.5 Алгоритм определения порядка восстановления некритических неисправностей

2.6 Выводы

Глава 3 Разработка модуля принятия решений для геоинформационных систем с учётом требований по надёжности

3.1 Анализ различных топологических вариантов распределённых сетей

3.1.1 Последовательные системы

3.1.2 Параллельные системы

3.2 Количественные оценки структурных характеристик сетей

3.3 Особенности построения сетевых структур повышенной надёжности

3.4 Разработка алгоритмов для организации модуля анализа сетевых структур

3.5 Выводы

Глава 4 Программное расширение Arcgraf

4.1 Состав программы

4.2 Модуль активации всех тем (active)

4.3 Модуль обнуления неисправностей таблиц (obnul)

4.4 Модуль ввода неисправностей помеченных вершин в активной теме (neispr)

4.5 Модуль номеров опор на текущей теме (graf)

4.6 Модуль программы расчёта (glavrasgraf)

4.7 Порядок работы с расширением ARCGRAF

4.8 Оценка сложности и быстродействия алгоритмов поиска кратчайших путей

4.9 Выводы

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение систем принятия решений в посткатастрофических ситуациях»

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

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

В настоящее время всё больше внимания уделяется проблемам защиты и прогнозирования восстановления объектов после катастроф и стихийных бедствий. Однако в катастрофических и посткатастрофических ситуациях существующие информационно-управляющие системы не обеспечивают эффективного анализа и управления территориально распределёнными объектами. Существующие системы ориентированы на решение задач восстановления в одной узкоспециализированной области техники и не удовлетворяют требованиям наглядности и полноты управления.

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

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

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

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

Научная новизна диссертационной работы состоит в следующем:

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

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

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

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

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

На защиту выносятся результаты разработки систем анализа и управления восстановлением протяженных сетевых структур, в том числе:

1. способ формализованного описания территориально протяженных систем с учётом форматов представления данных в д геоинформационной системе Arc View;

2. алгоритмы решения задачи определения приоритетного порядка восстановления территориально протяжённых систем на основе предложенной модели с использованием геоинформационных технологий;

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

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

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 9 статей и 3 тезиса докладов.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на I Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 1999 г.); II Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 2000 г.); IV Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2000 г.); Всероссийской научно-практической конференции «Электромагнитная совместимость (ЭМС) и безопасность при эксплуатации мобильных средств связи, телекоммуникаций и компьютерной техники» (г. Пенза, 2001 г.); Всероссийской научно-технической конференции «Методы и средства измерения в системах контроля и управления» (г. Пенза, 2001 г.); Межрегиональном постоянно действующем научно-техническом семинаре «Экологическая безопасность регионов России и риск от техногенных аварий и катастроф» (г. Пенза, 2001 г.); Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2002 г.).

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

Реализация и внедрение результатов работы. Разработанное программное расширение ArcGraf внедрено в составе геоинформационной системы NilesVl, разработанной ФГУП «НПП Рубин» г. Пенза и эксплуатируется филиалом ОАО «ПензаЭнерго» «Нижнеломовские электрические сети». (Приложение А).

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 144 страницы основного текста, 43 рисунка и 9 таблиц, 126 страниц приложений. Список литературы включает 55 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Пащенко, Дмитрий Владимирович

4.9 Выводы

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

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

3. Разработанная программа ARCGRAF на языках программирования Visual С++ и Avenue, обеспечивает быстрый и удобный способ анализа посткатастрофической ситуации на линиях электропередач и выдачу маршрутных карт движения ремонтных бригад, участвующих в процессе ликвидации аварии. Программа обладает свойствами универсальности и простоты в эксплуатации, что позволяет использовать её в процедурах устранения неисправностей и моделирования систем со сложной топологией.

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

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

6. Получено аналитическое выражение для определения вычислительной сложности алгоритма восстановления рёбер графа неисправностей. Из полученного выражения и графиков сравнения вычислительной сложности исследуемых алгоритмов Флойда, Дейкстры и разработанного следует, что при количестве вершин (п=1000) и количестве рёбер (t= 100000) разработанный алгоритм сравним по вычислительной сложности с алгоритмом Дейкстры и менее сложен, чем алгоритм Флойда. При увеличении количества рёбер вычислительная сложность алгоритма растёт, но это не имеет большого значения для исследуемых структур, так как ранг элемента структуры становится больше, чем 100.

136

Заключение

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

В результате теоретических и экспериментальных исследований, выполненных в диссертационной работе, получены следующие научные и практические результаты:

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

2. Разработан метод организации устранения последствий множественных аварий в сложных территориально распределённых системах с использованием элементов ситуационного управления. Использование этого метода в интегрированной геоинформационной системе позволяет автоматизировать процесс принятия решений при устранении последствий аварий.

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

4. Предложен алгоритм поиска кратчайших путей на сети, ^ который, в отличие от известных, учитывает приоритеты восстановления потребителей и коэффициенты неисправностей связей. Выполнен его сравнительный анализ с алгоритмами Флойда и Декстры по вычислительной сложности. Использование этого алгоритма позволяет снизить затраты времени на принятие решений при восстановлении функционирования сложно структурированной системы. ^ 5. Предложен способ организации функциональных подсистем в составе ГИС. Способ обеспечивает проектирование модулей ГИС на основе технологии динамически подключаемых библиотек (dll) и возможность функционирования в различных операционных системах. На основе данного способа разработано программное расширение Arcgraf, которое используется для определения порядка восстановления i территориально протяженных систем.

6. Разработана программа поиска порядка восстановления территориально протяжённой системы с использованием языков программирования Visual С++ и Avenue. Программа реализует процедуру построения маршрутов аварийных бригад на электронных географических картах с использованием внутренних форматов представления данных в Ф геоинформационной системе ArcView. Р

138

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

1. Цветков В.Я. Геоинформационные системы и технологии. — М.: Финансы и статистика, 1998. — 288 е.: ил.

2. Линник В.Г. Построение геоинформационных систем в физической географии. — М.: изд-во МГУ, 1990. — 80 с.

3. Доклад о наиболее важных достижениях в области науки, технки и производства топографо-геодезических и картографических работ в Российской Федерации и за рубежом за 1995 г. М.: ФСГиКб ЦНИИ-ГАиКб 1995. - 56 с.

4. Хаксальд В. Введение в городские географические информационные системы. — Изд-во Оксфордского университета, 1991. — 321 с.

5. Цветков В.Я. Информатизация: Создание современных информационных технологий. // 4.1. Структуры данных и технические средства.- М.: ГКНТ, ВНТИЦентр, 1990. — 118 с.

6. Snyder J.P. U.S. Geological Survey professional paper 1453 / Snyder J.P., Voxland P.M. // An Album of Map Projection Washington, 1989.

7. Цикритзис Д. Модели данных. / Д. Цикритзис, Ф. Лоховски — М.: Финансы и статистика, 1986. — 344 с.

8. Geographic Information System (GIS) based on Jupier Technology // Intergraph software solution. Aprel 1996. - 36 p.

9. Пащенко Д.В. Построение и использование модели энергетической системы. / Материалы Всероссийской научно-технической конференции «Методы и средства измерения в системах контроля и управления».- Пенза, 2001 г. — с. 171-172

10. Идельчик В.И. Электрические системы и сети // Учебник для вузов. — М.: Энергоатомиздат, 1989. — 592 е.: ил., ISBN 5283-01012-0

11. Клима И. Оптимизация Энергетических систем. / Пер. с чешского Л.Г. Ублинской , под ред. В.Р. Окорокова. // М.: Высш. шк., 1991. 302 с.

12. Пащенко Д.В. Системы контроля и анализа информации для энергосетей. /Межвуз. сб. науч. тр. «Датчики систем измерения, контроля и управления» — Вып. 20. — Пенза: Изд-во Пенз. гос. ун-та, 2000. с. 21-23

13. Башлыков А.А. Проектирование систем принятия решений в энергетике. — М.: Энергоатомиздат, 1986. — 120 с.

14. Акимов О.Е. Дискретная математика: логика, группы, графы. — М.: Лаборатория Базовых Знаний, 2001 — 352 с.

15. Новиков Ф.А. Дискретная математика для программистов — СПб: Питер, 2000. 304 е.: ил.

16. Филлипс Д., Гарси-Диас А. Методы Анализа сетей: Пер. с англ. — М.: Мир, 1984. — 496 е., ил.

17. Любарский Ю.Я. Интелектуальные информационные системы. — М.: Наука. Гл. ред. Физ.-мат. лит., 1980. — 232 с. — (Пробл. искусст. Интеллекта.)

18. Яхо, Альфред, В., Хопкрофт Джон Э., Ульман, Джеффи Д. // Структуры данных и алгоритмы.: Пер. с англ.: Уч. пособие — М: Издательство дом «Вильяме», 2000-384 е.: ил. — Парал. тит. англ.

19. Майника Э. // Алгоритмы оптимизации на сетях и графах: Пер. с англ. — М: Мир, 1981. — 323 е., ил.

20. Сешу С. и Рид М.Б. // Линейные графы и электрические цепи. // Перевод с англ. языка. Под ред. П.А. Ионкина. Учеб. пособие для вузов специальностей радиотехн., электронная техн., электроприборостр. и автоматика. М., «Высш. школа», 1971.

21. Многогранники, графы, оптимизация (комбинаторная теория многогранников). Емеличев В.А., Ковалёв М.М., Кравцов М.К. — М.: Наука. Главная редакция физико-математической литературы, 1981. — 344 с.

22. Давыдов Э.Г. Игры, графы, ресурсы. — «Радио и связь», 1981, 112 с.

23. Гентмахер Ф.Р. Теория матриц. — 4-е изд. — М.: Наука. Гл. ред. физ.-мат. лит., 1988. — 552 с.

24. Математическое моделирование. Редакторы Дж. Эндрюс, Р. Мак-Лоун: Перевод с ангглийского под редакцией Ю.П. Гупало, -М.: Мир, 1979.

25. Сикорский В.П. Математический аппарат инженера., «Техника», Киев, 1975, 768 с.

26. Пащенко Д.В. Моделирование энергетических систем. / Компьютерные технологии в науке, проектировании и производстве. Тезисы докладов II Всероссийской научно-технической конференции. Часть VII. — Нижний Новгород: 2000 г. — с. 34

27. Поспелов Д.А. Ситуационное управление: теория и практика. — М.: Наука. — Гл. ред. физ. — мат. лит., 1986. — 288 с.

28. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов/ Под ред. И.А. Ушакова. — М.: Радио и связь, 1988. 208 е.: ил.

29. Северцев Н.А. Надёжность сложных систем в эксплуатации и обработке: Учеб. пособие для вузов. — М.: Высш. шк., 1989. — 432 е.

30. Руденко Ю.Н. Надёжность систем энергетики / Руденко Ю.Н. Ушаков И.А. — 2-е изд., перераб. и доп. — Новосибирск: Наука. Сиб. отд-ние, 1989.-328 с.

31. Ясин Э.М. Результаты исследования и оптимизации надёжности систем нефтеснабжения // Методические вопросы исследования надёжности больших систем энергетики. — Иркутск.: СЭИ, 1981. Вып. 23.

32. Китушин В.Г. Надёжность энергетических систем.-М.: Высш. школа, 1984. — 256 с.

33. Емеличев В.А. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. — М.: Наука. Гл. ред. физ-мат. Лит., 1990. — 384 с.

34. Исследование операций: В 2-х томах. Пер. с англ. / Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981. Т. 1. 712 е., ил.

35. Пащенко Д.В. Анализ живучести сложных систем на примере энергетических сетей / Пащенко Д.В., Пащенко В.Г. //

36. Надёжность и качество: Труды международного симпозиума — Пенза: Информационно-издательский центр Пенз. гос. ун-та, 2002. -427-429

37. Пащенко Д.В. О моделировании региональных энергетических сетей. / Новые информационные технологии и системы: Материалы 4 Международной научно-технической конференции, Пенза, ПГУ, 2000 г. с — 155-156.

38. Руденко Ю.Н. Надёжность и резервирование в электроэнергетических системах / Руденко Ю.Н., Чельцов М.Б. // Методы исследования — Новосибирск: Наука. Сиб. отделение, 1974 264 с.

39. Руденко Ю.Н. Классификация задач в проблеме надёжности электроэнергетических систем / Руденко Ю.Н., Чельцов М.Б. //Методологические вопросы исследования надёжности больших систем энергетики — Сыктывкар, 1975 — Вып. 2 — с 6-17.

40. Автоматизация проектирования гибких производственных систем/ Р.И. Сольницев, А.Е. Кононюк, Ф.М. Кулаков. — Л.: Машиностроение. Ленингр. отделение, 1990. — 415 е.: ил.

41. Ушаков И.А. О надёжности систем со случайной длительностью выполнения задач // Надёжность и контроль качества. — 1972.-№ 6 — с. 44-45., Надёжность систем энергетики

42. Ю.Н. Руденко, И.А. Ушаков — 2-е издан., перераб. И дополн.- Новосибирск: Наука. Сиб. Отд-ние. 1989. — 328 с.

43. Горский Ю.М. Подходы к количественной оценке живучести Методические вопросы исследования систем надежности больших систем энергетики. — Иркутск: СЭИ. 1980.- Вып. 20. С. 24-31.

44. Руденко Ю.Н. Предисловие: Живучесть систем энергетики // Методические вопросы исследования надёжности больших систем энергетики. — Иркутск: СЭИ. 1980, Вып. 20. — С. 5-9.

45. Блок В.М. Электрические сети и системы. М.: Высшая школа, 1986.

46. Сухарев М.Г., Ставровский Е.Р., Брянских В.Е. Вопросы живучести при планировании развития систем газоснабжения // Методические вопросы исследования систем надежности больших систем энергетики. — Иркутск: СЭИ. 1980. — Вып. 20. — С.118-127

47. Ю.С. Сомов Композиция в технике. — 3-е изд., перераб. и дополн.- М.; «Машиностроение», 1987. 288 с.:ил.

48. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий / E.JT. Юшенко, Г.Е. Цейтлин, В.П. Грицай, Т.К. Терзян. — М.:Финансы и статистика, 1989.-208 с.:ил.

49. Пащенко Д.В. Анализ надёжности территориально протяжённых сетевых структур. / Новые информационные технологии и системы: Труды 5 Международной научно-технической конференции, Пенза, ПГУ, 2002 г. с — 37-41.

50. Пащенко Д.В. Алгоритмы устранения последствий множественных аварий на линиях энергоснабжения / Пащенко Д.В., Макарычев П.П., // Вычислительные системы и технологии обработки информации: Сб. науч. ст. Вып. 1. — Пенза: изд. ПГУ, 2000. с. 27.

51. Введение в разработку и анализ алгоритмов / Гудман С., Хидетниеми С. М.: Мир, 1981. 386 с.

52. Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978.