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

Российская академия наук Кабардино-Балкарский научный центр Научно-исследовательский институт прикладной математики и автоматизации

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

к/

РГБ ОД

НахушеваМаретаМухамедовна _ ^ 2и:В"

Метод динамической декомпозиции решения задач синтеза сетей и его приложения

05.13.16. - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Нальчик - 2000

Работа выполнена в Научно-исследовательском институте прикладной математики и автоматизации Кабардино-Балкарского научного центра Российской академии наук (НИИ ПМА КБНЦ РАН).

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

доктор физико-математических наук, профессор Кочкаров A.M.; кандидат физико-математических наук, доцент Кудаев Б.Ч.

Официальные оппоненты:

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

доктор физико-математических наук, профессор Перепелица В Л. кандидат физико-математических наук, старший ш учный сотрудник Атгаев А.Х.

Северо-Кавказский государственный технически университет, г. Ставрополь.

Защита состоится «£/>> . //¿>/>7о 2000 г. в 10°° на заседании регионального диссертационного совета К 200.74.01 в НИИ ПМА КБНЦ РАН по адресу: 360000, КБР, г. Нальчик, ул. Шортанова, 89 «а».

С диссертацией можно ознакомится в научной библиотеке НИИ ПМА КБНЦ

РАН.

Автореферат разослан «t А>» ¿/к: Ал?; /¿¡2.000 г.

Ученый секретарь РДС К 200.74.01, кандидат физико-математических наук /)¿ШФ'укс^ Шибзухов 3 М.

¿//г.

Общая характеристика работы

1. Актуальность исследования

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

2. Цель работы

Целью работы является создание нового метода синтеза оптимальных сетей с одним источником и разработка программных систем для оптимального проектирования сетей на ЭВМ.

3. Научная новизна

Впервые разработан метод синтеза, позволяющий проектировать сети, близкие к оптимальным (2-оптимальные сети), предложен принцип оптимальности для надежных сетей и на его основе "разработан метод синтеза надежных сетей (1-оптимальные сети).

4. Практическая ценность Метод может быть применен для оптимального проектирования инженерных сетей. Метод применен в разработанных системах автоматизированного проектирования на ЭВМ закрытых оросительных сетей и оросительных сетей для малых (фермерских) хозяйств.

5. Апробация работы

Основные результаты докладывались на семинаре по современному анализу, информатике и физике НИИ ПМА КБНЦ РАН; на международной конференции

«Нелокальные краевые задачи и родственные проблемы математической биологш информатики и физики», (Нальчик, 1996 г.); на 13 международной конференци «Уравнения состояния вещества» (пос. Терскол, 1998 г.); на III Вссроссийско; симпозиуме «Математическое моделирование и компьютерные технологии», пс священной 80-летшо академика Самарского A.A. (Кисловодск, 1999 г.).

6. Достоверность полученных результатов Представленные в работе теоремы имеют строгое математическое обоснова ние. Эффективность предложенных методов синтеза оптимальных сетей и соответ ствующих программных систем проверена проектированием оросительных сета на ЭВМ.

7. Публикации

Основные результаты диссертации опубликованы в работах [1]-[3].

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

Содержание работы Введение

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

Глава 1. Существующие методы решения задач синтеза сети В первом параграфе дано определение сети и рассмотрены различные методь решения задачи анализа сети.

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

* = + 7 -> 1ШП,

и, =Ц]11+ир Чу е Д ц, > О, V// Е Д

'L0lJ-Ц^>J^=8j, У/., 6Л; =0,

'1>

(1) (2)

(3)

(4)

(5)

где: Г(Я,£>) - заданный конечный, связный, вообще говоря, двузвенный орграф, моделирующий возможные соединения узлов (вершин) сети друг с другом; В и £> -множества его вершин и дуг; иа, и^, с^, - соответственно искомые значения кинетической (например, ток) и потенциальной (например, напряжение) переменных по у -ой дуге (ветви) сети, ее удельная (на единицу длины) стоимость и заданная длина; (),, ¡7,, Р - заданный поток в сеть, искомые потенциал источника и его стоимость; а,/3,у - заданные постоянные коэффициенты; gJ,U",UJ - заданный расход потока, нормативный (заданный) потенциал и потенциал в /-ом узле (вершине) сети соответственно.

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

Ограничения (2), (3) учитывают законы теории сетей, (2) и (4) - требования по обеспечению потребителей сети потоками и нормативными значениями потенциалов.

Удельная стоимость ветви сети имеет вид

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

Можно показать, что си(ии ,ии) есть непрерывная, вогнутая и возрастающая по , выпуклая и убывающая по функция, а стоимость источника Р(0,,и1) будем

«чДЧ/.иД если Ц, > 0 и ия е[и~,и+], сД^.н,,) =' ®> если ц, > 0 и иа ч[и ,и], О, если и0 = О,

(9)

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

Существующие методы решения задачи основаны на ее декомпозиции по типу переменных на две подзадачи и состоят в следующем. Несмотря на то, что стоимость ветви сети зависит существенно от обоих типов сетевых переменных, то есть сд=сй(0а,и8), полагают вначале са = с0)и решают задачу на минимум вогнутой

функции на транспортном многограннике (2), (5), а затем, найдя гло-

уеО

бальное (либо близкое к нему) решение {и*} ^ этой многостремленной задачи, переходят к решению простой задачи на минимум выпуклой функции

+ (Ю)

(где В' - множество дуг графа Г(В,П), по которым поток оказался отличным от нуля) при линейных ограничениях (3), (4).

Можно показать, что, в основе такого подхода лежит замена уравнений Кирхгофа (2), (3) неэквивалентным следствием - системой, содержащей только узловые уравнения (2) и закон сохранения энергии. Вследствие этого даже глобально-оптимальное решение этих двух задач не гарантирует получение хотя бы локального решения исходной задачи синтеза сети.

В третьем параграфе даются постановки задач синтеза надежной сети и излагаются существующие методы ее решения.

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

Разделим потокораспределения в сети на две части - X и У. Каждое из пото-кораспределений обязано обеспечивать в каждом узле расход не менее аварийного, а оба вместе - нормальные. Не исключено, что оптимальное решение будет содержать две параллельные магистрали, соединяющие узлы / и ] сети, по которым протекают соответственно потоки хи и уа. Получаем следующую задачу:

