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

На правах рукописи

ЗАБЕРЖИНСКИЙ Борислав Эдуардович

СИСТЕМНЫЙ АНАЛИЗ И ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ ОПТИМИЗАЦИИ РЕГИОНАЛЬНЫХ ГАЗОРАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ

Специальность 05.13.01 - Системный анализ, управление и обработка

информации (промышленность)

АВТОРЕФЕРАТ

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

□ОЗ 1"735 1"7

Самара-2007

003173517

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

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

Научный руководитель

доктор технических наук, профессор БАТИЩЕВ Виталий Иванович Официальные оппоненты

доктор технических наук ЮДАШКИН Александр Анатольевич, ГОУВПО «Самарский государственный технический университет»

кандидат технических наук, доцент ВОСТОКИН Сергей Владимирович, ГОУВПО «Самарский государственный аэрокосмический университет имени академика С П Королева»

Ведущая организация

ООО «Самараоблгаз», г Самара

Защита диссертации состоится « 15 » ноября 2007 г в 11 часов на заседании диссертационного совета Д212 217 03 в Самарском государственном техническом университете по адресу 443010, г Самара, ул Галактионовская, 141, ауд 28

С диссертацией можно ознакомиться в библиотеке Самарского государственного технического университета но адресу 443100, г Самара, ул Первомайская, 18, корп №1 и на официальном сайте чтут БатаШ ги

Отзывы на автореферат просим направлять в двух экземплярах по адресу 443100, г Самара, ул Молодогвардейская 244, ГОУВПО «Самарский государственный технический университет», главный корпус, на имя ученого секретаря диссертационного совета Д212 217 03

Автореферат разослан « 11 » октября 2007 г

Ученый секретарь

диссертационного совета Д212 217 03

Губанов Н Г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Через систему газопроводов на территории Российской Федерации транспортируется около 400 млрд куб м природного газа ОАО «Газпром» эксплуатирует свыше 500 тыс км газопроводов среднего и низкого давления, свыше 600 газораспределительных станций, обеспечивающие устойчивую подачу газа потребителям Вместе с тем, при таком мощном развитии газовой промышленности в России до сих пор около 40 городов, 400 поселков и 26 тыс сел еще не имеют никакого газоснабжения Уровень газификации природным газом в России составляет немногим более 50%, в том числе в сельской местности - 30% По данным ОАО «Газпром» в настоящее время износ основных фондов газотранспортных сетей составляет 56%, 14% газопроводов выработали нормативный срок службы Средний возраст газопроводов близок к 25 годам В целом по единой системе газоснабжения (ЕСГ) в период до 2010 года потребуется строительство около 28 тыс км новых магистральных газопроводов При этом объем планируемого строительства объектов газораспределения фактически совпадает с необходимым объемом их реконструкции.

Выполнение таких масштабных и капиталоемких работ (затраты на укладку 1 км газопровода РГРС составляют около 1,5 млн руб ) по планированию, проектированию и реконструкции газораспределительных сетей необходимо проводить на основании методов системного анализа и математического моделирования, обеспечивающих оптимизацию технико-экономических параметров РГРС Отсюда вытекает необходимость научного обоснования вопросов формализации и постановки задач системного анализа, оптимизации, разработки специального математического и программного обеспечения поддержки принятия решений при проектировании строительства и реконструкции РГРС Работа выполнялась в рамках НИР 517/05 и 501/06

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

Для достижения поставленной цели необходимо решить следующие задачи:

1 Провести системный анализ отраслевых особенностей функционирования и методов оптимизации РГРС

2 Исследовать методы анализа сетей и теории графов в принятии управленческих решений

3 Провести сравнительный анализ топологий сетей в отношении РГРС

4 Выявить системные связи и закономерности функционирования РГРС

5 Определить задачи синтеза и оптимизации РГРС

6 Формализовать модель оптимизации распределительно-транспортной системы

7 Получить алгоритмы оптимизации РГРС, как кратчайшей связывающей сети.

8 Разработать программное обеспечение решения задачи оптимизации РГРС с различными метриками

9 Провести оптимизацию участков реальных РГРС с евклидовой и ман-хэттенской метриками

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

Научная новизна результатов исследования состоит в разработке методики оптимизации РГРС, как совокупности методов системной идентификации и формализации модели оптимизации РГРС, разработки алгоритмов и программного обеспечения ее реализации, обеспечивающих получение оптимальных решений проектов новых и реконструкции существующих участков РГРС с учетом реальных условий трассировки газопроводов Конкретные элементы новизны состоят в следующем

1 Впервые определена структура подсистем и связей РГРС, как открытой системы, что позволяет учитывать реальные связи и процессы, определяющие эффективность функционирования РГРС

2 Установлены эндогенные и экзогенные условия синтеза РГРС, что в отличие от обычно используемой локальной оптимизации отдельных элементов, позволяет определять области существования оптимальных проектов РГРС

3 Поставлена задача и формализована модель оптимизации распределительно-транспортной системы, отличающаяся теоретико-графовым подходом и учетом реальной топологии РГРС, что позволяет дифференцировать задачу поиска кратчайшего остовного дерева на этапе предварительной проработки проекта и решение задачи Штейнера на основном этапе определения оптимальной топологии РГРС, обеспечивающее минимизацию наиболее капиталоемких параметров сети

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

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

6 Разработаны алгоритмы построения транспортно-распределительной сети, отличающийся от существующих для М^-трудных задач такого типа, возможностью получения близких к оптимальному решений для сетей с любым реальным количеством терминальных точек, оптимизации РГРС как кратчайшей связывающей сети, отличающийся учетом реальных условий трассировки РГРС и обеспечивающий минимизацию морфологических, наиболее капиталоемких параметров, таких как топология и длина сети в целом, оптимизации РГРС с точками Штейнера, отличающиеся наложением на план трассировки предложенной прямоугольной сетки, обеспечивающей формирование дополнительных узлов как мест расположения потенциальных точек Штейнера

7 Разработано оригинальное программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с евклидовой и манхэттенской метриками

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

На защиту выносятся:

1 Методика оптимизации РГРС как совокупность методов системной идентификации и формализации модели оптимизации РГРС, алгоритмы и программное обеспечение их реализации, обеспечивающие получение оптимальных решений проектов новых и реконструкции существующих участков РГРС

2 Подсистемы и связи РГРС как открытой системы

3 Модель оптимизации распределительно-транспортной системы

4 Алгоритмы оптимизации РГРС как кратчайшей связывающей сети и решения задачи Штейнера

5 Программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с различными метриками

