Реально функционирующие системы содержат наряду с непрерывной средой, локализованными в пространстве элементами, еще и каналы, по которым транспортируется вещество, энергия, информация и выносятся из системы продукты распада. Вследствие этого задачи оптимального определения конфигурации сети каналов и их параметров являются исключительно актуальными с математической и прикладной точек зрения.
В НИИ прикладной математики и механики КБГУ и НИИ ПМА КБНЦ РАН (г. Нальчик) в 1975;1990 гг. была разработана САПР закрытых оросительных сетей. Этой системой запроектированы и функционируют на Юге России десятки трубопроводных оросительных сетей. В 1993 г. в НИИ ПМА было решено продолжить работу по созданию новых и совершенствованию ранее созданной САПР в связи с появлением новых ЭВМ и компьютерных технологий.
Настоящая работа посвящена разработке новых методов синтеза оптимальных сетей с одним источником и приложению этих методов к оптимальному проектированию трубопроводных оросительных сетей.
Математическая теория сетей начинается с работ Л. Эйлера, Я. Штейнера, Г. Кирхгофа [39, 2]. В работах Р. Прима и И. Краскала построены эффективные алгоритмы определения кратчайшей связывающей сети [39, 40], Е. Дейкстра разработал алгоритм построения кратчайшего маршрута на взвешанном графе между заданными вершинами [39].
Для сетевой транспортной задачи с вогнутой целевой функцией в 1964 г. Хуанг Туй разработал практически эффективный алгоритм решения при числе вершин сети п «100 [23], В. П. Булатов на этой основе развил методы погружения в задачах оптимизации [24].
Переходим теперь к сжатому обзору работ по синтезу сетей для переноса вещества или энергии. Функционирование таких сетей описывается с помощью двух типов сетевых переменных — кинетических (потоковых) и потенциальных. Для этих переменных выполняются соотношения аналогичные уравнениям Г. Кирхгофа для электрической сети.
Дж. Денис показал, что уравнения Кирхгофа эквивалентны принципу минимума диссипации энергии в сети [12].
В работах М. В. Кирсанова, Д. М. Минца, Л. Ф. Мошнина показано, что функция затрат на создание и эксплуатацию сети выпукло по потенциальным и вогнута по кинетическим переменным.
В известной работе Г. Е. Кикачейшвили [25] задача оптимизации разветвленной сети при заданной конфигурации сводится к задаче линейного программирования.
В работах B.C. Михалевича, Н. З. Шора, В. А. Трубина и других сотрудников Института кибернетики Украины задачи синтеза сетей рассматриваются как чисто потоковые (задача определения структуры сети, задача трассировки) и решаются глобально методом последовательного анализа и отбраковки вариантов на заданном геометрическом графе, моделирующем возможные соединения узлов сети друг с другом и с источником сети [22, 28, 42, 43, 44, 45].
В большом цикле работ сотрудников Сибирского энергетического института СО РАН (г. Иркутск) задачи синтеза сетей решаются методом декомпозиции задач по типу переменных [10, 46−50, 24]. При этом на первом этапе решается задача определения конфигурации сети (задача трассировки) на геометрическом графе моделирующем перспективные возможные соединения узлов сети, а на втором этапе определяются параметры ветвей сети. Некоторое обоснование методу декомпозиции задач синтеза сети по типам сетевых переменных представлено в известной работе O.A. Некрасовой и В. Я. Хасилева [27]. В СЭИ на этой основе были разработаны мощные программные комплексы по автоматизированному проектированию трубопроводных сетей.
Следует также отметить направление решения задач синтеза сетей связанное со стремлением свести задачи синтеза сети к обобщенной задаче Штейнера. Для этого решается вначале задача оптимизации параметров ветвей сети на заданной конфигурации (задача оптимизации параметров -«хорошая» задача минимизации выпуклой функции при линейных (сетевых) ограничениях), а затем путем вариации положения точек ветвления сети (точек Штейнера) эта конфигурация и параметры каналов оптимизируются. Такой подход изложен в работах И. Б. Моцкуса, В. Л. Леонаса, В.Л. Шальтя-ниса [51], И. Д. Зайцева, В. Г. Вайнера [52].
В работе [21] предложено вначале решить задачу синтеза сети на геометрическом графе, а затем трансформировать сеть смещением ее точек Штейнера.
В работах сотрудников НИИ Прикладной математики и механики КБГУ и НИИ ПМА КБНЦ РАН (г. Нальчик) разрабатывается иной подход декомпозиции, состоящий в сведении оптимизации сети к оптимизации ее малых, специальных образом подбираемых фрагментов [21, 26, 34, 57, 61].
Переходим теперь непосредственно к содержанию диссертации.
В первой главе дается определение сети, рассматриваются методы решения задачи анализа сети, даются постановки задач синтеза сетей и приводятся существующие методы их решения.
Основная задача синтеза сети ставиться следующим образом: г = с,(р9,щ)1у + рр{&-,£/,) + г ш &trade-п>
1) (2).
3).
4).
5).
— 1″ 1 fijeD, >?/- V/ ц,>0, ZijeD, где: Г (В, Б) — заданный конечный, связный, вообще говоря, двузвенный орграф, моделирующий возможные соединения узлов (вершин) сети друг с другомВ и Б — множества его вершин и дуг-, иу, су, 1у — соответственно искомые значения кинетической (например, ток) и потенциальной (например, напряжение) переменных по у-ой дуге (ветви) сети, ее удельная (на единицу длины) стоимость и заданная длина- ?), их, Р ((21,и1) — заданный поток в сеть, искомые потенциал источника и его стоимостьа, р, у — заданные постоянные коэффициентыgJ-, U", UJ — заданный расход потока, нормативный (заданный) потенциал и потенциал в уом узле (вершине) сети соответственно.
Первый член целевой функции отражает стоимость ветвей сети, второйстоимость источника сети, третий — энергетические затраты на транспорт вещества и (или) энергии от источника к потребителям (узлам, вершинам).
Ограничения (2), (3) учитывают законы теории сетей, (2) и (4) — требования по обеспечению потребителей сети потоками и нормативными значениями потенциалов.
Удельная стоимость ветви сети имеет вид с0(ии'°ч)' если ииц оо, если 1) у>0 и иу ?[и, и+], (6).
О, если и. = О, где диапазон [и, и+] отражает физическую либо техническую невозможность обеспечения иных значений иу при оу > 0.
Можно показать, что су (иу, иу) есть непрерывная, вогнутая и возрастающая по иу, выпуклая и убывающая по иу функция, а стоимость источника Р (Я, и) будем считать (как это и имеет место на практике) непрерывной, выпуклой и возрастающей по их функцией. Вследствие таких свойств целевой функции задача (1) — (5) является многоэкстремальной.
Существующие методы решения задачи основаны на ее декомпозиции по типу переменных на две подзадачи и состоят в следующем. Несмотря на то, что стоимость ветви сети зависит существенно от обоих типов сетевых переменных, то есть cfj =, полагают вначале су = су (о^)и решают задачу на минимум вогнутой функции ^ на транспортном многогранijeD нике (2), (5), а затем, найдя глобальное (либо близкое к нему) решение и*}. d этой многоэкстремальной задачи, переходят к решению простой задачи на минимум выпуклой функции.
Z, Щ) hj + /Р (б,>Ux) + yQxUxt (7) ijsD' где D' - множество дуг графа T (B, D), по которым поток оказался отличным от нуля) при линейных ограничениях (3), (4).
Показано, что, в основе такого подхода лежит замена уравнений Кирхгофа (2), (3) неэквивалентным следствием — системой, содержащей только узловые уравнения (2) и закон сохранения энергии. Вследствие этого даже глобально-оптимальное решение этих двух задач не гарантирует получение хотя бы локального решения исходной задачи синтеза сети.
В задачах синтеза надежной сети предлагается, что элементы сети могут время от времени выходить из строя. В таком случае сеть должна работать определенное время в аварийном режиме, пока не будут устранены последствия аварии. При работе в аварийном режиме сеть должна обеспечивать хотя бы пониженный уровень требований потребителей. Имеется ряд работ в которых задача синтеза надежной сети рассматривается в вероятностном смысле. Однако получение и обоснование соответствующих данных является, по крайней мере, весьма затруднительным. Другое направление, которое развивается в Институте кибернетики Украины (B.C. Михалевич, Н. З. Шор, В. А. Трубин и др.) состоит в обеспечении надежности сети за счет избыточности ее ветвей. При этом надежной считается такая сеть, которая при выходе из строя любой ее ветви способна обеспечить в узлах потребления хотя бы аварийный уровень потока. Однако и здесь задача синтеза рассматривается как чисто потоковая, то есть как специальная сетевая транспортная задача с вогнутой целевой функцией.
В диссертации задача синтеза надежной сети ставится с учетом обеих типов сетевых переменных.
Разделим потокораспределение в сети на две части — X и У. Каждое из потокораспределений обязано обеспечивать в каждом узле расход не менее аварийного, а оба вместе — нормальный. Не исключено, что оптимальное решение будет содержать две параллельные магистрали, соединяющие узлы / и у сети, по которым протекают соответственно потоки ху и уу. Получаем следующую задачу:
ЦеО.
1]хУ~Ихлс=^> Хл — =Уj еГ7 *еГ7 /еГ* Шу е17 '&-В УуеД и^иЧ, У/'еД х^, У]>ё% где Г (В, И) — заданный конечный, связный, вообще говоря, четырехзвенный орграф1−1- g", gJ — заданные нормальный и аварийный расход в у-ом узле сети.
Задача (8)-(13) представляет собой многоэкстремальную задачу минимизации вогнуто-выпуклой функции при линейных ограничениях.
Во второй главе разрабатывается метод динамической декомпозиции решения задач синтеза сетей.
Вообще, граф содержит дугу (¡-,])Х потока X и дугу (/, у) Г потока У. Но верхний индекс можно не ставить, т.к. всегда из формул ясно, о какой из этих дуг идет речь.
8) (9) (10).
П) (12) (13).
Широко известна эффективность метода динамического программирования оптимизации марковских процессов и примыкающих к нему идейно методов локальных вариаций, последовательного анализа и отбраковки вариантов. Однако эти методы, суть которых состоит в том, что варьируется малая часть переменных при фиксации остальных при продвижении к оптимуму, удается реализовать не для всех задач оптимизации — вариация переменных немедленно сказывается на всех или большинстве остальных переменных. Законами теории сетей являются уравнения непрерывности и потенциальности. Поэтому их структура допускает использование такого подхода. При этом те элементы, которые следует варьировать, размещены на сети компактно. Пусть имеем некоторое допустимое решение задачи. Выделим любую связную часть Г (£,£>). Тогда при изменении значений переменных внутри этой части в широких пределах, на ее границе (а значит, и на всей остальной сети) сохранится прежнее значение переменных. Это свойство и использует метод динамической декомпозиции для последовательного продвижения к оптимуму задачи.
Основой метода динамической декомпозиции служат сформулированные особым образом условия экстремума в задачах синтеза сети. В этих условиях для каждой конкретной сетевой задачи расшифровывается изложенная выше идея сведения оптимизации всей сети к оптимизации ее малых фрагментов. При этом условия экстремума формулируются в удобном для решения сетевых задач виде — на языке теории графов. Для основной задачи синтеза сети (1) — (5) имеет место следующий.
Принцип оптимальности а) Найдется остов Т графа Г (В, Б) и соответствующее ему базисное решение задачи (по потоковым переменным) {и*., иц}?1еЕ), ?/* что у’бО и- = о, щ-ет, где { о у, иу} е ?>, С/1 — любое допустимое решение задачи, б) Пусть Г — любая связная часть графа Т, {ои, йу }у еВ, их =и[- любое такое допустимое решение, что Ц = и у, йу = и1}, МЦ ёГ (Г), где Г (Г') — граф, порожденный на графе Г (5, П) графом Г. Тогда: уеО у ей.
Условие а) сводит процесс оптимизации сети к перебору решений, соответствующих остовным деревьям графа Г (В, И). Однако, даже направленный перебор неосуществим в силу их большого количества, растущего фактори-ально от числа вершин и дуг графа Г (В, Б). Для преодоления «проклятия размерности» используется условие б), сводящие процесс оптимизации сети к оптимизации ее малых частей.
Этот принцип оптимальности был доказан в работе [21]. В диссертации он доказан более просто, что открыло путь для получения 2-оптимального решения задачи, то есть такого, которое оказывается наилучшим не только на симплексе многогранника ограничений задачи с вершиной, соответствующей этому решению, но и на симплексах, примыкающих к нему. С сетевой точки зрения это означает, что такое решение нельзя улучшить не только изменением значений потенциальных переменных, но и заметным изменением ее структуры — внесением в нее одной или двух новых ветвей и удалением ветвей инцидентных внесенным. Переборы новых вариантов структуры (возможно непрозондированных при получении 1-оптимального решения), на которых в принципе может реализовываться 2-оптимальное решение, удалось значительно сократить за счет выделения всех случаев их возникновения. Основным является тот, когда обе вносимые в 1-оптимальный остов хорды замыкают смежные контуры. На этой основе разработан программный модуль, включенный в САПР оросительных сетей головного на Юге России проектного института «Севкавгипроводхоз», позволяющий проектировать сети близкие к глобально-оптимальным. Проведено сравнение с результатами проектирования прежней САПР на реально запроектированных ею в Ставропольском крае сетях. Полученные результаты свидетельствуют о превосходстве новой САПР.
Далее анализируется задача синтеза надежной сети. Главным теоретическим результатом по задаче является следующая.
Теорема. Глобальное решение задачи (8) — (13) существует, локальные и глобальные решения являются базисными по потоковым переменным оптимальным (локально и глобально) потокораспределениям.
X, У соответствуют пара согласованных остовов графа Г (В, П) Тх, Т).
У 5 причем имеет место альтернатива: А.
X. = н, А либо.
УI .
У, = &.
На этой основе с учетом сетевых свойств задачи сформулирован следующий.
Принцип оптимальности * а) Найдутся остовы Тх и Ту графа Г {В, Б) и соответствующее им ба зисное решение (по потоковым переменным) задачи |х* у ео, и 1, что уеО уеО где х* = 0 /у? Т*, Уу = 0 /у? Ту и таковы, что н, а либО ^ Уг 81 [У, а {хи>Уу>щ} у е£>> ихлюбое допустимое решение задачи. * **<�¦ 1 б) Пусть Т’х, Ту — любые связные части графов Тх и Ту, |х (У, уу, иу} у ео> «=г * их=и 1 и ху, Уу, йу} и[ = и — пара любых допустимых решений задачи, но такая задача, что.
ХУ =х1> Уу щ у и ^ * Ху =*1> % = Уу> Цу.
Тогда будут выполнены неравенства: уеО г/'еО уеО у ей где Г (7^), Г (Г/) — графы порожденные на графе Г (В, О) графами * *.
Т’х и Ту соответственно.
Принцип оптимальности позволяет свести оптимизацию надежной сети к оптимизации ее фрагментов, подбираемых специальным образом. На основе принципа оптимальности разработан метод динамической декомпозиции решения задачи, аналогичный методу решения основной задачи синтеза сетей. Метод позволяет получить 1-оптимальное решение задачи.
Далее рассматривается более простая задача синтеза надежной сети, в которой.
У = + (1 — лхя- -gJ), У- = а — я)*- + ^ - >, я е ад.
При этом все потоковые ограничения исходной задачи выполняются автоматически. Показывается, что оптимум в такой задаче реализуется только при 2 = 0 или Я = 1, т. е. потокораспределение нужно выбрать так, что.
IXXX* = > IX — XX* = - § 1 • еГ/ /еГ/ /еГ/ ¡-еГ~.
Тем самым получает некоторое обоснование выбираемое обычно на практике решение: поток X обеспечивает аварийную подачу в узлы сети, а поток У — остаточную, то есть такую, что у, = g" - .
Наконец, рассматривается задача, в которой остовы Тх и Ту совпадают (задача синтеза с дублированием ветвей), поток в Тх обеспечивает аварийную подачу потребителям, т. е., а поток Ту — оставшуюся 01 • Эта ей 1еВ задача сводится к основной задаче синтеза сети.
В третьей главе метод динамической декомпозиции применяется для автоматизированного проектирования на ЭВМ реальных трубопроводных оросительных сетей. Для этого проводится моделирование элементов сетей: их конфигурации, трубопроводов, насосной станции и графиков работы дождевальных установок.
Задача оптимального проектирования ставится при этом следующим образом. Исходя из заданного местоположения гидрантов сети и ее источника, заданного на проектирование сортамента труб с1], с12,., с1к, их удельной стоимости с1, с1,., ск, заданного набора насосно-силовых агрегатов НСА}, НСА2НСА, графика поливов, запроектировать сеть, обеспечивающую на гидрантах заданные напоры и расходы воды и имеющую наименьшие затраты на ее создание и эксплуатацию. Моделирование элементов сети — ее конфигурации, трубопроводов, насосной станции, сезонов полива, приводит к следующей задаче оптимального проектирования сети: г = + РР* + у -> т’т,.
V/? е£> и У/еЯ,.
Я^Л^+Я, Уу е Д Я,>Я?, У/е?,.
Н’е{н., н*}, Р* е{р., р1}.
14).
15).
16).
17).
18) (19) где x’v поток по ijй ветви сети в tй сезон полива, П — множество номеров сезонов полива, zj — высотная отметка jго узла (гидранта) сети.
Задача относится к типу основной задачи синтеза сети и решается на ЭВМ методом динамической декомпозиции до получения 2-оптимального решения. Время счета для средних (30−50 узлов) сетей — 10−30 минут. При этом задача решается перебором по напорам в сеть Н1,., Н', причем на каждом очередном напоре в сеть задача решается с конфигурации и значений потенциальных переменных по ветвям сети, полученной на предыдущем напоре, а сами напоры Н., Н' выстроены по возрастанию.
Далее ставится задача оптимального проектирования оросительной сети для малых (фермерских) хозяйств и приводится входная информация и результаты проектирования этих сетей на разработанной САПР.
Для составления оптимального графика поливов сельхозкультур, произрастающих на территории орошения, решается задача комплектования графиков поливов.
Задача состоит в следующем: Заданы площади St полей на которых произрастает iая культура, i = 1, N и количество поливов каждой iой культуры /,. и.
Определим общее количество поливов a =ifi и с этого момента буi=i дем для удобства считать, что имеем не N, а, а полей. В норме каждое из этих полей нужно поливать в срок zi в течение ti дней. Будем считать, что полив производится квантами (1 день), так что время полива iго поля S g t, = round, где g, — поливная норма на 1 га iго поля, a Q — мощность поливного агрегата (сети).
Поскольку отсутствуют объективные данные по определению издержек от недополива и несвоевременного полива сельхозкультур, то целевую функцию будем подбирать в виде штрафной. Целевая функция будет иметь, а вид YjФ,(zi — t0i, tt, Ai) -" min, где z, — планируемое (искомое начало) орошении iой культуры, tm — нормативное начало, Аi — допустимое запаздывание в сроке начала орошения. К Ф1 предъявляются естественные требования: штраф пропорционален площади полива, ценности культуры, малости при Zjt0j~Ai. Ограничения задачи — обычные временные ограничения, характерные для задач теории расписаний. Приведем одно из них: zM — z, > -очередной полив не может быть начат до того, как закончится предыдущий. Полученная нелинейная целочисленная задача теории расписаний сводится декомпозицией к ряду задач существенно меньшей размерности, точные решения которых находятся методом перебора. Основным понятием, используемым в процессе декомпозиции, является кластер — временной участок соответствующий напряженному участку поливного графика. Приводится точное определение кластера. Решение задачи распадается на ряд этапов: а) Подготовка к основному циклуб) Выделение очередного кластерав) Оптимизация выделенного кластера.
Как известно, существующие методы решения задачи о покрытии множества (а к этой задаче и сводится оптимизация кластера, относящаяся к классу NPполных задач), являются теми или иными разновидностями переборных алгоритмов. Общим методом исчерпывающего поиска является т. н поиск с возвращением. Этот метод и используется при решении задачи.
Подробно излагается алгоритм решения задачи. Составлена программа решения задачи, текст которой приведен в приложении к диссертации. Просчитаны тестовые примеры.
Работа выполнена в НИИ ПМА КБНЦ РАН в отделе САПР смешанных систем.
Основные результаты диссертационной работы состоят в следующем:
Теоретические результаты.
1. По-новому доказан принцип оптимальности для основной задачи синтеза сети, что дало возможность проектировать 2-оптимальные сети.
2. Впервые разработан метод получения 2-оптимальных решений основной задачи синтеза сети.
3. Доказан принцип оптимальности для задачи синтеза надежной сети с одним источником.
4. Предложен метод получения 1-оптимального решения задачи синтеза надежной сети с одним источником.
Практические результаты.
1. Разработан программный модуль, включенный в САПР оросительных сетей головного на Юге России проектного института «Севкавгипроводхоз», позволяющий проектировать сети близкие к глобально-оптимальным. Проведено сравнение с результатами проектирования прежней САПР на реально запроектированных ею в Ставропольском крае сетях. Полученные результаты свидетельствуют о превосходстве новой САПР.
2. Разработана программная система для проектирования на ЭВМ оросительных сетей для малых (фермерских) хозяйств.
3. Разработана программа оптимального формирования графика поливов на орошаемой территории.
4. Получена точная зависимость стоимости магистрали сети от значений сетевых переменных при формировании магистралей из стандартных элементов.
ЗАКЛЮЧЕНИЕ
.
Существующие методы решения задач синтеза сетей не гарантируют получение даже локально-оптимальных решений.
В диссертационной работе развивается новое направление по решению задач синтеза сетей, заложенное в работах сотрудников НИИ ПМА КБНЦ РАН и состоящее в сведении процесса оптимизации сети к решению ряда задач малой размерности минимизации выпуклой функции при линейных (сетевых) ограничениях — метод динамической декомпозиции переменных.
