Содержание к диссертации
Введение
Глава 1. Теоретико-графовая модель задачи проектирования оросительных сетей и оценки ее сложности 22
1.1. Содержательное описание задачи и соответствующая теоретико-графовая модель 22
1.2. Общая постановка векторной задачи об остовных деревьях 25
1.2.1. Топологические критерии оптимизации векторных задач об остовных деревьях 26
1.3. Оценка вычислительной сложности задачи об остовных деревьях 27
Глава 2. Алгоритмы с оценками для векторной задачи об остовных деревьях 30
2.1. Математическая постановка проблемы 30
2.2. Описание алгоритма аъ 31
2.3. Вероятностный анализ алгоритма аъ 34
2.4. Вероятностный анализ применения алгоритма а2 к множеству M{n,R,A) 41
2.5. Статистически эффективный алгоритм а0 45
2.6. Обоснование условий статистической эффективности алгоритма а0 .47
Глава 3. Интервальные задачи об остовных деревьях и их неразрешимость с помощью алгоритмов линейной свертки 53
3.1. Отображение неопределенности значений параметров моделей средствами интервальной математики 53
3.2. Сведение интервальной задачи к задаче многокритериальной оптимизации 56
3.3. Неразрешимость интервальных задач с помощью алгоритма линейной свертки 56
Глава 4. Полиномиально разрешимый класс задач об остовных деревьях с топологическим критерием 62
4.1. Математическая постановка задачи об остовных деревьях 62
4.2. Полиномиальная разрешимость однокритериальных задач об остовных деревьяях с топологическими критериями 62
4.3. Полиномиальная разрешимость 2-критериальных задач, в которых один критерий является топологическим 64
Глава 5. Математическая модель водопользования на гиперграфах с интервальными данными 69
5.1. Основные определения теории гиперграфов 69
5.2. Математическая постановка задачи 70
5.3. Сведение задачи с интервальными данными к многокритериальной задачи 74
5.4. Сведение задачи на гиперграфе к задаче на графе 78
5.5. Оценки вычислительной сложности исследуемых задач 81
5.6. Полиномиально разрешимые постановки 84
5.7. Исследование «задачи 3» 86
5.8. Иллюстративный пример решения конкретной 2-критериальной задачи водопользования 92
Заключение 95
Литература 96
Приложения 105
- Оценка вычислительной сложности задачи об остовных деревьях
- Вероятностный анализ применения алгоритма а2 к множеству M{n,R,A)
- Сведение интервальной задачи к задаче многокритериальной оптимизации
- Полиномиальная разрешимость однокритериальных задач об остовных деревьяях с топологическими критериями
Оценка вычислительной сложности задачи об остовных деревьях
Условимся заранее, что все недостающие определения терминов и понятий, относящихся к графам и гиперграфам, можно найти в [24].
На содержательном уровне оптимизационная задача, решаемая с помощью системы автоматизированного проектирования (САПР) закрытой оросительной системы (ЗОС), состоит в следующем.
Исходя из заданных координат пунктов потребления воды (гидрантов) и водозабора, зон запрета на прокладку трасс трубопроводов, расходов и напоров воды на гидрантах, описания поверхности территории орошения, задаваемого сортамента труб для прокладки трубопроводов и марок насосно-силовых установок, следует выбрать такое соединение гидрантов с насосной станцией трубопроводами, указав по каждому из них материалы, марки, диаметры, толщины стенок используемых труб, и так выбрать марки и количество насосно-силовых установок насосной станции, чтобы при этом общие затраты на создание и эксплуатацию ЗОС в течении заданного количества лет были наименьшими [3,33,42,43,46,50,68,69].
Получаемая на выходе САПР ЗОС проектно-сметная и конструкторская документация содержит конкретные значение следующих основных параметров: 1. Структуру (конфигурацию) сети с указанием длин трубопроводов. 2. Параметры трубопроводов сети, из которых определяющим является диаметр. 3. Гидравлические параметры - напоры в узлах сети и размер потоков. 4. Затраты на создание ЗОС.
Территория орошения моделируется геометрическим графом перепек тивных соединений узлов сети друг с другом. Граф может содержать дополнительные вершины для огибания зон запрета, а также для возможности ветвления трубопроводов не только на гидрантах сети, что хотя и увеличивает размерность решаемой задачи проектирования оптимальной сети, но часто проводит к меньшим затратам. Сама задача оптимального проектирования тогда ставится как сетевая оптимизационная задача на графе [3,42,43,46].
Как отмечено выше, решаемые с помощью САПР ЗОС задачи реализованы на практике, включая выдачу проектно-сметной документации. Вместе с тем, в контексте общей постановки оптимизационной задачи ЗОС наметились перспективные направления дальнейших теоретических и прикладных исследований. Отметим некоторые из тех, которые рассматриваются в настоящей диссертационной работе. 1) Математическая модель ЗОС в конечном счете представляет собой экстремальную, т.е. оптимизационную задачу на графе. Вместе с тем, эффективность того или другого допустимого варианта ЗОС в полной мере можно отразить не одним, а целым рядом показателей или критериев, которые являются принципиально разнородными. Иными словами, можно считать объективно обусловленным тот факт, что задачу ЗОС необходимо формулировать в многокритериальной постановке. 2) Используемые в САПР алгоритмы относятся фактически к направленному перебору остовов графа возможных соединений узлов сети друг с другом. Таким образом возникает проблема разработки достаточно эффективных алгоритмов для соответствующих экстремальных задач на графах. 3) В одном из последних исследований задачи ЗОС [50] принципиально новым является то, что проектирование ведется на реально заданном сортаменте труб и сортаменте насосно-силовых агрегатов. Для решения задачи вначале генерируется некоторый остов графа, определяются потоки по его ветвям и на этом остове решается задача оптимального определения потерь напора по ветвям сети, начиная с наименьшего из напоров, обеспечивающего потребные напоры в узлах сети.
Из сказанного вытекает правомерность предложения представить указанный остов в виде дерева, в котором веса ребер отражают диаметры соответствующих труб. Что касается учета сортамента насосно-силовых агрегатов, то его можно увязать с ограничением на степени вершин допустимого остовного дерева. Иначе говоря, речь идет о постановке известной NP-трудной (NP-полной) задачи об остовном дереве ограниченной степени [14]. -насосная станция на сети
В заключении настоящего параграфа приведем заимствованный из [50] рисунок исходного графа и выделенного на нем оптимального остовного дерева.
Вероятностный анализ применения алгоритма а2 к множеству M{n,R,A)
Пусть к данному графу G = (у, Е) применен алгоритм а0. Из определения этого алгоритма следует, что для всякой пары v ,v" є V проверка того, содержится или отсутствует ребро е = (у ,v ) в Е, производится не более чем один раз за все время работы алгоритма а0. В дальнейшем будем использовать известное неравенство, которое выполняется для всякого с є [0,1]: Кроме того, введем обозначения s0 - п0 +т0. Выбор величины s0 обусловлен необходимостью максимизировать вероятность P(Ln_x) успешного (результативного) завершения всей работы алгоритма а0. Иными словами, значение s0 должно иметь смысл оптимального номера шага s, на котором подэтап а заканчивает свою работу. Значение оптимума s0 определяется в процессе получения явных выражений, определяющих вероятность успешного завершения работы подэтапов алгоритма а0. Рассмотрим работу подэтапа а 1Л) на каком - либо его шаге s є {l,2,...,s0}. К началу такого шага оказывается выделенной в графе G0 цепь Ls_x = [v,,v2,...,vj. Следовательно, на шаге s при переходе от этой цепи к следующей цепи Ls = [vx,v2,...,vs,vs+x] выбор ребра e = (v,,vJ+1) может быть осуществлен {щ - s) способами, или, что тоже самое, выбор вершины vs+x для продления цепи Ls_x к цепи Ls осуществляется из множества Vx \{vpv2,...,vj мощности (пх -s), пх У\ - Вероятность того, что не существует в G ребра e = (ys,v), v є (Vx \{v1,v2,...,vj) равна q" s, откуда вероятность успешного (результативного) завершения шага s равна Отсюда, с учетом обозначения LnQ+mo=LSQможем представить в явном виде формулу для вычисления вероятности успешного (результативного) завершения работы подэтапа а 1): Это соответствие переносится и на подэтап а0 в результате успешного завершения работы которого получаем цепьЬ2по+2то=Ь2$о. По аналогии с (2.28) вероятность успешного завершения какого-либо шага 5 є {s0 +l,s0 + 2,...,2s0) подэтапа а 2) определяется равенством где значения показателя степени щ + s0 представляет собой количество свободных четных вершин, т.е. вершин v є V2, которые к началу шага s еще не включены в цепь Ls_x. Тогда с учетом равенства (2.30) и обозначения L2no+2mo=L2so по аналогии с (2.29) можем представить в явном виде формулу для вычисления вероятности успешного (результативного) завершения работы подэтапа а 2):
Переходя к вероятностному анализу работы этапа а 2), отметим, что вероятность успешного завершения какого - либо шага s этого этапа по существу определяется выражением (2.6), или более конкретно, мощностью множеств V{(sA) и V2A) в зависимости от того какому подэтапу {af X) или af 2)) относится шаг s. В соответствии с описанием этапа а и его подэта-пов значение этой мощности есть количество свободных вершин в дереве Ls_x. К началу работы подэтапа af X) количество таких свободных четных вершин в дереве (в цепи) L2so равно s0. По завершению каждого шага этого подэтапа количество свободных четных вершин уменьшается на 1. Отсюда, с учетом всех шагов s = 2s0 + l,2s0 + 2,...,2s0 + k0, где k0 определяется согласно (2.26), получаем формулу для вычисления вероятности успешного завершения каждого из этих шагов P(LS \LS_} ) = 1- q3s+l s. Отсюда, получаем формулу для вычисления вероятности успешного (результативного) завершения работы подэтапа а Л): Сравнивая выражения (2.29) и (2.31) нетрудно убедиться, что имеет место неравенство P(L2so \LSQ ) P(LSQ ). Отсюда, с учетом соотношений (2.29), (2.31), (2.32), (2.33), а также примечания 2.3, получаем нижнюю оценку для вероятности успешного завершения всей работы алгоритма а0: где с учетом (2.26) определяем Для полного определения параметров алгоритма а0 остается вычислить оптимальное значение s0. Для обоснования этого значения заметим, что в формуле (2.34) величина Рх монотонно убывает с ростом s0, а величина Р2 монотонно возрастает с ростом sQ. Отсюда вытекает, что произведение РХР2 достигает максимума в точке равенства Px(s0) = P2(s0). Приближенное значение s0, обеспечивающее выполнение указанного равенства с учетом выражений (2.35) и (2.36) можно искать, приравнивая между собой максимальные сомножители в этих выражениях : 1 - q"] s = 1 - q2s "1, что тоже самое пх - s0 = 2s0 - пх или отсюда получаем приближенное значение искомого Таким образом, для определения условий статистической эффективности алгоритма а0 с учетом (2.37) остается определить по возможности максимальное значение вероятности q, при которой для определяемой выражением (2.35) вероятности Рх выполняется неравенство Из правой части равенство (2.35) с учетом (2.37) получаем 1 - ехр{- In In п] - 1 при и — оо, т.е. для величины q определена верхняя оценка (2.39) при которой выполняется соотношение (2.38). Соотношение (2.38) выполняется для значений (2.37), (2.39). Эти значения приняты в предположении, что в выражении (2.34) выполняется равенство Р2 = 0(РХ). Таким образом, доказано следующее утверждение относительно условий статистической эффективности алгоритма а0. то алгоритм а0 почти всегда находит остовное дерево Ln_x на графе G.
Сведение интервальной задачи к задаче многокритериальной оптимизации
Доказательство. Рассмотрим w-вершинный связный граф G = (V,E) и выделим в нем вершину v0 максимальной степени. Множество (V \ {v0}) разбиваем на подмножества Vx,V2,...,Vk,...,Vm, где Vk состоит из вершин, для каждой из которых ее расстояние до вершины v0 равно к. Далее осуществляем по этапам к = \,2,...,т следующую операцию окрашивания. На этапе к = 1 окрашиваем каждую вершину v є Vx и ребро, которое соединяет ее с v0. Пусть окрашены вершины подмножеств Vl,V2,...,Vk. На этапе к + \ окрашиваем каждую вершину v є Vk+l и в точности одно ребро, соединяющее ее с некоторой вершиной v є Vk. При к +1 = т совокупность всех окрашенных ребер составит остовное дерево. По построению степень этого дерева равна максимальной степени вершин в графе G = (V, Е), т.е. в выделенном остовном дереве ЦФ (4.4) имеет максимальное значение. полиномиально разрешима.
Доказательство (конструктивное). Рассмотрим следующий алгоритм. Фиксируем какую-либо вершину v0 в данном графе и соединим ее с остальными вершинами кратчайшими цепочками (например, с помощью алгоритма Дийкстры [24] или часто применяемого в САПР так называемого волнового алгоритма Ли). По определению этого алгоритма получаем остовное дерево, которое содержит кратчайшие цепи от вершины v0 до остальных вершин. Полученное дерево обозначим через D(v0).
Воспользуемся теперь тем, что из определения радиуса графа [24] вытекает следующее Пусть данный граф G содержит остовное дерево минимального радиуса с центром в вершине v0. Тогда выделенное с помощью указанной выше процедуры дерево D(v0) представляет собой дерево минимального радиуса. Построим последовательность деревьев D(v), v є V в графе G = (V,E) и вычислим для каждого дерева его радиус p(D(v)). После чего остается в качестве искомого указать то дерево D(v0), у которого значение /?(Z)(v0)) минимально. Поскольку построение каждого остовного дерева D(v) с помощью волнового алгоритма требует не более 0(т), т = \Е\ элементарных операций. Включая определение радиуса этого дерева, то трудоемкость нахождения дерева минимального радиуса очевидно не превосходит 0{тп). Рассмотрим случай, когда ВЦФ (4.1) состоит из критерия вида MIN-МАХ и минимизируемого топологического критерия радиуса остовного дерева Рассматривая двукритериальную задачу об остовных деревьях на данном графе G є МпХ и его подграфах Gs, s = 1,2,..., L0, используем обозначения: Xs -множество всех таких решений этой задачи на Gs, которые оптимальны по критерию F2 (х); Xs - определяемое векторной целевой функцией (4.1),(4.6)-(4.7) паретовское подмножество множества Xs. Для этой задачи на всяком графе G с непустым множеством остовных деревьев X справедлива следующая лемма. ЛЕММА 4.3. Для каждого непустого множества паретовских оптиму-мов Xs, s L0 мощность его образа в критериальном пространстве состоит из одной точки, т.е. мощность F(XS) = 1.
Доказательство. Доказательство леммы почти очевидно и вытекает из определения парето-оптимального решения и того факта, что по построению
множества Xs значения критерия F2 (х) для всех х є Xs одинаковы. Лемма 4.3. доказана. Через ах обозначим алгоритм, с помощью которого в результате LQ кратного его применения осуществляется нахождение ПМА Х задачи с ВЦФ (4.1), (4.6)-(4.7). Через а обозначим точный метод нахождения остовного дерева х, оптимального по критерию F2 (х) (4.7), остовного дерева х є X на невзвешенном графе. Алгоритм ах состоит из этапов as, s = 1,2,...,Z0, где as - алгоритм а нахождения в графе Gs остовного дерева xs, оптимального по критерию F2 (х), определенного согласно (4.7). Алгоритм ах прекращает работу на шаге s = L0 +1, когда обнаружится, что граф Gs больше не имеет остовных деревьев. Результатом этой работы является множество Х{ах) = {xs}, s = 1,2,...,L0.
Заключительная процедура алгоритма ах для множества Х(ах) формирует подмножество Х(ах) его паретовских оптимумов, затем строится его ПМА, т.е. выделяется такое подмножество Х(а1) с Х{ах), которое имеет минимальную мощность и удовлетворяет условию F (X(al)) = F (Х(а{)).
Покажем теперь, что проблема нахождения ПМА для двукритериальной задачи об остовных деревьях с ВЦФ (4.1), (4.6)-(4.7) разрешима с полиномиальной сложностью [80]. Для этого достаточно доказать, что результат Х(ах) применения к ней алгоритма ах представляет собой искомое ПМА Х этой задачи. Доказательству предпошлем ряд вспомогательных утверждений.
Пусть X - множество допустимых решений рассматриваемой задачи с ВЦФ (4.1), (4.6)-(4.7), Х- собственное подмножество множества X. ЛЕММА 4.4. Если X с X и парето-оптимальное для множества X решение х є [X п X), то х является парето-оптимальным решением и для подмножества X .
Эта лемма представляет собой обобщение очевидного свойства одно-критериального оптимума.
Полиномиальная разрешимость однокритериальных задач об остовных деревьяях с топологическими критериями
Гиперграф - это такое обобщение простого графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин. Подобные объекты в математике известны давно, однако введение термина «гиперграф» связано с успешным распространением на них ряда важных понятий и методов теории графов. Пусть V - конечное непустое множество, Е - некоторое семейство непустых (необязательно различных) подмножеств множества V. Пара (V,E) называется гиперграфом G с множеством вершин V и множеством ребер Е. Равные подмножества в Е называются кратными ребрами гиперграфа. Число вершин Г гиперграфа G называется его порядком. Если вершина v є V принадлежит ребру е є Е, то будем говорить, что они инцидентны. Каждой вершине v є V гиперграфа G сопоставим множество Е(у) всех инцидентных ей ребер. Число \Е(V) называется степенью вершины v, а \е\ - степенью ребра е. Две вершины v и v гиперграфа G назовем смежными, если сущест вует ребро є є Е 9 которое содержит обе эти вершины. Два ребра е и е гиперграфа G назовем смежными, если е \\е Ф0. Если в гиперграфе G нет кратных ребер и степень любого ребра е равна h 5 то гиперграф G называется h -однородным. Ясно, что всякий про стой фаф является 2-однородным гиперграфом. Тем самым граф - частный случай гиперграфа. Звездой в гиперграфе G назовем такой подгиперграф, состоящий из ребер еєЕ пересекающихся по некоторому множеству вершин V , где V \ \e\.
Рассматриваемая далее математическая модель задачи водопользования базируется на математическом аппарате теории гиперграфов. Это обусловлено тем, что специфика этой теории в наибольшей степени приспособлена для абстрактного представления циклических процессов чередования. Это позволяет рассматривать как единое целое источник воды, способ ее очистки и населенный пункт, куда ее поставляют, что составляет в ниже представленной модели ребро. Каждому ребру приписывают веса, отражающие экономический и медико-гигиенический эффект от потребления воды из данного источника, при данном способе очистке данным населенным пунктом.
Считается заданным и-вершинный гиперграф G = (V,E), множество вершин которого V = (v) разбито на три подмножества Vs, s = 1,2,3, где Vx представляет собой множество источников воды, точнее, множество географических точек водозабора; V2 - множество способов очистки, где термин «способ» означает определенный технологический процесс, которые базируются на определенном техническом сооружении; V3 - множество объектов потребления воды (населенные пункты). Некоторые тройки элементов vs GVS, S = 1,2,3 образуют ребро е = (vx,v2,v3)e Е при условии, что для потребителя v3 є V3 может быть осуществлен забор воды из источника v, є Vx и при этом ее очистка может быть реализована на определенном очистном сооружении v2 є V2. Подразумевается, что всякий элемент v2 є V2 может быть «привязан» только к одной конкретной вершине V, є Г,. На рис. 5.1 представлен пример такого 10-вершинного гиперграфа G = (V,E) Е = {ех,е2,. ..,е7} который является 3-дольным (т.е. однородным (т.е. каждое ребро ееЕ состоит из трех вершин).
Специфической особенностью рассматриваемых гиперграфов является то, что всякая вершина, представляющая собой очистное сооружение не может принадлежать двум ребрам относящимся соответственно к двум различным источникам. Для некоторых источников v, Е Vx может оказаться недостаточно разовой очистки на конкретном очистном сооружении v2. Это означает, что на пути от источника до потребителя вода должна последовательно пройти через г 2 очистных сооружений v3,v4,...,vr+2. Этот случай отражается в предлагаемой математической модели тем, что множество Е включая в себя (г+ 2) - вершинное ребро e = (vx,v2,...,vr+2). Каждому ребру ееЕ приписаны веса wv ( ?), v = 1,2. Содержанием задачи определено следующее условие: в каждом ребре є є Е обязательно присутствуют представители vx є Vx и v3 є F3, и при этом v, и v3 называют концевыми вершинами ребра е, а отличные от них вершины называются внутренними вершинами этого ребра.