Реализация результатов работы. Результаты работы были использованы в ООО «Газнадзор» Заволжский газотехнический центр (г Самара), ООО «Самарские системы связи» и в учебном процессе ГОУ ВПО «СамГТУ»

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 1-й Всероссийской конференции «Ин-фокоммуникационные и вычислительные технологии и системы » (Улан-Удэ, 2003), Международной научно-практической конференции «Ашировские чтения» (Самара, 2002), П-й Всероссийской конференции с международным участием «Инфокоммуникационные и вычислительные технологии и системы » (Улан-Удэ, 2006), Ш-й Всероссийской научной конференции «Математическое моделирование и краевые задачи » (Самара, 2006), 63-й Всероссийской научно-технической конференции по итогам НИР СГАСУ «Актуальные проблемы в строительстве и архитектуре Образование Наука Практика » (Самара, 2006), 1У-Й Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи » (Самара, 2007)

Публикации. По теме диссертации опубликовано 9 печатных работ, в том числе две в изданиях, из перечня рекомендованного ВАК

Структура и объём работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и приложения Основная часть содержит 145 страниц текста, 51 рисунок и 3 таблицы Список использованных источников содержит 117 наименований Приложение выполнено на 3-х страницах

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Системный анализ региональных газораспределительных сетей» проведен системный анализ отраслевых особенностей функционирования и оптимизации РГРС, выявлены системные проблемы развития региональных газораспределительных сетей, проведен анализ функционирования и развития РГРС на примере ООО «Средневолжская газовая компания», на основании контент-анализа выявлены сложившиеся методологические аспекты анализа и оптимизации в газовой промышленности, обоснованы принципы системного анализа и оптимизации в газовой промышленности

На примере функционирования ООО «Средневолжская газовая компания» (рисунок 1) в диссертации показано, что проблемы развития РГРС можно дифференцировать по двум направлениям замена устаревшей сети, как с позиции физического износа и реконструкции, так и отсутствия адекватной загрузки потребителями, и освоение новых в качественном и количественном отношении потребителей Если первая часть проблемы носит скорее характер инженерной задачи, решаемой в формате существующих стандартов и нормативов, то второй класс проблем уже нуждается в научном обосновании их решения Следовательно, разработку и реализацию проектов по строительству и реконструкции газораспределительных сетей необходимо проводить на основании методов системного анализа и математического моделирования, обеспечивающих оптимизацию технико-экономических параметров РГРС

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

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

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

1999 2000 2001 2002 2003 2004 2005 2006 2007 годы

И сельскохозяйственные объекты

□ пром. предприятия в сельской местности

□ городские пром. предприятия

Рисунок 1. - Динамика газификации промышленных и сельскохозяйственных предприятий Самарской области ООО «Средневолжская газовая компания»

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

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

Во второй главе «Методы системного анализа и теоретико-графового моделирования распределительных сетей» конкретизированы методы анализа сетей и теории графов в принятии управленческих решений; предложена схема алгоритма построения сети, близкой к оптимальной; выявлены системные связи и закономерности функционирования РГРС; проведен сравнительный анализ топологии сетей в отношении РГРС; выявлены системные связи и закономерности функционирования РГРС; получены концептуальная модель эндогенных и экзогенных условий синтеза региональной газораспределительной сети и их содержательное описание; идентифицированы задачи синтеза и оптимизации РГРС.

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

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

В случае РГРС топология сети - геометрическая форма или физическая связность сети

Топология сети влияет на состав необходимого сетевого оборудования, возможность расширения сети (наращиваемость), способ управления сетью, характеристики и параметры сетевого оборудования, надежность, стоимость, пропускную способность

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

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

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

Проведенный в диссертации анализ теоретико-графовых моделей и реальных условий формирования оптимизационных задач распределительных сетей позволил предложить следующую методику построения сети, близкой к оптимальной (рисунок 2), здесь X = {х,,} — координаты стоков (г — координата; у -сток); Р - номер источника; Г - нормативные таблицы для вычисления стоимости; д, - интенсивность г - го стока; п - число точек. Первый блок реализует обобщенный алгоритм Прима и выдает начальное приближение для координат дополнительных точек и информацию о дополнительных точках. Координаты этих точек содержатся в массиве Г, который реализован как продолжение массива X - координат исходных точек. Связи между исходными и дополнительными точками записаны в массиве Д в котором дерево задается рёбрами. Также вычисляется значение длины сети Ь.

Второй блок - вычисление стоимостей 7? - может быть составлен по-разному, в зависимости от рассматриваемой задачи. Если пропустить этот блок, то И. автоматически будут приняты равными единице. В этом случае алгоритм будет строить приближение к кратчайшей связывающей сети, т. е. будет решать традиционную задачу минимизации длины дерева Штейнера. Если положить, что стоимость является функцией Я (у) = (р (у(у)), где - интенсивность потока по ребру V, то алгоритм будет строить сети для задачи, в которой стоимость единицы длины связи зависит только от интенсивности потока.

Построение связывающего дерева (X, Р) —>(У, д /,;

Вычисление стоимости участков сети

(X, У, О, Т) —> (Я, К)

Построение локально-оптимального дерева при фиксированной структуре и стоимостях (X, У, А Я) —> (X, У, А ВД))

Рисунок 2. - Методика построения сети, близкой к оптимальной В третьем блоке происходит окончательное формирование связывающей сети - определяются оптимальные для данной структуры дерева и для данного закона вычисления стоимостей расположения дополнительных точек и вычисляется значение функционала Я Это осуществляется процедурой покоординатного спуска, причем если стоимости зависят от положения участка V, то, как указывалось выше, на каждом шаге происходит пересчет стоимостей. Блок заканчивает свою работу, когда разность между последовательными приближениями /?,■_/ - становится меньше заданного 5.

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

Рисунок 3. - Эндогенные и экзогенные условия синтеза РГРС

В диссертации проводится анализ процессов и связей, определяющих влияние выделенных подсистем на функционирование РГРС.

Каждый иерархический уровень транспортирующих газовых сетей в соответствии со специфическими для него назначением и задачами имеет характерную структуру, отражающую определенный способ компоновки и связи основных компонентов и объектов данного уровня Иерархическая топология региональных сетей газоснабжения обусловливает генеалогический принцип построения дерева ее графа- все потребители цепочками различного числа звеньев и длины подсоединены к единому источнику - входу от магистрали высокого давления Если таких входов несколько, их можно условно соединить либо с одним наиболее ранним или исходным, либо с фиктивным общим источником На основании сделанных в диссертации предпосылок постановка задачи синтеза и оптимизации РГРС может быть представлена следующим образом Имеется множество Г точек на плоскости, отображающих расположение потребителей и источников газа Требуется связать их сетью прямолинейных отрезков, идущих от точки к точке таким образом, чтобы длина сети была минимальной Примеры таких сетей для случая произвольной прокладки магистралей и соответствующей этому евклидовой метрики расстояний Е2, возможной, в частности, в сельских районах и для манхэтгенской (прямоугольной) метрики М2 в условиях плотной городской застройки и прокладки магистралей вдоль улиц и кварталов, пересекающихся под прямыми углами

В третьей главе «Теоретико-графовые модели и алгоритмы оптимизационных задач РГРС» формализована модель оптимизации распределительно-транспортной системы, разработан алгоритм оптимизации РГРС как кратчайшей связывающей сети, разработан алгоритм оптимизации РГРС с точками Штейнера

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

Для постановки задачи оптимизации в отношении РГРС необходимо ввести следующие определения

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

Узловые точки (узлы) показывают места присоединения сети к источникам и потребителям, а также разветвления сети и имеют свои координаты расположения

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

При постановке задачи также приняты следующие допущения

1) рассматриваются сети, имеющие топологию деревьев,