2 = № -> пип,

-=*,> Ну,,-2л Ч^ев,

/еГу /еГу '«Г7

|<17 («в

и,=и,+и„ У/уеД С/,. 2(7", УуеЛ,

еД,

(И) (12)

(13)

(14)

(15)

(16)

где Г (В, В) - заданный конечный, связный, вообще говоря, четырехзвенный орграф1^; g", - заданные нормальный и аварийный расход в у-ом узле сети.

Задача (11)-(16) представляет собой многоэкгремальнуто задачу минимизации вогнуто-выпуклой функции при линейных ограничениях.

Глава 2. Метод динамической декомпозиции решения задач синтеза сети В первом параграфе излагается метод динамической декомпозиции решения основной задачи синтеза сетей.

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

" Вообще, граф содержит дугу (;,_/)* потокаХидугу (1,У)Г потока У. Но верхний индекс можно не ставить, т.к. всегда из формул ясно, о какой из этих дуг идет речь.

вание такого подхода. При этом те элементы, которые следует варьировать, разм щены на сети компактно. Пусть имеем некоторое допустимое решение задачи. В] делим любую связную часть Г (В,О). Тогда при изменении значений переменнь внутри этой части в широких пределах, на ее границе (а значит, и.на всей остальнс сети) сохранится прежнее значение переменных. Это свойств? и использует мет< динамической декомпозиции для последовательного продвижения к оптимуму з дачи.

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

Принцип оптимальности

а) Найдется остов Т графа Г (В, О) и соответствующее ему базисное решет задачи (по потоковым переменным) {и'и, ц'},7ед, и' что

(/е/

где {иу, ив } у е о, С/1 - любое допустимое решение задачи, б) Пусть Т' - любая связная часть графа Г, { , йи} у е в, {/, =[/,'- любое т; кое допустимое решение, что Ц = ц', V//' еГ(Т'), где Г(Г) - гра<]

порожденный на графе Г (В, В) графом Т'. Тогда:

Условие а) сводит процесс оптимизации сети к перебору решений, соответс] вующих остовным деревьям графа Г (В, И). Однако, даже направленный перебо неосуществим в силу их большого количества, растущего факгориально от числ вершин и дуг графа Г(В,Д). Для преодоления «проклятия размерности» использ)

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

Из предоставляемых условием б) подграфов следует выделить те, на которых решение будет осуществляться, с вычислительной точки зрения, наиболее эффективно. Поскольку опгамумы соответствуют вершинам транспортного многогранника, а им, в свою очередь, остовы графа Г(5, £>), то используется наиболее мощный метод направленного перебора угловых точек - симплекс-метод, но в сетевой интерпретации. Продвижению из текущей угловой точки в смежную при этом будет соответствовать внесение в текущее остовное дерево любой его хорды из Г(В,П) и удаление инцидентной ей дуги. При этом изменятся потоки только по дугам контура К, образованного внесением хорды. Чтобы оба типа переменных , у е /), поставить в равное положение, выделим соответствующую контуру минимальную конструкцию (подграф графа Г), за пределами которой не произойдет не только изменение потоков, но и изменение потенциалов. Такой конструкцией является контур с присоединенными к нему смежными дугами. Эта минимальная конструкция и обеспечивает точное согласование значения переменных по ее границе с решением на остальной части графа сети. Поскольку модифицируются значения лишь малой и каждый раз новой части переменных (при переходе от одного контура к другому при продвижении к оптимуму), то речь идет о динамической декомпозиции переменных в процессе решения.

Пусть К - контур, образованный на текущем остовном дереве внесением в него очередной хорды из Г, МК - соответствующая ему минимальная конструкция. Тогда задача на МК состоит в следующем:

где о" , и" - потоки на у-ой дуге МК до и после внесения хорды и удаления инцидентной ей дуги.

I/, = и" + и^, V// а К, и, =и,, VI е МК! К,

ц, = Ли,; + (1-Л)и", Чд еМК, X €[0,1];

(17)

(18) (19)

Согласно принципу оптимальности оптимумы могут достигаться при X = или Л = 1. Таким образом, задача на МК сводится к задаче выпуклого программ рования малой размерности. Решив задачу на МК и сравнив результат с прежш решением на МК (до внесения хорды и удаления инцидентной ей дуги), фиксируй лучшее решение и переходим к следующему МК. Модификация структуры ее продолжается до тех пор, пока уже ни на одном МК текущего остовиого дерева н возможно будет получить лучшего решения. Полученное при этом решение являе ся 1-оптимальным, т.е. таким, что на смежных с ним базисных решениях (угловь точках множества допустимых решений) значение целевой функции не менып чем на нем. Такое решение является глобальным на симплексе многогранника о раничений с вершиной в этой точке. С сетевой точки зрения это означает, что пол; ченную сеть нельзя будет улучшить' не только изменением параметров ее ветвей, г и малыми изменениями ее структуры - внесением в полученное дерево сети любе из его хорд и удалением инцедентной ей дуги.

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

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

Возможности современных ЭВМ позволяют получить 2-оптимальное реши ние. Переборы новых вариантов структуры (возможно не рассмотренных при пол) чении 1-оптимального решения), на которых в принципе может реализовываться 2 оптимальное решение, удалось значительно сократить за счет выделения всех сл) чаев их возникновения. Основным является тот, когда обе вносимые в 1 оптимальный остов хорды замыкают смежные контуры.

А

А

было стало

