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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Анализ сходимости итерационных процессов для некоторых задач построения равновесных систем

Специальность 01.01.09 - дискретная математика и математическая

кибернетика

На правах рукописи

ТАХОНОВ Иван Иванович

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 2009

003480311

Работа выполнена в государственном образовательном учреждении высшего профессионального образования "Новосибирский государственный университет".

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Адиль Ильясович Ерзин доктор физико-математических наук, профессор Анна Владимировна Зыкина; доктор физико-математических наук Николай Павлович Дементьев Учреждение Российской академии наук Институт математики и механики Уральского отделения РАН

Защита состоится // ноября 2009 г. в /£> час. мин. на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Коптюга 4, к.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева Сибирского отделения РАН.

Автореферат разослан "1 " октября 2009 г.

"3 ■■

Ученый секретарь диссертационного совета д. ф.-м. н.

Ю. В. Шамардин

Общая характеристика работы

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

В диссертации под динамической распределенной системой понимается совокупность взаимосвязанных элементов, каждый из которых в каждый момент времени (которое полагается дискретным) характеризуется набором значений некоторых параметров — своим состоянием. Состояние системы - это совокупность состояний ее элементов. Элемент может находиться в различных состояниях, и на каждом временном шаге все элементы системы независимо друг от друга изменяют свои состояния на основании имеющейся у них информации о состояниях соседей. Так как элементы действуют независимо, то система попадает в состояние, отличающееся от того, которое ожидали элементы, что на очередном временном шаге побуждает их снова изменять свои состояния.

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

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

Методы исследований. В работе использовались методы матричного анализа, теории графов, исследования операций и дискретного анализа.

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

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

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

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

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

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

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

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

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

Публикации. Основные результаты диссертации опубликованы в 7 работах, из них 3 в рецензируемых изданиях и журналах, рекомендованных ВАК.

Личный вклад. Все результаты получены соискателем лично. В совместных публикациях вклад соискателя является существенным и

заключается в формулировке и доказательстве утверждений. Конфликт интересов с соавторами отсутствует.

Структура и объем работы. Диссертация изложена на 110 страницах и состоит из введения, вспомогательного раздела, двух глав, заключения и списка литературы, содержащего 49 наименований. Работа содержит 19 рисунков.

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

Содержание диссертационной работы

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

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

Основные результаты изложены в двух главах.

В первой главе исследуется процесс перераспределения ресурсов в динамической распределенной системе, моделируемой неориентированным графом <3 = (V, Е), |У| = п. Каждой вершине г € V приписан однородный ресурс (потенциал) в количестве qi > 0, который вершина па любом временном шаге к полностью перераспределяет между инцидентными ребрами. Обозначим через хколичество ресурса вершины г, распределенного на шаге к на ребро (г, 6 Е. Предположим, что начальное распределение ресурсов х?- : £ х^- = I & V, ] £ =

зек

{I £ V : (г, I) £ Е}, известно. Каждая вершина г оценивает качество взаимодействия с соседом j по значению известной функции хц).

Предположим, что произвольная вершина г на шаге к + 1 (к = 0,1,...) принимает решение о перераспределении своего ресурса на основании наблюдаемых на шаге к распределений ресурсов соседей по инцидентным г дугам. При этом вершина г выбирает такое распределение ресурса х*/1, ^ е V;, которое является решением следующей задачи:

■ = зЫ

где величины х^, ] € V* известны. Так как элементы действуют независимо друг от друга, система попадает в состояние, отличное о ожидаемого каждым элементом, что снова (на очередном временном шаге) побуждает элементы перераспределять свои ресурсы.

В первой главе рассматриваются системы с линейными оценивающими функционалами следующих видов:

1. с^агу.а:^) — ах^ где а,Ь е Я\

2. = сцхц + еа^х^, где € Я;

3. = ' {хц + х^г), где а^ £ Д;

4. = а^ где € К.

Также рассмотрены системы с оценивающими функционалами вида = ахц + Ьх^ и переменными векторами потенциалов, удовлетворяющим следующим условиям:

1- «? = ® + е?, € [-£,£];

2. «? = в?"1 -1(9? = ©-*)■

Далее, если не оговорено особо, речь идет о системах с постоянными векторами потенциалов.

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

Для формулировки основных результатов первой главы введем обозначения:

• Г - матрица смежности графа С;

• с^ - степень вершины г в графе б, а й = (<¿1,..., с1п)\

• Б - диагональная матрица с в г-ой строке;

• Д = £)-1Г, Д = ¿Д;

• е® - г-ый орт (столбец);

• "У = Д57 - 57