2) в сети имеется только один источник, причем поток, выходящий из источника, равен сумме потоков, подаваемых потребителям (требование сохранения потока)

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

Пусть в некоторой системе координат на плоскости расположены множество точек A{a¡, а2, , а„}, которые описывают положение конечных потребителей газа в обслуживаемом регионе Связывающей сетью для точек на плоскости называется дерево Т с вершинами в этих точках Задача состоит в том, чтобы связать заданное подмножество полюсов X с А, представляющих стоки (потребителей) данной сети и, возможно, некоторые дополнительные точки с источником сетью Т прямолинейных звеньев трубопроводов, обеспечивающих транспортировку и распределение продукта таким образом, чтобы доставить экстремум некоторому целевому функционалу Другие вершины, принадлежащие А—Х, могут либо стягиваться деревом Т, либо нет, в зависимости от ограничений целевого функционала В частности они могут быть выражены в форме бюджетных ограничений на величину капиталовложений в строительство новых ветвей газопроводов или размеров квоты объемов отпускаемого региону газа

Пусть S — произвольная трубопроводная сеть, соединяющая п исходных объектов В качестве ее модели с учетом сделанных предположений рассматривается набор {А, X, Т, q, р, D, С, В}, определяемый следующим образом

1 Множество А = {ai, а2, , а„}, — набор точек на плоскости (евклидовой метрики - Е2 или манхэттенской метрики - М2), координаты которых описывают расположение всех заданных (потенциальных или уже подключенных) исходных терминальных объектов трубопроводной сети S; множество A ={a„+i, а„+2, , а„+т} - набор дополнительных точек (точки Штейнера) из Е2 или М2, описывающих расположение разветвлений сети S, множество A U А" =А =fa¡, а2, , а„, ап+!, ап+2, , а„+„,} - множество, составленное из наборов терминальных и дополнительных точек

2 Множество X = {a¡, а2, , ак} представляет собой подмножество множества Á исходных объектов Х^А, покрываемых данной сетью и является результирующим вектором для определения величины дохода, затрат и прибыли от реализации природного газа в данном регионе, оно также обусловливает структуру дерева Т

3 Сети S ставится в соответствие граф Г так, чтобы каждому узлу С, сети S отвечала вершина г графа Т и каждой паре узлов С„ С„ соединенных связью, соответствовало ребро (г, j) графа Т Будем говорить, что граф Т определяет структуру сети S Пусть С - множество всех пар (i,j), i,j С А и С'СС- множе-

ство таких пар, каждая из которых является дугой дерева Т Граф Т(А) для точек множества Л определяется матрицей смежности дерева Z = |z„|, i,j С А

fl, если (г,у)еГ и [0, в противном случае

4 Для любой пары точек и = (ah а2, , а„) CP, v = (f}h р2, , fij СР функция p(u,v) определяет метрику плоскости, т е задает кратчайшее расстояние между точками и и v, которое может быть реализовано некоторой трассой Обычно в практике проектирования сетей используются евклидова метрика Е2

и прямоугольная (манхэтгенская) М2

п

p(u,v) = Y\a,~P\ 1=1

(для плоскости п = 2)

Задача отыскания оптимальной топологии и размещения объектов газораспределительной сети состоит в нахождении структуры сети Т, выделения подмножества потребителей X ^А, а также расположения дополнительных точек ветвления АСА и набора диаметров D таких, чтобы для заданных A, q, р имело место

F(A"*,Х*, Т*, D*, q, р, В) = max F(A, Т, D, q, р, В)

ХСА',А", T,D

при выполнении следующих условий

а) граф Г является деревом

Xzy>l VjeA, j*i0,

i,j jeA

zye{0,1}, I Ф], {Xv=\}=>{xv}Vi,jeA,

ieA" keA

б) множество висячих вершин T соответствует множеству А9

ieA'

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

Решению непрерывных и дискретных задач размещения на плоскости в настоящее время посвящено много работ Однако методы решения смешанных дискретно-непрерывных задач разработаны в значительно меньшей степени В

диссертации предложены алгоритмы для решения смешанных оптимизационных задач размещения объектов с учетом перечисленных особенностей Алгоритм их решения содержит три этапа 1) построение кратчайшей связывающей сети (ЖТ) без введения дополнительных узлов, 2) оптимальное расположение полученных промежуточных узлов сети - задача Штейнера и 3) оценка стоимости связей, дохода и максимизация целевого функционала

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

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

На основании проведенного анализа свойств точек Штейнера и условий проектирования РГРС в диссертации был разработан алгоритм модифицированного покоординатного спуска, предусматривающий включение только тех дополнительных точек, которые увеличивают эффективность дерева Штейнера Следовательно, возможно получение неполного дерева Штейнера в отличие от традиционного алгоритма покоординатного спуска, предполагающего нахождение полного дерева Штейнера, не всегда улучшающего ЖГ Предлагаемый в диссертации эвристический алгоритм модифицированного покоординатного спуска представляет последовательность следующих операций, проводимых после нахождения оптимальной сети без точек Штейнера, которую мы в данном случае будем называть О-решением

На территории размещения РГРС наносятся потенциальные точки Штейнера, в качестве которых выступают узлы наложенной на нее координатной сетки с заданным шагом Из этих узлов выделяются те, которые отвечают признакам точки Штейнера Затем рассчитываются значения длин множества сетей, в каждую из которых входит только одна из выделенных точек Штейнера В свою очередь из полученного множества значений, выделяются те варианты сети и, соответственно, точки Штейнера, которые обеспечивают решения более эффективные, чем 0-решение Выделенная таким образом совокупность точек Штейнера уже позволяет перейти к поиску оптимальных решений, предусматривающих различные сочетания этих точек В реальных условиях точек Штейнера может оказаться слишком много, чтобы найти глобальный оптимум пря-