Разработана программная система для проектирования на ЭВМ 2-оптимальных сетей (см. главу 3).

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

Теорема. Глобальное решение задачи (11) - (16) существует, локальные и глобальные решения являются базисными по потоковым переменным п, при-

• *

чем оптимальным (локально и глобально) потокораспределениям X, У соответствуют пара согласованных остовов графа Г(В,Д).

На этой основе с учетом сетевых свойств задачи сформулирован следующий Принцип оптимальности

а) Найдутся остовы Тх и Тг графа Г(В,Д) и соответствующее им базисное решение (по потоковым переменным) задачи \х'у,у1,и'^ уе£>, иг, что

«В^^+^о^ж, +/5Р(а.Ю+г ом *

!/еО

+ [у +РГ{0{,их) + у 6,1/1,

уеХ>

где |х,;, у0, | е р, [/¡- любое допустимое решение задачи.

б) Пусть Т'х , Ту - любые связные части графов Тх и Ту, {х^, уу, йя } у е 0,

Г/, = С/1 и |^, ув, йу | у 6 0, С/, = С/1 - пара любых допустимых решений задачи, но такая задача, что

= х1> У у ~ У1 ' = ",'> V// ёГ [г;] ,

=Х> % =Х> % = "]< (7г) ■

Тогда будут выполнены неравенства

+ с)(У*>и'Ж + 4 (У*'"Ж'

уеО

Д)+<£(?(/Д Ж, >

уеВ </ в£>

• •

где Г(7*£), Г (Ту) - графы порожденные на графе Г"(В,0) графами Т'х и Г/ I

ответственно.

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

товы Тх и Ту, при продвижении к оптимуму, изменяются (конечно, при эт< Отх + От, = Q\ )• Поэтому очень важно обоснованно выбрать начальные потоки в с товы. Для этого рассматривается более простая задача синтеза надежной сети, в к торой

X, = + (1 - Х)(ЯЧ -£); yJ=( 1 -+ Х(гЧ

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

IX " IX* = Я/' IX "XX* = я" -г" •

1"еГ/ ИГ/ /еГ/

Тем самым получает некоторое обоснование выбор начальных потокораспр делений Х°, У* : в Тх поток равен IX, в Т° — й .

Далее рассматривается задача, в которой остовы Тх и Гг совпадают (зада1 синтеза с дублированием ветвей), поток в Тх обеспечивает аварийную подачу п

требителям, т.е. , а. поток Тг - оставшуюся ■ Эта задача сводится к

ив . (ев

основной задаче синтеза сети.

Глава 3. Применение метода динамической декомпозиции для

проектирования оросительных сетей

В первом параграфе моделируются элементы трубопроводной оросительной сети , дается постановка задачи оптимального проектирования сети на ЭВМ и метод ее решения, приводятся запроектированные на ЭВМ реальные сети.

Техническая часть закрытой оросительной сети (ЗОС), которую, собственно, и следует проектировать, состоит из сети трубопроводов, служащих для транспорта воды от места водозабора к гидрантам, дождевальных установок, подключаемых к гидрантам, и насосной станции, осуществляющей забор и нагнетание требуемого расхода воды с необходимым напором в трубопроводную сеть.

Задача оптимального проектирования ставиться следующим образом. Исходя из заданного на проектирование сортамента труб с1,,с12...,с1к, их удельной стоимости с,,с2...,с4 заданного набора насосно-силовых агрегатов НСА1,НСА2...,НСА1, запроектировать сеть, обеспечивающую на гидрантах сети заданные напоры и расходы воды и имеющую наименьшие затраты на ее создание и эксплуатацию в течение заданного количества лет.

Для решения этой задачи (и для создания системы автоматизированного проектирования сетей на ЭВМ) следует перейти от конструктивных данных на проектирование к фундаментальным сетевым переменным - потоковым и потенциальным. Кроме того, необходимо каким-то образом выразить стоимость насосной станции через насосно-силовые агрегаты из которых она формируется.

Моделирование трубопроводов сети

В самом общем случае различные части одной и той же ветви сети могут укладываться трубами различных диаметров из заданного сортамента. Вычислим удельную потерю напора при условии, что по трубопроводу течет расход # = 1. Из гидравлики известно, что удельная потеря напора по трубе диаметром й при расходе воды по ней % равна h(l(g) = 0,OQn9g^•9/с!5Л. При # = 1, получим />¿(1) = 0,00179/с?5,1. Комплектуя трубопровод различными трубами из заданного

сортамента получим следующее выражение для его удельной стоимости и удельной

потери напора при единичном потоке воды по трубопроводу:

к к к с = "Е,сгЛг> A = Л,* О,

,.1 Г'1 Г-1

где Хг - доля длины трубопровода на которой укладываются трубы диаметром df. Обозначим удельную стоимость трубопровода по которому течет единичный поток с удельной потерей напора h через С(1,Л). Имеет место следующая

Теорема. С(1,А) является выпуклой, монотонной убывающей, кусочно-линейной функцией, точкам излома которой могут быть лишь точки (Cr,hr),

У = \к.

Построив эту функцию и поместив информацию о ней в ЭВМ можно на ее основе получить функцию C(x,h). Действительно, при х > 0, h > О

C(x,h) = C(\,h/xU9)

т.к. потери напора при потоке х отличаются от потерь на единичном потоке в х1,9 раз. Итак, удельная стоимость трубопровода выражена через сетевые переменные. Моделирование насосной станции В основу моделирования положен принцип модульного проектирования НС. В качестве строительно-технологических модулей выбраны строительные блоки прямоугольной формы (выпускаемые серийно) 6x4 и 6x6 метров со всем разме-щишым в них технологическим оборудованием. Всего таких модулей около сорока. Разработана соответствующая документация (Севкавгипроводхоз, г. Пятигорск). Рабочие характеристики (зависимость напора от расхода) насосно-силовых агрега-

(ßY (Ö)

тов аппроксимируются полиномами второго порядка Нт j j +cj; где

Q~ < Q < Q*, m - количество HCA работающих параллельно, S - номер HCA в сортаменте НСА. По расходу в сеть Q и диапазону работы насоса [£Г>0Л можно определить необходимое количество HCA S -того типа и напор Н' обеспечиваемый ими в сеть. Тогда определяется и стоимость НС при формировании ее из строи-

тельно-технологических модулей 5-того типа Р((),Н') - Г5 = т1 ■ С, где С, - стоимость одного строительно-технологического модуля ¿'-того типа.

Моделирование сезонов полива Весь период полива разбивается на кванты (сезоны). Каждой дождевальной установке сопоставляются в соответствии с периодом вызревания с/х культур и размещением полей севооборота на орошаемой территории определенная последовательность нулей и единиц (орошается, не орошается) ее работы по сезонам полива. Трубопроводы при этом должны рассчитываться на наибольший (пиковый) расход.

Постановка задачи оптимального проектирования ЗОС

Таким образом, имеем следующую задачу:

'г = а^с^х^и^ + РР' + у £?Я* -> тт, (20)

(21)

V/„еЛяМеГ,

(22)

Хя >Ху, Чу еИи V/ ЕТ, (23)

Я, =И111ц+Н,+21 -г,., У/у еД

(24)

Я,>Я;, V/ е В,

Я* е{я\...,я'}, Р' 6{Р',...,Р'}. (25)

где х'у поток по у" -й ветви сети в / -й сезон полива, Т- множество номеров сезонов полива, - высотная отметка у -го узла (гидранта) сети.

Задача относится к типу основной задачи синтеза сети и решается на ЭВМ методом динамической декомпозиции до получения 2-оптимального решения. Время счета для средних (30-50 узлов) сетей - 10-30 минут. При этом задача решается перебором по напорам в сеть Я',...,Я', причем на каждом очередном напоре в сеть задача решается с конфигурации (и, соответственно, потоков) сети, полученной на предыдущем напоре, а сами напоры Я1,...,Я' выстроены по возрастанию.

Во втором параграфе рассматривается разработанная САПР сетей для малых (фермерских) хозяйств и приводится основная проектно-сметная документация выдаваемая системой.

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

Поскольку сетевой трубопровод представляет последовательность ветвей, то нумеруем его ветви 1,2,...,/ начиная от источника сети. В соответствии с этим, обозначим др,Ир,1р,Ср заданный поток, искомую удельную потерю напора, заданную длину и удельную стоимость р -ой ветви сетевого трубопровода, а Нр,гр - напор и высотную отметку его р-то узла (т.е. узла в который входит р-я ветвь). Для ветвей подсетей используем двойную индексацию с указанием номера подсети. Получим следующую задачу: определить такие значения, {й,,} _, р и } _ что

(26)

J

».<>; (28)

(27)

(28) (29)

И- я; + +г;-г,',Уу =

н^н'у^ер, р=м, (30)

д:,; > 0, ЧЦеРр = \,1.

(32)

где ^ = Л/У, = —¡у, д° - расход одного оросителя. Задача решается на ЭВМ ме-Чр

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

Входная информация

В процессе автоматизированного проектирования задаются:

• Координаты точек периметра орошаемого участка и подучастков.

• Координаты узлов сетевого трубопровода и насосной станции.

• Общее время работы каждой подсети. Тип оросителей (из базы данных).

• Высотные отметки узлов сети (при значительном расхождении высот узлов).

• Тип насосно-силового агрегата или насосной станции.

• Максимальная и минимальная возможная скорость течения воды по трубопро-одам сети.

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

Результаты проектирования

Система выдает всю необходимую информацию для рабочего проектирования сети:

• План сети. Гидравлические параметры ветвей и узлов сети (напоры в узлах, потери напора и расходы по ветвям сети).

• Технические параметры и устройства сети (диаметры, толщины стенок и материал труб по ветвям сети; тип насосной станции).

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

База данных содержит:

• параметры и характеристики стальных, чугунных, асбестоцементных и пластмассовых труб, используемых в мелиорации;

• параметры и характеристика насосно-силовых установок;

• параметры и характеристики оросителей.

Технические возможности системы:

• система проектирует сети с числом оросителей до 500 шт.;

• время автоматизированного проектирования составляет около 15-30 минут для сетей с числом узлов в подсетях до 200 шт.

Система реализована на IBM PC/AT (286 и выше).

Ниже приводятся результаты проектирования оросительной сети для научно-

экспериментального хозяйства НИИ ПМА КБНЦ РАН.

ТАБЛИЦА РЕЗУЛЬТАТОВ ГИДРАВЛИЧЕСКОГО РАСЧЕТА СЕТИ

Длина Расход Высот. "[" Ско- J Диа- ' Тол- Т Код т Потери Напор 1 Стои-

уч-ка i на i Отметка , рость , метр , щина , мате- , напора ! в I ыость

I уч-ке уз. ) м/с I тр. 1 стен 1 риала i на уч. i узле I уч -ка

с (л/с) 1 (м) 1 1 (мм) 1 (мм) 1 1 (м) 1 (м) 1 (т. руб)

; ■ i i 6 3

65.3 1 ■ 10 1 ■ 100 0 о 51 168 5 0 1200 0 25 5 2 1 0 23

4.7 1 ■ 10 1 i 100 0 1 22 108 з 0 1200 0 16 5 0 I 1 0 01

70.0 1 20 1 ■ 100 0 о 88 180 5 0 1200 0 67 5 4 1 t 0 26

36.5 1 i 180 1 i 100 0 1 04 480 5 0 1200 0 13 6 1 1 1 0 39

5.5 1 i 180 1 i 100 0 1 49 402 5 0 1200 0 05 б 1 1 i 0 05

70.0 1 i 10 1 i 100 0 о 51 168 0 1200 0 27 5 0 1 1 0 24

28.3 1 i 20 1 i 100 0 о 68 203 5 0 1200 0 14 5 1 i 0 12

41.7 1 ■ 20 1 ■ 100 0 о 75 194 5 0 1200 0 27 5 3 1 1 0 17

99.0 1 120 1 i 100 0 о 99 402 5 0 120 0 0 40 5 7 1 i 0 84

15.0 1 ■ 30 1 i 100 0 о 69 245 5 0 1200 0 06 6 0 1 0 08

55.0 1 30 1 100 0 о 87 219 5 0 1200 0 40 5 6 1 i 0 25

8.7 1 i 10 1 i 100 0 о 38 194 5 0 1200 0 02 5 2 1 1 0 04

61.3 1 i 10 1 1 100 0 о 44 180 5 0 1200 0 17 5 0 1 1 0 23

70.0 1 i 40 1 i 100 0 о 61 299 5 0 1200 0 17 5 2 1 1 0 44

99.0 1 ■ 60 1 ■ 100 0 о 77 325 5 0 1200 0 33 5 4 1 1 0 68

70.0 1 i 30 1 1 100 0 о 69 245 5 0 1200 0 28 5 4 1 1 0 36

70.0 1 i 20 1 i 100 0 о 68 203 5 0 1200 0 36 5 3 1 1 0 30

99.0 1 i 10 1 i 100 0 0 38 194 5 0 1200 0 18 0 1 I 0 40

8.7 1 i 10 1 i 100 0 о 38 194 5 0 1200 0 02 5 2 1 i 0 04

61.3 1 i 10 1 i 100 0 о 44 180 5 0 1200 0 17 5 0 1 1 0 23

67.3 1 t 10 1 1 100 0 о 51 168 5 0 1200 0 26 1 1 i 0 23

2.7 1 ■ 10 1 ■ 100 0 1 22 108 з 0 1200 0 09 5 0 1 1 0 00

70.0 1 i 20 1 i 100 0 о 58 219 5 0 1200 0 24 5 2 1 1 0 32

70.0 1 1 10 1 1 100 0 о 51 168 5 0 1200 0 27 5 0 1 0 24

31.0 1 i 10 1 i 100 0 о 38 194 0 1200 0 06 5 1 1 ■ 0 13

39.0 1 10 1 -1- 100 0 .ill •180 5 0 _¡_ 1200 _[_ 0 11 0 1 0 15

2ЧАНИЕ: ВОЗМОЖНО В ТАБЛИЦЕ ИМЕЮТСЯ УЗЛЫ С НОМЕРАМИ ОТ 200 И ВЫШЕ, ТОЧКИ РАЗБИЕНИЯ УЧАСТКА ПРИ УКЛАДКЕ В НЕЙ 2-Х РАЗЛИЧНЫХ ДИАМЕТРОВ. РАСПРЕДЕЛЕНИЕ ТРУБ И МАТЕРИАЛА ПО СЕТИ.

материалам всего

в том числе по диаметрам

!ШИЕ ША

МАРКА i i i ГОСТ ИЛИ ТУ i 1 I НАРУЖ. ДИАМ. (ММ) i i ТОЛЩИНА СТЕНКИ (ММ) i i i ДЛИНА ДИАМЕТРА (М) 1 I I стоимость J ДИАМЕРТА ¡ (Т. РУВ). |

электросв. i 10704-76 i 168.0 I 5.00 ■ 272.60 i 0.95 ]

электросв. 1 1 10704-76 1 1 108.0 1 I 3.00 1 i 7.40 1 1 0.01

электросв. 1 i 10704-76 I I 180.0 1 ■ 5.00 1 i 231.68 1 ■ 0.87.

электросв. I 1 10704-76 1 1 480.0 I 1 5.00 1 i 36.54 1 ■ 0.39

электросв. i 1 10704-76 1 | 402.0 i 1 5.00 1 1 104.52 1 i 0.88

электросв. 1 i 10704-76 1 1 203.0 1 i 5.00 1 i 98.27 i i 0.42

электросв. i 1 10704-76 1 1 194.0 1 1 5.00 1 i 189.05 1 i 0.76 ;

электросв. i 1 10704-76 ' 1 I 245.0 1 i 5.00 1 1 85.03 1 1 0.44' ;

электросв. i 1 10704-76 I 1 219.0 ( 1 5.00 1 ■ 124.97 1 i 0.57

электросв. i 1 10704-76 1 1 299.0 1 1 5.00 1 1 70.00 1 i 0.44

электросв. 1 10704-76 1 325.0 1 5.00 1 98.99 1 0.68

1319.04 6.40

-20В третьем параграфе решается задача оптимального формирования графика поливов сельхозкультур на орошаемой территории. Эта задача является вспомогательной по отношению к рассмотренным в § 1 и § 2 задачам. Задача ставиться следующим образом: для заданных площадей сельхозкультур составить расписание их поливов так (при ограниченной мощности сети), чтобы поливы по возможности осуществлялись в нормативные сроки.

Постановка задачи. Заданы площади Я, полей на которых произрастает i -ая культура, % = \,И и количество поливов каждой / -ой культуры /(.

п

Определим общее количество поливов а = ]>]/, и с этого момента будем для

удобства считать, что имеем не N, а а полей. В норме каждое из этих полей нужно поливать в срок г, в течение /, дней. Будем считать, что полив производится кван-

$ 8,

тами (1 день), так что время полива / -го поля = гоипс! ^ , где - поливная

норма на 1 га г -го поля, а £> - мощность поливного агрегата (сети).

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

а

^Ф,^, — г0,А/) -> гшп, где г, - планируемое (искомое начало) орошении 1-ой

1=1

культуры, /0, - нормативное начало, Д/ - допустимое запаздывание в сроке начала орошения. К Ф, предъявляются естественные требования: штраф пропорционален площади полива, ценности культуры, малости при г, - /0, ~ А;. Ограничения задачи - обычные временные ограничен™, характерные для задач теории расписаний. Приведем одно из них: гм - г, > - очередной полив не может быть начат до того, как закончится предыдущий. Полученная нелинейная целочисленная задача теории расписаний сводится декомпозицией к ряду задач существенно меньшей размерности, точные решения которых находятся методом перебора. Основным понятием, используемым в процессе декомпозиции является кластер-временной участок соответствующий напряженному участку поливного графика. Приводится точное определение кластера. Решение задачи распадается на ряд этапов:

а) Подготовка к основному циклу;

б) Выделение очередного кластера;

в) Оптимизация выделенного кластера.

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

Подробно излагается алгоритм решения задачи. Составлена программа решения задачи, текст которой приведен в приложении к диссертации. Просчитаны тестовые примеры. Время счета на ЭВМ - секунды.

В заключении сформулированы основные результаты работы, которые состоят в следующем:

Теоретические результаты

1. По-новому доказан принцип оптимальности для основной задачи синтеза сети, что дало возможность проектировать 2-оптимальные сети.

2. Впервые разработан метод получения 2-оптимальных решений основной задачи синтеза сети.

3. Доказан принцип оптимальности для задачи синтеза надежной сети с одним источником

4. Предложен метод получения 1-оптимального решения задачи синтеза надежной сети с одним источником.

Практические результаты

1. Разработан программный модуль, включенный в САПР оросительных сетей головного на Юге России проектного института «Севкавгипроводхоз», позволяющий проектировать сети близкие к глобально-оптимальным. Проведено сравнение с результатами проектирования прежней САПР на реально запроектированных ею в Ставропольском крае сетях. Полученные результаты свидетельствуют о превосходстве новой САПР.

2. Разработана программная система для проектирования на ЭВМ оросительных сетей для малых (фермерских) хозяйств.

3. Разработана программа оптимального формирования графика поливов на орошаемой территории.

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

Публикации по теме диссертации

1. Кудаев В.Ч., Нахушева М.М. 2-оптималыюе решение задачи синтеза сетей методом динамический декомпозиции / Доклады АМАН, 1999, Т. 4, № 1, с. 15-20.

2. Нахушева М.М. Математическое моделирование стоимости трубопровода / Вестник КБГУ. Серия - Математические науки, Вып. 2,1998, с. 126-129.

3. Нахушева М.М. О системе автоматизированного проектирования сетей для малых (фермерских) хозяйств. Препринт/ Научно-исследовательский институт прикладной математики и автоматизации КБНЦ РАН, 1999, 14 с.

Введение

Глава 1. Существующие методы решения задач синтеза сетей

1.1. Определение сети. Задача синтеза сети. Методы решения задачи анализа сети.

1.1.1. Определение сети.

1.1.2. Задача анализа сети.

1.1.3. Методы решения задачи анализа сети.

1.2. Постановка основной задачи синтеза сети. Существующие методы решения задачи.

1.2.1. Актуальность задач синтеза сетей.

1.2.2. Содержательная постановка задачи. Инженерный способ решения задачи.

1.2.3. Постановка ,задачи.

1.2.4. Существующие методы решения задачи.

1.3. Постановка задачи синтеза надежной сети. Существующие методы решения задачи.

1.3.1. Существующие методы решения проблемы синтеза надежной сети.;.

1.3.2. Постановка задачи синтеза надежной сети с одним источником.

Глава 2. Метод динамической декомпозиции решения задач синтеза сетей.

2.1. Решение основной задачи синтеза сети.

2.1.1. Принцип оптимальности для задачи.

2.1.2. Решение задачи методом динамической декомпозиции

2.1.3. Задача оптимизации потенциальных переменных на сети.

2.2. Решение задачи синтеза надежной сети.

2.2.1. Принцип оптимальности для задачи синтеза надежной сети с одним источником.

2.2.2. Решение задачи синтеза надежной сети методом динамической декомпозиции.

2.2.3. Задачи синтеза надежной сети с пропорциональными потокораспределениями.

Глава 3. Применение метода динамической декомпозиции для проектирования оросительных сетей.

3.1. Оптимальное проектирование закрытой оросительной сети.

3.1.1. Состав и назначение технической части ЗОС. Назначение САПР ЗОС. Содержательная постановка задачи оптимального проектирования ЗОС.

3.1.2. Моделирование элементов ЗОС.

3.1.3. Постановка и решение задачи оптимального проектирования ЗОС.

3.1.4. Примеры оптимального проектирования ЗОС на ЭВМ.

3.2. САПР сетей для малых (фермерских) хозяйств.

3.2.1. Постановка задачи.

3.2.2. Последовательность решения задачи на ЭВМ.

3.2.3. Входная информация и результаты проектирования

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

3.3.1. Формализация задачи.

3.3.2. Метод решения задачи.

3.3.3. Решение задачи на ЭВМ.

3.3.4. Результаты расчетов.

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

В НИИ прикладной математики и механики КБГУ и НИИ ПМА КБНЦ РАН (г. Нальчик) в 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у + рр{&,£/,) + г ш ™п>

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 <?< н х, =gi ~Si А

У, = &

На этой основе с учетом сетевых свойств задачи сформулирован следующий

Принцип оптимальности * а) Найдутся остовы Тх и Ту графа Г {В, Б) и соответствующее им ба зисное решение (по потоковым переменным) задачи |х* у ео, и 1, что уеО уеО где х* = 0 \/у £ Т*, Уу = 0 \/у £ Ту и таковы, что н а либО ^ Уг 81 [У, а {хи>Уу>щ} у е£>> их- любое допустимое решение задачи. * **<■ 1 б) Пусть Т'х , Ту - любые связные части графов Тх и Ту, |х(У,уу,иу} у ео> « \ =г * их=и 1 и \ху,Уу,йу} и[ = и\ - пара любых допустимых решений задачи, но такая задача, что

ХУ =х1> Уу щ у и ^ * Ху =*1> % = Уу> Цу

Тогда будут выполнены неравенства: уеО г/'еО уеО у ей где Г(7^), Г(Г/) - графы порожденные на графе Г (В, О) графами * *

Т'х и Ту соответственно.

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

Далее рассматривается более простая задача синтеза надежной сети, в которой

У = + (1 - лхя; -gJ), У; = а - я)*; + ^ - >, я е ад.

При этом все потоковые ограничения исходной задачи выполняются автоматически. Показывается, что оптимум в такой задаче реализуется только при 2 = 0 или Я = 1, т.е. потокораспределение нужно выбрать так, что

IX -XX* = > 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 предъявляются естественные требования: штраф пропорционален площади полива, ценности культуры, малости при Zj -t0j~Ai. Ограничения задачи - обычные временные ограничения, характерные для задач теории расписаний. Приведем одно из них: zM - z, > -очередной полив не может быть начат до того, как закончится предыдущий. Полученная нелинейная целочисленная задача теории расписаний сводится декомпозицией к ряду задач существенно меньшей размерности, точные решения которых находятся методом перебора. Основным понятием, используемым в процессе декомпозиции, является кластер - временной участок соответствующий напряженному участку поливного графика. Приводится точное определение кластера. Решение задачи распадается на ряд этапов: а) Подготовка к основному циклу; б) Выделение очередного кластера; в) Оптимизация выделенного кластера.

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

