Содержание к диссертации
Введение
1. Современное состояние проблемы выбора оптимальной структуры тепловой сети 9
1.1. Обоснование выбора объекта исследования 9
1.2. Оптимизация систем теплоснабжения 12
1.3. Выводы по первой главе и постановка задачи исследования
2. Анализ развития тепловых сетей на примере ОАО «МОЭК» 23
2.1. Состояние тепловых сетей на примере ОАО «МОЭК» 23
2.2. Развитие тепловых сетей на примере ОАО «МОЭК» 32
2.3. Выводы по второй главе 37
3. Математическая модель трассы тепловой сети 38
3.1. Выбор математической модели и представления данных трасс тепловых сетей 38
3.2. Определение весовых коэффициентов карт факторов 45
3.3. Расчет ключевых точек 49
3.4. Выводы по третьей главе 55
4. Задача оптимизации структуры тепловой сети 56
4.1. Формулировка задачи оптимизации 56
4.2. Задача целочисленного линейного программирования 62
4.3. Оптимизация вычислений 72
4.4. Выводы по четвертой главе 81
5. Расчет нескольких вариантов структуры тепловой сети 82
5.1. Поиск оптимального решения с внесением возмущений 82
5.2. Получение решения путем последовательного преобразования существующих решений 93
5.3. Выводы по пятой главе 98
6. Реализация методов расчета трассы и структуры тепловой сети в виде прикладных программ 99
6.1. Средства реализации
6.2. Структура комплекса прикладных программ 100
6.3. Элементы реализации ПО
6.4. Выводы по шестой главе 114
Выводы п5
Литература
- Оптимизация систем теплоснабжения
- Развитие тепловых сетей на примере ОАО «МОЭК»
- Определение весовых коэффициентов карт факторов
- Оптимизация вычислений
Введение к работе
Актуальность темы. Современные тепловые сети представляют собой сложные инженерные сооружения. Протяженность городских тепловых сетей от источника тепла до потребителей может достигать десятков километров. Системы централизованного теплоснабжения включают большое число объектов инфраструктуры, таких как насосные станции, тепловые пункты, абонентские вводы и т.д. При проектировании тепловых сетей новых районов важно создание системы централизованного теплоснабжения, которая способна решить задачи теплоснабжения абонентов на высоком уровне, обеспечить максимально низкие цены для потребителей и минимизировать вредное влияние на окружающую среду.
Проектирование, строительство и эксплуатация тепловых сетей осуществляются в условиях изменяющейся тепловой нагрузки, параметров и режимов их работы под воздействием многочисленных внешних и внутренних факторов.
Первым этапом проектирования системы теплоснабжения новых районов является выбор схемы теплоснабжения, структуры и трассы тепловой сети от источника тепла до потребителей. Этот этап оказывает определяющее влияние на строительство и функционирование тепловых сетей в целом. Оптимизация процесса выбора структуры и трассы тепловой сети играет важнейшую роль в снижении финансовых и материальных затрат на сооружение и последующую эксплуатацию сети.
Современные вычислительные технологии дают возможность учитывать всю совокупность пространственных, технических и экономических данных для выбора структуры тепловой сети. В целях эффективного использования инновационного потенциала этих технологий для определения оптимальной трассы и структуры тепловой сети необходима разработка математической модели структуры тепловой сети, а также создание новых и совершенствование существующих методов и алгоритмов, позволяющих производить моделирование и оптимизацию структуры тепловой сети.
Таким образом, определение оптимальной структуры тепловых сетей является актуальной научно-технической задачей.
Цель работы - разработка метода выбора оптимальной по капитальным затратам и получаемым прибылям структуры тепловой сети.
Для достижения указанной цели решались следующие задачи исследования:
разработка методов оптимизации трассы тепловой сети по нескольким критериям одновременно;
разработка математической модели структуры тепловой сети, учитывающей экономические показатели;
разработка численных методов приближенного решения задачи нахождения оптимальной структуры тепловой сети;
разработка эвристических методов улучшения полученной структуры тепловой сети;
разработка методов расчета нескольких вариантов трасс тепловой сети;
создание комплекса прикладных программ, реализующих расчет и оптимизацию структуры тепловой сети.
Научная новизна:
разработан новый подход к выбору оптимальной трассы прокладки тепловых сетей, позволяющий производить оптимизацию трассы одновременно по нескольким критериям. Разработанные методики позволяют выделить ключевые точки прокладки тепловой сети и соединяющие их участки;
рассмотрена задача планирования структуры тепловых сетей с учетом затрат на сооружение сетей. Предложены целевые функции, позволяющие проводить оптимизацию структуры тепловых сетей по дисконтированным доходам, полученным от потребителей тепла, по общей прибыли, а также по доходности инвестированного капитала;
для решения поставленной задачи планирования структуры тепловой сети предложена формулировка задачи оптимизации графа тепловой сети в виде задачи целочисленного линейного программирования. Предложен метод приближенного решения полученной задачи линейного программирования;
для решения проблемы попадания решения в локальный минимум разработан метод, позволяющий улучшить полученные варианты структуры тепловой сети путем варьирования коэффициентов целевой функции, соответствующих дисконтированным доходам, получаемым от потребителей, и стоимости строительства тепловой сети;
разработан метод, позволяющий получать множество трасс тепловой сети, близких к оптимальной и существенно отличающихся друг от друга. Несколько вариантов тепловой сети получаются посредством последовательного преобразования одного имеющегося решения в другое и последующего отбора лучших трасс;
разработан комплекс прикладных программ для расчета оптимальной структуры тепловой сети. Комплекс реализует алгоритмы и методы, разработанные для определения трассы прокладки тепловой сети и дальнейшей оптимизации ее структуры.
Достоверность результатов. Теоретическая часть работы базируется на методах математической статистики и дискретной математики. Основные допущения, принятые при выводе исходных уравнений модели, широко используются в работах других авторов.
Практическое значение и реализация результатов. Разработанные методы расчета и оптимизации структуры тепловой сети могут быть использованы в производственной практике теплоснабжающих предприятий.
Полученные результаты могут быть использованы для обоснования выбора трассы тепловой сети, а также для определения экономической целесообразности подключения потребителей к системе центрального теплоснабжения или строительства локальных котельных.
Материалы исследований используются в лекционном курсе «Теплоснабжение», читаемом на кафедре теплогазоснабжения и вентиляции Юго-Западного государственного университета, а также в дипломном проектировании студентов.
На защиту выносятся:
метод оптимизации трассы тепловой сети по нескольким критериям одновременно;
модель оптимизации структуры тепловой сети с учетом экономических показателей;
методы приближенного решения задачи нахождения оптимальной структуры тепловой сети;
метод, позволяющих вывести полученное решение из локального минимума путем варьирования коэффициентов целевой функции;
метод расчета нескольких вариантов трасс тепловой сети;
комплекс прикладных программ, реализующих расчет и оптимизацию структуры тепловой сети.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на региональном межвузовском семинаре «Моделирование процессов тепло- и массообмена» (Воронеж, 2009-2011 гг.), на 64-66 научных конференциях и семинарах Воронежского государственного архитектурно-строительного университета (Воронеж, 2009-2011 гг.).
Публикации. Соискатель имеет 35 научных работ, из них по теме диссертации опубликовано 4 научных работы общим объемом 24 с. Личный вклад автора составляет 14 с.
Четыре статьи опубликованы в изданиях, включенных в перечень ВАК: «Вестник Московского государственного строительного университета» и «Научный вестник Воронежского государственного архитектурно-строительного университета. Строительство и архитектура».
В статьях, опубликованных в рекомендованных ВАК изданиях, изложены основные результаты диссертации: в работе [1] рассмотрен метод объединения растровых карт в единую карту; в работах [2,3] представлена модель оптимизации структуры тепловой сети с учетом затрат и дисконтированных доходов, а также методы приближенного решения задачи нахождения оптимальной структуры тепловой сети; в работе [4] получена математическая модель выбора оптимальной трассы прокладки инженерных сетей, учитывающая экономическую эффективность вариантов прокладки по чистому дисконтированному доходу.
Объем и структура диссертации. Диссертация состоит из введения, шести глав, основных выводов, списка литературы и приложения.
Диссертация изложена на 128 страницах и содержит 77 страниц машинописного текста, 52 рисунка, 2 таблицы, список используемых источников из 110 наименований и приложение.
Оптимизация систем теплоснабжения
В настоящее время системы теплоснабжения составляют важную часть топливно-энергетического комплекса России. Производство тепловой энергии для систем теплоснабжения представляет собой одного из основных потребителей энергоресурсов нашей страны [54, 60, 83]. Доля теплового хозяйства в потреблении энергоресурсов диктует важность совершенствования и оптимизации тепловых сетей [77, 85].
Тепловые сети представляют собой сложные инженерные сооружения, строительство которых требует выполнения ряда дорогостоящих операций. Из всех инженерных коммуникаций городов тепловые сети являются наиболее дорогими, материало- и трудоемкими при сооружении, поэтому при их проектировании необходимо учитывать требования длительной эксплуатации без проведения ремонтов и перекладок. Кроме того, необходимо учитывать важность сохранения эксплуатационных качеств на всем протяжении срока службы.
Системы теплоснабжения, в отличие от других систем, таких как системы газоснабжения, имеют локальный характер. Однако, несмотря на локальность, суммарное влияние систем теплоснабжения в масштабе страны весьма существенно, поэтому оптимизация тепловых сетей является важным направлением исследований [5, 81].
При проектировании тепловой сети одним из ключевых этапов является выбор схемы тепловой сети. Этот этап в значительной мере определяет многие основные свойства системы теплоснабжения [25, 27]. Системы теплоснабжения должны проектироваться исходя из иерархического построения, то есть, разделения системы на несколько отдельных подсистем, расположенных на разных уровнях иерархии [49]. По своему назначению тепловые сети подразделяются на магистральные, распределительные и ответвления к отдельным зданиям. На высшем уровне иерархии находятся магистральные тепловые сети, соединяющие крупные распределительные сети с источниками тепла. На среднем уровне происходит распределение теплоносителя по сетям более низкого уровня иерархии, к которому относятся распределительные сети. Иерархический принцип построения систем позволяет осуществлять автономное регулирование гидравлического и температурного режима в сетях, находящихся на различных уровнях иерархии. В [27] отмечается, что принципы, используемые при построении систем теплоснабжения высшего, среднего и низшего уровней, существенно отличаются друг от друга.
Кроме уровня иерархии, построение тепловой сети определяется типом сети - радиальным или кольцевым. Кольцевые сети характеризуются прокладкой от источника тепла до потребителей не менее двух магистралей, соединяющихся между собой. Это обеспечивает подачу тепла потребителям не менее чем с двух направлений [61]. Подобные сети обладают высокой надежностью за счет применения принципа резервирования. Этот принцип позволяет продолжать подачу тепла абонентам при отказе некоторых элементов сети. По кольцевой схеме обычно выполняются тепловые сети, относящиеся к высшему уровню иерархии.
Радиальные сети применяются для реализации теплоснабжения в сетях с невысокой нагрузкой. В этих сетях отдельные тепловые магистрали прокладываются от источника тепла до каждого потребителя. Подобные сети обладают невысокой надежностью, поскольку в них трудноосуществим принцип резервирования. Они могут применяться для реализации теплоснабжения в тех случаях, когда источник тепла расположен по центру района. Радиальные сети просты в сооружении и требуют относительно небольших начальных затрат на строительство. Системы теплоснабжения могут быть характеризованы такими показателями, как автономность и централизация [9, 80]. Автономность отражает независимость подсистем в иерархии, а централизация отражает степень централизации распределения тепла потребителям.
При проектировании теплоснабжения новых районов необходимо выбрать источники тепла, которые будут удовлетворять потребности абонентов. Для этого рассматриваются различные варианты структуры системы теплоснабжения. Эти варианты могут отличаться степенью централизации распределения тепла и видом источников тепла [4, 40]. Выбор структуры теплоснабжения зависит от ряда условий. Одним из главных условий является экономическая эффективность снабжения потребителей тепловой энергией. Согласно СНиП 41-02-2003 [70], схема теплоснабжения потребителя тепла определяется путем расчета технико-экономических показателей вариантов и дальнейшего их сравнения. Тем самым выбирается централизованное теплоснабжение от различных источников тепла либо децентрализованные варианты теплоснабжения [11, 55, 56, 57, 78]. Кроме технико-экономических показателей, при выборе схемы тепловой сети необходимо учитывать такие факторы, как требуемый уровень теплоэнергосбережения, надежность сети, безопасность эксплуатации, а также требования экологии. В частности, применение децентрализованного теплоснабжения позволяет достичь снижения потерь тепла и затрат на обслуживание и ремонт тепловых сетей за счет отсутствия внешних тепловых сетей. По этой же причине достигается существенное снижение капитальных вложений при строительстве системы децентрализованного теплоснабжения. В целом, системы децентрализованного теплоснабжения должны разрабатываться и применяться с учетом технологических особенностей процесса выработки тепловой энергии. Все эти особенности должны в обязательном порядке учитываться при проектировании здания под данную схему теплоснабжения.
Развитие тепловых сетей на примере ОАО «МОЭК»
Прокладка тепловых сетей в населенных пунктах должна производиться параллельно линиям улиц и дорог. При этом теплопроводы не должны пересекаться с источниками блуждающих токов. Пересечение же с прочими инженерными сетями должно осуществляться на разных уровнях. При этом должны приниматься меры по устранению негативного взаимного влияния сетей. Среди прочих критериев нужно выделить уклон тепловых сетей, который не должен превышать установленных нормами величин независимо от направления движения теплоносителя и способа прокладки.
В последнее время во многих предприятиях, эксплуатирующих тепловые сети, осуществляется переход к электронным носителям данных о тепловых сетях. Разрабатываемые электронные схемы тепловых сетей, как правило, содержат информацию о технологических элементах, а также основные параметры участков сетей. Осуществляется и перевод в цифровое представление данных, необходимых для определения трассы тепловой сети. Многие организации начинают использовать технологии геоинформационных систем [50, 107] для анализа и обработки пространственных данных о тепловых сетях.
Геоинформационные системы представляют собой средства хранения, анализа и обработки пространственных данных [23, 82, 102, 106]. Геоинформационные технологии могут, в частности, использоваться для обоснования проектных решений и для автоматизации некоторых аспектов проектирования. Ключевым аспектом геоинформационных систем является пространственно-временное положение объекта, которое используется для индексирования всей прочей информации. Как и реляционные базы данных [17, 19, 42, 43], геоинформационные системы могут объединять несвязанную иначе информацию посредством ключевых индексных переменных. Благодаря этому может быть произведен анализ и обработка данных, связанных по пространственно-временному признаку. Это позволяет эффективно применить методы математического моделирования к определению трассы тепловой сети [52, 53, 67].
В общем виде моделирование представляет собой замещение объекта-оригинала моделью и дальнейшее изучение свойств модели. Математические модели являются формализованным математическим представлением моделируемых объектов. Такое представление должно адекватно отражать функционирование объекта-оригинала. При применении математического моделирования для исследования объектов появляется возможность многократного использования модели при различных исходных данных, что является одним из главных преимуществ математического моделирования.
Системы теплоснабжения представляют собой множество разнородных по характеристикам объектов. При проведении математического моделирования целесообразной представляется разработка отдельных моделей для рассматриваемых объектов или систем объектов. При таком подходе система теплоснабжения представляется иерархией моделей [24, 84].
Изучение свойств объекта с помощью математических моделей происходит в несколько этапов [71]. Первым этапом является переход от объекта к его расчетной схеме. Свойства объекта, являющиеся важными в данном вычислительном эксперименте, акцентируются, а те свойства, влиянием которых можно пренебречь, отбрасываются. Затем создается формальное математическое описание расчетной схемы, которое и называют математической моделью. На третьем этапе производится анализ полученной математической модели. В случае обнаружения неточностей или противоречий, происходит корректировка расчетной схемы. На этом этапе из модели могут быть исключены некоторые параметры, слабо влияющие на получение решения. Четвертый этап математического моделирования характеризуется в первую очередь разработкой алгоритма проведения вычислительного эксперимента. На следующем, пятом этапе, полученный алгоритм реализуется в виде компьютерной программы. По результатам расчета, произведенного с помощью разработанной программы, математическая модель может быть скорректирована. Расчет может также выявить недостатки в алгоритме или в его реализации, которые могут потребовать исправления [65]. После устранения выявленных недостатков совокупность модели, алгоритма и программы используется для изучения исходного объекта.
Применение современной вычислительной техники в сочетании с технологиями геоинформационных систем позволяет осуществить тесную алгоритмическую интеграцию разных этапов проектирования тепловых сетей, а также автоматизировать процесс проектирования сетей на разных этапах. Все это позволяет снизить стоимость и улучшить качество проектных решений.
Инженерные сети вообще и тепловые сети в частности отличаются от прочих пространственных объектов, рассматриваемых как субъект геоинформационных систем тем, что инженерные сети в первую очередъ необходимо рассматривать как связный математический граф [79, 91], а не как некоторый пространственный объект. Поэтому к тепловым сетям, представленным в виде графов, возможно применение методов и алгоритмов оптимизации на сетях [12, 22, 46, 58, 63]. Сеть представляется в виде вершин и соединяющих их ребер графа. В зависимости от специфики решаемой задачи вершинам и ребрам могут быть сопоставлены скалярные величины, определяющие прибыли, затраты и другие факторы.
При проектировании тепловых сетей новых районов ставится задача соединения потребителей тепла и источника тепла при выполнении всех поставленных ограничений. Типичными методами, используемыми для решения аналогичных задач в других отраслях, является расчет минимального остовного дерево, нахождение максимального потока, расчет кратчайшего пути и т.д [88, 96]. Каждый из методов обладает своими преимуществами, недостатками и характеризуется областью применения. Задача построения минимального остовного дерева, решаемая методами, предложенными Крускалом [105] и Примем [ПО], и систематизированными Корменом [45], применима лишь для радиальных сетей, поскольку не допускает циклов в графе. В задаче о максимальном потоке каждое ориентированное ребро графа рассматривается как трубопровод, по которому идет транспортировка теплоносителя. Каждый трубопровод имеет собственную пропускную способность. Вершины графа рассматриваются как точки соединения трубопроводов. Решается задача о максимальной скорости передачи теплоносителя от источника к стоку, при которой не будут нарушены ограничения по пропускной способности. Для решения этой задачи используется алгоритм, разработанный Фордом и Фалкерсоном [99]. В задачах, сводящихся к расчету кратчайшего пути, требуется найти минимальную сумму весов всех ребер графа, образующих путь из начальной вершины в конечную. Существует три вариации задачи о кратчайшем пути: 1. Задача о кратчайшем пути в заданную вершину графа; 2. Задача о кратчайшем пути между двумя заданными вершинами графа; 3. Задача о кратчайшем пути между всеми парами вершин графа. Для решения различных вариантов рассмотренной задачи о кратчайшем пути на графе используются алгоритмы Беллмана-Форда [90], Дейкстры [95], Флойда-Варшалла [97], Джонсона [103].
Определение весовых коэффициентов карт факторов
Современные вычислительные технологии дают возможность разработки математической модели для выбора оптимальной трассы тепловых сетей с учетом большого количества влияющих факторов. При разработке математической модели ключевым моментом является выбор соответствующих способов представления исходных данных, модели выбора оптимальной топологии и трассы и расчетных алгоритмов для реализации модели на вычислительных средствах. Сложность выбора численного метода помимо особенностей, присущих топологическим моделям, осложняется наличием большого количества ограничивающих факторов.
Рассмотрим задачу выбора трасс тепловых сетей при проектировании теплоснабжения новых районов как задачу многокритериальной оптимизации, а также возможности ее решения.
Необходимо рассчитать трассу районной тепловой сети от РТС до каждого из абонентов. Сначала рассмотрим подзадачу, заключающуюся в выборе трассы от РТС до одного из абонентов. Рассмотрим эту задачу как задачу оптимизации на графах. Положим набор вершин, нумерованных в произвольном порядке от 1 до п. Каждая пара вершин соединяется друг с другом. Цену перемещения из вершины / в вершину у положим произвольно положительной, не зависящей напрямую от расстояния между верщинами і и у. Получим несимметричную матрицу T=(ty), каждый элемент которой - цена перемещения. Поставим задачу поиска набора вершин, перемещение по которым от вершины 1 до вершины п будет иметь наименьшую цену. Представим сначала задачу в общем виде [15, 89].
Очевидно, что для того, чтобы была достигнута сходимость последовательности {ft{k)}, необходимо максимум п-1 итерация.
Дополним алгоритм запоминанием на каждой итерации ph г = \..п, равного номеру предыдущей вершины в трассе с наименьшей ценой перемещения. Это позволит нам в конце каждой итерации восстановить трассу с минимальной ценой перемещения.
Для решения задачи выбора трассы тепловых сетей указанным методом необходимо в первую очередь определить вершины и ребра графа, по которым будет происходить поиск оптимальной трассы. Наиболее естественным подходом является представление участков тепловой сети прямыми линиями. Каждый участок представляет собой ребро графа, соединяющее две вершины.
Участок всегда имеет в качестве своих конечных вершин два технологических элемента тепловой сети. Такой подход соответствует векторному представлению данных. Пример векторного представления данных при проектировании внутриквартальной тепловой сети приведен на рис. 3.1.
Векторное представление данных тепловой сети. Линиями показаны ребра графа, квадратами - вершины графа. Существенным преимуществом такого представления данных является то что для хранения данных требуется небольшой объем памяти. Кроме того, обеспечивается более высокая точность позиционирования объектов и явлений. Объекты, имеющие линейную структуру, представляются в явном виде, без разрывов. Многие данные, как, например, топология тепловой сети, наиболее естественно представимы в векторной форме. Использование такой формы хранения данных позволяет проводить операции, требующие топологической информации, например, анализ сетей.
К недостаткам относится то, что манипулирование данными в векторном представлении требует сложных алгоритмов и затратно в плане вычислительного времени. Кроме того, хранение данных, расположенных плотно с пространственной точки зрения, реализуется неэффективно. Многие данные, требующиеся для выбора трассы тепловых сетей, например, топографические условия местности, характер планировки и застройки городских районов, размещение надземных и подземных инженерных сооружений и коммуникаций, свойства грунтов и глубина их залегания, а также режим и физико-химические свойства подземных вод, представлены в непрерывном виде и не могут быть эффективно переведены в векторную форму.
При этом каждой ячейке сетки соответствует одинаковый по размерам, но разный по характеристикам участок представляемых объектов или явлений. Существенным недостатком такого подхода является то, что хранение данных требует больших объемов памяти, что особенно неэффективно для данных, сильно разнесенных в пространстве. Граф, используемый при прокладке трассы тепловой сети, образуется из структурированной сетки по следующему правилу: каждая ячейка соединяется ребрами графа с восемью соседними ячейками.
Каждая такая сетка соответствует одному фактору и определяет влияние этого фактора на трассу тепловой сети. Пусть при прокладке учитываются N факторов. Обозначим сетку (или, иначе, растровую карту), соответствующую /-му фактору, как А1. Элементы этой карты обозначим как а1... Чем меньше число тем меньше вероятность, что ячейка с индексами г и j попадет в итоговую трассу, и наоборот.
Факторы могут быть как положительными, благоприятствующими прокладке тепловой сети, так и отрицательными, нежелательными для прокладки тепловой сети. Примером положительного фактора может служить прокладка участков тепловой сети параллельно линиям улиц, дорог и проездов. В качества примера отрицательного фактора можно привести нежелательность прокладки подземных теплопроводов с пересечением источников блуждающих токов. фактору прокладки пример растровой карты, соответствующей параллельно линиям улиц, приведен на рис. 3.3:
Оптимизация вычислений
К сформулированной задаче можно применить несколько методик, описанных в [94]. Эти методики позволяют ускорить вычисление оптимального дерева. Пусть дана вершина х е X, соответствующая потребителю тепла. Пусть эта вершина имеет локальную степень, равную единице, 5(х)=1, то есть, потребитель присоединяется к сети только одним участком тепловой сети. В терминах теории графов этой вершине инцидентно только одно ребро є є Е гт а Ьа G Если с р , то вершина х еX и ребро ееЕ не могут входить в оптимальное решение. То есть, если стоимость строительства участка тепловой сети до потребителя больше, чем ожидаемая прибыль от этого потребителя, то данный потребитель не может входить в оптимальное решение. Это легко объяснимо тем, что если бы вершина х и ребро е входили в решение, то это решение можно было бы улучшить путем их исключения из него. Пример дерева с вершиной, локальная степень которой равна 1, приведен на рис. 4.5: а) до исключения вершины; б) после исключения вершины На рис. 4.5а и рис. 4.56 вершины, представленные окружностями, заполненными темным цветом - это вершины, включенные в текущее решение. Ребра, показанные штрихами и вершины, представленные окружностями, заполненными белым цветом, не являются частью решения. Числа на ребрах -это стоимости строительства участков тепловых сетей, а числа на вершинах -это прибыли, получаемые от подключения соответствующих потребителей к тепловой сети.
Поскольку вершина с прибылью, равной 3, имеет локальную степень, равную единице, то есть, соединена только одним ребром с вершиной с прибылью, равной 5, и стоимость строительства участка сети до вершины с прибылью 3, равна 4, то эту вершину и единственную инцидентную ей дугу можно исключить из решения. Решение, получаемое после удаления этой вершины и соответствующей дуги, представлено на рис. 4.56.
Вышеизложенный метод исключения вершин из решения может применяться итеративно. После очередной итерации в результате удаления вершин и инцидентных им ребер могут образоваться вершины 15(х)=1, которые не рассматривались на предыдущих итерациях. Приведем пример применения такого метода. На рис. 4.6 приведен граф до исключения вершин, а также результаты первой и второй итерации исключения.
После первой итерации удаляется потребитель с прибылью, равной 5, а также потребитель с прибылью, равной 7. В результате этого в начале второй итерации потребителю с прибылью, равной 4, инцидентно только одно ребро графа со стоимостью строительства, равной 6. Поэтому на второй итерации потребителю с прибылью, равной 4, исключается из решения. Исключение потребителя с =0из оптимального решения: а) до исключения потребителя; б) после исключения потребителя
Потребитель с соответствующей ему прибылью, равной 0, приведенный на рис. 4.7а, является листом дерева решения; его исключение из решения приводит к улучшению решения (см. рис. 4.76).
Пусть дана вершина х, локальная степень которой равна 2: 5(х)1=2. Обозначим инцидентные ей вершины как JCI и хг, а соответствующие ребра - в\\ (х, х,) и ег: (х, х2). Пусть также сЄі 0 и сгг 0. Если выполнено условие рх = 0, то либо оба ребра входят в оптимальное решение, либо ни одно из них не входит в оптимальное решение. Это следует из того, что х е X с рх = 0 не может являться листом оптимального дерева. Вершину х можно удалить, вводя при этом новое ребро е\2 и назначая ему стоимость сЄ{ + сеі. Пример такой операции приведен нарис. 4.8: a)
Этот метод можно расширить на вершины со степенью, больше или равной 3: х е Х, ] 5(х) [ 3, рх = 0. При выполнении некоторых условий вершина X будет отсутствовать в оптимальном дереве. Для наглядности рассмотрим сначала случай Ь(х) ]= 3. Обозначим вершины, являющиеся соседями вершины X как Х],Х2 и хз. Обозначим дуги, соединяющие вершину х и вершины хь хг, хз как вh е2 и ез. Обозначим длину кратчайшего пути между вершинами а и Ь как р(а, Ъ). В случае, если выполнено следующее условие: р{хх,х2) + р{хх,хг), min р(х2,х]) + р(х2,х3), кр(х3,хх) + р(х„х2) с +с +. (4.26) то существует более дешевый вариант дерева, и поэтому степень вершины хеХ равна либо 0, либо 1, либо 2. Однако вариант со степенью, равной 1, или 5(х)=1, можно исключить по соображением, изложенным выше. Поэтому справедливы следующие равенства: либо 5(х) = 0, либо 15(х) = 2.
При выполнении неравенства (4.26) мы можем удалить вершину х, а инцидентные ей пары ребер заменить на новые, пример расчета стоимости которых приведен выше. На рис. 4.9 показан пример графа, в котором для потребителя с прибылью, равной нулю, выполняется условие (4.26):
Этот метод может быть применен и к вершинам х е X с Ь(х) 3 в случае, если все ребра, инцидентные вершине х, имеют положительные веса. Однако, в силу того, что количество проверок растет комбинаторно в зависимости от степени вершины х, практическое применение этого метода ограничено вершинами с невысокими локальными степенями.
Еще одним методом, позволяющим оптимизировать решение, является тест кратчайшего пути. Этот тест применим только в том случае, если стоимости, ассоциированные со всеми ребрами, положительны, т.е. саЬ 0 для всех ребер (а,Ь)єЕ. Обозначим через d(a,b) длину кратчайшего пути, проложенного по взвешенному графу G от вершины а к вершине Ъ. В случае тепловой сети, длина кратчайшего пути представляет собой суммарную стоимость строительства участков тепловой сети от потребителя а до потребителя Ъ. Ребро (а,Ь) Е может быть исключено из графа G в том случае, если d(a, Ъ) саЬ, то есть, стоимость строительства тепловой сети от а до Ь, проложенной наименее затратным способом, меньше, чем стоимость строительства участка от а до Ъ. На рис 4.11 приведен пример исключения ребра графа с помощью теста кратчайшего пути:
Ускорить расчет решения можно еще одним способом. На каждой итерации при выявлении ограничений, которые не выполняются, нужно создавать секущие плоскости, в которых вершины, принадлежащие подмножеству, определяющему нарушение ограничения, не будут попадать в другие подмножества, определяющие нарушение ограничения, созданные на данной итерации. Такие секущие плоскости, не имеющие общих переменных, называются ортогональными. Использование ортогональных плоскостей позволяет существенно ускорить вычисление нижних границ LP-релаксаций. Пусть (5с, у) - решение полученной на данной итерации LP-релаксации. Ортогональные секущие плоскость можно получить путем решения задачи (4.20)-(4.22) для графа, дополнительного к решению (х,у). Пусть V -подмножество, соответствующее ограничению, которое нарушено больше других. Это ограничение вносится в многогранную область Рз в качестве секущей плоскости; все вершины, входящие в V, удаляются из дополнительного графа. В результате получается видоизмененный дополнительный граф G s. Эта процедура применяется к графу G s до тех пор, пока существуют ограничения, которые не выполняются.