1 См Прим Р К Кратчайшие связывающие сети и некоторые обобщения /Кибернетический сборник, Новая серия Вып 2,-М Мир, 1961 С 95-107, KruskalJB J On the Shortest Subtree of Graph and the travelling Salesmen Problem /Procession American Mathematics Society 1956 №7 P 43-62

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

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

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

В четвертой главе «Программное обеспечение и решение задач оптимизации РГРС» разработано программное обеспечение решения задачи Штейнера при оптимизации РГРС с различными метриками, проведены численные эксперименты по оптимизации участков реальных РГРС по предложенным моделям и алгоритмам оптимизации с евклидовой и манхэттенской метриками

Для реализации разработанных алгоритмов нахождения SST сети разработано оригинальное программное обеспечение на языке FORTRAN в среде программирования FORTRAN-32 WORKSTATION Эти программы позволили провести численные эксперименты по решению примеров оптимизации РГРС для конкретных ситуаций Программное обеспечение выполнено из отдельных блоков и процедур, что позволяет строить из них различные программы, приспосабливая к разным постановкам задачи Блочная структура дает возможность также легко расширять «библиотеку» процедур с тем, чтобы охватить новые постановки задач Поэтому программное обеспечение выполнено таким об-

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

Разработанное программное обеспечение решения задачи Штейнера для оптимизации РГРС состоит из трех основных блоков 1) процедуры формирования списка эффективных точек Штейнера для евклидовой метрики, 2) процедуры формирования списка эффективных точек Штейнера для манхэттенской метрики, 3)процедуры покоординатного спуска для сформированного на предыдущем шаге списка эффективных точек Штейнера

На основании полученных программ был проведен ряд численных экспериментов, обеспечивших проверку работоспособности, быстродействия и точности алгоритмов, а также выбор шаг решетки Рассмотрим в качестве иллюстрации работы предлагаемого алгоритма в продолжение также рассмотренного в диссертации решения задачи Штейнера для РГРС Шенталинского района Самарской области, метрика которого является евклидовой

Шаг 1 Решение задача нахождения SST для сети, определяемой множеством терминальных точек РГРС Шенталинского района Из полученного ранее решения следует, что длина исходного SST, являющаяся базовой для оценки эффективности введения точек Штейнера составляет 33,27 уел ед

Шаг 2 В рассматриваемом примере величина шага прямоугольной сетки, накладываемой на территорию района, составляет 10X10 В каждом узле этой сетки последовательно располагается дополнительная точка с координатами (x,,yj и рассчитывается длина SST

На рисунке 4 даны послойные срезы - сечения этой поверхности плоскостями, параллельными ZOY с шагом, равным 1 уел ед Фактически мы получили значения длин 100 вариантов кратчайших остовных деревьев — локальных оптимальных сетей РГРС, каждая из которых включает только одну дополнительную точку Вся совокупность полученных значений эффективности этих деревьев показана на трехмерной диаграмме рисунка 5

На последующих 4-х шагах из 100 были выделены 20 точек, обладающих признаком точки Штейнера

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

В диссертации изложен аналогичный численный эксперимент оптимизации сети с манхэттенской метрикой введением в нее точек Штейнера на примере участка РГРС Сергиевского района Самарской области

В целом по рассмотренным примерам использование предложенных моделей оптимизации РГРС позволяет снизить длину участков РГРС Шенталинского района на 26,5% и РГРС Сергиевского района на 30,0% по сравнению с существующими сетями

36.0 35.5 35,0 I 34.5

'О

| 34.0 ^ 33.5 33.0 32,5

Рисунок 5. - Пространство множества оценок эффективности РГРС Шенталинского района Самарской области с одной точкой Штейнера

ЗАКЛЮЧЕНИЕ

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

2 3 4 5 6 7 8 9 10 12 3 4 5 ^678

Рисунок 4. - Срезы эффективности РГРС Шенталинского района Самарской области с одной точкой Штейнера для различных уровней У (—0---длина 55Тсети без точек Штейнера)

37

36.5

36

35,5

= 35

о 34.5

г 34

<=Т 33,5

33

35,5

-с

£ 35 ¡34.5

в 34

■5:33,5

35,5 . 35 а.34,5

£ 34

и о

|33,5 33

36,5 36 ^35,5

^ тс

к 35

|34.5

о

Я

г 34 ^3,5 33

методики их проектирования и эксплуатации во многом основываются на эмпирическом опыте и использовании упрощенных математических моделей, адекватных алгоритму конкретных АСУ и оптимизирующих функциональные характеристики отдельных элементов сети, но не условиям реальных РГРС и не обеспечивающих минимизацию морфологических, наиболее капиталоемких параметров, таких как топология и длина сети в целом При этом, основные показатели и, соответственно, методы анализа любой индустриальной, в том числе -газораспределительной системы следует разделить на две группы - морфологические и функциональные Морфологические свойства, определяющие характер связей - топологию - объектов системы, характеризуются в экономических категориях как вложения в основные средства, а функциональный аспект отражает протекание физических потоков и связанные с этим эксплуатационные затраты В случае газораспределительных сетей издержки морфологической группы значительно превышают функциональные

2 Исследованы методы анализа сетей и теории графов в принятии управленческих решений

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

4 Выявлены системные связи и закономерности функционирования РГРС

5 Определены задачи синтеза и оптимизации РГРС Постановка задачи синтеза и оптимизации РГРС в формате теоретико-графовых методов дифференцируется на задачу поиска кратчайшего остовного дерева на этапе предварительной проработки проекта и решение задачи Штейнера на основном этапе определения оптимальной топологии РГРС При этом общую задачу Штейнера необходимо рассматривать в следующих постановках- задача Штейнера на плоскости как непрерывная задача для новых РГРС и задача Штейнера на графе, представленном на исходный момент определенной структурой, как дискретная задача для реконструируемых РГРС В свою очередь для проектов «в чистом поле» используется задача с евклидовой метрикой и для проектов на застроенных территориях целесообразно применять решение задачи Штейнера с прямоугольной (манхэттенской) метрикой

6 Формализована модель оптимизации распределительно-транспортной системы Доказано, что задача поиска кратчайшего дерева при проектировании РГРС всегда имеет точное оптимальное решение Задачу Штейнера практических размерностей в реальных условиях РГРС следует отнести к классу 1ЧР-трудных и многоэкстремальных, а ее решение обеспечивает нахождение только локальных оптимумов, что обуславливает необходимость разработки соответствующих эвристических алгоритмов

7 Получены алгоритмы оптимизации РГРС, как кратчайшей связывающей сети При этом, алгоритм решения теоретико-графовых задач оптимизации РГРС содержит три этапа 1) построение кратчайшей связывающей сети (ББТ) без введения дополнительных узлов, 2) оптимальное расположение полученных промежуточных узлов сети - задача Штейнера и 3) оценка стоимости связей, дохода и максимизация целевого функционала

