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

• Автор: Тахонов, Иван Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 110 с. : ил.

Оглавление
Введение

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

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

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

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

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

Тд (ХХц Ьхг

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

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

1.5.1 Случай ||| <

1.5.2 Случай |||
1.6 Основные результаты
1.7 Иные оценивающие функционалы
1.7.1 Функционалы вида. с(х, жд) = + еах
1.7.2 Функционалы вида Су(жу, х#) = ац (ж,-, + х)
1.7.3 Функционалы вида Сц{х, х) - (цхц +
1.8 Распределение ресурсов в системе с переменными потенциалами
1.8.1 Потенциалы ограниченной вариации
1.8.2 Убывающие потенциалы
1.9 Результаты и выводы к Главе

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 Результаты и выводы к Главе 2
Заключение
Благодарности
Список литературы

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

состоянием системы и обозначим через Хк (Хк € ф[ Л)). Полагаем, что

предельные точки: “четную” и “нечетную”, определяемые следующими соотношениями:

• Пусть а — Ь и граф G не является двудольным. Тогда
г=4+ф°Мв-(Д-чГ(д| ita хг1 = -4 - —(д - о2] - (д| - £) + f.
• Пусть а=-6и граф G не является двудольным. Тогда
Ш 4" = 4 - />D [Е -(Д - Lfl - (д| - ,
lim 4m+1 - 4 - i/°D [S — (А — L)2]_1 (A- - ) . m-*00 ** а-7 L v J V dj dij
• Пусть й = Ьи граф G является двудольным. Тогда
lim 4» = 4 + fD [Е - (д. _ ц]-‘ (д| _ |); ит 4»« = -4 - > [я - (д2 - ц]- (д4 _ £) +Я
• Пусть а — —Ь и граф С является двудольным. Тогда
lim 4" = 4 - Vl) [£? - (Д2 - L)]-1 (Д£ - f) ;
ш-*оо J J о, di dj J
lim ж2Г+1 = 4--/°D [Я - (Д2 - L)]_1 (Д- -
V j i J
т—юо
где I = 1, если г € У1 и / = 2, если г € У2, а / +1 = 2, если г е У1 и I + 1 = 1, если г £ V2.
Доказательство. Следует из Лемм 1.6 и 1.8. □
Замечание 1.1. Для нахождения предельных состояний системы необхо-