Подробно излагается алгоритм решения задачи. Составлена программа решения задачи, текст которой приведен в приложении к диссертации. Просчитаны тестовые примеры.

Работа выполнена в НИИ ПМА КБНЦ РАН в отделе САПР смешанных систем.

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

Теоретические результаты

1. По-новому доказан принцип оптимальности для основной задачи синтеза сети, что дало возможность проектировать 2-оптимальные сети.

2. Впервые разработан метод получения 2-оптимальных решений основной задачи синтеза сети.

3. Доказан принцип оптимальности для задачи синтеза надежной сети с одним источником

4. Предложен метод получения 1-оптимального решения задачи синтеза надежной сети с одним источником.

Практические результаты

1. Разработан программный модуль, включенный в САПР оросительных сетей головного на Юге России проектного института «Севкавгипроводхоз», позволяющий проектировать сети близкие к глобально-оптимальным. Проведено сравнение с результатами проектирования прежней САПР на реально запроектированных ею в Ставропольском крае сетях. Полученные результаты свидетельствуют о превосходстве новой САПР.

2. Разработана программная система для проектирования на ЭВМ оросительных сетей для малых (фермерских) хозяйств.

179

3. Разработана программа оптимального формирования графика поливов на орошаемой территории.

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

ЗАКЛЮЧЕНИЕ

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

