Содержание к диссертации
Введение
Глава 1. Системный анализ региональных газораспределительных сетей 9
1.1. Системные проблемы развития региональных газораспределительных сетей 9
1.2. Анализ функционирования и развития РГРС 15
1.3. Методологические аспекты системного анализа и оптимизации в газовой промышленности 24
1.4. Выводы 35
Глава II. Методы системного анализа и теоретико-графового моделирования распределительных сетей 38
2.1. Методы анализа сетей и теории графов в принятии управленческих решений 38
2.2. Системные связи и закономерности функционирования РГРС 58
2.3. Идентификация задачи синтеза и оптимизации РГРС 66
2.4. Выводы 79
Глава III. Теоретико-графовые модели и алгоритмы оптимизационных задач РГРС 82
3.1. Формализация модели оптимизации распределительно-транспортной системы 82
3.2. Алгоритм оптимизации РГРС, как кратчайшей связывающей сети 88
3.3. Алгоритм оптимизации РГРС с точками Штейнера 91
3.4. Выводы 102
Глава IV. Программное обеспечение и решение задач оптимизации РГРС 104
4.1. Программное обеспечение и решение задач построения SST РГРС 104
4.2. Программное обеспечение и решение задачи Штейнера в оптимизации РГРС 117
4.3. Выводы 130
Заключение 132
Основные результаты работы 134
Список сокращений 136
Список использованных источников
- Системные проблемы развития региональных газораспределительных сетей
- Методологические аспекты системного анализа и оптимизации в газовой промышленности
- Методы анализа сетей и теории графов в принятии управленческих решений
- Формализация модели оптимизации распределительно-транспортной системы
Введение к работе
Актуальность темы исследований. Газовая промышленность является одной из системообразующих отраслей РФ, обеспечивающих рост национальной экономики, а также решение ряда социальных, геополитических и экологических задач. В силу этого вопросы разработки программ развития газовой отрасли в целом и региональных газораспределительных сетей (РГРС), в частности, должны рассматриваться исключительно с позиций системного анализа, учитывая реальные условия всех подсистем поставщиков и потребителей газа.
Через систему газопроводов на территории Российской Федерации транспортируется около 400 млрд. куб. м. природного газа. ОАО «Газпром» эксплуатирует свыше 500 тыс. км. газопроводов среднего и низкого давления, свыше 600 газораспределительных станций, обеспечивающие устойчивую подачу газа потребителям. Вместе с тем, при таком мощном развитии газовой промышленности в России до сих пор около 40 городов, 400 посёлков и 26 тыс. сёл ещё не имеют никакого газоснабжения. Уровень газификации природным газом в России составляет немногим более 50%, в том числе в сельской местности - 30%. По данным ОАО «Газпром» в настоящее время износ основных фондов газотранспортных сетей составляет 56%, 14%» газопроводов выработали нормативный срок службы. Средний возраст газопроводов близок к 25 годам. В целом по единой системе газоснабжения (ЕСГ) в период до 2010 года потребуется строительство около 28 тыс. км новых магистральных газопроводов. При этом объём планируемого строительства объектов газораспределения фактически совпадает с необходимым объёмом их реконструкции.
Выполнение таких масштабных и капиталоёмких работ (затраты на укладку 1 км газопровода РГРС составляют около 1,5 млн. руб.) по строительству и реконструкции газораспределительных сетей необходимо проводить на основании методов системного анализа и математического моделирования, обеспечивающих оптимизацию технико-экономических
параметров РГРС. Отсюда вытекает необходимость научного обоснования вопросов формализации и постановки задач системного анализа, оптимизации, разработки специального математического и программного обеспечения принятия решений при проектировании строительства и реконструкции РГРС.
Целью настоящей диссертационной работы является: разработка методики, моделей, алгоритмов и программного обеспечения решения задач оптимизации региональных газораспределительных сетей, на основании методологии системного анализа отраслевых особенностей их функционирования.
Для достижения поставленной цели необходимо решить следующие задачи:
Провести системный анализ отраслевых особенностей функционирования и методов оптимизации РГРС.
Исследовать методы анализа сетей и теории графов в принятии управленческих решений.
Провести сравнительный анализ топологий сетей в отношении РГРС.
Выявить системные связи и закономерности функционирования РГРС.
Определить задачи синтеза и оптимизации РГРС.
Формализовать модель оптимизации распределительно-транспортной системы.
Получить алгоритмы оптимизации РГРС, как кратчайшей связывающей сети.
Разработать программное обеспечение решения задачи оптимизации РГРС с различными метриками.
Провести оптимизацию участков реальных РГРС с евклидовой и ман-хэттенской метриками.
Методами исследований являются: общая теория систем, кибернетические методы, методы теории управления, методы системного
анализа и оптимизации в управлении, методы исследования операций, контент-анализ, методы теории сетей и теории графов.
Научная новизна результатов исследования состоит в разработке методики оптимизации РГРС, как совокупности методов системной идентификации и формализации модели оптимизации РГРС, разработки алгоритмов и программного обеспечения её реализации, обеспечивающих получение оптимальных решений проектов новых и реконструкции существующих участков РГРС с учётом реальных условий трассировки газопроводов. Конкретные элементы новизны состоят в следующем.
Впервые определена структура подсистем и связей РГРС, как открытой системы, что позволяет учитывать реальные связи и процессы, определяющие эффективность функционирования РГРС.
Установлены эндогенные и экзогенные условия синтеза РГРС, что, в отличие от обычно используемой локальной оптимизации отдельных элементов, позволяет определять области существования оптимальных проектов РГРС.
Поставлена задача и формализована модель оптимизации распределительно-транспортной системы, отличающаяся теоретико-графовым подходом и учётом реальной топологии РГРС, что позволяет дифференцировать задачу поиска кратчайшего остовного дерева на этапе предварительной проработки проекта и решение задачи Штейнера на основном этапе определения оптимальной топологии РГРС, обеспечивающее минимизацию наиболее капиталоёмких параметров сети.
Выявлены особенности задачи нахождения кратчайшего остовного дерева и задачи Штейнера для оптимизации РГРС, отличающиеся построением эффективного неполного дерева Штейнера и обеспечивающие разработку эвристических алгоритмов адекватных реальным условиям оптимизации.
Обоснована целесообразность и достаточность нахождения локального оптимума (в отношении количества точек Штейнера и их размещения) и
6 предлагается методика его поиска, отличие которой от существующего метода прямого перебора заключается в том, что полученные точки Штейнера ранжируются по длине сети, а среди них выбирается наиболее эффективная точка и к ней добавляются следующие по рангу и т.д., что позволяет минимизировать затраты машинного времени на решение NP-трудной задачи данного типа.
Разработаны алгоритмы: построения транспортно-распределительной сети, отличающийся от существующих для iVP-трудных задач такого типа, возможностью получения близких к оптимальному решений для сетей с любым реальным количеством терминальных точек; оптимизации РГРС как кратчайшей связывающей сети, отличающийся учётом реальных условий трассировки РГРС и обеспечивающий минимизацию морфологических, наиболее капиталоёмких параметров, таких как топология и длина сети в целом; оптимизации РГРС с точками Штейнера, отличающиеся наложением на план трассировки предложенной прямоугольной сетки, обеспечивающей формирование дополнительных узлов как мест расположения потенциальных точек Штейнера.
Разработано оригинальное программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с евклидовой и манхэттенской метриками.
Практическая ценность результатов исследований заключается в том, что разработанные алгоритмы и программное обеспечение позволяют получать оптимальные решения проектов новых и реконструкции существующих участков РГРС с учётом реальных условий трассировки газопроводов.
На защиту выносятся:
1.Методика оптимизации РГРС как совокупность методов системной идентификации и формализации модели оптимизации РГРС, алгоритмы и программное обеспечение их реализации, обеспечивающие получение
оптимальных решений проектов новых и реконструкции существующих участков РГРС.
Подсистемы и связи РГРС как открытой системы.
Модель оптимизации распределительно-транспортной системы.
Алгоритмы оптимизации РГРС как кратчайшей связывающей сети и решения задачи Штейнера.
Программное обеспечение решения задачи Штейнера и оптимизации РГРС как кратчайшей связывающей сети с различными метриками.
Реализация результатов работы. Результаты работы были использованы в ООО «Газнадзор» Заволжский газотехнический центр (г.Самара), 000 «Самарские системы связи» и в учебном процессе ГОУ ВПО «СамГТУ».
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 1-й Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы.» (Улан-Удэ, 2003), Международной научно-практической конференции «Ашировские чтения» (Самара, 2002), И-й Всероссийской конференции с международным участием «Инфокоммуникационные и вычислительные технологии и системы.» (Улан-Удэ, 2006), Ш-й Всероссийской научной конференции «Математическое моделирование и краевые задачи.» (Самара, 2006), 63-й Всероссийской научно-технической конференции по итогам НИР СГАСУ «Актуальные проблемы в строительстве и архитектуре. Образование. Наука. Практика.» (Самара, 2006), IV-й Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи.» (Самара, 2007).
Публикации. По теме диссертации опубликовано 9 печатных работ, в том числе две в изданиях, из перечня рекомендованного ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и приложения; Основная часть содержит 145 страницу текста, 51 рисунок и 3 таблицы. Список использованных источников содержит 117 наименований. Приложение выполнено на 3-х страницах.
Системные проблемы развития региональных газораспределительных сетей
Газовая промышленность является одной из системообразующих отраслей РФ, обеспечивающих рост национальной экономики, а также решение ряда социальных, геополитических и экологических задач. В силу этого вопросы разработки программ развития газовой отрасли в целом и региональных газораспределительных сетей (РГРС), в частности, должны рассматриваться исключительно с позиций системного анализа, учитывающих цели и ограничения всех подсистем поставщиков и потребителей газа.
Сложившаяся за годы реформ газораспределительная система Российской Федерации представляет собой сложный производственно-технологический комплекс, включающий в себя: 316 газораспределительных организаций (ГРО); около 530 тыс. км. газопроводов среднего и низкого давления; 179 газонаполнительных станций и 234 газонаполнительных пункта. Сырьевая база газовой промышленности оценивается в 47,2 трлн. куб. м причем «Газпром» контролирует из них около 60%. В настоящее время третья часть добытого газа идет на экспорт, а во внутреннем потреблении около 40% идет в электроэнергетику (рисунок 1.1). Газпром обеспечивает поставки газа для выработки более 58% электроэнергии России [25, 35,49, 51, 82, 84, 88].
С 1996 по 2000 г. газификация регионов России проходила в соответствии с разработанной Программой газификации Российской Федерации на 1996-2000 гг. Программа имела большое значение для развития экономики регионов - закладывались энергетическая и технологическая база для развития промышленности и сельского хозяйства, но многие показатели федеральной программы были определены на основе генеральных схем газоснабжения и газификации 10-15-летней давности и не соответствовали рациональной структуре региональных топливно-энергетических комплексов в современных условиях, инвестиционным, ценовым и налоговым условиям, новым техническим решениям, технологиям и оборудованию, не обеспечивали рационального использования газа. 39,7%
Учитывая негативный опыт выполнения Федеральной программы и ранее разработанных региональных программ, Министерство энергетики РФ считает необходимым реализовать новый подход к разработке Генеральных схем газификации регионов, в частности, учитывающий: переход от экстенсивного наращивания объёмов строительства газопроводов к экономически обоснованному формированию программ газификации, направленных на максимальную загрузку действующих газотранспортных мощностей; проведение реконструкции объектов газового хозяйства с большим сроком эксплуатации, замена газоиспользующего оборудования [51].
Приоритетами, в соответствии с утверждённой правительством РФ «Энергетической стратегии России на период до 2020 года» являются: полное и надежное обеспечение населения и экономики страны энергоресурсами по доступным и вместе с тем стимулирующим энергосбережение ценам, снижение рисков и недопущение развития кризисных ситуаций в энергообеспечении страны; снижение удельных затрат на производство и использование энергоресурсов за счет рационализации их потребления, применения энергосберегающих технологий и оборудования, сокращения потерь при добыче, переработке, транспортировке и реализации продукции ТЭК;
Согласно Энергетической стратегии объём переработки газа в целом увеличится более чем в 2 раза. В результате углубления переработки углеводородных ресурсов намечаются рост производства моторного топлива, сжиженных газов и серы, получение полиэтилена и при благоприятной конъюнктуре внешнего рынка - метанола. Также в 1,5-2 раза возрастет использование природного газа - метана на нетопливные нужды [85].
Осознавая неотложность реформирования газовой отрасли, Российский Союз Промышленников и Предпринимателей (работодателей) (РСПП) в инициативном порядке принял решение подготовить собственный вариант Концепции реформы [38]. В ходе деятельности Рабочей группы РСПП рассматривались предпосылки необходимости реформирования газовой отрасли, анализировалась текущая ситуация и перспективы развития, порядок осуществления структурных и организационных изменений и пр. Главной задачей при разработке Концепции реформы являлось соблюдение баланса интересов производителей газа (как ОАО "Газпром", так и независимых), потребителей (к которым относятся десятки тысяч предприятий и большинство населения страны) и государства (поступления от газовой отрасли являются важнейшей составляющей доходной части бюджета).
По мнению РСПП в настоящее время газ в стране используется неэффективно, в том числе и самим ОАО "Газпром". Как было установлено, газопотребление на собственные нужды (50 млрд. куб. м газа в год) превышает западные характеристики в 1,5 раза. Существует значительная зависимость электроэнергетики от газа (как ценовая, так и технологическая). Снижение газопотребления РАО "ЕЭС России" планируется до 60% к 2020 году с 64% 65% в настоящее время. Энергетические установки в России на газе работают с КПД 33%, в то время в Европе этот показатель превышает 55%. Расход газа в металлургии и производстве аммиака в России превышает аналогичные зарубежные показатели в 1,6 - 2,2 раза.
В настоящее время основная часть добываемого в России газа используется в качестве топлива. Объём извлекаемых пропан-бутановых соединений составляет около 36-38% от возможных, этана - только 5-6%. Мощности по переработке газа в России составили к 2001 году 5,1%) от мировых. Кроме того, в России отсутствует промышленное производство сжиженного природного газа (СПГ), в то время как мировой рынок СПГ является самым динамично развивающимся рынком углеводородных энергоносителей. Следовательно, по мнению РСПП, необходимо стимулирование развития газопереработки с целью наиболее полного извлечения всех целевых продуктов, входящих в состав природного газа, их комплексного и рационального использования, переработки газового конденсата, имеющего более высокую рентабельность переработки, чем нефть. Необходимо решать вопросы утилизации и переработки попутного газа, который по официальным данным сжигается в объёмах, превышающих 7 млрд. куб. м в год, и, по экспертным оценкам, может достигать 25 млрд. куб. м с увеличением добычи нефти. Развивать направления переработки газа необходимо в комплексе со стимулированием газосбережения.
Методологические аспекты системного анализа и оптимизации в газовой промышленности
Необходимость использования системного анализа и оптимизационных моделей при разработке и анализе функционирования производственных систем уже давно признана учёными, проектировщиками, производственниками и экономистами всех уровней.
В соответствии с существующими определениями (концептами) [2, 10, 11, 34, 60, 75]: системный анализ - совокупность методологических средств, используемых для подготовки и обоснования решений по сложным проблемам; оптимальное решение - наилучшее, по какому-либо критерию решение из всех допустимых. Известно, что система определяется заданием системных объектов, свойств и связей. Системные объекты - это вход, процесс и выход. Входом называется то, что изменяется при протекании данного процесса. Во многих случаях компонентами входа являются «рабочий вход» (то, что «обрабатывается») и процессор (то, что «обрабатывает»). Выходом называется результат или конечное состояние процесса. Процесс переводит вход в выход. Способность переводить данный вход в данный выход называется свойством данного процесса. Связь определяет следование процессов, т.е. что выход некоторого процесса является входом определённого процесса. Всякий вход системы, является выходом этой или другой системы, а всякий выход - входом. Выделить систему в реальном мире значит указать все процессы, дающие данный выход. Проблемой в системном анализе принято считать ситуацию, характеризующуюся различием между необходимым (желаемым) выходом и существующим выходом. Существующий выход обеспечивается существующей системой. Желаемый выход обеспечивается желаемой системой. Проблема есть разница между существующей и желаемой системой. Условие проблемы представляет желаемую систему. Решение проблемы есть то, что заполняет промежуток между существующей и желаемой системами. Система, заполняющая промежуток, является объектом конструирования и называется решением проблемы. Процесс нахождения решения концентрируется вокруг итеративно выполняемых операций идентификации условий, цели и возможностей для решения проблемы [60,2,4, 34].
В формате модели системного подхода «вход - процессор - выход» элементы системы «газовая промышленность» как подсистемы национальной экономики представляют[А7,А8]: «вход» - природные месторождения и технологические комплексы их добычи, «процессор» - комплекс магистральных трубопроводов и других средств, обеспечивающих транспортировку газа и «выход» - совокупность потребителей газа. В свою очередь каждый элемент как подсистема этой системы может быть так же представлен структурой «вход - процессор - выход», будь то газотранспортная подсистема, компрессорная станция, газоперерабатывающий завод или автомобильная газозаправочная станция. Вместе с тем контент-анализ научно-технических публикаций в специализированных периодических изданиях, сборниках трудов и материалов научно-практических конференций по проблемам газовой отрасли выявил определённую неоднозначность как в интерпретации методологии системного анализа и оптимизационного моделирования, так и их совместной реализации в формате постановки и решения конкретной задачи [22, 42, 53, 54, 58, 59, 62, 64, 67, 71, 80, 81, 83, А2,АЗ,А5,А6]. В данных исследованиях делается попытка обобщить эти противоречия и конкретизировать особенности системной постановки задач на примере регионального газораспределительного комплекса.
Реальная ситуация сложившейся методологии управления - как принимаются решения (методы), что и по каким критериям оптимизируется - в газовой и, в общем случае - нефтегазовой отрасли выглядит следующим образом: «Традиционные методы управления промысловыми и магистральными системами сбора (распределения), подготовки и транспорта нефти, газа и газового конденсата основаны на уникальных знаниях патриархов нефтегазовой отрасли России. Практически в штате каждого предприятия ТЭК можно найти такого «гуру» технологических сетей, обладающего феноменальным набором конкретных управленческих решений для большинства ситуаций, возникающих на производстве» [42, с. 32]. В отношении оптимизации работы сложной газотранспортной системы (ГТС) указывается: «В настоящее время оптимизация проводится диспетчерским персоналом на основе имеющегося опыта и интуиции, так как математическая модель ГТС, работающая в реальном времени, до сих пор пока не создана» [22, с. 57]. В методологическом аспекте исследуемой реальной ситуации следует отметить, что опыт и интуиция диспетчеров признаются в качестве инструментария оптимизации.
Нельзя так же согласиться и с такой методологической предпосылкой: «Между моделью, предназначенной для расчёта и моделирования процессов в ГТС, и моделью, предназначенной для постановки и решения оптимизационных задач для той же системы, есть принципиальные различия. Коротко говоря, математическая модель оптимизации (МО) почти всегда проще» [58, с. 42]. Характерно отсутствие обоснования необходимости и содержания этой дефиниции. Если рассматривать моделирование в системных категориях, то сложность системы определяется количеством элементов, связей между ними и стохастичностью [10, 86]. Расчёт и моделирование процессов связан исключительно с технической, то есть детерминированной системой, в то время как при оптимизации ГТС уже может включать и социально-экономические элементы. Поэтому, в частности по классификации Ст. Вира, деятельность предприятия, относится к очень сложным системам, а составляющие его технологические системы - сложным [10].
Методы анализа сетей и теории графов в принятии управленческих решений
Социально-экономическую систему любого уровня - страна, город, предприятие - отчасти можно рассматривать как систему сетей, предназначенных для транспортирования, передачи и распределения различных ресурсов: энергетических, товарных и информационных. Каждая из таких подсистем имеет весьма сложную структуру и является дорогостоящей, при этом возникает необходимость в эффективном использовании уже существующих и оптимальном проектировании новых технических средств. При проектировании и усовершенствовании больших и сложных систем, а также поиске путей их наиболее рационального использования существенное значение могут иметь методы сетевого анализа.
Основные показатели и параметры любой сети следует разделить на две группы - морфологические и функциональные, отражаемые в экономических категориях как вложения в основные средства и эксплуатационные затраты. Под морфологическими - структурными - характеристиками понимаются объекты сети и их связи. В региональной газораспределительной сети (РГРС) они представлены совокупностью оборудования: автоматические газораспределительные станции (АГРС), компрессорные станции (КС) и т.п. и соединяющих их линий трубопроводов и каналов связи. Оборудование, входящее в состав сети, а также различные её объекты обычно называют узлами. Очевидно, что в случае газораспределительных сетей издержки морфологической группы значительно превышают функциональные. Функциональные характеристики в основном определяют параметры качества обслуживания и показатели эффективности работы сети.
Дифференциация показателей и параметров сети на морфологические и функциональные кластеры на наш взгляд требует и разделения методов их анализа на качественные и количественные. Под качественными методами следует понимать анализ свойств тех или иных структур (морфологии) как способов связи объектов.
В этой связи при рассмотрении структур распределительно-транспортных сетей, к классу которых относится РГРС как совокупность объектов и соединяющих их линий трубопроводов, предлагается использовать понятие топологии. Следует отметить, что проведенный нами контент-анализ достаточно широкого круга публикаций [54, 58, 59, 64, 71, 80, 81, 83 и др.] в области трубопроводных сетей различного назначения показал, при обосновании проектов морфологические свойства таких сетей не исследуется, в то время как термины, определяющие отдельные типы топологий в описании различных трубопроводных сетей используются. При этом рассматривается только функциональная сторона - протекание физических потоков, но не морфологические свойства, определяющие характер связей объектов сети.
В данном случае топология сети - геометрическая форма или физическая связность сети. Топология сети определяется способом соединения ее узлов каналами связи и передачи и характеризует физическое расположение газопроводов, АГРС, КС и др. компонентов сети. Топология сети влияет на: состав необходимого сетевого оборудования; возможность расширения сети (наращиваемость); способ управления сетью; характеристики и параметры сетевого оборудования; надёжность; стоимость; пропускную способность.
В практике проектирования сетей используются следующие базовые топологии: магистральная (bus), звездообразная (star), кольцевая (ring) и древовидная (tree). Все остальные топологии получаются путём комбинацией базовых.
Магистральная (или линейная) топология - это структура при которой источник и концевой потребитель соединены кратчайшим путем - линейной магистралью. Станции (электро- и понижающие газовые подстанции, компьютерные серверы и т.п.), обеспечивающие отвод для промежуточных потребителей, подключаются к магистральному каналу (рисунок 2.1).
Магистральная топология относится к наиболее простым и широко распространенным для нефте- и газопроводов высокого давления, соединяющих месторождения и отдаленных потребителей в первую очередь благодаря своей экономичности. Вследствие этого она употребляется как в глобальных (рисунок 2.2а), так и локальных, в частности региональных сетях (рисунок 2.26). Затраты ресурсов при прокладке магистралей являются очень высокими (в среднем около 1 млн. долл. на 1 км) и оптимизация конфигурации сетей - одна из главных возможностей их сокращения.
Поскольку один общий канал связи (магистраль) используется всеми потребителями сети, такие сети называются также моноканальными. В случаях последовательно соединенных магистральных трубопроводов, как, например, показано на рисунке 2.26, в местах соединения сегментов устанавливаются специальные связующие элементы.
Формализация модели оптимизации распределительно-транспортной системы
В общем случае задача проектирования сложных распределительно-транспортных систем и построения сети трубопроводов на заданной территории состоит в определении топологии и геометрии этой сети, которая связывает источники потоков ресурса с его потребителями, так, чтобы оптимизировать некоторый целевой функционал. В зависимости от особенностей конкретной задачи это может быть, например, максимизация величины прибыли от реализации газа, минимизация длины и стоимости транспортных линий, приведенных или эксплуатационных затрат и т. п. При этом должны выполняться некоторые условия, вытекающие как из технологии и конструктивных особенностей сети, так и из ограничений экономического характера, связанных в основном с дефицитом ресурсов капитала и сырья.
Существующие модели размещения транспортно-распределительной сети формализуются как задача нахождения кратчайшего остовного дерева (SST) в общем случае и задача Штейнера при введении в сеть дополнительных точек. Обе эти задачи в их традиционной постановке предполагают целевую функцию в виде построения связывающего дерева минимальной длины. Под длиной дерева понимается суммарный вес входящих в него рёбер, каждому их которых приписан вес в виде длины или стоимости. Ввиду больших размеров решение таких задач практических размерностей регулярными методами перебора невозможно, поэтому для них разрабатываются эвристические алгоритмы решения.
Для постановки задачи оптимизации в отношении РГРС необходимо ввести следующие определения.
Исходные объекты представляют собой соединяемые сетью терминалы (любые точки сети, в которых происходит преобразование потока газа - АГРС, ГРП, потребители и т.п.) и характеризуются геометрическими параметрами, а также координатами расположения. В больших транспортирующих сетях, к которым относятся РГРС, такие объекты для упрощения задаются точками в рассматриваемой области прокладки трубопроводов.
Узловые точки (узлы) показывают места присоединения сети к источникам и потребителям, а также разветвления сети и имеют свои координаты расположения.
Дуга определяется как участок сети, ограниченный двумя узлами и не содержащий больше никаких узлов.
При постановке задачи также приняты следующие допущения: 1) рассматриваются сети, имеющие топологию деревьев; 2) в сети имеется только один источник, причем поток, выходящий из источника, равен сумме потоков, подаваемых потребителям (требование сохранения потока).
Рассмотрим формализацию задачи синтеза и оптимизации при размещении терминалов трубопроводной системы транспортировки газовых потоков как построения РГРС из прямолинейных отрезков, связывающей источники с потребителями.
Пусть в некоторой системе координат на плоскости расположены множество точек A{aj, а.2, ..., ап}, которые описывают положение конечных потребителей газа в обслуживаемом регионе. Связывающей сетью для точек на плоскости называется дерево Т с вершинами в этих точках. Задача состоит в том, чтобы связать заданное подмножество полюсов X а А, представляющих стоки (потребителей) данной сети и, возможно, некоторые дополнительные точки с источником сетью Г прямолинейных звеньев трубопроводов, обеспечивающих транспортировку и распределение продукта таким образом, чтобы доставить экстремум некоторому целевому функционалу. Другие вершины, принадлежащие А-Х, могут либо стягиваться деревом Т, либо нет, в зависимости от ограничений целевого функционала. В частности они могут быть выражены в форме бюджетных ограничений на величину капиталовложений в строительство новых ветвей газопроводов или размеров квоты объёмов отпускаемого региону газа.
Пусть S - произвольная трубопроводная сеть, соединяющая п исходных объектов. В качестве её модели с учетом сделанных предположений рассматривается набор {А, X, Т, q, р, D, С, В}, определяемый следующим образом.
1. Множество А = {сії, аг, ..., anj, - набор точек на плоскости (евклидовой метрики - Е или манхэттенской метрики - М), координаты которых описывают расположение всех заданных (потенциальных или уже подключенных) исходных терминальных объектов трубопроводной сети S; множество A ={a„+i, ап+2, ..., ап+т} - набор дополнительных точек (точки Штейнера) из Е2 или М2, описывающих расположение разветвлении сети Л; множество A yj А =А ={аі, аг, ..., ап, ап+], ап+2, ..., ап+т} - множество, составленное из наборов терминальных и дополнительных точек.
2. Множество X = {а\, аг, ..., а]} представляет собой подмножество множества ,4 исходных объектов Х А, покрываемых данной сетью и является результирующим вектором для определения величины дохода, затрат и прибыли от реализации природного газа в данном регионе; оно также обусловливает структуру дерева Т.
3. Сети S ставится в соответствие граф Г так, чтобы каждому узлу С/ сети S отвечала вершина і графа Т и каждой паре узлов С„ С,-, соединенных связью, соответствовало ребро (i, j) графа Т. Будем говорить, что граф Т определяет структуру сети S. Пусть С - множество всех пар (i, j), і, j Є А и С QC множество таких пар, каждая из которых является дугой дерева Т. Граф Т(А) для точек множества А определяется матрицей смежности дерева Z = zy, ij Є А:
Похожие диссертации на Системный анализ и теоретико-графовые модели оптимизации региональных газораспределительных сетей