8 Разработано программное обеспечение решения задачи оптимизации РГРС с различными метриками

9 Проведена оптимизация участков реальных РГРС с евклидовой и ман-хэттенской метриками Результаты проведенных численных экспериментов по оптимизации РГРС, проведенные на разработанных в диссертации модели, алгоритмах и программах для ЭВМ, позволяют снизить длину участков РГРС Шенталинского района (евклидова метрика) на 26,5% и РГРС Сергиевского района (манхэттенская метрика) на 30,0% по сравнению с существующими сетями

По теме диссертации опубликованы следующие работы:

1 Забержинский БЭ Эволюционные методы в решении задач оптимизации /Вестник Самарского ГТУ, №15-2002 г. С 49-53 (0,47 п л) Изд-во Самарского ГТУ, 2002

2 Забержинский Б Э Методологические аспекты системного анализа и оптимизации в газовой промышленности /Вестник Самарского ГТУ, №40-2006г С 11-15 (0,46 п л ) Изд-во Самарского ГТУ, 2006

3 Забержинский Б Э Исследование и оптимизация структуры потребителей в системе газораспределения /Ашировские чтения Тезисы докл Междунар на-учно-практ конф Самара 2002 г С 58 (0,11 пл) Изд-во Самарского ГТУ, 2002

4 Забержинский Б Э Перспективные методы для решения задач оптимизации /Инфокоммуникационные и вычислит технологии и системы М-лы Всеросс конф , Улан-Удэ 2003 г Ч 1 С 142-145 (0,42 п л ) Изд-во Бурятского ГУ, 2003

5 Забержинский БЭ Распределение и оптимизация ресурсов в условиях неопределенности /Инфокоммуникационные и вычислит технологии и системы М-лы Всеросс конф Улан-Удэ 2003 г Ч 1 С 141-142 (0,12 п л) Изд-во Бурятского ГУ, 2003 г

6 Забержинский Б Э Постановка задачи оптимизации региональных газораспределительных систем /Инфокоммуникационные и вычислит технологии и системы М-лы II Всеросс конф Улан-Удэ 2006 г Т 1 С 144-147 (0,17 п л) Изд-во Бурятского ГУ, 2006

7 Забержинский БЭ Системные принципы в описании региональных газораспределительных сетей /Актуальные проблемы в строительстве и архитектуре Образование Наука Практика М-лы 63-й Всеросс научно-техн конф по итогам НИР СГАСУ за 2005 г С 338-339 (0,12 п л ) Изд-во Самарского ГАСУ, 2006

8 Забержинский Б Э Системообразующие факторы проекта адаптации региональной газотранспортной сети /Математ моделирование и краевые задачи Труды Третьей Всеросс научн конф 2006 г Ч 2 С 68-72 (0,26 п л) Изд-во Самарского ГТУ, 2006

9 Забержинский БЭ Обоснование алгоритма оптимизации региональной газораспределительной сети /Математ моделирование и краевые задачи Труды четвертой Всеросс научной конф 2007 г Ч 4 С 41-43 (0,14 п л) Изд-во Самарского ГТУ, 2007

Автореферат отпечатан с разрешения диссертационного совета Д212 217 ГОУВПО «Самарский государственный технический университет» (протокол № 12 от 5 октября 2007 г )

Формат 60x90/16 Уел печ JI1 Заказ № 710 Тираж 100 экз

Самарский государственный технический университет Отдел типографии и оперативной печати 443110, г Самара, ул Молодогвардейская, 244

ВВЕДЕНИЕ.

Глава 1. СИСТЕМНЫЙ АНАЛИЗ РЕГИОНАЛЬНЫХ

ГАЗОРАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ.

1.1. Системные проблемы развития региональных газораспределительных сетей.

1.2. Анализ функционирования и развития РГРС.

1.3. Методологические аспекты системного анализа и оптимизации в газовой промышленности.

1.4. Выводы.

Глава II. МЕТОДЫ СИСТЕМНОГО АНАЛИЗА И

ТЕОРЕТИКО-ГРАФОВОГО МОДЕЛИРОВАНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ.

2.1. Методы анализа сетей и теории графов в принятии управленческих решений.

2.2. Системные связи и закономерности функционирования РГРС.

2.3. Идентификация задачи синтеза и оптимизации РГРС.

2.4. Выводы.

Глава III. ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ И АЛГОРИТМЫ

ОПТИМИЗАЦИОННЫХ ЗАДАЧ РГРС.

3.1. Формализация модели оптимизации распределительно-транспортной системы.

3.2. Алгоритм оптимизации РГРС, как кратчайшей связывающей сети

3.3. Алгоритм оптимизации РГРС с точками Штейнера.

3.4. Выводы.

Глава IV. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ И

РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ РГРС.

4.1. Программное обеспечение и решение задач построения SSTYTVC

4.2. Программное обеспечение и решение задачи Штейнера в оптимизации РГРС.

4.3. Выводы.

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

Через систему газопроводов на территории Российской Федерации транспортируется около 400 млрд. куб. м. природного газа. ОАО «Газпром» эксплуатирует свыше 500 тыс. км. газопроводов среднего и низкого давления, свыше 600 газораспределительных станций, обеспечивающие устойчивую подачу газа потребителям. Вместе с тем, при таком мощном развитии газовой промышленности в России до сих пор около 40 городов, 400 посёлков и 26 тыс. сёл ещё не имеют никакого газоснабжения. Уровень газификации природным газом в России составляет немногим более 50%, в том числе в сельской местности - 30%. По данным ОАО «Газпром» в настоящее время износ основных фондов газотранспортных сетей составляет 56%, 14% газопроводов выработали нормативный срок службы. Средний возраст газопроводов близок к 25 годам. В целом по единой системе газоснабжения (ЕСГ) в период до 2010 года потребуется строительство около 28 тыс. км новых магистральных газопроводов. При этом объём планируемого строительства объектов газораспределения фактически совпадает с необходимым объёмом их реконструкции.

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести системный анализ отраслевых особенностей функционирования и методов оптимизации РГРС.

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

3. Провести сравнительный анализ топологий сетей в отношении РГРС.

4. Выявить системные связи и закономерности функционирования РГРС.