В диссертационной работе развивается новое направление по решению задач синтеза сетей, заложенное в работах сотрудников НИИ ПМА КБНЦ РАН и состоящее в сведении процесса оптимизации сети к решению ряда задач малой размерности минимизации выпуклой функции при линейных (сетевых) ограничениях - метод динамической декомпозиции переменных.

1. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. - М.: Мир, 1968.

2. Kirchhoff G. Uber die Autlosung der Gleichungen, auf welche man bei Untersuchung der linearen Vertheilung, galvanische Strome geführt Wird. Leipzig Annalen der Physik und Chemie, 1847, Bd. 72, № 12. S. 497-508.

3. Кениг Г., Блекуэлл В. Теория электромеханических систем. М.-Л.: Энергия, 1965.

4. Сигорский В.П. Математический аппарат инженера. Киев: Техника, 1975.

5. Бердичевский В.Л. Вариационные принципы механики сплошной Среды. М.: Наука, 1983.

6. Helmholz Н. Zur Theorie der Stationaren Strome in reibenden Flüssigkeiten. -Verhandl. der naturalist. med. Vereines, 30 Okt. 1868.

7. Седов Л.И. Об основных моделях в механике. М.: Изд-во МГУ, 1992.

8. Ершов В.Н. К вопросу о минимуме диссипации механической энергии в потоке вязкой жидкости. Труды ХАИ, Вып. 20, 1960.