• /* = Е с«(х* );

• /° - вектор-строка, состоящий из величин

• - сумма ресурсов всех вершин графа; в случае, если граф б является двудольным, через <5; обозначим суммарный ресурс вершин доли £ = 1,2), а <3 = +

Теорема 1.1. Для сходимости процесса перераспределения ресурсов в системе с оценивающими функционалами вида с^ (х^, гс^) — ах^ +Ьх^ достаточно вьшолнепие условия | £ |< 1. При этом:

1. Если | £ |< 1, то процесс перераспределения ресурсов сходится. Предельное (равновесное) состояние не зависит от начального распределения ресурсов и определяется следующим соотношением:

к-*оо ^ ~^ й dj^

2. Если = 1, то процесс перераспределения ресурсов имеет две предельные точки: "четную" и "нечетную", определяемые следующими соотношениями:

• Пусть а — b и граф G не является двудольным. Тогда

lim = 4 + -fD [Е-(А- L)2] Vij,

к~*оо J J а

Um х^ = -4 - l-fD [Е-(А- L)2] Vji + Щ-.

к—*оо d S

• Пусть а = —Ь и граф G не является двудольным. Тогда

lim х% = 4 - -fD [Е-{А- L)2}

«_кПЛ * J п u J

fc—»oo

Hm = 4 - [JB - (Д - Lf] -1 Wji.

k—>oo

• Пусть а = 6 и граф (? является двудольным. Тогда

Нт х% = 4 + [Я - (Д2 - X)]-1 Ит х2^1 = -х% - [Я - (Д2 - Ь)]+ Я

к—» оо ^ а в/

к—юо

Нт х^

-1

• Пусть а = —Ь и граф б является двудольным. Тогда

" а

Нт х2; = х» - [Я - (Д2 - X)] -1

-1

Дт х2^1 = 4 - [Я - (Д2 -Ь)}-1 +

<31 - 01+1

где 1 = 1, если г € V1 и I = 2, если г е У2, а I + 1 = 2, если г 6 У1 и г + 1 = 1, если г е У2.

Матрица Ь определяется следующим образом. В случае, если граф в не является двудольным,

Пусть теперь граф С является двудольным: У = У1 и У2, |У'| = гц

Теорема 1.2. Для сходимости процесса перераспределения ресурсов в системе с оценивающими функционалами вида х^) = сцх^ +

еа^х^ достаточно выполнения условия |е| < 1. При этом:

1. Если |е| < 1, то процесс перераспределения ресурсов сходится. Предельное (равновесное) состояние системы не зависит от начального распределения ресурсов и определяется соотношением:

»=1

(|I = 1,2). Тогда

( \

2. Если |е| = 1, то существует две предельные точки: "четная" и "нечетная", определяемые следующими соотношениями

• Если граф не является двудольным, то

Иш х% = х% + [Е - (Д - Ь)2] -1

+

где s — J2 du а ВИД матрицы L указан выше. iev

• Если граф G является двудольным, то

lim ^ = х% + —f°D [Е - (Д2 - L)]~l Vij,

h—юо CXj

& =- -(A2 - v»+f'

где st = Q, = E E 4 + i = 1, если i e V1

ieV jevi

и / = 2, если г £ У2, а Z + 1 = 2, если г € F1 и I + 1 = 1, если i € F2.

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

вида: Cij(xij,xji) = aij ■ (Xij +Xji). Введем обозначения: •<* = £

j&Vi 3

• а = («1,... ,а„);

• A = diag{ax,a 2,...,ап}.

Теорема 1.3. При выполнении условия аij = aji для каждого ребра (г, j) € Е процесс перераспределения ресурсов в системе с оценивающими функционалами вида Cij(xij, Xji) = а^ ■ (xij +xJt) для произвольного графа G имеет две предельные точки, "четную" и "нечетную", определяемые следующими соотношениями:

- «а+<Е - (дг - (4 ^ й ■

Jim «Г = -4 - ±ГЛ (Е - (А» - i))"' (< " + 4,

Величины Qij зависят от вида графа G. В случае, если граф G не явля-~ п

ется двудольным, Q¿j — 2Q/(a¿j ^ am). В случае двудольного графа

7П=1

„ П1 — П1+П2

G Qij = Q/{a{j £ «m), если i £ У1, и Qi¿ = Q/{aij £ am), если

m=l т=щ+1

i € У2.

Матрица L определяется следующим образом. Если граф G не является двудольным, то

L =

/ ai ai . . a„

1 ai а 2 • • "n

л

X) 04

i=l \ ai "2 • • )

Если граф G является двудольным: V = У1 U V2, |У'| = n¡ (I = 1,2), то

/

Чо

А

ni \»=i

, (¿ = 1,2).

t,j=l,...n¡

Теорема 1.4. Для сходимости процесса перераспределения ресурса в системе с оценивающими функционалами вида «чД®^

ЬцХц достаточно выполнения условия ^ < | для каждого ребра

€ Е. При этом предельное (равновесное) состояние, не зависит от начального состояния Х°.

Теорема 1.5. Достаточным условием сходимости процесса перераспределения ресурсов в системе с оценивающими функционалами вида сц(хИ>ха) = ахч + и вектором потенциалов, удовлетворяющем условию д* = <?»+£* (£{ £ [—£,£]) , является выполнение неравенства |Ь/а| < 1. При этом верна следующая оценка для предельного распределения ресурсов:

(га+1)£2 < lim 4 <4+ (П + 1)£

(1-ÜI)2 (1-IÍI)

2 '

где {х^ |(г,6 Е} - это предельное распределение ресурсов в системе с постоянным вектором ресурсов д.

Теорема 1.6. При выполнении условия \Ь/а\ < 1 в системе с оценивающими функционалами вида Cij(xij,xji) = axtj + bxji и вектором потенциалов, удовлетворяющем условию qf — qi — к верны следующие соотношения:

3* = х% - 1 - kI(E - Д)_1и + 1(Е - A)~2v + о(к),

щ

где v = Aj- — а ~ количество ресурса, распределенного на ребро (г, j) е Е в момент времени к в системе с постоянным вектором потенциалов q.

Таким образом, в первой главе рассмотрена n-элементная модель распределенной системы на графе и исследован вопрос сходимости процесса перераспределения ресурсов в системах с различными линейными оценивающими функционалами. Сформулированы полиномиально проверяемые достаточные условия сходимости этих процессов, получены аналитические выражения для вычисления предельных и равновесных состояний, трудоемкость вычисления которых равна 0(п3). Проведен анализ процесса перераспределения ресурсов в системе с переменными потенциалами и показана сходимость процесса в частном случае. Получены оценки для предельных состояний системы с потенциалами ограниченной вариации и асимптотическое распределение ресурсов в системе с убывающими потенциалами.

Во второй главе исследуется процесс перераспределения потока в динамической распределенной системе, моделируемой ориентированным графом G — (У,Е), |V| - п. Каждой вершине г G V соответствуют два подмножества вершин: = {к & V|(fc, г) 6 Е} и О» = {fc G V\(i, к) е Е}. Обозначим через Т множество стоков графа G: Т — {г € V\Oi = 0}. Потоком в графе G назовем множество действительных чисел X = {xij > 0|(г, j) 6 Е}. Для каждой вершины, не являющейся стоком, считаем заданным ее потенциал <j{, характеризующий величину потока, возникающего в этой вершине в единицу времени. Также для каждой вершины г е V\T считаем заданным вектор пропорций Ai = {dij > 0|j G Oi, aij — 1}.

jeOi

Предположим, что каждая вершина i £ V\T в момент времени (fc + 1) перераспределяет пришедший в нее в момент к (к > 0) поток по исходящим дугам согласно заданным пропорциям ац\

4*1 = «У (« + xPi)' 1 е V\T> 3 е Oi, к = 0,1,..., pe/i

Начальный поток ■, (i.j) € Е считается известным. Эти соотношения

определяют процесс изменения состояний системы.

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

Для формулировки основных результатов этой главы введем обозначения:

• Г = {7^ } - матрица смежности графа б;

• А = {а^}, <Хц = ащу - матрица коэффициентов

• 9 - вектор (строка) потенциалов вершин;

• — Л I - суммарный поток, входящий в вершину г в момент времени к (к > 0);

• Р° ~ (р?) ■ ■ • !Рп) " вектор (строка), содержащий величины

• Е- единичная матрица, а е* - ее г-ый столбец (г-ый координатный орт).

Введем функцию Л (б). Пусть (7 -некоторый ориентированный граф. Тогда:

• если С? сильно связен, то значение /¿(б) равно НОД длин всех контуров в С;

• если С? не является сильно связным, то /1(С)=НОК(Л((?1),..., К{Сд)), где {(?!,..., Стд} - сильные компоненты (?, являющиеся стоками в графе компонент К (С).

Теорема 2.1. Пусть граф б имеет непустое множество стоков Т и каждая вершина графа соединена путем с некоторым стоком. Тогда процесс перераспределения потока сходится к предельному состоянию, определяемому следующим соотношением:

причем сходимость осуществляется со скоростью геометрической прогрессии.

Теорема 2.2. Пусть <7 - граф, в котором есть вершины, не соединенные путями со стоками, и вектор потенциалов 9 = 0. Тогда процесс перераспределения потока имеет Л = Л(С?) предельных точек:

х(г+1)+/,оо = а. .^+/.00^ г = о,... ,/г - 1, (у')еЕ,

Здесь через Аг+Н°° обозначен следующий предел: lim AT+h k.

к—юо

Измерение параметров реальных систем неизбежно сопровождается погрешностями, а вычисление значений потоков - машинными округлениями. Это может привести к сильному расхождению между теоретически вычисленными значениями потоков и результатами численных экспериментов. Поэтому возникает вопрос: насколько сильно неточности в параметрах системы и вычислительные погрешности влияют на результаты вычислений. Чтобы ответить на него, наряду с процессом

J2 4i=Pi

P€J¡

reii

(1)

рассмотрим процесс

Здесь

p€li

peh

(2)

+ Tij

$=Р? + С< qi = 4i + Vi

Или

A = A + T P°=P° + C

q = q + f]

Считаем, что влияние погрешностей сказывается следующим образом: вместо точных значений параметров А, р°, д известны "приближенные" А,р°, отличающиеся от истинных значений на величины небольших порядков. Помимо этого, на каждом шаге вычислений происходит округление. Относительно А полагаем, что искажению подверглись только ненулевые элементы матрицы А. То есть, для каждого г выполняются соотношения:

ац > 0, з € V;,

£ ä

jeOi

ij

■ Е ^ = { i, и

jeOi

является стоком; иначе.

Отсюда следует, что = 0.

¿60;

Теорема 2.3. Пусть в графе С из каждой вершины есть путь в сток. Тогда процессы (1) и (2) сходятся. Пусть г — тах {г(Л), г(А)}, а £ такое

положительное число, что г + f < 1. В случае, когда параметры системы, их возмущения и погрешности вычисления удовлетворяют неравенствам: |гу| < т, | < в, dij <a,qi< q, qi < q, | < £, верна следующая оценка:

i к к I п { паЧт ав + rq \

Теорема 2.4. Пусть в графе G есть вершины, из которых нет путей в стоки и вектор q = 0. В этом случае процесс, определяемый соотношениями (2) расходится. Пусть ß - некоторое положительное число. Тогда при к < -—-верпы неравенства:

I к _ к I n^C'TmaxamaxPmax . * . 1 Д

Wij — < _ - i TlQ-max^max i TiTmaxPmax + P

I ß

I fc * I ^ бттах^тахРтах . „

Wij ~ I — , _ - г TlO-maxsmax т ПТтахРтах + P +

L fl

~^~QmaxPmaxC'ß j

где fi (ß) меньше единицы, но больше второго по абсолютной величине собственного числа А (А), а С = С (А, р) (С — С(А, Д)) некоторая величина, не зависящая от к.

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

Список публикаций

Основные результаты диссертации опубликованы в семи работах. Из них три статьи в реферируемых изданиях и журналах, рекомендованных ВАК:

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

[2] Брзин А.И.,Тахонов И.И. Задача поиска сбалансированного

потока. Сибирский журнал индустриальной математики. 2006. Т. IX, 4(28). с. 50-63.

[3] 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. (перевод работы [1])

Материалы и тезисы докладов на международных и всероссийских конференциях:

[4] Ерзин А.И., Астраков С.Н., Тахонов И.И., Гадяцкая O.A. Одна за-

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

[5] Гадяцкая O.A., Тахонов И.И. Одна модель развития взаимоотно-

шений элементов системы. Материалы XLII международной научной студенческой конференции "Студент и научно-технический прогресс": Математика. Новосибирск, 2004.

[6] Тахонов И.И. Устойчивость предельных состояний двух распре-

деленных систем. Материалы XLV международной научной студенческой конференции "Студент и научно-технический прогресс": Математика. Новосибирск, 2007. с. 170-171.

[7] Тахонов И.И. Распределение ресурсов в сетевой модели с перемен-

ными потенциалами. Материалы XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения", секция "Математическая экономика". Иркутск, 2008. с. 608-617.

ТАХОНОВ Иван Иванович

Анализ сходимости итерационных процессов для некоторых задач построения равновесных систем

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 2 октября 2009. Формат 60x84 1/16. Заказ №347 Офсетная печать. Объем 1,0 п.л. Тираж 100 экз.

Редакционно-издательский центр НГУ 630090, г. Новосибирск, ул. Пирогова, 2.

Введение

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

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. Соболева СО РАН, которые принимали участие в обсуждении работы на разных стадиях ее выполнения. Отдельных слов благодарности заслуживает Владимир Тихонович Дементьев.

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

Заключение

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

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.