5. Определить задачи синтеза и оптимизации РГРС.

6. Формализовать модель оптимизации распределительно-транспортной системы.

7. Получить алгоритмы оптимизации РГРС, как кратчайшей связывающей сети.

8. Разработать программное обеспечение решения задачи оптимизации РГРС с различными метриками.

9. Провести оптимизацию участков реальных РГРС с евклидовой и ман-хэттенской метриками.

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

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

1. Впервые определена структура подсистем и связей РГРС, как открытой системы, что позволяет учитывать реальные связи и процессы, определяющие эффективность функционирования РГРС.

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

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

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

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

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

7. Разработано оригинальное программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с евклидовой и манхэттенской метриками.

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

На защиту выносятся:

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

2. Подсистемы и связи РГРС как открытой системы.

3. Модель оптимизации распределительно-транспортной системы.

4. Алгоритмы оптимизации РГРС как кратчайшей связывающей сети и решения задачи Штейнера.

5. Программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с различными метриками.

Реализация результатов работы. Результаты работы были использованы в ООО «Газнадзор» Заволжский газотехнический центр (г.Самара), ООО «Самарские системы связи» и в учебном процессе ГОУ ВПО «СамГТУ».

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 1-й Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы.» (Улан-Удэ, 2003), Международной научно-практической конференции «Ашировские чтения» (Самара, 2002), П-й Всероссийской конференции с международным участием «Инфокоммуникационные и вычислительные технологии и системы.» (Улан-Удэ, 2006), III-й Всероссийской научной конференции «Математическое моделирование и краевые задачи.» (Самара, 2006), 63-й Всероссийской научно-технической конференции по итогам ПИР СГАСУ «Актуальные проблемы в строительстве и архитектуре. Образование. Наука. Практика.» (Самара, 2006), IV-й Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи.» (Самара, 2007).

Публикации. По теме диссертации опубликовано 9 печатных работ, в том числе две в изданиях, из перечня рекомендованного ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и приложения. Основная часть содержит 145 страницу текста, 51 рисунок и 3 таблицы. Список использованных источников содержит 117 наименований. Приложение выполнено на 3-х страницах.

Основные результаты работы

В процессе проведенных исследований получены следующие результаты.

1. Проведен системный анализ отраслевых особенностей функционирования и оптимизации РГРС.

2. Конкретизированы методы анализа сетей и теории графов в принятии управленческих решений.

3. Проведен сравнительный анализ топологии сетей в отношении РГРС.

4. Выявлены системные связи и закономерности функционирования РГРС.

5. Идентифицированы задачи синтеза и оптимизации РГРС.

6. Формализована модель оптимизации распределительно-транспортной системы.

7. Получен алгоритм оптимизации РГРС, как кратчайшей связывающей сети.

8. Разработано программное обеспечение решения задачи Штейнера при оптимизации РГРС с различными метриками.

9. Проведены численные эксперименты по оптимизации участков реальных РГРС по предложенным моделям и алгоритмам оптимизации с евклидовой и манхэттенской метриками.

Ю.Разработан алгоритм оптимизации РГРС с точками Штейнера.

11.Выявлены системные проблемы развития региональных газораспределительных сетей.

12.Проведен анализ функционирования и развития РГРС на примере ООО Средневолжская газовой компания (СВГК).

13.На основании контент-анализа выявлены сложившиеся методологические аспекты анализа и оптимизации в газовой промышленности.

14.Обоснованы принципы системного анализа и оптимизации в газовой промышленности.

15.Предложена схема алгоритма построения сети, близкой к оптимальной.

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

17. Результаты проведенных численных экспериментов по оптимизации РГРС, проведенные на разработанных в диссертации модели, алгоритмах и программах для ЭВМ, позволяют снизить длину участков РГРС Шенталинского района (евклидова метрика) на 26,5% и РГРС Сергиевского района (манхэттенская метрика) на 30,0% по сравнению с существующими сетями.

ЗАКЛЮЧЕНИЕ

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

2. Исследованы методы анализа сетей и теории графов в принятии управленческих решений.

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

4. Выявлены системные связи и закономерности функционирования РГРС.

5. Определены задачи синтеза и оптимизации РГРС. Постановка задачи синтеза и оптимизации РГРС в формате теоретико-графовых методов дифференцируется на задачу поиска кратчайшего остовного дерева на этапе предварительной проработки проекта и решение задачи Штейнера на основном этапе определения оптимальной топологии РГРС. При этом общую задачу Штейнера необходимо рассматривать в следующих постановках: задача Штейнера на плоскости как непрерывная задача для новых РГРС и задача Штейнера на графе, представленном на исходный момент определенной структурой, как дискретная задача для реконструируемых РГРС. В свою очередь для проектов «в чистом поле» используется задача с евклидовой метрикой и для проектов на застроенных территориях целесообразно применять решение задачи Штейнера с прямоугольной (манхэттенской) метрикой.

6. Формализована модель оптимизации распределительно-транспортной системы. Доказано, что задача поиска кратчайшего дерева при проектировании РГРС всегда имеет точное оптимальное решение. Задачу Штейнера практических размерностей в реальных условиях РГРС следует отнести к классу Л^-трудных и многоэкстремальных, а её решение обеспечивает нахождение только локальных оптимумов, что обуславливает необходимость разработки соответствующих эвристических алгоритмов.

7. Получены алгоритмы оптимизации РГРС, как кратчайшей связывающей сети. При этом, алгоритм решения теоретико-графовых задач оптимизации РГРС содержит три этапа: 1) построение кратчайшей связывающей сети (SST) без введения дополнительных узлов, 2) оптимальное расположение полученных промежуточных узлов сети - задача Штейнера и 3) оценка стоимости связей, дохода и максимизация целевого функционала.

8. Разработано программное обеспечение решения задачи оптимизации РГРС с различными метриками.

9. Проведена оптимизация участков реальных РГРС с евклидовой и манхэттенской метриками. Результаты проведенных численных экспериментов по оптимизации РГРС, проведенные на разработанных в диссертации модели, алгоритмах и программах для ЭВМ, позволяют снизить длину участков РГРС Шенталинского района (евклидова метрика) на 26,5% и РГРС Сергиевского района (манхэттенская метрика) на 30,0% по сравнению с существующими сетями.

1. Акиндинова В.А. Фролов А.Е. Использование методов теории графов для выбора оптимальных маршрутов перекачки газожидкостной смеси в условиях морских месторождений //Нефтяное хозяйство. 2005. №6. С. 22-30.

2. Акофф Р. Планирование будущего корпораций. М.: Прогресс, 1985.