9. Максвелл Дж.К. Трактат об электричестве и магнетизме. Т. I, М.: Наука, 1989.

10. Ю.Меринков А.П., Хасилев В.Я. Теория гидравлических цепей. М.: Наука, 1985.

11. П.Цой С., Рязанцев Г.К. Принцип минимума и оптимальная политика управления вентиляционными и гидравлическим сетями. Алма-Ата: Наука, 1968.

12. Денис Дж.Б. Математическое программирование и электрические сети. -М.:ИЛ, 1961.

13. Хасилев В.Я. Элементы теории гидравлических цепей. Автореферат докт. дис. Новосибирск, 1966.

14. Сумарков C.B. Математическое моделирование систем водоснабжения.- Новосибирск: Наука, 1983.

15. Лобачев В.Г. Вопросы рационализации расчетов водопроводных сетей.- М.: ОНТИ, 1936.

16. Cross H. Analysis of flow in networks of conduits or conductors Urbana, Illinois: Eng. Exp. Station of Univ. of Illinois, 1936, November, Bull. № 286.

17. Евдокимов А.Г. Оптимальные задачи на инженерных сетях. Харьков: Изд-во ХГУ, 1976.

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

19. Андрияшев М.М. Техника расчета водопроводной сети. М.: Сов. Законодательство, 1932.

