Анализ сходимости итерационных процессов для некоторых задач построения равновесных систем тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Тахонов, Иван Иванович

• Тахонов, Иван Иванович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Тахонов, Иван Иванович

Введение

Элементы матричного анализа и теории графов

1 Равновесное распределение ресурсов в динамической распределенной системе

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

1.2 Обозначения и предварительные замечания.

1.3 Распределение ресурсов в системе с оценивающими функционалами вида

Cij (Xij j Xji) (XX jj bXji.

1.4 Анализ рекуррентных соотношений.

1.5 Сходимость итерационного процесса.

1.5.1 Случай

1.5.2 Случай

1.6 Основные результаты.

1.7 Иные оценивающие функционалы.

1.7.1 Функционалы вида Cjj(xij,xji)

1.7.2 Функционалы вида Cij(xij,xji) = a,ij ■ {хц + Xji)

1.7.3 Функционалы вида с^ (жу, xji) CLjXjj Ч- bijXji

1.8 Распределение ресурсов в системе с переменными потенциалами

1.8.1 Потенциалы ограниченной вариации.

1.8.2 Убывающие потенциалы.

1.9 Результаты и выводы к Главе 1.

2 Поиск сбалансированного потока в распределенной сети

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

2.2 Обозначения и предварительные замечания.

2.3 Анализ итерационного процесса.

2.4 Графы без стоков.

2.4.1 Редукция графа

2.4.2 Анализ сходимости процесса.

2.5 Непрерывная зависимость предельного потока от параметров системы.

2.5.1 Все вершины графа связаны со стоками.

2.5.2 Графы без стоков.

2.6 Результаты и выводы к Главе

Введение диссертации (часть автореферата) на тему «Анализ сходимости итерационных процессов для некоторых задач построения равновесных систем»

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

Под динамической распредтаенной системой в данной работе понимается следующий объект. Рассмотрим совокупность элементов V = {1,., п}. Каждый элемент i в момент времени к (время полагается дискретным) характеризуется конечным набором некоторых параметров xf = (ж^, ., xfm ). Назовем этот набор состоянием элемента в данный момент времени и обозначим множество допустимых состояний через Х\ (А^ б Rmi). Совокупность состояний всех элементов системы в момент времени к назовем п состоянием системы и обозначим через

Хк (Хк G д Полагаем, что г= 1 в начальный момент времени система находится в известном состоянии Х°. Каждому элементу i системы сопоставляется подмножество элементов Vt С V (назовем их "соседями" элемента г) и множество Ci С Ujg^U^^', I). Пусть X - некоторое состояние системы. Через Ci(X) обозначим множество параметров {xji\(J,l) G Ci}. Каждый элемент динамической распределенной системы способен изменять свое состояние независимо от остальных элементов. Решение о выборе нового состояния х2 £ Д^ принимается элементом г на основании наблюдаемых в предыдущий момент времени компонент состояний соседей Сг{Хк). То есть, для элемента г известна функция (fii : R 1С,1 —> Л4 выбора нового состояния. Назовем эту функцию стратегией элемента г, а кортеж М = (V, {Vt}, {Хг}, {CJ, назовем динамической распределенной системой.

В этом определении параметры системы (множества соседей Vi и допустимых состояний Xi, множества С{ и оператор перехода Ф) не изменяются от шага к шагу, однако можно рассматривать и такие системы, где эти множества зависят от времени: Vk, Х-% Cf. Речь в данной работе будет идти преимущественно о системах с постоянными параметрами.

В динамической распределенной системе происходит процесс изменения состояний, который описывается соотношением: Хк ь1 = Ф(Х*), где Ф - оператор перехода. При этом возникает ряд естественных вопросов: сходится ли этот процесс к некоторому предельному состоянию? Если сходится, то с какой скоростью, и какими свойствами обладает предельное состояние? Помимо предельных состояний интерес представляют также стационарные (не изменяющиеся со временем) и равновесные (устраивающие все элементы, не смотря на возможную противоположность их интересов) состояния. Рассмотрим последовательность состояний {Xl} (I £ N): Х° - начальное состояние, X1 = Ф(Х°), X2 = Ф(Хх) и так далее. Пусть для некоторого номера к выполняются равенства: Хк = Хк+1 = Хк 12 = . В этом случае состояние Хк является стационарным. Состояние 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) и отыскание сбалансированного потока в распределенной сети (глава 2). Обоснована сходимость этих процедур, получены оценки скорости сходимости, проанализированы свойства предельных решений.

Формально рассматриваемые модели близки к линейным разностным уравнениям. Процесс изменения состояния системы может быть представлен в виде Хк = Ф(Хк~1), где Хк - вектор, описывающий состояние системы в момент времени к, а Ф - аффинный оператор перехода, не зависящий от к. Поэтому решение вопроса о существовании предельного состояния (при к —> оо) сводится к локализации спектра некоторой матрицы. Однако, задача вычисления спектра не самосопряженного оператора до сих пор не решена в общем виде. В работе [28] приведен критерий принадлежности спектра матрицы единичному кругу в терминах решения дискретного уравнения Ляпунова. Для рассмотренных в данной работе систем приведены более простые для проверки достаточные условия сходимости.

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

Изложение материала организовано следующим образом.

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

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

Результаты автора, изложенные в данной главе, опубликованы в работах [3, 9, 11, 12, 13].

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

Результаты автора, изложенные в данной главе, опубликованы в работах [10, 11].

Работа завершается Заключением, содержащим основные результаты диссертационной работы.

Основные научные результаты работы докладывались и обсуждались на семинарах кафедры Теоретической кибернетики Новосибирского государственного университета и отдела Теоретической кибернетики Института Математики имени С. JI. Соболева СО РАН, на семинарах "Дискретные экстремальные задачи" и "Избранные вопросы математического анализа" Института Математики имени С. JI. Соболева СО РАН. на XLII и XLV международных студенческих конференциях "Студент и Научно-Технический Прогресс" (г. Новосибирск, 2004 и 2007 годы), на международной школе-семинаре "Вычислительные методы и решение оптимизационных задач" (г. Бишкек, Киргизия, 2004 год), на XIV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (г. Северобайкальск, 2008 год).

Элементы матричного анализа и теории графов

Введем обозначения и напомним известные понятия и результаты из матричного анализа.

Пусть Мп - это множество п х п действительных квадратных матриц; Ат ~ транспонированная матрица А: через Spec (А) обозначим множество собственных чисел (спектр) матрицы А, а спектральным радиусом матрицы А назовем г (А) = шах |А|.

A €Spec(A)

Каждому вектору х G Rn поставим в соответствие неотрицательный скаляр - норму ЦжЦдп, обладающую следующими свойствами:

1. ||ж + 2/||д» < \\x\\Rn + \\y\\Rn-,

2. ||А.т||дп = |А||М|я«;

3. \\x\\Rn > 0, если ж^О, где х, у £ Rп, а Л - скаляр.

Рассмотрим произвольную матрицу А размерности т х п и линейное преобразование у = Ах, где х £ Rn, а у <Е Rm. Используя нормы || • ||дп и || ■ ||j?m, определим норму матрицы А следующим образом:

А\\ = sup

Ах\\Ет

Из этого определения следует выполнения неравенств ||A+J3|| < \\А\\ + ||Л| и \\АВ\\ < \\А\\\\В\\. п

Легко видеть, что функция ||А|| = max Yl\aii\ является матричной нормой. В дальнейшем эта норма будет часто использоваться.

Матрица А называется неотрицательной, если все ее элементы не меньше нуля.

Матрица А является разложимой или приводимой, если существует такая матрица перестановок Р, что где В и D квадратные матрицы. В противном случае А является неразложимой (неприводимой) матрицей.

Неразложимая неотрицательная матрица А называется примитивной, если г (А) единственное собственное число с максимальным модулем. В противном случае, матрица А называется импримитивной. Обозначим через h(A) количество собственных чисел с максимальным модулем и назовем его индексом импримитивности матрицы А.

Обозначим матрицу смежности графа G — (V, Е) через

Граф Г(Л) = (V, Е) соответствует матрице А, если ф 0 тогда и только тогда, когда (i,j) £ Е.

Граф Н = (у(Н),Е(Л)) называется сильно связным, если для любой пары его вершин i,j £ V{H) существует путь из вершины г в вершину j.

Подграф И' графа Н назовем сильной компонентой графа Н, если множество его вершин V{H!) представляет собой максимальное по включению сильно связное подмножество вершин графа. Иными словами, сильная компонента есть максимальное по включению множество вершин, попарно связанных путями. Очевидно, все дуги между вершинами двух различных сильных компонент ориентированы из одной компоненты в другую. По графу G однозначно строится граф его сильных компонент. Это граф, вершинами которого являются сильные компоненты {Gk}, а дуга (Gk. Gf) принадлежит графу в том и только том случае, когда существует дуга из некоторой вершины компоненты Gk в некую вершину компоненты Gi. Нетрудно видеть, что граф компонент представляет собой ориентированный ациклический граф. В дальнейшем граф компонент, построенный по графу G будем обозначать через K(G).

Замечание I. Граф сильных компонент можно построить с трудоемкостью

Замечание II. Если матрица А соответствует графу G, Р - некоторая матрица перестановок, А' = РАРТ, то матрица А' соответствует графу, получаемому из G соответствующей перенумерацией вершин. Замечание III [15]. Матрица А является неразложимой тогда и только тогда, когда граф Г(т4) сильно связен.

Действительно, приводимость А означает существование такой матрицы жество вершин графа G содержит подмножество (соответствующее блоку D), все вершины которого связаны путями только между собой и не связаны путями с остальными вершинам графа G. То есть, граф G не является сильно связным.

Замечание IV ([14], XIII, §4). Если А приводимая матрица, то существует матрица перестановок Р, под действием которой матрица А принимает следующий блочный вид

0(\V\ + \Е\) [19].

Ai о ! О Aitg+l A1i9+2 О Л2 • О А2,д+1 А2,9+2

Ai ,тп+1

О О ; Ад Ад>д+1

РАРТ =

-m—l,m

Ащ Aj^m+l V 0

Здесь А{ - неприводимые квадратные блоки. В каждом "блочном столбце" A\j, A2J,. -, Af-ij (/ = д + 1,., т + 1) есть хотя бы одна ненулевая матрица. Более того, матрица Р такая, что в случае существования нулевых строк в матрице А, в матрице РАРТ они формируют последнюю "блочную строку" с номером (m + 1). Если в матрице А нет нулевых строк, то в матрице РАРТ отсутствует последний "блочный столбец" с номером m + 1.

Это Замечание справедливо и для случая построчного блочного представления.

Замечание IV'. Если А приводимая матрица, то существует матрица перестановок Р, под действием которой матрица А принимает следующий блочный вид

Ai 0 0 \

0 А2 0 0

РАРТ = 0 0 Ад

А9+1,1 Ад+1,2 • ' Ag+ltg Ад+1

Л+2,1 Ад+2,2 • . Ад+2,д+1 Ад+2

Amfi А , А ■^тпутп—1 -^т

V Am+1,1 Атг+1,2 • ■ • • '"' ''' Ат<т+1 0 J

Здесь А{ - неприводимые квадратные блоки. В каждой "блочной строке" А/д, А/9,. • •, Afj-i (/ = д+1,., m+1) есть хотя бы одна ненулевая матрица. Более того, матрица Р такая, что в случае существования нулевых столбцов в матрице А, в матрице РАРТ они формируют последний "блочный столбец" с номером (га + 1). Если в матрице А нет нулевых столбцов, то матрица РАРТ не содержит "блочной строки" с номером m + 1. Утверждение I (Теорема Фробениуса) [14]. Неразложимая неотрицательная матрица А всегда имеет положительное собственное число г, которое является простым корнем характеристического многочлена. Модули остальных собственных чисел не превосходят г. Максимальному собственному числу г соответствует положительный собственный вектор. Если при этом имеется h собственных чисел, равных по модулю г, то все они различны между собой и являются корнями уравнения xh 0. При h > 1 перестановкой строк матрицу А можно представить в следующем (блочном) виде:

А =

0, niXnx о о

Л1'2

ХП2 о

2,3

О А А 0 h,l nhxni о о о о.

П3ХП3 о о о о о о i-lXnb-x о о о о z\h—l,h

Anh-ixnh о nhxnh J

Утверждение II.([15], п. 8.1) Пусть А - неотрицательная неприводимая матрица. Тогда справедливы следующие неравенства. min ciij < г (А) < шах ^^ с//у. % % з=1 j=1 п min ajj < г (А) < тах^^ a.

Vi i= 1 г—1 причем, равенство в одном из неравенств достигается только в том случае, когда все соответствующие строчные или столбцовые суммы равны между собой.

Утверждение III. Матрица А в степени к стремится к нулевой матрице при неограниченном росте степени (т. е. lim Ак — 0 ), тогда и только тогда, к—* оо когда спектральный радиус матрицы А меньше единицы: r(A) < 1. доказательство. Рассмотрим жорданову форму матрицы А. Ее элементами являются всевозможные степени собственных чисел матрицы А. Таким образом, жорданова форма матрицы Ак (а значит, и сама Ак) стремится к нулевой матрице в том и только в том случае, когда r(A) < 1. □

Утверждение IV. Ряд Ак сходится тогда и только тогда, когда г (А) < к=о

1, и сумма ряда равна матрице {Е — А)-1.

Доказательство. При нарушении условия r(A) < 1 общий член ряда не будет стремиться к нулю (Утверждение III), а значит, будет нарушено необходимое условие сходимости. В случае, когда г (А) < 1, рассмотрим

77 частичные суммы ряда Sn = ]Г) Ак. Нетрудно видеть, что Sn(E — А) = к=о

Е — Л'г+1, и т. к. единица не является собственным числом матрицы А, то матрица (Е — А) обратима. Таким образом, Sn = (Е — А)~1(Е — Лп+1), а значит по Утверждению III Sn —»■ (Р — Л)-1. □

Утверждение V (Теорема Романовского, [15], п. 8.5) Пусть Л неотрицательная и неразложимая матрица, и граф G с множеством вершин {Рг} соответствует матрице Л. Обозначим через L( = {к}, kf,.} количества дуг во всевозможных контурах из Pi в Рг-, а через gt наибольший общий делитель элементов Li. Тогда pi = р2 = • • • = On = h, где h индекс импримитивности матрицы А.

Лемма I [15]. Пусть A G Мп, Л - комплексное число и х, у такие векторы, что Ах = Хх; Ату = Ху и хту = 1. Обозначим L = хут. Тогда, если Л является единственным собственным числом матрицы А с максимальным модулем |А| = г (А) > 0, и собственные числа удовлетворяют следующим неравенствам: |Ai| < | Ао j < . < |Ате| = г {А), то r(i4-AL)<|A„i|<r(i4);

• (ЛА-1)"1 = L + (ЛА-1 - L)m —L, при m +оо;

• Если для некоторого числа р, < р < 1, то || (г1Л)т — L ||оо< Срт, где число С зависит от р и Л. (Здесь и далее через || Л Ц^ или п просто || Л || обозначена матричная норма: || Л ||оо= max J2 \щЛ). Из этой леммы следует теорема:

Утверждение VI (Теорема Перрона) [15]. Если неотрицательная матрица Л неразложима и примитивна, г ее максимальное собственное число и Ах = гх, у А = гу (х,у >0; ух = 1), то Нш (г-1Л)т = L = ху и т—юо (r1A)m — L ||oo< Cp"\ где |Ani| < p <r (A„i - следующее по абсолютной величине собственное число А после г. С определена выше). Утверждение VII [14]. Если неотрицательная матрица А неразложима, а некоторая ее степень As разложима, то с помощью перестановки строк матрица As может быть представлена в блочно-диагональном виде с блоками {А\,., Ad}, где все матрицы Aj являются неразложимыми и имеют одно и то же максимальное собственное число, а число d является наибольшим общим делителем степени s и индекса импримитивности h. Утверждение VIII ([15], п. 5.6) Пусть А матрица размерности п х п и задано некоторое число £ > 0. Тогда существует такая не зависящая от к величина С = С(Д s), что для всех к G N и i,j = 1,., п выполняются неравенства \{Ak)ij\ < С (г (А) +ь)к.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Тахонов, Иван Иванович

Основные результаты:

1. Сформулированы полиномиально проверяемые достаточные условия сходимости процессов изменения состояний в двух классах динамических распределенных систем.

2. Определены оценки скорости сходимости.

3. Получены аналитические выражения для предельных и равновесных состояний.

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

Благодарности

Диссертация выполнена под руководством Адиля Ильясовича Ерзина, которому автор выражает искреннюю благодарность за его неоценимый труд и неизменную поддержку.

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

Автор считает своим долгом поблагодарить всех сотрудников отдела теоретической кибернетики института математики имени С. JI. Соболева СО РАН, которые принимали участие в обсуждении работы на разных стадиях ее выполнения. Отдельных слов благодарности заслуживает Владимир Тихонович Дементьев.

Также автор с большим удовольствием благодарит свою коллегу Таню Алдын-оол, которая всегда с готовностью оказывала поддержку в трудную минуту.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Тахонов, Иван Иванович, 2009 год

1. Астраков С.Н., Ерзин А.И. Одна модель взаимодействия элементов системы. Материалы Всероссийской конференции "Проблемы оптимизации и, экономические приложения". Омск, 2003, с. 74.

2. Астраков С.Н., Ерзин А.И. Одна модель саморегулирующейся системы. Матаматические структуры и моделирование. 2004. 13. С. 30-38.

3. Ерзин А.И., Астраков С.Н., Тахопов И.И., Гадяцкая О. А. Одна задача функционирования распределенной сети. Материалы межд. семинара "Вычислительные методы и решение оптимизационных задач". Бишкек, Кырг. респ. 2004. С. 77-82.

4. Астраков С.Н., Ерзин А.И. Моделирование устойчивых взаимоотношений на графах. Материалы 13-й Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. Т. 1, с. 413-420.

5. Астраков С.Н., Калашников С.Н. Моделирование взаимоотношений между двумя коалициями. Материалы 4~ой Всероссийской научно-практической конференции "Информационные технологии в экономике, науке и образовании". Бийск, 2004, с. 55-58.

6. С.Н. Астраков. Моделирование устойчивых взаимоотношений на графах. Вестник КузГТУ. 2005. №2, с. 94-97.

7. Гадяцкая О.А., Тахонов И.И. Одна модель развития взаимоотношений элементов системы. Материалы XLII Международной научной студенческой конференции "Студент и научно-технический прогресс" (секция "Математика"). Новосибирск, НГУ, 2004.

8. Ерзин А.И., Тахонов И.И. Равновесное распределение ресурсов сетевой модели. Сибирский журнал индустриальной математики. 2005. Т. VIII, №3(23). с. 58-68.

9. Ерзин А.И., Тахонов И.И. Задача поиска сбалансированного потока. Сибирский журнал индустриальной математики. 2006. Т. IX, 4(28). с. 50-63.

10. Тахонов И.И. Устойчивость предельных состояний двух распределенных систем. Материалы XLV Международной научной студенческой конференции "Студент и научно-технический прогресс' (секция "Математика"). Новосибирск, НГУ, 2007. с. 170-171.

11. Erzin A.I., Takhonov I.I. Equilibrium resource Distribution in a Network Model. Journal of Applied and Industrial Mathematics. 2007. V.l №3, 293-302. (перевод)

12. Тахонов И.И. Распределение ресурсов в сетевой модели с переменными потенциалами Материалы 14~й Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, 2008. Т. 5, с. 608-617.

13. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1966.

14. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989.

15. Хакими C.JI. О реализуемости множества целых чисел степенями вершин графа. Кибернетика. Сб. Новая серия. М.: Мир. 1966. 2. С. 40-53.

16. Миронов А.А. О свойствах наборов степеней вершин обобщенных графов. ДАН. 1992. Т. 324. №5. С.959-963.

17. Макеев С.П. О реализуемости взвешенных графов с заданными весами вершин. Управляемые системы. ИМ СО РАН. 1993. 13. С. 40-52.

18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Центр непрерывного математического образования, 2000.

19. Нэш Д. Бескоалиционные игры. Матричные игры. М: Физматгиз, 1961.

20. Дмитриев В.К. Экономические очерки. М.: ГУ ВШЭ, 2001.

21. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985

22. Смольяков Э.Р. Равновесные модели при несовпадающих интересах участников. М.: Наука, 1986.

23. Леонтьев В.В. Межотраслевая экономика. М.: Экономика. 1997.

24. Астафьев Н.Н. Оптимизационный и маргинальный анализ балансовой модели Леонтьева. Оптимизация, управление, интеллект. 2005. №1(9). С. 28-35.

25. Дюсуше О.М. Статичное равновесие Курно-Нэша и рефлексивные игры олигополии: случай линейных функций спроса и издержек. Экономический журнал Высшей школы экономики. 2006. Т. 10, №1. С. 3-32.

26. Р1ванилов В.Ю., Огарышев В.Ф., Павловский Ю.Н. Имитация конфликтов. М.: ВЦ РАН, 1993.

27. Годунов С.К. Современные аспекты линейной алгебры. Новосибирск: Научная книга, 1997.

28. Павловский Ю.Н. Имитационные моде^аи и системы. М.: ФАЗИС, ВЦ РАН, 2000.

29. Попов В.П. Основы теории цепей. М.: Высшая школа, 1985.

30. Котов В.Е. Сети Петри. М.: Наука, 1984.

31. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991.33. фон Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.

32. Минский М. Вычисления и автоматы. М.: Мир, 1971.

33. Adamidou Е. A., Kornhauser A. L., Koskosidis Y. A. A game theoretic/network equilibrium solution approach for the railroad freight car management problem. Transportation Research Part B: Methodological. 1993. 27 (3). P. 237-252.

34. Albin P.S., Hormozi F.Z. Theoretical reconciliation of equilibrium and structural approaches. Mathematical Social Sciences. 1983. V.6. №2. P.261-284.

35. Cobb J.A., Gouda M.G., Musunuri R. A Stabilizing Solution to the Stable Path Problem. Proc. of 6th International Symposium Self-Stabilizing Systems". San Francisco, USA . 2003. P. 169-183.

36. Dolev S., Schiller E. Self-Stabilizing Group Communication in Directed Networks. Proc. of 6th International Symposium 'Self-Stabilizing Systems". San Francisco, USA . 2003. P. 61-76.

37. Fabrikant A., Papadimitriou Ch., Talwar K. The Complexity of Pure Nash Equilibria. Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. 2004. P.604-612.

38. Fudenberg D., Tirole J. Game Theory. Massachusetts: MIT Press, 1991.

39. Gibbons R. Game Theory for Applied Economists. Princeton: Princeton University Press, 1992.

40. Groeber P., Schweitzer F., Press K. How Groups Can Foster Consensus: The Case of Local Cultures. Journal of Artificial Societies and Social Simulation. 2009. 12(2)4 <http://jasss.soc.surrey.ac.Uk/12/2/4.html>.

41. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities Proceedings of the National Academy of Sciences. 1982. V.79. N.8. P.2554-2558.

42. Jahan S. The determination of stability and similarity of Markovian land use change processes: a theoritical and empirical analysis. Social-Economic Planning Sciences. 1986. V.20. №4. P.243-251.

43. Lunberg E. On the concept of economic equilibrium. Structural Change and Economic Dynamics. 1996. V.7. №3. P. 361-390.

44. Meyer F., Vallee J. The dynamics of long-term growth. Technological Forecasting and Social Change. 1975. V.7. №3. P. 285-300.

45. Nishikawa Т., Imai M., Shimuzu S. Nonlinear phenomena in a self-organizing model. Computers and Mathematics with Applications. 1997. V.33. №3. P.73-79.

46. Pawlak Z. About conflicts. Warsaw: Prace IPI PAN №451. 1981.