3. Акофф Р., Сасиени М. Основы исследования операций.- М.: Мир, 1971.

4. Ансофф И. Стратегическое управление. М.: Экономика, 1989.

5. Басакер Р., Саати Т.Л. Конечные графы и сети. -М.: Наука, 1974.

6. Берж К. Теория графов. М.: ИЛ, 1962.

7. Берн М.У., Грэм Р.Л. Поиск кратчайших путей //В мире науки. 1989. №3. С. 64-70.

8. Берталанфи Л. История и статус общей теории систем /Системные исследования. -М.: Наука, 1973. С. 20-37.

9. Берталанфи Л. Общая теория систем критический обзор /Исследования по общей теории систем. -М.: Прогресс, 1969. С. 23-82

10. Ю.Бир Ст. Кибернетика и управление производством. М.: Наука, 1965.

11. П.Блауберг И.В., Юдин Э.Г. Системный подход /Философский энциклопедический словарь. -М.: Сов. энциклопедия, 1983. С. 612-614.

12. Болтянский В.Г. Оптимальное управление дискретными системами. М.: Наука, 1973.

13. Бучнев О.А., Маслова О.И., Соколов А.Е. Основные подходы к анализу текущих затрат транспортных организаций //Газовая промышленность. 2004. №6. С. 30-32.

14. Вагнер Г. Исследование операций: В 3-х томах. М. Мир, 1972.

15. Гильберт Э.Н., Поллак Г.О. Минимальные деревья Штейнера. /Кибернитический сборник. Новая серия. Вып. 8. -М.: Мир, 1971, с.19-49.

16. Григорьев Э. П. Теория и практика машинного проектирования объектов строительства. М.: Стройиздат, 1974.

17. Гхосал А. Прикладная кибернетика и ее связь с исследованием операций. -М.: Радио и связь, 1982.

18. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. -М.: Наука, 1990.

19. Данилов-Данильян В. И., Рыбкин А. А. Основные принципы оптимизационного подхода и возможности его реализации /Системные исследования. -М: Наука, 1983. С. 172-196.

20. Данциг Д.Л. Линейное программирование и его применения и обобщения. -М.: Прогресс, 1966.

21. Зайцев И.Д. Теория и методы автоматизированного проектирования химических производств: Структурные основы. Киев: Наукова думка, 1981.

22. Игошин Н.В. Инвестиции. Организация управления и финансирование. М.: Финансы, ЮНИТИ, 2000.

23. Исаев Е.С., Бородавко А.Ю. Выбор оптимальных параметров проектируемых магистральных газопроводов //Газовая промышленность. 2004. №7. С. 47-48.

24. Исаев Е.С., Бородавко А.Ю. Учет и анализ затрат и калькулирование себестоимости в магистральном транспорте газа //Газовая промышленность. 2004. №8. С. 29-33.

25. Исследование операций: В 2-х томах. М.: Мир, 1981.

26. Каравой М Ф Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах //Автоматика и телемеханика. 2005. №2. С. 175-181.

27. Карп Р.П. Сводимость комбинаторных проблем. /Кибернетический сборник. №12. 1975. С. 16-38.

28. Кафаров В. В. Методы кибернетики в химии в химической технологии. М.: Химия, 1976.

29. Кафаров В. В., Дорохов И. Н. Системный анализ процессов химической технологии. -М.: Наука, 1978.

30. Клиланд Д., Кинг У. Системный анализ и целевое управление. М.: «Сов. радио». -1974.

31. Клименко В.А., Красильникова М.В., Комаров В.Н. О разработке и реализации программ газификации Российской Федерации //Газ России. 2005. №5. С. 8-13.

32. Кокстер Г. С. М., Введение в геометрию. М.: Наука, 1966.

33. Концепция развития рынка газа для бытовых нужд. Распоряжение Правительства Российской Федерации от 3 июля 2003 г. № 908-р.

34. Концепция РСПП по реформированию газовой отрасли и развитию рынка газа http://www.gasforum.rU/concept/rspp.shtml#21

35. Кристофидес Н. Теория графов: Алгоритмический подход. М.: Мир, 1978.

36. Куделя В.Н., Привалов А.А. Анализ и синтез информационных систем с применением методов теории графов //Автоматизация и современные технологии. 2005. №5. С.20-24.

37. Курант Р., Роббинс Г. Что такое математика?. М.: Наука, 1970.

38. Кутуков С.Е., Васильев В.И. Элементы искусственного интеллекта в системах сбора, подготовки и транспорта углеводородного сырья /Нефтегазовое дело, 2003.

39. Кучин Б.Л., Седых А.Д., Апостолов А.А. Повышение экономической эффективности реконструкции газотранспортных систем //Газовая промышленность. 2002. №4. С. 67-69.

40. Лившиц В.Н. Оптимизация при перспективном планировании и проектировании. -М.: Экономика, 1983

41. Лившиц В.Н. Системный анализ экономических процессов на транспорте. -М.: Транспорт, 1986.

42. Лотарев Д.Т., Супрун А.В., Уздемир А.П. Локальная оптимизация в задаче Штейнера на евклидовой плоскости //Автоматика и телемеханика, 2004, №7. С. 60-70.

43. Лотарев Д.Т., Уздемир А.П. Размещение транспортных сетей на неоднородной территории //Автоматика и телемеханика, 2002, №7. С. 114-124.

44. Мазур И.И., Иванцов И.М. Безопасность трубопроводных систем М.: Издательский центр «Елима», 2004.

45. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.51 .Матюшечкин В. Газ в энергетической стратегии России Вестник Российского Газового Общества. 2003, №1. С. 15-21.

46. Мелихов А.П., Берштейн Л.С, Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

47. Мещерин И.В., Безкоровайный В.П., Исламова В.Р. Системный подход при управлении процессами проектирования объектов //Газовая промышленность, 2003. №12. С. 50-55.

48. Микаэлян Э.А. Комплексная оценка характеристик газотранспортной системы для ресурсосберегающих технологий //Газовая промышленность. 2005. №7. С. 16-21.

49. Моисеев Н.Н. Численные методы в теории оптимального управления. М.: Наука, 1971.

50. Нутенко В.Я. Использование проблемы Штейнера и её обобщений для решения некоторых задач пространственной экономики. М.: ЦЭМИ, 1968.570 газоснабжении Российской Федерации. Федеральный закон №69-ФЗ от 31 марта 1999 г.

51. Плужников Л.Н., Андреев В.О., Клименко О.С. Применение метода случайного поиска при промышленном проектировании //Изв. АН СССР. Сер. Техн. кибернетика. 1971. № 2. С. 26-33.