20. Пшеничный Б.Н. Расчет энергетических сетей на ЭВМ. Журнал вычисл. матем. и мат. физики, 1962, № 5, с. 942-947.

21. Кудаев В.Ч. Задачи оптимального проектирования сетей Кирхгофа: Автореферат дис. канд. физ.-мат. наук. Ростов-на-Дону, 1993. 18 с.

22. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимальные задачи производственно-транспортного программирования. М.: Наука, 1986.23 .Туй X. Вогнутое программирование при линейных ограничениях. Доклады АН СССР, 1964. т. 159, № 1, с. 32-35.

23. Анциферов В.П., Ащепков Л.Т., Булатов В.П. Методы оптимизации и их приложения. Ч. 1. Новосибирск: Наука, 1990.

24. Кикачейшвили Г.Е. Технико-экономический расчет разветвленных водопроводных сетей методом линейного программирования. Водоснабжение и сан. техника, 1969, № 6, с. 7-8.

25. Луценко Е.В. Задачи оптимального проектирования ЗОС. В сб. науч. тудов САПР И АСПР в мелиорации. Нальчик, КБГУ, 1983.

26. Некрасова O.A., Хасилев В.Я. Оптимальное дерево трубопроводной системы. Экономика и математические методы, 1970, т. 4, № 3.

