Содержание к диссертации
Введение
ГЛАВА 1. Полиэдральный подход к исследованию структурно сложных системы 15
1.1. Симплициальная модель структурно сложной системы 15
1.2. Исследование роли отдельных элементов системы 21
1.2.1. Эксцентриситет 21
1.2.2. Использование симплициальных звезд в исследовании роли элементов.
1.2.3. Исследование узлов структуры с позиции входящих и исходящих связей
1.3. Анализ сложности структуры систем 35
1.3.1. Структурный вектор 35
1.3.2. Мера сложности 36
Глава 2. Исследование сетевых потоков 39
2.1. Сетевой подход в рамках полиэдрального анализа зэ
2.2. Характеристики потоков 43
2.3. Динамичность 46
2.4. Согласованность 48
ГЛАВА 3. Многомерное взаимодействие элементов 52
3.1. Многомерные связи и многомерные потоки 52
3.2. Анализ q-компонент 55
3.3. Симплициальная модель q-компоненты 70
3.4. Нерв совокупности 71
3.5. Многомерные препятствия, q-дыры 72
ГЛАВА 4. Полиэдральный анализ транспортных сетей
4.1 Исследование транспортных сетей с позиций полиэдрального анализа
4.2 Исследование участка реальной транспортной сети 84
ГЛАВА 5. Применение полиэдрального подхода к исследованию систем, описанных уравнениями в пространстве состояний
5.1 Подходы к построению симплициальнои модели линейных динамических систем
5.2 Полиэдральный анализ при нечётком подходе к описанию симплициальных комплексов
заключение из-
литература не
приложение '23
- Анализ сложности структуры систем
- Характеристики потоков
- Симплициальная модель q-компоненты
- Исследование участка реальной транспортной сети
Введение к работе
Значительные достижения науки и техники в разработке, создании и управлении системами большой сложности, совершенствовании существующих методов их анализа и синтеза способствуют возникновению новых интересных задач, охватывающих проблематику самых разных областей традиционной науки. Общие системные концепции позволяют перейти к объединяющей научные направления деятельности, сосредоточенной на исследовании свойств систем и связанных с этим задач, и обычно называемой теорией систем. Эта деятельность характеризуется стремлением к раскрытию присущей системам сложности, определению общей структуры организации способов взаимодействия между элементами системы, совокупного взаимоотношения системы и внешней среды.
Актуальность работы. Одним из наиболее важных и необходимых этапов исследования систем является структурный анализ, требования к результатам которого возрастают в связи с усложнением структуры самих систем и необходимостью повышения качества решений по организации взаимодействия подсистем системы. Изучение структуры представляет интерес и с точки зрения выявления закономерностей существования и развития систем, а также особенностей или недостатков, которые требуют повышенного внимания исследователя. Кроме того, на этапе структурного анализа формируется первоначальное представление, влияющее в значительной степени на объяснение многих характеристик систем, среди которых можно выделить структурную устойчивость и сложность организации, выявляются "слабые места" системы и определяется значимость ее элементов. Поскольку всякая сложная система выполняет определенные функции, реализуемые посредствам потоков энергии, материи, информации, то анализ структуры систем, по существу, ориентирован и на определение множества ограничений и направлений (каналов), которые структура способна создать для потоков. В настоящее время в математике существует множество традиционных подходов и направлений, таких как теория графов, кластерный анализ, описание систем в пространстве состояний, которые в той или иной степени позволяют проводить анализ структур сложных систем. Многие из этих подходов фундаментальны по своей природе и имеют широкую область
5 применения. Они получили довольно значительное развитие и популярность, а их методы и алгоритмы играют значительную роль в моделировании систем.
Так, например, теория графов, начиная с 70-х годов, привлекает к себе пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от неё, -экономику, социологию, лингвистику и другие. Теория графов оказалась полезной при изучении задач, возникающих в некоторых других разделах математики, таких как топологическая теория, теория групп, теория матриц и теория вероятностей. Не маловажной является взаимосвязь между теорией графов и теоретической кибернетикой, особенно теорией автоматов, исследованием операций, теорией кодирования и теорией игр. Всякий раз, когда встречалась новая область применения теории графов, возникала необходимость во введении и изучении новых или в дальнейшей разработке некоторых известных понятий. Эта необходимость в свою очередь возбуждала творческую активность в области исследования различных связанных с ними концепций. Такое непрерывное взаимодействие способствовало быстрому росту этой ветви математики. Был написан ряд книг, обсуждающих различные аспекты теории графов: анализ, синтез, перечисление, алгоритмы и приложения. Разработанная Фордом и Фал^ерсоном теория потоков в сетях осветила ряд комбинаторных вопросов и позволила получить новые доказательства важных теорем теории графов. Закон Кирхгофа о сохранении потока играет центральную роль в разработке теории потоков в сетях. Большое внимание было уделено конструированию сетей связи, имеющих заданные свойства. Эта задача обычно сводится к построению экстремального графа, т.е. графа, имеющего минимальное или максимальное число ребер и обладающего заданным значением одного из топологических параметров.
Большую роль сыграла теория графов и в такой области знаний как вычислительная техника. Для специалистов по вычислительной технике теория графов - это удобный язык выражения понятий этой области. Широкое применение теория графов получила при исследовании проблем оптимизации, возникающих при построении компиляторов. В рамках этих исследований были разработаны многие, неизвестные ранее теоретико-
графовые понятия. Теория графов имеет большую привлекательность для специалистов по вычислительной, технике и помимо использования ее как инструмента для решения конкретных задач. Одним из основных направлений в вычислительной технике является построение эффективных алгоритмов и анализ их сложности, где теория графов предоставляет большие возможности.
Большую роль в исследовании систем играют методы, посвященные анализу взаимодействия компонент системы и их классификации. Развитие подобных методов, а также методов оптимизации дало толчок развитию кластерного анализа, который ныне занимает одно из первостепенных положений в этой области. Кластерный анализ представляет собой совокупность методов классификации многомерных наблюдений или объектов, основанных на определении расстояния между объектами с последующим выявлением из них кластеров или групп наблюдений. При этом одним из достоинств кластерного анализа является отсутствие необходимости в априорной информации о распределении генеральной совокупности. Выбор конкретного метода кластерного анализа зависит от цели классификации. Всю совокупность методов кластеризации можно разбить на три группы. К первой группе относятся иерархические (дивизивные и агломеративные) методы, главная цель которых получение представления о структуре всей классифицируемой совокупности. Вторая группа - методы расщепления смесей вероятностных распределений. В рамках этой группы методов каждый класс представлен в виде параметрически заданной одномодальной генеральной совокупности при неизвестном значении определяющего ее параметра, а классифицируемые наблюдения - как выборка из смеси таких генеральных совокупностей. Третья группа - методы собственно автоматической классификации или кластер-анализа. В этих методах исследователь не имеет оснований для параметризации моделей.
К сожалению, большинство методов кластерного анализа подкреплено лишь опытом разработчика. Они разрабатывались для определенных научных дисциплин, поэтому несут на себе отпечатки специфики этих дисциплин. Разные методы кластерного анализа могут порождать и порождают различные решения для одних и тех же исходных данных. Узловым моментом исследования, от которого зависит окончательный вариант разбиения объектов на классы при использовании любого алгоритма
7 разбиения и, в определенном смысле, "узким местом" подхода является выбор метрики или меры близости между объектами, каждый из которых представлен значениями характеризующего его многомерного признака. В зависимости от главных целей исследования, от физической и статистической природы анализируемого многомерного признака, от априорной информации о классах и т.п. выбор метрики для каждой задачи кластеризации различен.
Как видно, рассмотренные методы позволяют создавать модели систем с целью решения какого-либо определенного класса задач, т.е. представляют собой взгляд на систему как бы с одной стороны. Кроме того, зти подходы содержат определенные недостатки. Так, например, многомерность и многосвязность практически не учитываются при теоретико-графовом подходе к построению модели. В свою очередь, кластерные алгоритмы в попытке преодолеть сложность изучаемых объектов неизбежно приводят к потере информации о системе и разрушению ее реальной структуры. В связи с этим, представляется актуальной разработка методики исследования структуры сложных систем на глобальном уровне, т.е. с позиции структуры как единого целого, и локальном уровне, с позиции отдельных элементов, уровнях. Использование нестандартного, имеющего в настоящее время ограниченное применение, аппарата алгебраической топологии, теории групп, теории множеств и бинарных отношений дает возможность анализа структуры как сложного многомерного геометрического образования - симплициального комплекса. Формирование основных путей использования симплициальных комплексов для построения математических моделей структур систем и исследования их сложности относится к началу 70-х годов и связано с именами математиков К.Доукером (C.Dowker) и Р.Эткина (R.HAtkin) [9, 10, 48, 53].
Целью данной работы является развитие методологии и создание методов и средств моделирования и анализа структуры структурно сложных систем, при наличии минимальной априорной информации относительно исследуемых объектов и явлений.
Поставленная цель достигается решением следующих задач:
Разработка на основе системных принципов методологической концепции комплексного исследования структурно сложных систем.
Развитие методов анализа взаимодействия и роли отдельных подсистем в структурно сложных системах.
Разработка подхода к использованию возможностей полиэдрального анализа при исследовании сетевой проводимости.
Развитие анализа многомерных связей и многомерных потоков структурно сложных систем.
Исследование возможности применения аппарата нечёткой логики при исследовании систем описанных уравнениями в пространстве состояний с использованием полиэдрального анализа.
Разработка программно-математического обеспечения, реализующего процесс исследования структурно-сложных систем.
Диссертационная работа состоит из введения, пяти глав, заключения, списка использованной литературы и приложения.
во введении обоснована актуальность проблемы и дана общая характеристика работы.
Первая глава диссертационной работы посвящена обсувдению основных идеи и принципов, легших в основу полиэдрального анализа, основной установкой которого является рассмотрение системы в виде отношения менаду элементами конечных множеств. Структура системы используется для получения геометрического и алгебраического представления системы как симплициального комплекса, состоящего из множества вершин и заданного семейства непустых подмножеств этих вершин - симплексов. Другими словами, любое отношение представляется таким образом, что множество элементов, соотносимых конкретному элементу, трактуется как геометрический симплекс, а совокупность таких симплексов образует симплициальный комплекс. Математические основы такого подхода были заложены К.Доукером (C.Dowker), а дальнейшее развитие идеи получили в работах Р.Эткина (R.H.Atkin), послуживших началом процесса формирования метода исследования структур сложных систем - Q-анализа или полиэдральной динамики. Немногочисленные публикации Р.Эткина, Дж.Касти, С.Сейдмана, Дж.Джонсона, К.Эрла, П.Гоулда, Х.Кауклелиса, С.Макгилла, АКуллена, ХГриффитса позволяют говорить о том, что приложение Q-анализа к социальным, производственным, биологическим, экономическим системам помогает раскрыть многомерную геометрию таких систем, проследить влияние различных локальных
изменений на структуру системы в целом, сделать акцент на структурных особенностях, которые не выявляются при других подходах. Использование такого подхода для анализа структурно сложных систем позволяет по-другому взглянуть на само понятие сложности, а также обратить более пристальное внимание на отдельные элементы и их роли в структуре, влияние, оказываемое ими на остальные элементы.
Относительную важность отдельного симплекса для комплекса в целом отражает понятие эксцентриситета. Оно позволяет оценить «плотность» вложения каждого симплекса в комплекс и, тем самым, характеризует локальные особенности структуры. В работе рассмотрены идеи, на которые опирались авторы при построении выражения для вычисления эксцентриситетов, недостатки этого выражения и пути их устранения. Наряду с приведенными рассужениями, представлен модифицированный вариант выражения для вычисления эксцентриситетов, разработанный в [1], а также предложено новое выражение, устраняющее некоторые недостатки последнего.
Эффективным средством исследования интеграции, взаимного влияния и важности узлов систем является использование таких топологических объектов, как симплициальные звезды. Построение и анализ симплициальных звезд позволяет получить оценки взаимного влияния узлов системы, а также сделать выводы о возможном характере таких взаимодействий. Так, например, исходя из сравнения близости пересечения звезд, построенных для вершин симплекса, к объединению этих звёзд, можно судить о степени интеграции симплекса. Кроме того, для каждой вершины симплекса мощность соответствующей звезды представляет число симплексов, совместно использующих эту вершину как источник (приемник). Это позволяет исследовать симплексы с позиции, приходящейся на них доли информации, т.е. рассматривать важность элемента в прямой зависимости от количества источников (приёмников) и в обратной зависимости от количества конкурирующих узлов по каждому из них.
В качестве характеристики связности используется понятие цепи связи. Ее наличие отражает тот факт, что два симплекса могут не иметь общей грани, но могут быть связаны при помощи последовательности (цепи) промежуточных симплексов. Такие симплексы принято объединять в одну группу или q-компоненту. Число компонент на каздом уровне связанности q
10 от 0 до dim К отражает глобальную связность системы и содержит информацию о структуре комплекса в целом. Процедура Q-анализа,
предложенная Р.Эткиным, предполагает объединение этих значений в структурный вектор Q. На основе значений элементов структурного вектора вводится числовая оценка ложности структуры системы. Сравнение числовых значений сложности для различных комплексов позволяет классифицировать их по степени сложности структурной организации и использовать эту информацию для практических целей.
Во второй глаае рассматриваются возможности использования полиэдрального анализа для исследования роли узлов систем в распространении сетевых потоков. В главе используются понятия теории графов, такие как транзитивное замыкание, отображение и матрица достижимости, благодаря которым удается построить на основе исходной симплициальной модели ряд производных моделей. Анализ этих моделей позволяет получить более точное представление как о роли элементов системы в процессе распространения информационных потоков, так и о структуре этих потоков в целом. Наряду с этим, вводятся две новых характеристики потоков системы: динамичность и согласованность, предлагаются выражения для их вычисления.
В третьей главе затронута наиболее интересная область исследования структурной связности систем в рамках полиэдрального анализа - многомерное взаимодействие элементов. В то время как сетевое взаимодействие между элементами системы происходит, как было сказано, посредством прямого воздействия или передачи информации по связи, многомерное взаимодействие элементов несет принципиально другой характер. Согласно определению два симплекса q-связны, если они имеют q+1 общих вершин. Другими словами, если, согласно введенному на множестве вершин отношению, симплекс можно охарактеризовать как приемник, а его элементы - как источники, то два симплекса будут q-связны только в том случае, если они будут связаны минимум с q+1 одинаковыми источниками. Очевидно, что такой тип связи не даёт возможности симплексам влиять друг на друга, в традиционном смысле слова, т.е. посредством сетевых связей. Предположим теперь, что "объем4 информации, потребляемый одним из симплексов изменился, скажем, в сторону увеличения. Зная, что оба симплекса получают информацию частично из
одних и тех же источников, можно утверждать, что второй симплекс начнёт переживать недостачу объема информационного потока. При этом можно предположить, что реальный объект, описанный этим симплексом, скорее всего, попытается компенсировать эту недостачу из других источников. Это приведёт к разряжению информационных потоков других симплексов. Те в свою очередь также попытаются компенсировать недостаток информации из альтернативных источников и т.д. Таким образом, можно наблюдать цепную реакцию или "волну", которая способна прокатиться по всей цепочке симплексов, возможно, не один раз, пока не найдется новое равновесное состояние. Эту волну можно рассматривать как информационный поток, посредством которого симплексы способны влиять на состояния друг друга. Учитывая многомерность симплициальных связей, такие потоки логично называть многомерными. Принимая во внимание отличие такого взаимодействия от сетевого, способность системы поддерживать высокий уровень многомерных потоков удобно называть дополнительной или многомерной проводимостью. Симплициальные связи ограничивают область распространения многомерных потоков конкретной компонентой. Поэтому одно из направлений изучения дополнительной проводимости видится в анализе способов разделения уровней связности на q-компоненты и исследовании структур симплициальных связей внутри них. Другими словами, необходимо знать, на сколько совокупностей какого размера распадается заданный уровень связности, сколько и какой длины симплициальные цепочки образованы внутри этих совокупностей. В рамках анализа многомерной проводимости в работе предлагается ряд численных характеристик q-компонент: эффективность формирования потоков, коэффициент цикличности, оптимальность структуры, сложность, остаточная проводимость и степень покрытия уроеня связности; а также ряд характеристик уровня связности в целом: относительное перекрытие, дополнительная проводимость и усредненная сложность q-компонент. Для более глубокого анализа симплициального взаимодействия был предложен метод построения симплициальной модели на базе q-компонент, что открывает возможности для рекурсивного использования полиэдрального анализа. Использование топологического понятия нерва симплициального комплекса позволяет исследовать важность каждой отдельной симплициальной цепочки, и определить сложность структуры образуемой ими q-компоненты.
Другая сторона анализа многомерного взаимодействия заключается в исследовании геометрических препятствий, заложенных в структуру системы. Этот подход подразумевает построение и анализ групп гомологии симплициапьной модели исследуемой системы. Результатом построения групп гомологии является набор так называемых q-мерных дыр. С физической точки зрения, они представляют собой участки цепи, в которых q-мерная связь нарушается, заменяясь связью меньшей размерности. С точки зрения q-мерной связи, р-мерная связь (p В главе четыре рассматривается возможность применения предложенной в настоящей работе методологии к анализу транспортных сетей. Рассматриваются особенности построения симплициальной модели транспортной сети, приводятся аналоги симплексов, симплициальных связей и многомерных препятствий. В заключение проводится исследование участка реальной транспортной сети. В пятой главе рассматривается возможность применения полиэдрального анализа к исследованию систем, описанных уравнениями в пространстве состояний. Для каждой пары переменных состояния q.tqj предлагается поставить в соответствие силе их взаимодействия вероятность того, что утверэдение "переменная состояния gi оказывает ощутимое влияние на переменную д^' справедливо. Полученная матрица вероятностей играет роль нечёткой матрицы инциденции, где каждый симплекс представлен нечётким множеством из переменных состояний. В рамках нечёткого описания предлагаются выражения для вычисления размерностей симплексов и комплекса в целом, рассматривается взаимодействие симплексов. Предложенные выражения позволяют перейти к оценке эксцентриситета нечёткого симплекса, представлению структурного веісгора и оценке сложности структуры нечёткого комплекса. В завершение главы приводиться алгоритм поиска элементов нечёткого структурного вектора. 13 В заключении представлены выводы по теоретическим и прикладным результатам работы. В приложении приведена структурная схема предложенной концепции анализа структурно-сложных систем, блок-схемы ряда использованных в работе алгоритмов, руководство по использованию разработанного программного обеспечения для анализа структурно-сложных систем и набор возможных шкал градации ряда предложенных оценок. Научная новизна: получены модифицированная оценка эксцентриситета симплекса и ряд дополнительных оценок важности отдельных элементов структурно сложной системы; разработан метод оценки динамичности и согласованности сетевых потоков на основе данных полиэдрального анализа; введено понятие дополнительной проводимости; предложены: метод исследования структур q-компонент и алгоритмы получения оценок остаточной проводимости, сложности и эффективности организации структуры q-компонент; предложен метод исследования структур линейных динамических систем на основе нечётких симплициальных комплексов с использованием оценок полиэдрального анализа, адаптированных для нечёткого представления данных. Практическая ценность результатов работы состоит в создании эффективного рабочего инструмента математического моделирования и анализа структуры сложных систем, позволяющего: раскрывать присущую всем системам многомерность и структурную сложность; использовать идеи алгебраической топологии в контексте теоретико-множественного подхода к построению моделей с их последующим анализом и реализацией в виде соответствующих программных средств; создать единую методику исследования систем на ранних этапах проектирования. 14 Разработанное на основе предложенной методики программное обеспечение CssResearch ориентировано на широкий круг специалистов различных областей знаний и позволяет значительно сократить время проведения анализа структуры систем, прежде всего, за счёт ускорения вычислений и удобной формы представления результатов. Материалы диссертационной работы отражают результаты развиваемого на кафедре направления, связанного с развитием теории и созданием инструментария исследования структурно сложных систем, и используются в учебных курсах «Системный анализ» и «Математическое моделирование», читаемых на кафедре. Апробация работы: Основные положения диссертации докладывались и обсуждались на: о научно технической конференции "Моделирование и исследование сложных систем", Кашира. Март 1996; * четвёртой всероссийской научно-технической конференции "Новые научных семинарах кафедры "Управление и моделирование систем" По теме диссертационной работы опубликовано семь печатных работ. Процедура вычисления струїстурного вектора была предложена как первый шаг к структурному анализу и оказалась достаточно эффективной при изучении глобальной связности структуры системы. Поскольку вычисляемый структурный вектор принято обозначать буквой Q, то метод получил название Q-анализа. Процедура вычисления структурного вектора целиком опирается на анализ симплициальной модели исследуемой системы. В связи с тем, что симллициальный комплекс представляет собой семейство симплексов, соединенных посредством общих граней, в качестве характеристики связности используется понятие цепи связи, отражающее тот факт, что два симплекса могут не иметь общей грани, но могут быть связаны при помощи последовательности связанных друг с другом промежуточных симплексов. Другими словами, два симплекса sa и sb комплекса К соединены цепью связи, если существует такая конечная последовательность симплексов , что sCi и sa имеют общую грань размерности qal sC и sb имеют общую грань размерности qhl и каждая пара симплексов se,sCi имеет общую грань размерности qc . Эта цепь называется q-связной, если q - наименьшее из значений qayqb и {qc}. Если симплексы sa и соединяются цепью q свяэи, то они также и р-связны, q р 0. Такие симплексы целесообразно объединять в одну группу или q-компоненту. На каждом уровне связанности q от 0 до dim К таких q-компонент может быть несколько; их число обозначается Qq. Каждый элемент структурного вектора представляет собой количество q-компонент для соответствующего уровня связности. Анализ структурного вектора позволяет сделать предположение о качестве связей между элементами, их нарушениях и изолированных участках. Распад уровня связности на q-компоненты, прежде всего, означает невозможность беспрепятственного прохождения потоков соответствующей мощности между симплексами разных компонент, что указывает на наличие структурных препятствий. Очевидно, что наиболее благоприятный с точки зрения структурной сложности результат будет представлен структурным вектором, все элементы которого равны единицам, что будет означать отсутствие разрывов и изолированных друг от друга компонент на всех уровнях связности. Однако структурный вектор дает мало возможностей для сопоставления результатов анализа различных систем, так как достаточно тяжело правильно сравнить два различных структурных вектора. Потребность в единой для системы оценке приводит к появлению меры сложности. Матрицы достижимости и контрдостижимости позволяют построить с/мплициальные модели системы, описывающие области распространения потоков внутри неё, степени вовлечённости и роли узлов в распространении зтих потоков. Однако это позволяет исследователю взглянуть уже на результат распространения потоков, что не даёт возможности судить о том, как быстро вершины могут быть достигнуты, сколько промежуточных вершин необходимо миновать, чтобы достигнуть той или иной вершины, сколько альтернативных путей может быть предоставлено конкретному потоку. Такая информация важна, так как позволяет оценить задержки сигнала, преходящего от одной вершины к другой, нагрузки на промежуточные узлы, а также заложенные в систему возможности распараллеливания потоков. Кроме того, появляется возможность оценить скорость распространения информации в системе, причем имеется в виду не скорость передачи информации менаду соседними вершинами, а возможности структуры обеспечить минимум промежуточных узлов при передаче информации от одной вершины к любой другой, даже самой удаленной. Возможности структуры обеспечивать передачу сигнала между её узлами за минимальное время, т,е. способность поддерживать высокую степень мобильности или динамичности перемещения сигнала, можно рассматривать как динамичность потоков системы. С другой стороны, не менее важно понять каким образом могут взаимодействовать сигналы в процессе их перемещения от вершины к вершине. Сигнал, вышедший из некоторой вершины, с каждым следующим моментом времени достигает новых узлов, одновременно пополняя список пройденных вершин. В некоторый момент времени, зтот список может значительно отличаться от списка вершин, пройденного сигналом, исходящим из какой-либо другой вершины. Такое несоответствие указывает на то", что на некотором участке сигналы распространяются изолированно друг от друга, так как система, в силу особенностей своей структуры, не в состоянии обеспечить возможность использования одних и те же узлов для перемещения сигналов. Эту характеристику системы предлагается назвать несогласованностью потоков, Для более полного раскрытия значения этих характеристик необходимо рассмотреть ряд дополнительных понятий. Прежде всего, введем понятие неполного (для начала прямого) транзитивного замыкания степени п - T n(xt). В отличие от полного транзитивного замыкания Т ( ), оно будет объединением только первых п отображений: Вычислив неполные транзитивные замыкания для всех вершин, можно построить матрицу Л", которую назовем матрицей неполной достижимости степени п. Отметим, что матрица смежности может совпадать с матрицей неполной достижимости первой степени R1. Таким образом можно прийти к последовательности матриц неполной достижимости степени к, где к будет лежать в диапазоне l k Nmax. Величина же iVmax представляет собой максимальную из длин путей между двумя вершинами в системе. Её можно определить выражением: где М - это количество вершин исходного графа, a ri - минимальная степень негслного прямого транзитивного замыкания T (xs) вершины х{, такая, что T rfixt) = T l)(xl) = r+{xt). Очевидно, что N не превысит числа вершин графа М. Сам по себе набор п1, вычисленных для каждого симплекса и соответствующей ему вершины, можно представить, как вектор степеней достижимости Лґ{и,_.,ям}. Этот вектор будет содержать информацию о скорости достижения наиболее удаленного узла потоком, исходящим из соответствующей вершины графа. Такая информация также представляется весьма интересной и полезной, в особенности, если её рассматривать отічссительно числа вершин модели. В качестве характеристики относительной удаленности узлов в системе предлагается использовать отношение среднего значения n\\ i M к числу узлов в системе: В предыдущем разделе была предложена классификация, согласно котооой симплексы q-компонент разделяются на три вида: терминальные, связующие и симплексы пересечений. Информация о числе и характеристиках этих симплексов даёт возможность судить о структуре и сложности q-компонент, а также оценить возможное число симплициальных цепей. Вспомним, что отнесение симплексов к тому или иному типу осуществлялось только на основе числа симплексов, с которыми классифицируемый симплекс был связан. Так терминальный симплекс (или край) всегда связан лишь с одним симплексом, связующий - ровно с двумя и, наконец, симплекс пересечений - не менее чем с тремя. Это позволило рассматривать q-компоненту как набор узлов и ненаправленных связей между ними, и без труда представить компоненту в виде графа. Граф, в свою очередь, позволяет перейти снова к симплициальной модели. Для этого в качестве множества вершин новой симплициальной модели X принимается множество всех симплексов пересечений и терминальных симплексов рассматриваемой q-компоненты исходной симплициальной модели. Отношение же между вершинами задаётся следующим выражением: кузел і входит в состав симплекса I если в компоненте базоеой модели симплекс і q-сзязан с симплексом] непосредственно или связующей цепью». Очевидно, что из-за ненаправленности симплициальных связей матрица инциденций бу ет симметрична относительно главной диагонали и, следовательно, прямая и сопряженная модели будут совпадать. Результаты проведения полиэдрального анализа полученной симплициальной модели позволяют более детально описать структуру компоненты и оценить её сложность. Исследование же сетевых потоков и неполных транзитивных замыканий даст более точную информацию об особенностях формирования симплициальных цепей в исследуемой компоненте. Заметим, что полное транзитивное замыкание матрицы инциденций новой модели будет всегда представлено матрицей, полностью состоящей из единиц. Этот факт свидетельствует о взаимной достижимости всех симплексов модели. Попытка исследовать многомерное взаимодействие неизбежно заставляет рассматривать всю совокупность симплексов, полученных для определенного уровня связности, как еще одну структурно сложную систему. Поэтому было бы интересно попытаться использовать разработанную в рамках полиэдрального подхода методологию и полученный набор оценок для исследования совокупностей симплексов- Кроме того, это открывает возможность использовать неограниченное число итераций при рекуррентном применении полиэдрального анализа для исследования структурно сложных систем. Имеется в виду то, что в результате построения производной симплициальной модели снова появляется набор симплексов. Это позволяет получить последовательность симплициальных моделей, результаты анализа которых будут характеризовать исходную систему в зависимости от номера итерации, который можно воспринимать как "глубину11 анализа, С каэедой следующей итерацией полученная структура будет проще. Это свойство можно использовать для определения шага, на котором следующая итерация производиться не будет, задав некоторое пороговое значение показателя структурной сложности системы. Количество же шагов, необходимых для достижения заданного предела сложности, также можно рассматривать как дополнительную характеристику исследуемой модели. В основу перехода от набора симплексов к симплициальной модели ложится одно из понятий симплициальной теории - нерв совокупности. Чтобы прояснить, что представляет собой нерв совокупности, рассмотрим некоторое множество X и предположим, что задана некоторая совокупность w = {w} его подмножеств. Будем полагать, что непустые подмножества из W, пересечение которых не пусто, представляют собой симплексы, образующие некоторый сим.плициальный комплекс KQV), Образованный таким образом симплициальный комплекс K(W) и является нервом совокупности w. Понятно, что вершины комплекса K(W) - это элементы совокупности W, не являющиеся пустым множеством. Предположим теперь, что для некоторой структурно сложной системы получена симплициальная модель. Если за множество X принять множество всех вершин исходной модели, то найденные симплексы будут задавать на множестве X совокупность пересекающихся подмножеств. В зависимости от уровня связности, симплициальные цепи образуют нерв совокупности, играя роль непустых подмножеств, пересечение которых не пусто. Поскольку все цепи, имеющие пересечения, непременно будут принадлежать одной и той же компоненте, то матрица инциденций полученной модели будет состоять из набора подсистем, число которых равно элементу структурного вектора Q исследуемого уровня связности. До сих пор многомерные препятствия рассматривались с точки зрения разрывов или отсутствия связей соответствующей размерности ме вду симплексами. Эти разрывы являются причиной разбиения уровня связности на q-компоненты. Однако симплициальная теория и теория гомологии позволяют выделить особенный вид препятствий в симплициальном комплексе, получивший название многомерной дыры, или q-дыры. Одним из первых на такой вид препятствий указал Р.Эткин. Он предложил рассмотреть для некоторого симплициального комплекса КТ(Х;А) с размерностью dim(J5T) = « формальные линейные суммы р-симплексов, допуская кратность для любого sp, где 0 р п. При этом для любого р задана нумерация (slP«slt...9shpp)t где Н? - общее число таких р-симплексов. Напомним, что симплекс считается р-мерным, если в его состав входят не менее чем р+1 вершин. Любая формальная комбинация будет являться алгебраическим представлением некоторой р-цепи. Можно обозначить семейство всех р-целей через Ср1 а любой элемент семейства Ср - через с . Тогда типичная р-цепь имеет вид Попытаемся теперь использовать предложенную в работе методологию анализа структурно сложных систем и изложенные выше соображения по переходу к симплициальнои модели для анализа участка реальной транспортной сети. На рисунке 4.6 изображена схема такого участка. При построении симплициальнои модели в качестве множества вершин выберем все узлы, обозначенные на рисунке 4.6 точками. Введем следующее отношение эквивалентности между вершинами: і-узел принадлежит j-симплексу, если между і-узлом uj-узлом существует путь и, согласно установленным правилам, разрешено движение транспорта от /-узла к j-узлу, Симплициальная модель, соответствующая заданному отношению и множеству вершин, будет представлена в виде матрицы инциденций, изображенной на рисунке 4.7 (номер симплекса соответствует номеру узла на схеме). В результате анализа этой матрицы инциденций получен набор характеристик симплексов, приведенный в таблице 4.1.Из таблицы видно, что в структуре преобладают симплексы больших размерностей - 3 и 4. Значения эксцентриситетов приблизительно пополам разделились на средние и незначительные, что свидетельствует о том, что симплексы связаны друг с другом, в среднем, не более половиной своих узлов и, скорее всего, не способны формировать компоненты больших размерностей; и, следовательно, многомерные потоки больших размерностей. Этот факт отрицательно сказывается на скорости разрешения чрезвычайных ситуаций. Значение степени конкуренции для всех симплексов, кроме одного, являются средними, что свидетельствует о достаточном количестве альтернативных путей, следовательно, выход из строя одного из узлов не повлечёт фатальных последствий для транспортной сети. Этот вывод подтверждают значения в колонке возможного ущерба, вызванного удалением узла, которые колеблются в диапазоне от незначительного до малого. Таким образом, основываясь на данных таблицы, можно сделать вывод о том, что система хорошо защищена от различного рода сбоев, однако не обладает высокой реакцией и скоростью разрешения критических ситуаций, если таковые все же имеют место. Проведение полиэдрального анализа позволило получить следующий структурный вектор Q; (10, 37, 19, 1). Большое число q-компонент на всех уровнях связности, за исключением нулевого, подтверждает предположение о неспособности системы формировать потоки больших размерностей. Кроме того, если сравнить эти значения с колонкой Card(s) таблицы 4.1, то легко заметить, что число симплексов размерности А и 3 совпадают со значениями структурного вектора на уровнях 3 и 2, а именно -10 и 37. Это означает, что в рассматриваемой системе симплексы вообще не способны устанавливать друг с другом связь на этих двух уровнях связности и, как следствие, формировать какие-либо компоненты даже из двух симплексов. Более детальную информацию об уровнях связности можно получить из анализа самих q-компонент. Значение оценки сложности, вычисленное на основе структурного вектора, позволяет отнести исследуемую систему к системам со средней сложностью структуры. Результаты анализа уровня связности 3 и 2, как и ожидалось, оказались достаточно тривиальными и не внесли никаких серьезных дополнений к имеющейся информации, кроме подтверждения предположений о крайней изолированности симплексов этих уровней. На уровне связности 3 найдено 10 q-компонент, состоящих из одного элемента (будем называть их вырожденными или единичными) и включающих в себя следующие симплексы: s8, s9, slO, slS, sl9, s22, s26, s31, s32, s34. В силу относительно большого их числа, значения коэффициента покрытия уровня и относительной проводимости этих q-компонент крайне мало. Однако может удивить крайне высокое значение оценки сложности этих q-компонент. В связи с этим, хотелось бы напомнить, что оценка сложности подразумевает некий остаток от максимально возможной сложности q-компоненты, к которому привела неэффективная организация связей между симплексами. При этом предполагается, что q-компонента максимально сложна, если каждый из ее симплексов связан со всеми остальными, то есть q-компонента имеет максимальное число возможных связей. В симплициальной q-компоненте непременно выполняются два условия: симплициальная связь является ненаправленной, и все симплексы в q-компоненте достижимы. Очевидно, что с учетом этих условий q-компоненты из одного и двух симплексов могут иметь лишь один единственный набор возможных связей, а потому этот набор может восприниматься и как самый простой, и как самый сложный. Результаты анализа уровня связности 2 абсолютно идентичны результатам анализа уровня 3. На этом уровне располагаются 37 единичных q-компонент на базе симплексов s2, s3, s4, s5, s7, s8, s9, siO, 311,512,313, sl4, sI5, sl6f sl7, slS, sl9, s20, s21T s22, s23, s24, s25, s26, s27, s28, s30, s31, s323 s33, s34, s35, s37, s38r s39, s40, s42. Каждая q-компонента характеризуется крайне малыми значениями коэффициента покрытия уровня и относительной проводимости. На уровне связности 1 анализ q-компонент позволил получить достаточно интересные результаты. Несмотря на значительное число q-компонент на этом уровне - 1ЭТ только 12 из 41 симплексов (s1, s6, s11, s12, s14, s26, s27, s28, s30, s33, s36, s37) не связаны ни с одним другим симплексом, и формируют 12 единичных q-компонент с незначительными величинами коэффициента покрытия уровня и относительной проводимости. Все остальные симплексы участвуют в формировании семи q-компонент. Первая q-компонента сформирована шестью симплексами s2T s8f s4, s10, s13, s20, причем два из них - s2 и s20 - являются терминальными, и нет ни одного симплекса пересечений- Такое разделение симплексов говорит о довольно простом устройстве q-компоненты и указывает на то, что q-компонента не содержит циклов и пересечений, и представлена одной симплициальной цепью, ограниченной симплексами s2 и s20, На это также указывает и крайне малое значение сложности q-компоненты. Средняя величина коэффициента покрытия уровня свидетельствует об относительно большом размере q-компоненты и её роли среди других компонент. Однако значение дополнительной проводимости остаётся крайне малым. Напомним, что оценка дополнительной проводимости строится из оценки коэффициента покрытия уровня и оценки сложности q-компоненты. Первая из них указывает, какую часть дополнительной проводимости q-компонента в состоянии поддерживать от максимально возможной проводимости, т,е. в случае, когда все симплексы уровня объединены в одну q-компоненту. Вторая оценка учитывает эффективность устройства самой компоненты с точки зрения дополнительной проводимости. В связи с этим, несмотря на то, что размер исследуемой q-компоненты позволяет поддерживать дополнительную проводимость на среднем уровне, её внутренняя организация уменьшает эти возможности до чрезвычайно малых.
информационные технологии", Москва, МГАПИ. Апрель 2001;
МГАПИ (1996-2001 гг).Анализ сложности структуры систем
Характеристики потоков
Симплициальная модель q-компоненты
Исследование участка реальной транспортной сети
Похожие диссертации на Методы и средства исследования структурно сложных систем на основе симплициальных комплексов