52. Попов М.Я., Мартыненко Г.Н. Многофакторный анализ городских систем газоснабжения //Газовая промышленность. 2003. №4. С. 38-44.

53. Прахов И.А. использование графовых моделей при создании прикладных справочных ГИС //Газовая промышленность. 2004. №11. С. 108-109.

54. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. /Кибернетический сборник, Новая серия. Вып. 2, М.: Мир, 1961. С. 95-107.

55. Пути повышения эффективности работы региональной системы газоснабжения ОАО Газпром //Газовая промышленность. 2004. №1. С. 35-41.

56. Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.

57. Садовский В.Н. Диалектика и системный подход /Диалектика и системный анализ. -М.: Наука, 1986.

58. Селезнев В.Е., Алешин В.В., Клишин Г.С. Методы и технологии моделирования газпроводных систем. -М.: Едиториал УРСС, 2002.

59. Столяров Г. Ближе к трубе. Хотят стать химические предприятия Тольятти /Ведомости Поволжье. 8 апреля 2004, №60.

60. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

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

62. Философский энциклопедический словарь. -М.: Сов. Энциклопедия, 1983.

63. Форд J1.P., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966.

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

65. Харари Ф. Теория графов. М.: Мир, 1973.

66. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

67. Худрамова Р.И. Расчет магистрального газопровода с учетом рельефа местности //Газовая промышленность. 2005. №8. С. 68-72.

68. Цыбульник В.Н., Рубель В.В. Комплекс моделирования и оптимизации газотранспортных систем "Астра" //Газовая промышленность. 2006. №1. С. 47-52.

69. Шагинян Н.Э., Замерград В.Э. Мельников А.П. Антерман О.В. Оценка потенциала газоснабжения в регионах России //Газовая промышленность. 2005. №8. С. 44-49.

70. Шамис J1.B. Методы оценки эффективности функционирования производственных структур газовой отрасли //Газовая промышленность. 2005. №2. С. 82-85.

71. Шилов С.В., Локотунин В.И. Структурная реформа в газораспределении: направления развития //Газ России. 2004. №4. С. 2-7.

72. Энергетическая стратегия России на период до 2020 г. Утверждена правительством РФ 28 августа 2003 г. № 1234-р.

73. Эшби У. Введение в кибернетику. М.: ИЛ, 1959.

74. Юдин Д.Б. Исследование операций /Математика и кибернетика в экономике. -М.: Экономика, 1975.

75. Якименко А.А. Особенности совершенствования системы управления газотранспортным предприятием //Газовая промышленность. 2004. №8. С. 76-82.

76. Ярыгин Ю.Н. и др. Перспективы использования СПГ и КПГ в качестве газомоторного топлива и как энергоносителя //Газ России. 2005. №4. С. 32-34.

77. Bazarra М., Jarvis J.J. Linear Programming and Network Flows. New York: Wiley, Inc., 1978.

78. Breadley G.H., A Survey of Deterministic Networks //AIIE Transactions. 1975. №7. P. 222-234.

79. Change S.-K. The generation of minimal trees with Steiner topology //ACM. 1972. №19. P. 699-709.

80. Charnes A., Cooper W.W. Managment Models and Industrial Applications //Linear Programming. 1961. Vols. 1-2.

81. Cockayne E. J. On the efficiency of thefalgorithm for Steiner minimal trees //SIAM. Applied Mathematics. 1970. №18. P. 150-167.

82. Cockayne E. J., Melzak Z. A. Steiner's for problem set terminals //Quart. Applied Mathematics. 1968. №26. P. 213-223.

83. Dreyfus S.E., Wagner R.A. The Steiner problem in graphs. //Networks. 1972. №1. P. 195-212.

84. Elmagraby S., Some Networks Models in Management Science. New York: Springer Verlag, Inc., 1970

85. Euler L. The Konigsberg Bridges //Scientific American. 1953. №189. P. 66-70.

86. Fulkerson D.R., The Flow Networks and Combinatorial Operation Research //American Mathematical Monthly. 1966. №73. P. 115-138.

87. Gilbert E.N. Minimal Cost Communication Networks //Bell System Technological Journal. 1967. Vol.7, №9. P.48-50.

88. Hakimi S.L. Steiner's problem in graphs and its implications //Networks. 1971. №1. P. 113-124.

89. Hitchcock F.L. The Distribution of a Product from Several Sources in Numerous Localities //Journal of Mathematics and Physics. 1941. №20. P. 224230.

90. Jensen P.A., Barnes W. Network Flow Programming. New York: Wiley, Inc., 1980.

91. Koopmans T.C. Optimum Utilization of the Transportation System /Proceedings of the International Statistical Conference. Washington, D.C., 1947.

92. Kruskal J.B.J. On the Shortest Subtree of Graph and the travelling Salesmen Problem. /Procession American Mathematics Society. 1956. №7. P. 43-62.

93. Melzak Z. A. (1961), On the problem of Steiner /Canadian Mathematical Bulletin, 1961. №4. P. 335-351.

94. Pritsker A.A.B., Happ W.W. GERT: Part I Fundamentals //Journal of Industrial Engineering. 1966. Vol. 17, №5. P. 267-292.

95. Whitehouse G.W. System Analysis and Design Using Network Techniques. -New York: Prentice-Hall, Inc., Engelwood Cliffs, 1973.

96. Работы автора по теме диссертации:

97. А1.3абержинский Б.Э. Эволюционные методы в решении задач оптимизации. /Вестник Самарского государственного технического университета, 2002 г. №15 С. 49-53: Издательство Самарского ГТУ, 2002.

98. А2.3абержинский Б.Э. Методологические аспекты системного анализа и оптимизации в газовой промышленности. /Вестник Самарского государственного технического университета, 2006 г. №40 С. 11-15: Издательство Самарского ГТУ, 2006.

99. АЗ.Забержинский Б.Э. Исследование и оптимизация структуры потребителей в системе газораспределения. /Ашировские чтения. Тезисы докладов. Международная научно-практическая конференция. Самара 2002 г. С. 58: Издательство Самарского ГТУ, 2002.

100. А4.3абержинский Б.Э. Перспективные методы для решения задач оптимизации. /Инфокоммуникационные и вычислительные технологии и системы.

101. Материалы Всероссийской конференции, Улан-Удэ 2003 г. Ч. 1. С. 142-145: Издательство Бурятского ГУ, 2003.

102. А9.3абержинский Б.Э. Обоснование алгоритма оптимизации региональной газораспределительной сети. /Математическое моделирование и краевые задачи. Труды четвертой Всероссийской научной конференции 2007 г. Ч. 4. С. 41-43: Издательство Самарского ГТУ, 2007.