27. Трубин В.А. Свойства и методы решения задач оптимального синтеза сетей. Киев: Общество "Знание" УССР, 1982.

28. Меренкова H.H. Математические модели для оптимизации трассировки и структуры трубопроводных систем. В кн.: Вопросы прикладной математики. -Иркутск: СЭИ СО АН СССР, 1977, с. 145-158.

29. Хасилев В.Я. О методике оптимизации резервируемых систем водоснабжения с учетом критериев и параметров надежности. В кн.: Проблемы надежности систем водоснабжения. М.: МИСИ, 1973, с. 16-29.

30. Хасилев В.Я., Меренков А.П., Каганович Б.М., Виноградов H.A. О проблеме надежности теплоснабжения с нагруженным резервированием. -Известия АН СССР, Энергетика и транспорт, 1976, № 1, с. 146-153.

31. Кудаев В.Ч. Нахушева М.М. 2-оптимальное решение задачи синтеза сетей методом динамический декомпозиции / Доклады АМАН, 1999, Т. 4, № 1, с. 15-20.

32. Карманов В.Г. Математическое программирование. М.: Наука, 1986.

33. Кудаев В.Ч., Луценко Е.В., Алдошин В.И. Об одном подходе к автоматизированному проектированию оросительных насосных станций. В кн.: САПР и АСПР в мелиорации. Сборник научных трудов (междуведомственный). Нальчик, 1983.

34. Кудаев В.Ч., Каров Х.М., Луценко Е.В., Хахо И.Х. Об одной задаче проектирования гидромелиоративной системы. В кн.: Перспективныеметоды планирования и анализа экспериментов. Тезисы докладов II Всесоюзной конференции, ч. II. М., 1985.

35. Кристофидес Н. Теория графов. М.: Мир, 1978.

36. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. Кибернетический сборник, 1961, № 2, с. 95-107.

37. Кирсанов М.В. Экономический расчет водопроводных сетей. M.-JL: Минкомхоз РСФСР, 1949.

38. Галустанова JI.A., Струтинская С.П., Мамот А.И. Методика оптимизации энергетических сетей. В кн.: I Всесоюзная конференция по оптимизации и моделированию транспортных сетей. Сборник докладов. Киев: ИК УССР, 1969, с. 91-98.

39. Ермольев Ю.Н., Мельник И.Н. Экстремальные задачи на графах. Киев: Наукова думка, 1968.

40. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика., 1965. № 1, с. 45-46, № 2, с. 85-89.

41. Емеличев В.А., Комлик В.И. Метод построения последовательности' планов для решения задач дискретной оптимизации. М.: Наука, 1981.

42. Свами М., Тхуласирман К. Графы, сети и алгоритмы. М.: Мир, 1984.

43. Меринков А.П. Применение ЭВМ для оптимизации разветвленных тепловых сетей. Изв. АН СССР, Энергетика и транспорт, 1963, № 4, с. 531-538.

44. Арякин А.Н., Арский А.К., Кузнецов Ю.М., Меренков А.П., Рогожина Х.Я. Оптимизация развития во времени сложных газопроводных систем. Экономика и математика, 1970, т. 6, № 1, с. 105-111.

45. Сумароков C.B. Метод решения многоэкстремальной сетевой задачи. -Экономика и мат. методы, 1976, т. 12, № 5, с. 1016-1018.

46. Сумароков C.B. Математическое моделирование систем водоснабжения. Новосибирск: Наука, 1983.

47. Абрамов H.H., Поспелова М.М., Сомов М.А., Воропаев В.Н., Керимо-ва Д.Х. Расчет водопроводных сетей. М.:. Стройиздат, 1983.

48. Рейнтолд Э., Нивергельд Ю. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

49. Казиев В.М. О задаче комплектования графиков гидромодулей. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик: КБГУ, 1983.

50. Аттаев А.Х. Задача оптимально й трассировки трубопроводной сети. В сб. науч. тудов САПР И АСПР в мелиорации. Нальчик, КБГУ, 1983.

51. Кудаев В.Ч., Аттаев А.Х., Байрактаров Б.Р. Задача трассировки оросительной сети. В кн.: Перспективные методы планирования и анализа экспериментов. Тезисы докладов III Всесоюзной конференции, ч. 2, -М., 1988. С. 121-123.

52. САПР-СКГВХ (первая очередь). Автоматизированные технологические линии проектирования, разработанные в НИИ ПММ КБГУ, г. Нальчик, 1982.

53. САПР-СКГВХ (вторая очередь). Подсистемы разрабатываемые в НИИ ПММ КБГУ, г. Нальчик, 1985.185

54. Кудаев Б.Ч. поиск оптимального дерева в трубопроводной сети. Сб. науч. трудов (межведомственный). Нелокальные задачи их приложения к автоматизированным системам, г. Нальчик, с. 152-153.

55. Кудаев В.Ч. Задача оптимального синтеза активных сетей. Международная конференция. Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики. Тезисы докладов, г. Нальчик, с. 53-55.