Содержание к диссертации
Введение
1 Равновесное распределение ресурсов в динамической распределенной системе 18
1.1 Постановка задачи 18
1.2 Обозначения и предварительные замечания 21
1.3 Распределение ресурсов в системе с оценивающими функционалами вида
1.4 Анализ рекуррентных соотношений 29
1.5 Сходимость итерационного процесса 30
2 Поиск сбалансированного потока в распределенной сети 69
2.1 Постановка задачи 69
2.2 Обозначения и предварительные замечания 73
2.3 Анализ итерационного процесса 74
2.4 Графы без стоков 80
2.5 Непрерывная зависимость предельного потока от параметров системы 94
Заключение 104
Благодарности 105
Список литературы 106
- Обозначения и предварительные замечания
- Анализ рекуррентных соотношений
- Анализ итерационного процесса
- Непрерывная зависимость предельного потока от параметров системы
Введение к работе
Актуальность темы. Объектом исследования данной работы являются динамические распределенные системы, моделируемые взвешенными графами. Предмет исследования - итерационные процессы изменения состояний динамических распределенных систем.
В диссертации под динамической распределенной системой понимается совокупность взаимосвязанных элементов, каждый из которых в каждый момент времени (которое полагается дискретным) характеризуется набором значений некоторых параметров - своим состоянием. Состояние системы - это совокупность состояний ее элементов. Элемент может находиться в различных состояниях, и на каждом временном шаге все элементы системы независимо друг от друга изменяют свои состояния на основании имеющейся у них информации о состояниях соседей. Так как элементы действуют независимо, то система попадает в состояние, отличающееся от того, которое ожидали элементы, что на очередном временном шаге побуждает их снова изменять свои состояния.
Динамические распределенные системы являются адекватными моделями описания различных физических, экономических и социальных систем, поэтому представляет интерес получение достаточных условий сходимости процесса изменения состояний, а также вычисление предельных и равновесных состояний системы. Несмотря на то, что динамические распределенные системы изучаются в различных областях знаний, вопрос сходимости процессов изменения состояний исследован недостаточно. В диссертации анализируется сходимость процессов изменения состояний в двух классах динамических распределенных систем, представляющих интерес как с теоретической, так и с практической точек зрения.
Цель работы. Исследование итерационных процессов изменения состояний в распределенных динамических системах. Поиск достаточных условий сходимости и оценка скорости сходимости этих процессов. Нахождение аналитических выражений для предельных и равновесных состояний. Анализ устойчивости процессов вычисления предельных и равновесных состояний к вычислительным погрешностям.
Методы исследований. В работе использовались методы матричного анализа, теории графов, исследования операций и дискретного анализа.
Научная новизна. В диссертации рассматриваются две модели динамических распределенных систем, представленных взвешенными графами. Первая из них является обобщением рассматривавшихся ранее
моделей. Вторая модель ранее не рассматривалась. Сформулированы новые легко проверяемые условия сходимости процессов изменения состояний, впервые получены аналитические выражения для предельных и равновесных состояний и проведен анализ устойчивости процессов вычисления предельных состояний к вычислительным погрешностям. Основные результаты.
Сформулированы полиномиально проверяемые достаточные условия сходимости процессов изменения состояний в двух классах динамических распределенных систем.
Определены оценки скорости сходимости.
Получены аналитические выражения для предельных и равновесных состояний.
Найдены условия устойчивости процесса вычисления состояний системы к ошибкам округления и погрешностям начальных данных и показана непрерывная зависимость предельного и равновесного состояний от параметров системы.
Практическая и теоретическая ценность. Работа носит теоретический характер, однако ее результаты могут быть полезны при проведении качественного анализа различных физических, социальных и экономических процессов, а также могут быть использованы при анализе других итерационных процедур.
Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на семинарах кафедры Теоретической кибернетики НГУ и отдела Теоретической кибернетики ИМ СО РАН, на семинарах "Дискретные экстремальные задачи" и "Избранные вопросы математического анализа" ИМ СО РАН, на XLII и XLV международных студенческих конференциях "Студент и Научно-Технический Прогресс" (г.Новосибирск, 2004 и 2007 годы), на международной школе-семинаре "Вычислительные методы и решение оптимизационных задач" (г.Бишкек, Киргизия, 2004 год), на XIV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (г.Северобай-кальск, 2008 год).
Публикации. Основные результаты диссертации опубликованы в 7 работах, из них 3 в рецензируемых изданиях и журналах, рекомендованных ВАК.
Личный вклад. Все результаты получены соискателем лично. В совместных публикациях вклад соискателя является существенным и
заключается в формулировке и доказательстве утверждений. Конфликт интересов с соавторами отсутствует.
Структура и объем работы. Диссертация изложена на 110 страницах и состоит из введения, вспомогательного раздела, двух глав, заключения и списка литературы, содержащего 49 наименований. Работа содержит 19 рисунков.
Обозначения и предварительные замечания
Задачи, связанные с построением и анализом равновесных систем возникают в различных областях человеческой деятельности, где в той или иной форме проявляется конфликтное взаимодействие: при принятии политических решений, при анализе соотношения сил конфликтующих сторон, при исследовании экономических явлений, при проектировании технических систем. Исследование вопросов, связанных с поиском и анализом равновесий в различных системах производится в рамках теории игр, математической экономики, математической физики. Однако, как правило равновесное состояние указывается в виде решения системы неравенств, неподвижной точки некоторого отображения или решения системы дифференциальных уравнений. Зачастую при этом неявно предполагается централизованностъ системы, то есть существование лица, которое обладает полной информацией обо всех элементах системы и извне предлагает равновесное состояние. Такой подход не всегда оправдан. Например, в случае анализа поведения распределенных (децентрализованных) систем, ни один из элементов которых не обладает полной информацией о состоянии всей системы.
Под динамической распред&аенной системой в данной работе понимается следующий объект. Рассмотрим совокупность элементов V = {1,..., п}. Каждый элемент і в момент времени к (время полагается дискретным) характеризуется конечным набором некоторых параметров ж = (ж ,..., xfm.). Назовем этот набор состоянием элемента в данный момент времени и обозначим множество допустимых состояний через Х\ [ХІ Є Rmi). Совокупность состояний всех элементов системы в момент времени к назовем п состоянием системы и обозначим через Хк Хк е YI д;). Полагаем, что г =1 в начальный момент времени система находится в известном состоянии Х. Каждому элементу г системы сопоставляется подмножество элементов Vi С V (назовем их "соседями" элемента г) и множество СІ С Ц у и , Ї). Пусть X - некоторое состояние системы. Через СІ{Х) обозначим множество параметров {XJI\(J,1) Є СІ}. Каждый элемент динамической распределенной системы способен изменять свое состояние независимо от остальных элементов. Решение о выборе нового состояния хк+1 Є ХІ принимается элементом і на основании наблюдаемых в предыдущий момент времени компонент состояний соседей Ct{Xk). То есть, для элемента і известна функция Pi : R}c \ — ХІ выбора нового состояния. Назовем эту функцию стратегией элемента г, а кортеж М = (V, {Vt}, {Хг}, {CJ, {ipi},X) назовем динамической распределенной системой.
В этом определении параметры системы (множества соседей Vi и допустимых состояний Хг-, множества СІ и оператор перехода Ф) не изменяются от шага к шагу, однако можно рассматривать и такие системы, где эти множества зависят от времени: Vk, Х- , Ck. Речь в данной работе будет идти преимущественно о системах с постоянными параметрами.
В динамической распределенной системе происходит процесс изменения состояний, который описывается соотношением: Хк ь1 = Ф(Хк), где Ф - оператор перехода. При этом возникает ряд естественных вопросов: сходится ли этот процесс к некоторому предельному состоянию? Если сходится, то с какой скоростью, и какими свойствами обладает предельное состояние? Помимо предельных состояний интерес представляют также стационарные (не изменяющиеся со временем) и равновесные (устраивающие все элементы, не смотря на возможную противоположность их интересов) состояния. Рассмотрим последовательность состояний {X1} (І Є N): Х - начальное состояние, Xі = Ф(Х), X2 = Ф(ХХ) и так далее. Пусть для некоторого номера к выполняются равенства: Хк = Хк+1 = Хк 2 = ... В этом случае состояние Хк является стационарным. Состояние X является равновесным если X = Ф(Х). Очевидно, предельное и стационарное состояния являются равновесными.
Анализ рекуррентных соотношений
Свойства распределенных систем изучаются в различных областях ма тематики. Например, при анализе таких моделей теории вычислений, как нейронные сети [34, 43], клеточные автоматы [32, 33] или устойчивые сети Петри [31]. Также динамические распределенные системы изучаются в рамках теории игр. В этом случае процесс изменения состояний системы можно рассматривать как процедуру поиска равновесия по Курно [21], а стационарному состоянию системы соответствует равновесие по Нэшу [22]. Динамические распределенные системы используются и для описания различных социальных и экономических явлений, например, при моделировании конфликтов [18, 27, 29, 48], построении экономических моделей [26, 40, 41, 45], анализе социальных взаимодействий [42, 49] и изучении саморазвивающихся систем [44, 46, 47].
Несмотря на то, что динамические распределенные системы рассматриваются во многих разделах математики, вопросы сходимости процесса изменения состояний затрагиваются редко. Одним из основных направлений исследований является поиск равновесных состояний и условий, при которых такие состояния существуют. Так, например, в работах [16. 17, 18] рассматривается вопрос существования баланса сил сторон и приводятся условия его существования в виде системы неравенств. Однако вопрос о том, может ли распределенная система достичь равновесия без вмешательства извне остается открытым.
В данной работе анализируется процесс изменения состояния двух распределенных систем, моделируемых взвешенными графами. В главе 1 описывается модель динамической распределенной системы, элементы которой представляются вершинами некоторого неориентированного графа. Вершина г взаимодействует с вершиной j в том и только том случае, когда они соединены ребром. Каждый элемент системы обладает некоторым количеством однородного ресурса и взаимодействует с соседями, распределяя свой ресурс по инцидентным ребрам. "Качество" взаимодействия с соседями оценивается каждой вершиной на основании наблюдаемого распределения ресурсов соседей согласно значениям заданных функционалов. В каждый момент времени все элементы системы независимо друг от друга перераспределяют свои ресурсы с целью "оптимизировать" отношения с соседями. Однако, так как элементы действуют независимо друг от друга, система попадает в состояние, отличное о ожидаемого каждым элементом, что снова (на очередном временном шаге) побуждает элементы перераспределять свои ресурсы. В первой главе рассматриваются процессы перераспределения ресурсов в системах с различными линейными оценивающими функционалами. Ранее подобные модели для частных случаев графов были рассмотрены в работах [1, 2, 3, 4, 5, 6, 7]. Также похожая модель с оценивающими функционалами специального вида рассматривалась в рамках теории конфликтов [16, 17, 18]. В данной главе автором рассматривается более общая модель и приводятся результаты, обобщающие полученные ранее. Найдены легко проверяемые достаточные условия сходимости процесса изменения состояний системы, произведена оценка скорости сходимости, а также приводятся аналитические выражения для предельных и равновесных состояний. Показана устойчивость процесса вычисления состояний системы к вычислительным погрешностям.
В главе 2 описывается потоковая модель динамической распределенной системы, элементы которой отождествляются с вершинами ориентированного графа. Каждой вершине графа приписан некоторый потенциал, характеризующий мощность потока, возникающего в этой вершине в каждый момент времени. Любая вершина, не являющаяся стоком графа, в каждый момент времени по определенным правилам перераспределяет поступающий в нее поток по исходящим дугам. Ранее такая модель в литературе не рассматривалась. Формально она близка к централизованной динамической модели межотраслевого баланса В. В. Леонтьева [24, 25], однако при анализе этой модели вопросы сходимости как правило не рассматриваются, а условия существования равновесия формулируются в виде неравенств для собственных значений некоторого оператора. В главе исследован вопрос сходимости процесса перераспределения потока, приведены полиномиально проверяемые достаточные условия сходимости в терминах топологии графа, оценена скорость сходимости, указаны аналитические выражения для предельных и равновесных состояний. Показана непрерывная зависимость предельного потока от параметров системы. Процессы изменения состояний представляют интерес также в случае анализа централизованных систем. Зачастую поиск точного значения равновесных параметров системы является затруднительным [39], и приходится использовать приближенные методы. Среди них выделяются итерационные алгоритмы, которые позволяют получить решение в виде предела некоторой последовательности, члены которой вычисляются единым образом в ходе итерационного процесса. К числу неоспоримых достоинств итерационных методов можно отнести их сравнительную простоту в реализации на современных вычислительных устройствах. Однако для реализации метода необходимо обосновать его сходимость, что зачастую сделать не так просто. Помимо этого, при анализе итерационного алгоритма полезно знать с какой скоростью осуществляется сходимость процесса, является ли сходимость монотонной и какими свойствами обладает полученное в пределе решение.
Анализ итерационного процесса
Формально рассматриваемые модели близки к линейным разностным уравнениям. Процесс изменения состояния системы может быть представлен в виде Хк = Ф(Хк 1), где Хк - вектор, описывающий состояние системы в момент времени к, а Ф - аффинный оператор перехода, не зависящий от к. Поэтому решение вопроса о существовании предельного состояния (при к —» со) сводится к локализации спектра некоторой матрицы. Однако, задача вычисления спектра не самосопряженного оператора до сих пор не решена в общем виде. В работе [28] приведен критерий принадлежности спектра матрицы единичному кругу в терминах решения дискретного уравнения Ляпунова. Для рассмотренных в данной работе систем приведены более простые для проверки достаточные условия сходимости. Результаты исследования могут быть интересны специалистам из раз ных областей. Рассмотренные модели распределенных систем позволяют дать качественное описание широкого класса экономических и физических процессов. Например, с помощью соответствующей итерационной процедуры можно эффективно оценить распределение воздушных потоков в вентиляционной сети без проведения дорогостоящего имитационного моделирования. Кроме того, описанные модели можно использовать для исследования переходных процессов в различных динамических системах. Изложение материала организовано следующим образом. Во вводном разделе Элементы матричного анализа кратко приведены необходимые утверждения из теории матриц, которые используются в последующих главах. В главе 1 описывается модель динамической распределенной системы, представляемая взвешенным неориентированным графом. Каждый элемент системы обладает некоторым количеством однородного ресурса, который он на каждом шаге распределяет между инцидентными ребрами. В данной главе исследуется процесс перераспределения ресурсов в этой системе, приведены достаточные условия сходимости этого процесса, получены оценки скорости сходимости, а также аналитические выражения для предельных и равновесных состояний. Показана устойчивость процесса вычисления состояний системы к вычислительным погрешностям. Результаты автора, изложенные в данной главе, опубликованы в работах [3, 9, 11, 12, 13]. В главе 2 описывается потоковая модель динамической распределенной системы, элементы которой отождествляются с вершинами взвешенного ориентированного графа, и рассматривается процесс перераспределения потока в этой системе. Приведены достаточные условия его сходимости, оценена скорость сходимости, указаны аналитические выражения для предельных и равновесных состояний. Показана непрерывная зависимость предельного потока от параметров системы. Результаты автора, изложенные в данной главе, опубликованы в работах [10, 11]. Работа завершается Заключением, содержащим основные результаты диссертационной работы. Основные научные результаты работы докладывались и обсуждались на семинарах кафедры Теоретической кибернетики Новосибирского государственного университета и отдела Теоретической кибернетики Института Математики имени С. Л. Соболева СО РАН, на семинарах "Дискретные экстремальные задачи" и "Избранные вопросы математического анализа" Института Математики имени С. Л. Соболева СО РАН. на XLII и XLV международных студенческих конференциях "Студент и Научно-Технический Прогресс" (г. Новосибирск, 2004 и 2007 годы), на международной школе-семинаре "Вычислительные методы и решение оптимизационных задач" (г. Бишкек, Киргизия, 2004 год), на XIV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (г. Северобайкальск, 2008 год).
Непрерывная зависимость предельного потока от параметров системы
Подграф И графа Н назовем сильной компонентой графа Н, если множество его вершин V{H ) представляет собой максимальное по включению сильно связное подмножество вершин графа. Иными словами, сильная компонента есть максимальное по включению множество вершин, попарно связанных путями. Очевидно, все дуги между вершинами двух различных сильных компонент ориентированы из одной компоненты в другую. По графу G однозначно строится граф его сильных компонент. Это граф, верши нами которого являются сильные компоненты {Gk}, а дуга (Gk, Gf) принадлежит графу в том и только том случае, когда существует дуга из некоторой вершины компоненты Gk в некую вершину компоненты Gi. Нетрудно видеть, что граф компонент представляет собой ориентированный ациклический граф. В дальнейшем граф компонент, построенный по графу G будем обозначать через K(G). Замечание I. Граф сильных компонент можно построить с трудоемкостью 0(\V\ + \Е\) [19]. Замечание II. Если матрица А соответствует графу G, Р - некоторая матрица перестановок, А = РАРТ, то матрица А соответствует графу, получаемому из G соответствующей перенумерацией вершин. Замечание III [15]. Матрица А является неразложимой тогда и только тогда, когда граф Г (А) сильно связен. Действительно, приводимость А означает существование такой матрицы ( В с\ перестановок Р, что РАРТ = I . Это эквивалентно тому, что мно жество вершин графа G содержит подмножество (соответствующее блоку D), все вершины которого связаны путями только между собой и не связаны путями с остальными вершинам графа G. То есть, граф G не является сильно связным.
Здесь АІ - неприводимые квадратные блоки. В каждой "блочной строке" А/д, Afo,- Afj-i (/ = д+1,..., m+1) есть хотя бы одна ненулевая матрица. Более того, матрица Р такая, что в случае существования нулевых столбцов в матрице Л, в матрице РАРТ они формируют последний "блочный столбец" с номером (га + 1). Если в матрице А нет нулевых столбцов, то матрица РАРТ не содержит "блочной строки" с номером ттг + 1. Утверждение I (Теорема Фробениуса) [14]. Неразложимая неотрицательная матрица А всегда имеет положительное собственное число г, которое является простым корнем характеристического многочлена. Модули остальных собственных чисел не превосходят г. Максимальному собствен ному числу г соответствует положительный собственный вектор. Если при этом имеется h собственных чисел, равных по модулю г, то все они различны между собой и являются корнями уравнения xh — rh = 0. При
Рассмотрим модель динамической распределенной системы, заданную неориентированным графом G = (у,Е), \V\ — п. Каждое ребро (i,j) Є Е будем представлять парой дуг: (i,j) и (_? ,і). Каждой вершине і графа ставится в соответствие множество соседей V{ = {І Є V\ (і, І) Є Е}. Также предполагаем, что каждой вершине і Є V приписан ресурс (потенциал) в количестве Qi 0, который эта вершина на каждом временном шаге к полностью перераспределяет между инцидентными дугами. Обозначим через х\л количество ресурса вершины і, распределенного на шаге к на дугу (i,j) Є Е.
В дальнейшем будем называть описанную модель системой, а величины Хц и Xji весами соответствующих дуг. Назовем множество весов Х% = {%%\з Є Vi} состоянием элемента і в момент времени к, а совокупность состояний всех элементов системы - состоянием системы. Целью исследования является поиск достаточных условий сходимости процесса изменения состояния системы, определяемого (1.1)—(1.3). Найдены условия существования предельных и равновесных состояний, получены оценки скорости сходимости, а также аналитические выражения для этих состояний. Трудоемкость их вычисления не превосходит 0(п3), а для частных случаев (для полного или полного двудольного графа отношений) существенно меньше [2].
Также исследуется процесс перераспределения ресурсов в системе с переменными потенциалами и оценивающими функционалами Cij(xij,Xji) =
Рассматриваемая в данной главе проблема допускает различные содержательные трактовки. Например, пусть исходная система - это глобальная распределенная коммуникационная сеть. Произвольная вершина сети г имеет ресурс, который определяется аппаратными, программными и другими средствами, и отвечает за качество связи с каждой смежной вершиной j Є V{. Ресурс вершины і распределяется по инцидентным дугам (hj)i З Є Vi, таким образом, чтобы суммы весов Ху + х31 были одинаковыми. Такая стратегия имеет смысл, когда все инцидентные ребра равнозначны, а их качество прямо пропорционально количеству выделенного ресурса. Например, если ресурс используется для профилактики заражения компьютерным вирусом, то неважно, откуда придет вирус. Необходимо обезопасить все направления в равной степени. При этом ресурс, в частности, идет на мониторинг коммуникаций, на развитие аппаратной части, а также на разработку соответствующего программного обеспечения для анализа характеристик сети. Данная задача для частного случая топологии сети рассматривалась в [3].
Похожие диссертации на Анализ сходимости итерационных процессов для некоторых задач построения равновесных систем
