Содержание к диссертации
Введение
Глава 1. Моделирование многостоковых сетевых систем. Показатель уровня просачиваемости 15
1.1. Теоретико-графовая многостоковая потоковая модель сложной сетевой системы 16
1.1.1. Некоторые понятия и определения теории графов 16
1.1.2. Многостоковая потоковая модель трубопроводной системы 18
1.1.3. Математические модели теории просачиваемости 23
1.3. Выводы 28
Глава 2. Исследование метрических характеристик ориентированных фрактальных графов с различными затравками 29
2.1. Ориентированный предфрактальный граф. Определение 29
2.2. Диаметр и радиус ориентированного предфрактального графа 37
2.3. Выводы 43
Глава 3. Алгоритмы распознавания ориентированных предфрактальных графов с различными затравками 44
3.1. Распознавание ориентированного предфрактального графа с затравкой "дуга" 44
3.2. Распознавание ориентированного предфрактального графа с затравкой "однонаправленный ориентированный путь длины g" 50
3.3. Распознавание ориентированного предфрактального графа с затравкой "внешненаправленная звезда" 58
3.4. Распознавание ориентированного предфрактального графа с затравкой "однонаправленный контур четной длины" 62
3.5. Выводы 73
Глава 4. Гарантированные оценк потока в многостоковых задачах на ориентированых предфрактальных графах с заданными затравками ... 74
4.1. Классификация потоков в сетевых системах 74
4.2. Многокритериальная оптимизация. Термины, понятия, алгоритмы с оценками 81
4.3. Многокритериальная потоковая задача на ориентированных предфрактальных графах 82
4.4. Выводы 90
Заключение 91
Библиографический список
- Некоторые понятия и определения теории графов
- Диаметр и радиус ориентированного предфрактального графа
- Распознавание ориентированного предфрактального графа с затравкой "однонаправленный ориентированный путь длины g"
- Многокритериальная оптимизация. Термины, понятия, алгоритмы с оценками
Введение к работе
В предшествующем развитии нелинейной динамики можно выделить два больших периода, связанных с развитием двух ее парадигм. В рамках первой было показано, что во многих открытых нелинейных системах вдали от равновесия происходит самоорганизация. При этом обычно возникают пространственно-неоднородные стационарные (т.е. не зависящие от времени) распределения переменных, которые И.Р. Пригожий предложил называть диссипативными структурами, либо возникают периодические или непериодические колебания, которые с легкой руки Р.В. Хохлова стали называть автоволновыми процессами.
При построении второй парадигмы основное внимание было уделено динамическому хаосу - сложному непериодическому поведению в простейших детерминированных системах (т.е. в таких, где будущее однозначно определяется прошлым и настоящим и нет случайных факторов). Основным результатом этого периода стало установление факта пределов предсказуемости, т.е. существование горизонта прогноза - конечного времени, через которое динамический прогноз поведения системы становится невозможен. Были также описаны универсальные сценарии перехода от простого движения к хаотическому при изменении внешнего параметра.
Обе развитые парадигмы базируются на ключевом для нелинейной динамики представлении о самоорганизации, т.е. о выделении из большого, а иногда бесконечного числа переменных, описывающих систему, сравнительно небольшого числа величин, называемых параметрами порядка, к которым на больших временах подстраиваются остальные степени свободы системы.
Активные исследования в рамках обеих парадигм проводились в течение 30 лет научной школой член-корр. РАН Курдюмова СП.
Одной из важнейших проблем современной нелинейной науки является вопрос о природе и свойствах сложного. Где граница, отделяющая простое от сложного? Какие механизмы приводят к появлению у сложной системы свойств, которые отсутствуют у ее частей, т.е. к целостному поведению?
Можно ли выделить общие черты в поведении сложных систем разной природы и, если «да», то чем обусловлена эта общность? Каковы перспективы развития единых подходов к сложному, применимых не только в технических, но и в общественных науках, а также в науках о живом? Обусловлена ли сложность процессами самоорганизации или является организованной искусственно?
Поиск ответов на эти и многие другие вопросы связан со становлением новой парадигмы нелинейной динамики - третьей по счету, — которая могла бы в полной мере претендовать на звание "науки о сложности" (science of complexity). Она призвана сформировать язык для описания свойств целостности и системности, катастрофического и рефлексивного поведения, необратимо развивающихся систем, взаимодействия явления и процессов разных масштабов...
Этот круг тем обычно обозначают словосочетанием "жизнь на кромке хаоса", хотя, по-видимому, более точной является метафора СП. Обухова о скольжении вдоль этой кромки, поскольку сложное не вытеснено на кромку, а только на ней и может существовать.
Можно сказать, что создаваемая парадигма сама, в некотором смысле, лежит на кромке хаоса, т.е. на стыке двух предшествующих парадигм. Сами они слишком просты, чтобы описывать сложное, ведь поведение изучаемых в их рамках систем достаточно однородно - диссипативные структуры "одинаково регулярны", хаос — "одинаково нерегулярен".
Кроме того, целостное поведение предполагает не только выделение параметров порядка из числа старых переменных, но и формирование в процессе самоорганизации новых, что также выходит за рамки парадигм самоорганизации и хаоса.
Сложное может быть понято только в простом контексте, иначе мы просто не сумеем увидеть за деревьями леса. Поэтому, попытки построения подробных исчерпывающих моделей каких бы то ни было сложных явлений-т.н. жесткое моделирование - при изучении сложного, заведомо обречены на
неудачу (по крайней мере, на настоящем этапе). Перспективным является построение, напротив, максимально упрощенных концептуальных моделей. Пределом упрощения здесь служит лишь сохранение каких-либо существенных черт поведения реальных систем (причем заранее, вообще говоря, нельзя указать, каких именно). Этот подход получил название мягкого моделирования.
Одной из отличительных черт сложных систем является то, что они обладают свойствами, которые не присущи составляющим их частям. Поскольку при мягком моделировании не ожидается получения ответов на том же языке, на котором задаются вопросы, оно оказывается потенциально перспективным при изучении сложного.
Жесткие модели, напротив, обыкновенно не демонстрируют никаких черт, кроме тех, которые были изначально заложены в их правила, т.е. получаемые результаты оказываются хороши ровно в той степени, в какой мы a priori знаем существо вопроса - фундаментальные законы, непосредственно определяющие ход процесса. Они лишь уточняют наши старые представления, не способствуя выработке новых. Поэтому, наделяя части системы теми свойствами, которые мы заранее надеемся увидеть у нее в целом, мы фактически исключаем из рассмотрения эффекты, связанные с ее сложностью и целостностью, самоорганизацией и выделением параметров порядка. Соответственно не удается определить, какие именно базовые свойства или их комбинации определяют те или иные "конечные свойства".
Еще одним доводом в пользу мягкого моделирования является то, что сейчас наступает революционный этап расширения рамок естествознания, когда фундаментальная наука становится достаточно зрелой, чтобы рассуждать на темы, традиционно относимые к наукам гуманитарным или вообще ранее не рассматривавшиеся как научные. Однако в этих областях существует принципиальное противоречие между недостаточной строгостью их языка, с одной стороны, и необходимостью формального вывода следствий и сопоставления их с реальностью - с другой.
Путем преодоления этого противоречия и является мягкое моделирование, служащее источником образов и аналогий, которые могут конкретизировать базовые понятия рассматриваемой дисциплины, обрисовывать взаимосвязь между ними и стать основанием для философских обобщений, т.е. вместо того, чтобы говорить обо всем подробно, но нестрого, появляется возможность высказывать строгие суждения общего плана, лежащие в рамках одной теории, одного круга представлений, которые можно проверять, развивать и соотносить с реальностью, - по крайне мере, в главном.
В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и (или) нетривиальных связей между ними. А с другой стороны, речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны,, и понятие "сложность" далее будет использоваться только во втором из упомянутых значений. Хотя строгого определения сложности не существует, опыт развития синергетики и изучения конкретных систем, интуитивно определяемых нами как сложные, позволяет высказать некоторые общие соображения о свойствах любой сложной системы на разных уровнях описания.
На математическом уровне сложность неразрывно связана с нелинейностью описания, поскольку к линейным системам применим принцип суперпозиции, позволяющий независимо рассматривать различные действующие факторы, части системы и т.п., что гарантирует ее простоту.
На физическом уровне описание, как правило, возможно лишь в статистических терминах, как то: плотность вероятности, корреляция, ляпунов-ские показатели, математическое ожидание, дисперсия и т.п. Это происходит либо в силу характерного для многих нелинейных систем хаотического поведения, ограничивающего возможности детерминированного описания,
либо в силу очень большого числа составляющих систему элементов, делающих такое описание бесполезным практически.
На философском уровне наиболее существенным является осознание того обстоятельства, что чем более изощрен и специфичен механизм некоторого явления, тем реже оно должно реализовываться. А поскольку практически все сколь- нибудь важное или интересное в природе так или иначе связано со сложностью, то лежащие в ее основе механизмы должны быть просты и универсальны.
Резюмируя сказанное, приходим к выводу, что работа в рамках третьей парадигмы должна быть сосредоточена на универсальных нелинейных механизмах, приводящих к сложному поведению.
К таким сложным системам отнесем современные сетевые системы, которые являются "живыми организмами" с изменяющейся во времени структурой. В сетевых системах возможно появление как новых узловых элементов, так и новых связей между уже существующими. Характер изменений может быть совершенно различным. Поэтому изменение структур сетевых систем может происходить также по совершенно различным законам. В настоящее время изучение и выявление таких законов занимают особое место в исследованиях сетевых систем. Общие концептуальные представления о структурных изменениях сетевых систем можно объединить понятием "структурная динамика".
Правилам изменения структур сетевых систем и законам структурной динамики посвящено множество работ [58-60,176,180,183-196,199,200]. В значительной степени это работы иностранных исследователей. Отечественными исследователями для описания изменений в сложных сетевых структурах было введено понятие "фрактального графа" [76,158-166,196]. Фрактальный граф (и его конечный аналог - предфрактальный граф)- объект, совмещающий в себе основные идеи структурной динамики, свойство масштабной инвариантности (самоподобия) фракталов [13,103,156,181], и абстрактность теории графов.
Еще до введения понятия фрактального графа возникали и решались задачи с фрактальной структурой. Например, в 1989 году И. Г. Винтизенко в диссертационной работе на соискание ученой степени доктора технических наук « » была рассмотрена и решена задача о компоновке , алгоритм решения которого имеет фрактальную структуру.
Изучение фрактальных графов и областей их приложения ведутся по трем направлениям: распознавание фрактальных графов [76], свойства и характеристики фрактальных графов [58-61,77-82,184], задачи многокритериальной оптимизации [181] в системах с масштабно-инвариантной структурой [7-9,36-47]. В работах, связанных с оптимизационными задачами, предложен и обоснован ряд параллельных алгоритмов поиска решений [40,47,62,63].
Эту методологию можно использовать для описания и моделирования селевых потоков, водотоков рек, потоков лавинообразных процессов, а также потоков транспорта в системе автомобильных дорог, перевозок товаров по железным дорогам, перекачки нефти и газа по сети трубопроводов от источника до пункта назначения, используя потоки в сетях и на графах [20-22,27,29,87,149,159].
С одной стороны, естественным образом, возникает класс многокритериальных задач оптимизации [2,11,12,24,31,92-96,124-126] потоков в сетевой системе с ограничениями по пропускным способностям передающих составляющих. Поиск решения многокритериальных потоковых задач необходим при динамически изменяющихся, или случайно выбранных значениях пропускных способностей передающих составляющих сетевых систем.
Важные классы задач, с другой стороны, возникают при исследовании непосредственно самой структуры многостоковых сетевых систем. Во-первых, это задачи допустимости (или существования) потоков между выбранными тяготеющими парами. В-вторых, это задачи анализа, т.е. задачи исследования систем на соответствие и наличие заданных характеристик, и задачи синтеза, т.е. задачи проектирования систем с заданными характери-
стиками. Отметим, что под характеристиками систем подразумеваются различные их свойства, связанные как со структурными так и пропускными особенностями. В настоящей работе они будут детально классифицированы, и подразделены по качественные и количественные характеристики.
Все перечисленные задачи лежат в области понятий математического моделирования, исследования операций и системного анализа [11,14-17,85,127,128,150].
В нескольких институтах Российской Академии Наук (в Институте прикладной математики им. М.В. Келдыша, Институте проблем управления им. Трапезникова, Вычислительном центре им. А.А. Дородницына), в различных научных школах ведутся работы по исследованию живучести и поведения сетевых систем, находящихся в условиях внезапных внешних воздействий неопределенного характера [66-73,88-91,98-104, 135-139].
Способность системы функционировать во внештатных режимах называют живучестью [32,102]. Более узко способность системы функционировать в условиях внешних негативных воздействий ряд исследователей называют стойкостью [56,66-73,135-139]. Исследование живучести, стойкости и уязвимости [100,112-114] сетевых систем являются важными практически востребованными задачами.
Краткое содержание и структура диссертационной работы
Диссертационная работа посвящена моделированию сложных сетевых систем и моделированию задач на этих системах.
Целью диссертационного исследования является определение потока на пред фрактальном ориентированном графе, оптимизирующего целевые функции. В соответствии с поставленной целью были решены следующие задачи:
1. Построение математической модели потока сетевой системы с одним истоком и множеством стоков.
Адаптация многостоковой потоковой модели для сетевой системы со сложной масштабно-инвариантной (фрактальной) структурой.
Определение метрических и числовых характеристик ориентированных фрактальных графов.
Разработка алгоритмов распознавания масштабно-инвариантных структур в виде ориентированных предфрактальных графов.
Постановка и исследование многокритериальной задачи о потоке на ориентированных предфрактальных графах.
Объектом исследования являются ориентированные предфрактальные графы.
Предметом исследования являются: характеристики ориентированного предфрактального графа; многокритериальная задача о потоке на предфрак-тальном ориентированном графе.
В диссертационной работе использованы теория графов, методы математического моделирования комбинаторной оптимизации, методы и подходы дискретной математики и теории графов, в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач, связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем. В работе используются также методы когнитивного моделирования, связанные с анализом динамики нелинейных процессов, развивающихся на ориентированных графах, методы нелинейной динамики, теории вероятности, теории фракталов и имитационного моделирования.
В диссертационной работе построена математическая модель потока сетевой системы с одним истоком и множеством стоков элементов.
Сетевая система со сложной масштабно-инвариантной (фрактальной) структурой представлена на многостоковой потоковой моделью.
Введено понятие ориентированного предфрактального графа, исследован ряд его свойств и характеристик.
Получены оценки метрических (радиуса, диаметра, минимальной степени) и числовых (общего суммарного веса) характеристик ориентированного предфрактального графа, порожденного различными классами затравок (дугой, контуром, полным орграфом).
Разработаны алгоритмы распознавания предфрактальных ориентированных графов порожденных различными затравками.
Описана многокритериальная постановка задачи о потоке на ориентированных предфрактальных графах. Векторно-целевая функция в предложенной многокритериальной постановке состоит из шести критериев, каждый которых имеет конкретную практическую интерпретацию. Для нескольких из критериев векторно-целевой функции приведены и обоснованы оценки оптимальных решений.
Практическая ценность результатов работы определяется возможностью их применения при создании систем принятия решений. Построена математическая теоретико-графовая многостоковая потоковая модель сетевой системы. Все исследованные модели, в случае реализации, способны повысить эффективность рассматриваемой системы.
Дано определение ориентированного предфрактального графа, а также заложены теоретические основы развития ориентированных предфрактальных графов; предложены: методика подсчета метрических характеристик ориентированного предфрактального графа; алгоритмы распознавания ориентированного предфрактального графа. Теоретическая значимость состоит в разработке основ целого ряда направлений по фрактальным ориентированным графам.
В первой главе построена и исследована теоретико-графовая многостоковая потоковая модель сетевой системы и подсчитан показатель уровня просачиваемости.
Во второй главе введено понятие ориентированного предфрактального графа и исследован ряд его свойств и характеристик.
Третья глава посвящена распознаванию ориентированных предфрактальных графов. Предложен и обоснован комплекс алгоритмов распознавания ориентированных предфрактальных графов, порожденных различными затравками: алгоритм ух — распознавание ориентированного предфрактального графа, порожденного затравкой "дуга"; алгоритм у2 — распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины g"; алгоритм у3 — распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда"; алгоритм у 4 - распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный контур четной длины".
Все предложенные алгоритмы являются полиномиальными.
Четвертая глава посвящена многокритериальной постановке потоковой задачи на ориентированных предфрактальных графах.
На основании результатов исследования на защиту выносятся следующие положения:
1) многостоковая потоковая модель сложной сетевой системы представлена предфрактальным ориентированным графов, для которого определен уровень просачиваемости;
исследован ряд свойств и характеристик ориентированного предфрактального графа, порожденного различными классами затравок; получены оценки метрических (радиуса, диаметра, минимальной степени) и числовых (общего суммарного веса) характеристик;
разработан комплекс алгоритмов для распознавания предфрактальных ориентированных графов, порожденных различными затравками:
— распознавание ориентированного предфрактального графа, порож
денного затравкой "дуга";
- распознавание ориентированного предфрактального графа, порож
денного затравкой "однонаправленный ориентированный путь длины g";
распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда";
распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный цикл четной длины";
4) многокритериальная модель задачи о максимальном потоке на ориентированном предфрактальном графе определена шестью критериями; с помощью известного алгоритма Форда-Фалкерсона выделяется приближенное решение поставленной задачи и вычисляется погрешность.
Некоторые понятия и определения теории графов
Будем считать тождественными следующие понятия: граф системы и структура системы, вершина графа и элемент системы, дуга графа и связь между элементами системы.
Для всякого конечного ориентированного графа будем использовать обозначение -G = {V,E), где V = {vi},i = \,n - множество вершин, а E={e = (v,ii)} - множество его дуг. Последовательность чередующихся вершин v,- и дуг е,- = (v/5v/+) (vi,ei,v2,e2,...,vhehvi+l,...,vN), v,- єУ, i = 1,2,...,N, (1.1) орграфа G = (V,E) называется маршрутом или (vj, v ) -маршрутом. Вершины Vj и Уд, назовем крайними, а все остальные - промежуточными. Длиной маршрута назовем число входящих в него дуг. Маршрут называется цепью, если все входящие в него дуги различны, и путем, если входящие в него вершины различны. Будем говорить, что вершина vN достижима из вершины Vj, если существует (VJ , vN ) -путь. Если в орграфе G нет параллельных дуг и петель, маршрут (1.1) можно записать в виде последовательности его вершин = (vl5v2,...,v,-,v,-+1,...,vAr).
Маршрут называется циклическим, если совпадают его крайние вершины. Циклический путь называется контуром .
Последовательность (1.1) чередующихся вершин и дуг орграфа G таких, что et =(v,-,v/+1) или ei = (v/+1, v,-), называется по л у маршрутом. Аналогично определяются полуцепь, полупуть и полуконтур.
Орграф называется сильносвязным, если любые две его вершины достижимы друг из друга. Орграф называется слабосвязным, если две его вершины соединены полупутем.
Сильносвязной компонентой орграфа называется его максимальный, относительно включения, сильносвязный подграф. Очевидно, что отношение взаимной достижимости орграфа G рефлексивно, транзитивно и симметрично. Поэтому получим разбиение множества вершин V на классы, если в один класс включим вершины, достижимые друг из друга. Как подтверждается, подграфы, порожденные классами этого разбиения, и только они, служат сильносвязными компонентами орграфа G. В орграфе могут быть дуги, не входящие ни в одну из его сильносвязных компонент.
Пусть {Н1г,Н2,...,Нт} - множество всех сильносвязных компонент орграфа G. Конденсацией орграфа G называется граф G , вершины hl,h2,...,hm которого соответствуют сильносвязным компонентам орграфа G, и пара (hj,hj) является дугой в G тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте Hj а конец - Н.-.
Очевидно, что любой контур орграфа G входит в одну из его сильно связных компонент, но тогда конденсация G не имеет контуров, а значит является бесконтурным графом.
Пусть H=(W,Q) есть n-вершинный связный граф. Длина кратчайшего пути, соединяющей пару вершин w,v eW, называется расстоянием между вершинами w и v и обозначается через p(w, v). Заметим, что введенное та ким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.
Для фиксированной вершины weW величина s(w) max p(w,v) Have зывается эксцентриситетом вершины w&W. Максимальный среди всех эксцентриситетов вершин графа H=(W,Q) называется диаметром графа Н и обозначается через d(H), т.е. d(H) = maxs(w). Если пара вершин u,weW CO-единяется кратчайшим путем длины p(u,w) - d(H), то этот путь называется диаметральным. Вершина w называется периферийной, если s(w) = d(H). Радиус графа Я обозначается через г(Н) и вычисляется по формуле r(H) = m ms(w). Вершина w называется центральной, если s{w)-r{H). weW Центром графа Я называется множество центральных вершин.
Распространение (продвижение) потока от одного элемента і системы к другому на графе системы будем задавать ориентированным ребром- дугой с определенными началом и концом. Ориентированное ребро называют дугой, а граф с дугами - орграфом . Орграф структуры моделируемой системы не будет иметь петель (т.е. дуг, конец и начало которых совпадает). На орграфе G-(V,E) для дуги є, є Ё,і є jl,2,..., Ё] весом co(et), является величина пропускной способности дуги графа системы.
Диаметр и радиус ориентированного предфрактального графа
Для всякого предфрактального ориентированного (п,Ь)-графа GL=(VL,EL) множество остовных деревьев X = X(G) содержит собственное подмножество, состоящее только из наименьшего остовного дерева (НОД), то есть выполняется строгое неравенство для их мощностей:
Доказательство. Для данного предфрактального (и,/,)-графа GL рассмотрим в траектории 2.1 ее начальные элементы GX=H и G2. Выделим в ( =( , ) остовное дерево xl=(Vl,Ex) минимальной степени deg(x,) = (maxdegv) = S0(G{). В Gx выделим и окрасим дуги ееЕх. Далее в veV\ ч каждой затравке графа G2 = (V2, Е2) выделим остовное дерево минимальной степени, равной S0(H). Все дуги, выделенных таким образом по построению остовных деревьев, и все окрашенные ребра в G2, образуют остовное дерево, в котором, в силу непересечения старых ребер, каждая вершина имеет степень, не превосходящую S0(H) + \.Тем самым неравенство 2.4 для текущих графов G, и G2 доказано.
Достижимость верхней оценки 2.4 вытекает с очевидностью для случая, когда затравка Н представляет собой простой цикл, для которого число S0(H) =1 и при этом граф G2 не является гамильтоновым.
Полное доказательство теоремы 2.2 для любого (гс,)-графа осуществляется индукцией по / = 1,2,3,...,L. Действительно, рассмотрим в траектории предфрактального графа текущий орграф GL=(VL,EL) с числом вершин N[ = К/, в котором N; -1 дуг оказываются окрашенными и образуют остовное дерево х, =(V,,E ). При переходе к текущему графу GM каждая вершина этого дерева замещается затравкой Я. Выделим и окрасим в каждой из этих затравок остовное дерево минимальной степени S0 (Я). Поскольку, по определению траектории старые ребра в GM не пересекаются, то каждая вершина v є Vl+l будет инцидентна не более чем (S0(H) +1) окрашенной дуге. Учитывая при этом, что все окрашенные дуги образуют остовное дерево, получаем выполнения неравенства (2.4).
Доказательство достижимости оценки (2.4) получается аналогично представленному выше доказательству для 1 = 2. ТЕОРЕМА 2.2 Для всякого (я,)-графа GL =(VL,EL), порожденного затравкой Я справедливы оценки минимальной степени: SQ(H) S0(G) LSQ(H), (2.5) причем верхняя и нижняя оценки достижимы.
Доказательство. Рассматривая траекторию предфрактального ориентированного графа, построим в ней текущие остовные деревья х, =(V,Exl), E аЁ,, I = 1,2,...,L следующим образом: выделим в G произвольное остовное дерево, которое обозначим xl = (VVEX ), всякая дуга из хх є Ех окрашена.
Далее в каждой затравке текущего графа G2 выделим ее остовное дерево, дуги которого окрасим. Эти окрашенные ребра вместе с ребрами дерева хх образуют в G2 его остовное дерево, которое обозначим х2 =(V2,EX ), Е а Ех . Продолжая этот процесс индуктивно по / = 1,2,..Х, рассмотрим в траектории текущий граф G,, в котором при переходе к GM каждая вершина v G V/ замещается затравкой Н. Выделим в каждом из этих затравок какое-либо остовное дерево, дуги которого окрасим. По построению выделенные остовные деревья указанных затравок, вместе с окрашенными дугами выделенного в G, текущего дерева х7 =(V,EXI) образуют текущее остовное дерево хм = (VM ,ЁХ ) текущего графа GM. Относительно описанного выше процесса построения текущих деревьев JC/5 / = 1,2,.../, справедливы два утверждения. Во-первых, при I = L получаем остовное дерево, которое по своему построению представляет НОД. Во-вторых, всякое остовное дерево данного графа G = GL может быть получено как результирующий элемент последовательности текущих деревьев X/, / = 1,2,..Х.Тем самым, первая часть теоремы доказана. Под весом остовного дерева будем понимать сумму весов дуг ОД. ТЕОРЕМА 2.3 Во всяком масштабированном взвешенном (п, L) -графе GL =(VL,EL) при q — вес каждого его НОД ограничен сверху величиной п ——, где р(Н) - максимум веса остовных деревьев затравки Н. \-nq
Доказательство. Рассмотрим какое-либо НОД x = {V,Ex) данного (n,L) -графа G = (V,E), ЁхаЁ. Из определения НОД вытекает, что его множество ребер разбито на подмножество Ё[ ребер ранга /, / = \,L, причем мощности этих подмножеств определяются формулой: Ё = (п-1)п -\ (2.6) Для начальных весов ребер затравки Н = (W, Q) используем далее обозначение (р(Н) = max Xwi(e) гДе максимум берется по множеству Y всех оставшихся деревьев y = (JV,Qy) затравки H,Qy eg.
Распознавание ориентированного предфрактального графа с затравкой "однонаправленный ориентированный путь длины g"
Алгоритм распознавания предфрактального дерева, порожденного затравкой «однонаправленный путь длины g», будем строить по принципу описанного выше алгоритма у1, за исключением некоторых дополнительных процедур условия «сформированное» затравки.
Через у2 обозначим алгоритм распознавания ориентированного предфрактального (g + l,L) -дерева D = {V,E) в случае, когда его затравка Н - (W,Q) представляет собой простой путь длины g (g дуг). До применения алгоритма у2, как и в предыдущих алгоритмах распознавания, проверяем выполнение необходимых условий предфрактальности. В алгоритме у2 используем элементарные операции: а) окрашивание дуги; б) стягивание дуги. Пусть данный ориентированный граф G = (V,E) является ориентированным деревом. Алгоритм у2.
Цель применения алгоритма у2 к данному ориентированному (g + \,L) -дереву D состоит в том, чтобы преобразовать D в ориентированное (g + \,L — 1) дерево Dx. Применительно к D работа у2 состоит из К этапов, пронумерованных индексом k=l,2,...JC; K L-\. В свою очередь, всякий этап (кроме последнего) состоит из подэтапов, пронумерованных индексами 7Гк = 1,2,..., тк, где величина тк есть число висячих путей в дереве, которое представлено на вход алгоритма у2 к началу реализации этапа к. Каждый очередной подэтап реализуется на очередном висячем пути и состоит из шагов s=l,2,...,d, где d - длина, т.е. число дуг в этом пути. На каждом из этих шагов рассматривается очередная дуга указанного пути, которая окрашивается или остается неокрашенной в зависимости от того, не окрашивалась или окрашивалась дуга на предыдущем шаге. Пусть M = M(D) - множество всех (9-путей данного ( +1,)-дерева D = (V, Е). Можно считать очевидным следующее УТВЕРЖДЕНИЕ 3.2 Для всякого ориентированного ( +7,,)-дерева D его множество M{D) определяется однозначно. Через Мк будем обозначать подмножество всех тех 0-путей , на которых реализуются подэтапы этапа к, т. е. Мк - это (исходная) информация, ко к торая составляет вход этапа k; [jMk =М. /ы
Работа этапа к=1 состоит из m1=JM1 подэтапов, пронумерованных индексом 7Tj =1,2,...,171]. На подэтапе пх рассматривается TTJ-ЫЙ по порядку висячий путь, дуги которого имеют одностороннюю ориентацию в направлении к висячей вершины этого пути. Далее дуги nx-vo висячего пути нумеру ются в направлении от висячей вершины индексами 1,2,3,..., после чего окрашиваются все дуги, кроме дуг, соответствующие индексы которых кратны g+1, они остаются неокрашенными.
Пусть осуществлено к этапов, в результате которых в данном дереве D оказывается непустым множество неокрашенных дуг. Тогда в работе алгоритма у2 следует переход к этапу (+1). В начале этапа к+1 формируется множество Mk+i висячих путей дерева, являющегося результатом преобразования предыдущего этапа.
Началом каждого такого пути является узловая вершина, инцидентная ориентированным дугам, а также одной и только одной неокрашенной дуге. Эти пути нумеруются индексом 7Гк+х = 1,2,...,тк+1, тк+[ = \Мк+[\.
Работа подэтапа 7гк+1 заключается в раскраске дуг лгк+1-го пути согласно следующих правил:
1) если начальная дуга пути пересекается дугами, две из которых яв ляются окрашенными, то окрашиваются все дуги, кроме дуг, которые обо значены индексом с номером i = (l + (g+ ї)т), где т = 0,1,..., [—] и d- длина g рассматриваемого висячего жк+] -го пути;
2) если начальная дуга пути пересекается дугами, не являющимися окрашенными, то окрашиваются все дуги тгк+1 -го пути, кроме дуг, индексы которых кратны (g+l);
3) если начальная дуга пути пересекается дугами, одна из которых является окрашенной е {v\v"), то определяется длина z (число дуг) подпути
C = [v",...,v] О-пути, состоящая только из окрашенных дуг О-пути и содержащая дугу е = (v ,v"):
Многокритериальная оптимизация. Термины, понятия, алгоритмы с оценками
В классической (1-критериальной) оптимизации задача считается решенной точно, если в X найдено хотя бы одно решение х , на котором значение критерия F(x) = Fl О) достигает требуемого экстремума, например, минимума. При этом X может содержать сколь угодно мощное подмножество Х оптимумов задачи F(x), однако вопрос о выделении из X всех представителей х є Х не ставится. Аналогично, в многокритериальной оптимизации не ставится вопрос о выделении из X всего паретов-ского множества X. Говорят, что всякое полученное с помощью некоторого алгоритма а подмножество Ха с X является точным решением многокритериальной задачи, если F(Xa) = F{X), т.е. если образ выделенного Ха совпадает с П-границей МД F{X). Нахождение точек П-границ F{X) относится к числу очень важных, и в то же время, очень трудных задач дискретной оптимизации. Трудоемкость выделения из X подмножества Ха отвечающего определению точного решения задачи F(X) = {(F1(x),F2(x),F3(x),F4(x),F5(x),F6(x)),x =X }, по-видимому существенно превосходит трудоемкость решения так называемых переборных или универсальных задач, для которых известны лишь алгоритмы экспоненциальной трудоемкости.
По указанной причине, одной из наиболее актуальных является разработка такого приближенного алгоритма а, который для определенного класса исходных данных многокритериальной задачи гарантирует получение приемлемых приближенных решений Ха за счет существенного сокращения трудоемкости Ха с X. При этом предполагается строгое математическое обоснование, как границ выделенного класса исходных данных, так и оценок качества (точности) получаемых решений. Здесь речь идет об оценивании в терминах пространства критериев F{X) точ ности аппроксимации паретовского множества X, выделенным с помощью алгоритма подмножеством Ха а X.
Методология алгоритмов с оценками разрабатывалась применительно к классическим, т.е. однокритериальным задачам, которые являются частным случаем задач векторной оптимизации с множеством критериев F(x) = {Fk(x)},k 2. Отсюда, многие, казалось бы, устоявшиеся определения и понятия в условиях многокритериальности "не работают" и по этой причине нуждаются в построении новых, более общих моделей и формальных определений. При этом предполагается, что всегда выполняется система строгих неравенств: ак О, где ак - minF x), к = 1,6. хеХ Приведем некоторые замечания. Для каждого Fk F выделим в X подмножество частных оптимумов Хк -{хк /Fk(xk) = minFk(xk)} и рас хеХ т 0 смотрим пересечениеX = f]Xk . Если оно непустое(X 0), то тогда по определению X = X и мощность множества точек П-границы F(X) = F{X) . В этом случае решение задачи F(x) = (F1(x),F2(x),...,Fm(x)) заключается в нахождении хотя бы одного элемента из множества X. Если X = 0, то F(X)\ 2 и, в случае выбора какой бы то ни было точки Зс0 є X в качестве окончательного решения задачи возникает противоречие или конфликтная ситуация: среди невыбранных точек найдется такая, которая по некоторому показателю качества Fk строго превосходитх0. Указанное противоречие порождает основную проблему многокритериальности, или в другой терминологии, проблему принятия решения.
ПРИМЕЧАНИЕ 4.1 Рассмотрим подмножество X є X, такое, что в пространстве критериев задачи F(X) количество точек F(X ) 2 и любая пара точек из F(X ) векторно не сравнима по F(X), т.е. в каждой такой паре нет отношения доминируемости. При этом пересечение X П X может быть пустым. Ясно, что в этом случае по отношению к точкам из X основная проблема многокритериальное в пределах X сохраняется в такой же степени, как и для паретовского множества X. т ПРИМЕЧАНИЕ 4.2. Если множество X - ( }Х% не пусто, то в дальні нейшем точки хєХ будем называть абсолютными оптимумами. В этом случае, согласно приведенным выше определениям и равенствам X — X, задача F решена точно, если из множества допустимых решений X выделен хотя бы один абсолютный оптимум х еХ.
Пусть Ха - множество, выделенное с помощью некоторого алгоритма а решений х є X. Через ха є Ха обозначим множество векторно не улучшаемых (в пределах Ха) решений задачи F(X). В соответствии с известным принципом Парето и замечанием 1.1 множество Ха называется приближенным решением задачи F(X), получаемое с помощью алгоритма а.
