автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Ресурсные сети и анализ их динамики

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ Институт проблем управления им. В.А. Трапезникова РОССИЙСКОЙ АКАДЕМИИ НАУК

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

005531285

Жилякова Людмила Юрьевна

РЕСУРСНЫЕ СЕТИ И АНАЛИЗ ИХ ДИНАМИКИ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ

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

2013

Москва 2013

005531285

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А. Трапезникова РАН

Научный консультант: доктор технических наук,

профессор Кузнецов Олег Петрович

Официальные оппоненты: доктор физико-математических наук

Назин Александр Викторович

доктор физико-математических наук, профессор

Дмитриев Михаил Геннадьевич

доктор физико-математических наук, профессор

Рыков Владимир Васильевич

Ведущая организация: ФГБУН Институт системного анализа

РАН

Защита состоится «сУ » 2013 г. в часов на заседании

диссертационного совета Д 002.^26.02 при Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А. Трапезникова РАН по адресу: 117997, Москва, ул. Профсоюзная, 65.

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

Автореферат разослан «2013 г.

Ученый секретарь

диссертационного совета /Д^//

кандидат технических наук /([) ' В.Н. Лебедев

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

Актуальность темы. Сетевые и графовые модели применяются при описании разнообразных процессов во многих предметных областях, при исследовании системных свойств сложных объектов, в оптимизационных задачах, в задачах сетевого управления, обработки информации и прогнозирования. Эти модели используются при решении классических потоковых задач, комбинаторных задач, при моделировании стохастических и детерминированных процессов с конечным или бесконечным множеством состояний, при решении проблем централизованного и децентрализованного управления сложными системами, задач распределения нагрузки в электрических, транспортных, компьютерных, коммуникационных и других сетях, в системах обработки распределенной информации. Разнообразие предметных областей влечет за собой разнообразие применяемых моделей и методов. Основные направления развития классических графовых моделей обусловлены их применением в задачах о нахождении потоков, обладающих заданными характеристиками или удовлетворяющих критерию оптимальности по совокупности параметров. В большинстве этих задач ищутся некоторые выделенные пути на графе. Исследованием потоковых моделей занимались многие российские и зарубежные специалисты алгоритмической теории графов, среди которых Г.М. Адельсон-Вельский, Е.А. Диниц, A.B. Карзанов, А.И. Ерзин, И.И. Тахонов, Я.М. Ерусалимский, L.R. Ford, D.R. Fulkerson, J. Edmonds, R.M. Karp, E.W. Dijkstra, T.C. Hu, R.K. Ahuja, T.L. Magnanti, J.B. Orlin и другие исследователи. Принципиально иной подход используется в моделях рассеяния на графах: в них рассматриваются все возможные пути между вершинами в связном графе. Такая формулировка задач может быть названа «интегральной по путям»1. Алгоритмами, построенными на основе случайных блужданий, решаются задачи распределения нагрузки в электрических и компьютерных сетях, моделируется распространение мнений в социальных сетях, производится анализ значимости пользователей и сайтов Интернет (алгоритм PageRank и

1 Blanchard, Ph., Volchenkov, D. Random Walks and Diffusions on Graphs and Databases: An Introduction (Springer Series in Synergetics). Springer-Verlag - BerlinHeidelberg. 2011.

его модификации), решаются задачи информационного управления. Задачи анализа топологических характеристик графов, сходимости асимптотических методов, спектрального анализа матриц смежности и лапласовских матриц, получения качественных оценок конечных состояний и многие другие задачи решались в работах следующих авторов: П.Ю. Чеботарев, Р.П. Агаев, А.И. Ерзин, И.И. Тахонов, В.Л. Стефанюк, J.G. Kemeni, J.L. Snell, Ph. Blanchard, D. Volchenkov, DJ. Aldous, L. Lovâsz, P. Winkler и др. Еще один вид моделей - пороговые целочисленные модели, в частности, игры выстреливания фишек (chip-firing games), в которых рассеяние происходит только в тех вершинах, для которых хранимая в них величина превосходит пороговое значение. Основные результаты в исследовании этих моделей получены в работах L. Lovâsz, P. Winkler, N.L. Biggs, A. Bjôrner, R.J. Anderson, P.W. Shor, J. Spencer, E. Tardos, F. Chung, R. Ellis, E. Prisner. Такими пороговыми моделями, в частности, описываются явления самоорганизующейся критичности «лавина» или «абелева куча». Эти исследования принадлежат, в основном, зарубежным авторам: P. Вак, С. Tang, К. Wiesenfeld, R. Cori, D. Rossin, D. Dhar, T. Sadhu, S. Chandra, E.R. Speer и др.

Функционирование ресурсных сетей, исследованных в настоящей работе, отличается от всех известных моделей. Вершины в них отдают ресурс в исходящие ребра по двум разным правилам. Выбор правила в каждой вершине обусловлен количеством содержащегося в ней ресурса. Указанные особенности расширяют область применимости сетевых моделей и позволяют имитировать нелинейные процессы; делимость ресурса обеспечивает сходимость там, где в пороговых моделях она не имела места. Моделирование сложных систем с помощью ресурсных сетей позволяет при их анализе выделять объекты предметной области, соответствующие классу аттрактивных вершин, способных аккумулировать большую часть ресурса в сети. Для классов сетей, в которых предельное состояние зависит от начального, ставятся и решаются прямая и обратная задачи управления. Именно этим обусловлена актуальность настоящей диссертационной работы.

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

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

Для достижения этой цели поставлены следующие задачи:

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

2. Определение порогового значения ресурса для каждого класса сетей, при котором некоторое множество вершин изменяет правило функционирования. Исследование процессов, происходящих в сетях в окрестности порогового значения ресурса.

3. Исследование функционирования регулярных сетей при малых ресурсах.

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

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

6. Исследование явления аттрактивности и нахождение критерия аттрактивности вершин в регулярных несимметричных сетях.

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

8. Исследование поглощающих сетей с несколькими стоками и несимметричных сетей с несколькими аттракторами.

9. Определение условий, при которых возможна постановка задачи управления в сетях. Формулировка двух задач управления.

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

Методы исследования. Для описания предельных состояний и потоков использовались методы конечных цепей Маркова, теории матриц, теории графов, спектрального анализа, исследования операций и численные методы. При исследовании предельных состояний и потоков, а также динамики переходных состояний и видов асимптотических процессов, использовалась программа, написанная в среде Visual FoxPro 9.0. Все примеры работы сети (протоколы, гистограммы, графики), представленные в работе, и множество других, были получены с помощью данной программы. Экспорт данных в MS Excel позволил получить на основе табличных данных их графическое представление.

Научная новизна. Ресурсная сеть - новая, ранее не исследованная потоковая модель, предложенная в 2009 году О.П. Кузнецовым2. Им был исследован частный случай - полная однородная сеть. В настоящей работе исследованы функционирование, предельные состояния и потоки всех классов ресурсных сетей при любых начальных состояниях и любом суммарном ресурсе. В процессе исследования получены следующие теоретические результаты.

1. Проведена классификация ресурсных сетей в соответствии со свойствами их матриц пропускных способностей и структурными свойствами их графов.

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

2 Кузнецов О.П. Однородные ресурсные сети. I. Полные графы // Автоматика и телемеханика, 2009, № 11. С.136-147.

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

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

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

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

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

8. В эргодических циклических сетях с ¿1 циклическими классами описаны г/ предельных векторов, между которыми происходят колебания состояний сети при малых ресурсах. Найден класс начальных состояний, при которых в сетях с малыми ресурсами существует равновесие. Показано, что при больших ресурсах циклические сети теряют осцилляционность, их поведение становится эквивалентным поведению регулярных сетей; найдены все характеристики циклических сетей: пороговое значение ресурса Т, критерий аттрактивное™ вершин, предельный поток и предельное состояние.

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

Практические результаты:

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

2. Модель реализована в виде программного комплекса, рассчитывающего в дискретном времени распространение вещества по акватории.

Основные положения, выносимые на защиту:

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

2. Классификация ресурсных сетей в соответствии со свойствами их матриц пропускных способностей и порождаемых ими цепей Маркова.

3. Методы нахождения основных характеристик ресурсных сетей: определение порогового значения ресурса Т\ предельного состояния регулярных сетей при малом ресурсе и предельного потока при любой величине ресурса.

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

5. Методы вычисления предельного состояния в эйлеровых сетях при больших значениях ресурса как функции от начального состояния.

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

7. Формулы нахождения предельного состояния в поглощающих сетях при любых значениях суммарного ресурса.

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

9. Модель распространения вещества в водной среде и ее программная реализация.

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

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

На основе несимметричной ресурсной сети автором разработана модель распространения загрязняющих веществ в водной среде «Substance Spreading», позволяющая производить оперативное прогнозирование. Модель внедрена в Азовском научно-исследовательском институте рыбного хозяйства (ФГУП АзНИИРХ), что подтверждается актом о внедрении.

В работах В.Б. Тарасова и B.C. Дюндюкова ресурсные сети расширены до ресурсно-целевых - такие сети применяются при моделировании взаимодействий агентов в многоагентных системах3.

Апробация. Основные результаты диссертационной работы докладывались на Всемирном Конгрессе IF АС (Milano, Italy, 2011), на Двенадцатой и Тринадцатой национальных конференциях по искусственному интеллекту с международным участием (Тверь, 2010, Белгород 2012), на X международной научно-технической мультиконференции «Актуальные проблемы информационно-компьютерных технологий, мехатроники и робототехники» (Дивноморское, 2009), на X, XI и XII международных конференциях им. Т.А. Таран «Интеллектуальный анализ информации» (Киев, 2010, 2011, 2012), на Научной сессии НИЯУ МИФИ-2010 (Москва, 2010), на Международных научно-технических конференциях «Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems OSTIS» (Минск, 2011, 2012, 2013), на первой всероссийской конференции с международным участием «Системный анализ и семиотическое моделирование» SASM-2011 (Казань, 2011), на 4-й Всероссийской мультиконференции по проблемам управления МКПУ-2011 (Дивноморское, 2011), на международной научно-практической конференции «Теория активных систем» (Москва, 2011), на Общемосковском семинаре «Экспертные оценки и анализ данных», на семинарах Института проблем управления им. В.А. Трапезникова РАН. На программные продукты получены два свидетельства об официальной регистрации программы для ЭВМ

Дюндюков B.C., Тарасов В.Б. Формирование многоагентных систем с помощью ресурсно-целевых сетей // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2012): материалы Международной научно-технической конференции. Минск: БГУИР, 2012. С. 257 - 265.

Федеральной службы по интеллектуальной собственности, патентам и товарным знакам: свидетельство № 2010617261: Модель неоднородной ресурсной сети «Resource Distribution» и свидетельство № 2010617260: Модель распространения химических веществ и пассивных биологических объектов «Substance Spreading».

Исследования по теме диссертационной работы проводились в соответствии с плановой тематикой работ Учреждения Российской академии наук Института проблем управления им. В.А. Трапезникова РАН в рамках темы 3113/10 и Программы фундаментальных исследований № 14 ОЭММПУ РАН, а также при поддержке РФФИ (грант № 11-01-00771) и при финансовой поддержке Минобрнауки России по государственному контракту от 16.05.2012 г. №07.524.12.4018 в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы».

Публикации. Основные результаты диссертации опубликованы в 32 статьях и докладах, среди которых 10 публикаций в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК, 2 - в международных изданиях. Доклады доложены на 15 международных, 5 всероссийских научно-практических конференциях. Программные продукты защищены двумя авторскими свидетельствами об официальной регистрации программ для ЭВМ.

Личный вклад автора. Все результаты по теме диссертации были получены автором самостоятельно. В совместных публикациях автора с О.П. Кузнецовым [1, 2, 11, 12, 17, 18, 23, 29, 30, 32] О.П. Кузнецову принадлежат понятия, основные определения и результаты, полученные для полных однородных сетей. Все определения и результаты, касающиеся остальных классов сетей, получены автором; автору принадлежат определения и формальные построения моделей, основанных на ресурсных сетях, а также описания их компьютерной реализации. В работах [20, 21], автором написаны разделы, касающиеся ресурсных сетей.

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

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

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

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

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

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

Третий класс - целочисленные пороговые модели. Это, в первую очередь, модель «игра выстреливания фишек». Игра выстреливания задает графовую интерпретацию модели «абелева куча песка», описывающей явление самоорганизованной критичности.

Дается определение ресурсной сети, описываются правила ее функционирования и основные свойства.

Ресурсной сетью называется связный орграф G = (V, Е) с вершинами v, е V, \V\= п, ребрам которого е,у = (v„ vj) е Е приписаны неотрицательные числа Гц, постоянные во времени и называемые пропускными способностями. Ресурсами q,(t) называются неотрицательные числа, приписанные вершинам v, и изменяющиеся в дискретном времени t. Вершины v, могут хранить неограниченное количество ресурса.

Состоянием Q{t) сети в момент t считаем вектор Q{t) = (q\{t), ..., q„(t)), содержащий значения ресурсов в каждой вершине.

Состояние Q = (д\, ..., q„) называется предельным, если для любого е > 0 существует 1С такое, что для всех t > tE \q*-q(t)\<z,i= 1,2, ...,n.

R = (rij)n x n - матрица пропускной способности сети.

п и

rsum = X Tjrij ~ суммарная пропускная способность сети. i=iy=i

п п

г'" = ХО' и г'°г" = Х'// — входная и выходная пропускные

/=1 м

способности вершины, соответственно. Пропускная способность петли, если она существует, входит в обе суммы.

В сети выполняется закон сохранения: при функционировании

и

ресурс не поступает извне и не расходуется: V7 = const = W

i=l

(fV- суммарный ресурс сети).

Распределение ресурса происходит по одному из двух правил, выбор которых зависит от количества ресурса в вершинах.

Правша распределения ресурса. В момент t вершина v, отдает в ребро, соединяющее ее с вершиной vk:

r,k единиц ресурса, если qi{t)>r°ut (правило 1);

ресурса, если qi(t)<r°M (правило 2).

ri

Ресурс, выходящий из вершины v, по ребру (v„ v*) в момент t, приходит в вершину vk в момент t+l.

Множество вершин с ресурсом #,(/), не превосходящим г""', называется зоной Z~(t). Вершины из Z~(t) функционируют по правилу 2. Z+(t) - множество вершин, ресурс которых больше их

выходной пропускной способности, они функционируют по правилу 1. Для предельного состояния Q обозначим эти зоны Z" и Z+\

Поток ресурса. Ресурс, выходящий из вершины v, по ребру (v„ v,) в момент t, приходит в вершину v, в момент t + 1. Будем считать, что между моментами t и t+l ресурс находится в ребре (v„ Vj). Этот ресурс назовем потоком /¡¡(t). Общий поток сети описывается матрицей F(t) = (J]j(t))n/n.

п

]Г/у (() = /""'(t) - поток, выходящий из вершины V,- в момент t.

/=1

п

Yjfy (0 = ff +1) поток, входящий в вершину у,; f" (0) = 0.

;=1

п п

Величиной потока называется сумма: fslim(t) Х/у (') •

/=iy=i

Fm"(t) = {f"l"(t),...J^"(t)) - вектор исходящего потока и F'"(t) = (/,"' (/),...,/„'"(/)) - вектор входящего потока.

Пределы lim Fou'{t) и X\mFln(t), если они существуют,

t—»00 t—»CO

обозначим через F"* и F""*, соответственно.

Вводятся две независимые классификации ресурсных сетей: по топологии (С,) и по пропускным способностям (С2).

Первая из них основана на классификации соответствующих цепей Маркова (рис.1).

Рис. 1. Топологическая классификация ресурсных сетей (Ci)

Эргодической сетью называется сеть, граф которой сильно связен. Если, дополнительно к этому, НОД всех циклов графа равен 1, сеть называется регулярной. Эргодической компонентой неэргодической сети называется сильно связная компонента, из которой нет выходящих ребер. Компоненты сети, отличные от эргодических, называются переходными4. Сеть, в которой все эргодические компоненты представлены стоковыми вершинами, называется поглощающей. Пунктирная стрелка на рис. 1 показывает, что изучение неэргодических сетей общего вида сводится к изучению соответствующих поглощающих сетей.

Вторая классификация - классификация по пропускным способностям (для нее неважны свойства стохастических матриц). Введем дополнительные определения.

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

Ресурсная сеть называется симметричной, если симметрична ее матрица пропускной способности: Я = ЯТ.

Ресурсная сеть называется квазисимметричной, если V/ г,'" = г'я".

Если сеть не квазисимметрична, в ней существует хотя бы пара вершин, для которых г}" - г°м ^ 0. Для произвольной вершины V,

обозначим эту разность через Лт-,: Дг, = г'" - г°ш. Тогда все вершины сети можно разделить на три класса:

1) вершины-приемники, для которых А г, > 0;

2) вершины-источники, для которых А г, < 0;

3) нейтральные вершины, для которых А/-, = 0.

В квазисимметричных сетях все вершины нейтральны.

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

4 Их называют также невозвратными (см., например, Дж.Кемени, Дж.Сиелл. Конечные цепи Маркова, М., Наука, 1970, с.52).

5 Термин «однородная ресурсная сеть» не связан с понятием однородной цепи Маркова.

р = ;гГ')..(г/^г,;л'')) - кортеж, характеризующий

вершины сети.

На рис. 2 представлена классификация Сг.

Рис. 2. Классификация ресурсных сетей по пропускным способностям (Сг)

Три класса: полные однородные, симметричные и квазисимметричные сети объединены в общий класс эйлеровых сетей.

Матрица классов сетей, содержащая все допустимые пары из декартова произведения С\ х С2, представлена в таблице 1.

Таблица 1. Классы ресурсных сетей и структура диссертации

с2 с, Однородные Несимметричные Эйлеровы

Регулярные Глава 1 (полные) Глава 2, 3, 7 Глава 2,4

Циклические Глава 5 Глава 5 Глава 5

Поглощающие Глава 6, 7 Глава 6, 7 -

Полные однородные сети. Для полных однородных сетей определено пороговое значение ресурса Т: при IV < Т все вершины сети с некоторого такта ( переходят на правило 2; при W > Т для любого ? > 0 хотя бы одна вершина функционирует по правилу 1. В полной однородной сети Т=гп2. Предельное состояние существует

при любом суммарном ресурсе. Оно является единственным при IV < Т и зависит от начального состояния при IV > Т. Приведены формулы компонент вектора предельного состояния при любом значении ресурса.

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

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

В общем случае процесс функционирования регулярной сети по правилу 2 описывается однородной цепью Маркова, которая задается стохастической матрицей Я': К' = 0~{Я, где

Вектор 2'*= (<71*> ••■. <]„) предельного состояния сети при IV = 1 совпадает с вектором предельных вероятностей цепи Маркова и, соответственно, обладает всеми его свойствами.

Вводится понятие малого ресурса и описывается предельное состояние регулярной сети при малых ресурсах. Ресурс считается «малым», если за конечное число тактов все вершины сети переходят на функционирование по правилу 2. Малый ресурс существует для любой сети. В силу регулярности сети положительный собственный вектор матрицы Я' единствен, и, таким образом, при любом малом ресурсе выполняется равенство:

о)

Путь от нейтральной вершины к источнику, не содержащий вершин-приемников, назван неположительным путем.

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

Доказана теорема о существовании и единственности порогового значения ресурса Т.

Теорема 2.3. В регулярной несимметричной сети существует пороговое значение суммарного ресурса Т, такое, что:

при IV < Т все вершины, начиная с некоторого {, переходят в зону

при IV > Т зона непуста, начиная с некоторого ?". Т единственно и не зависит от начального состояния 2(0).

Значение Т не превосходит суммарной пропускной способности г5,„„. Чем более разнятся суммарные входные и выходные пропускные способности вершин сети, тем меньше становится пороговое значение Т. В однородной сети Т= гя,ш; чем больше проявляется несимметричность, тем дальше значение Т от г„,т. Коэффициентом симметричности сети называется отношение Т

X =-. В регулярных сетях % е (0, 1].

В ресурсной сети не только источники и нейтральные вершины, но и некоторые вершины-приемники не могут перейти в зону 2+(/) при любом сколь угодно большом значении суммарного ресурса IV и начальном состоянии 0(0). Поэтому для несимметричных сетей вводится понятие аттрактора. Вершины, которые при IV > Г из любого начального состояния переходят в зону Z+(t) за некоторое число тактов, называются аттракторами. Вершины, для которых существует начальное состояние 2(0), из которого они переходят в зону 2 +(0, называются потенциальными аттракторами.

Аттракторы в сетях делятся на два непересекающихся класса: 1) активные аттракторы — это вершины, способные притянуть ресурс в процессе функционирования сети; активным аттрактором может быть только вершина-приемник; 2) пассивные аттракторы — вершины, способные удержать большой ресурс при определенном начальном состоянии, но не способные притянуть его; пассивными аттракторами могут быть только нейтральные вершины, из которых нет неположительных путей.

В несимметричной сети необходимо существует один активный аттрактор.

В третьей главе рассмотрены потоки при любом значении ресурса и предельные состояния при ]¥> Т в регулярных несимметричных сетях. Показано, что при IV <Т предельные потоки существуют, причем:

= = С, = к.

Вектор предельного состояния для ]¥= Т обозначим через 0 = (¿71, ...,</„), потоки через и . Тогда

= рШ= д. 1ит = Т

Из доказательства теоремы 2.3 следует, что при IV = Т хотя бы одна вершина будет иметь ресурс, равный своей выходной

пропускной способности: q¡ = г""'. Введем в сети такую нумерацию

вершин, при которой ц, = г""' выполняется для первых / вершин

(/>!)•

Тогда 0 = (гхш..,?„) ■

Те о р ем а 3.1. В регулярной несимметричной сети для IV > Ти любого начального состояния предельный поток существует, и матрица предельного потока Р имеет вид:

ги П2 ■ П„

П\ г12 Пп

5/+1 он/ ГМ,1 Н+1 Чм _ 0М ГМ,2 • ГМ 9м _ ' оШ /+1,« г1+1

Яп _ оШ гп <?„ оШ "2 гп я» г оШ »" Гп у

где первые I вершин имеют при IV = Т ресурс, равный своей выходной пропускной способности (/ > 1).

Непосредственно из этой теоремы следует истинность ряда утверждений для регулярной несимметричной сети:

3.1. При любой величине и начальном распределении ресурса IV > Г предельное состояние существует.

3.2. При любой величине и начальном распределении ресурса IV > Т суммарный предельный поток равен пороговому значению

ресурса: /,*„„ = Т.

3.3. Для любого IV> Т вектор предельного потока совпадает с вектором предельного состояния при УУ = Т:

Р» = И*)т = 0=(гГ,.,гГ,чм,.,чп).

3.4. Вершина является потенциальным аттрактором тогда и только тогда, когда в предельном состоянии при IV = Т она имеет

ресурс, равный своей выходной пропускной способности: с[к = г™".

3.5. Вершины, имеющие при Ш= Т ресурс, меньший своей выходной пропускной способности: <7 ■ < г°ш, при любом IV > Т

имеют в предельном состоянии ресурс, равный ду., и вектор предельного состояния имеет вид:

0* = (гГ + Ая1...,гГ' =\¥- Т.

¿=1

3.6. В регулярной несимметричной сети, имеющей один аттрактор, при любом IV > Г предельное состояние единственно.

Если сеть имеет более одного потенциального аттрактора, ее предельное состояние не единственно. Распределение ресурса по потенциальным аттракторам зависит от начального состояния сети. Ресурс в остальных вершинах в предельном состоянии одинаков для любого \¥> Т.

Семейство сетей, соответствующих одной стохастической матрице. Любой матрице пропускной способности Я соответствует единственная матрица Я':

Г\\ г\2 Г2\ г22

гп\ гп2

\

Пп

Г2П

ги г\2 г\п

ои1 „оШ ОШ

'1 . п П.

гп 1 г„2 Г ' пп

ои!

*п г п С )

С другой стороны, одной стохастической матрице Л' соответствует бесконечное множество матриц пропускных способностей Я, поскольку пропорциональное изменение строк матрицы 7? инвариантно относительно Я'.

Инвариантность относительно Я' задает отношение эквивалентности на множестве матриц пропускной способности. Семейство матриц пропускной способности, имеющих одну и ту же стохастическую матрицу Я', обозначим через [Л']. [Л/], / = 1,2, ... — классы эквивалентности на множестве матриц пропускной

способности. Все сети семейства [Л/] при Ж = 1 имеют один и тот

же вектор предельного состояния из формулы (1) следует, что

предельный вектор $ при IV < Т также одинаков для всех сетей из класса [Л/].

Рассмотрим сеть с одним аттрактором. Не нарушая общности, будем считать, что аттрактор имеет номер 1. Справедлива следующая теорема.

Теорема 3.3. В несимметричной регулярной сети, обладающей единственным аттрактором V,:

1) компоненты вектора 0 = , соответствующего

суммарному ресурсу IV = Т, находятся по формуле:

2) пороговое значение ресурса Т = -^—р .

Сформулируем критерий аттрактивности вершины.

Теорема 3.4 (об аттракторах). Вершина Vj

несимметричной регулярной сети является потенциальным

out

аттрактором, если и только если / = arg min .

Замечание. Непосредственно из доказательства теоремы следует, что пороговое значение Т находится по формуле rout

Т= min -^-р.

ie{l,...,n} q)

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

Теорема 3.5 (о предельном состоянии). Значения компонент вектора предельного состояния

Q ={с!\ > •••> <?«) регулярной несимметричной ресурсной сети определяются по следующим формулам:

out

I. При W< Т, q* =q)* -W , где Т= min

/е! 1,--.,»} q)

2. При IV > Т ресурс во всех не-аттракторах рассчитывается по формуле: д* = д'* • 7, г ^ где ]к - номера потенциальных

rout

аттракторов, определяющиеся из условия: /. =arg min

ie{l,...,n} gj*

Оставшийся ресурс распределяется между потенциальными аттракторами.

Таким образом, вектор Q* определяется тремя параметрами:

1) суммарным ресурсом W;

2) вектором предельных вероятностей цепи Маркова

3) суммарными выходными пропускными способностями потенциальных аттракторов: г°ш.

При W<T предельное состояние единственно. При IV> Т становится существенным деление вершин на потенциальные аттракторы и множество остальных вершин. Количество ресурса в аттракторах в предельном состоянии зависит от его начального распределения. Все не-атгракторы получают фиксированное количество ресурса q* = qt = qf ■ Т .

Аналогично теореме о предельном состоянии формулируется теорема о предельном потоке.

Теорема 3.6 (о предельном потоке). В регулярной несимметричной ресурсной сети предельный поток определен однозначно при любом значении W:

out

Х.При W< Т fi"* = f°w* = q]*W , где Г = min .

2. При W>T ff"* = ff""* = ql*T.

Теорема о предельном потоке показывает, что поток задан однозначно для всех значений суммарного ресурса И7.

Для частного случая - сети с одним источником и одним приемником — получены формулы предельного состояния при больших и малых ресурсах и порогового значения Т как функции от пропускных способностей сети.

Построение матрицы Я с произвольным количеством аттракторов по заданной матрице Я\ Рассмотрим регулярную несимметричную сеть с матрицей пропускных способностей Я. Пусть Vj - ее единственный аттрактор. Матрице Я соответствует стохастическая матрица Я', задающая семейство [Л']. Чтобы некоторая вершина ук также стала аттрактором, ее выходные пропускные способности нужно пропорционально уменьшить так, чтобы выполнилось соотношение:

1*

.ом _ Чк „ом к Г) '

При фиксированных строках матрицы Я, кроме выделенной строки с номером к, изменяя значение гЦш в полуинтервале

\*

получим, что при любом значении г£ш >—т^г°'"

4}

Я/

вершина V,- - единственный аттрактор, и только в одной точке сеть имеет два аттрактора.

Аналогично, можно, изменяя / строк, получить сеть с / аттракторами. Таким образом, при фиксированной строке ),

и-1

соответствующей аттрактору, существует Х^-п-1 =2""' -1 матриц,

ы

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

Отсюда следует, что теорема о предельном состоянии определяет его однозначно почти всегда за исключением указанного конечного множества.

Четвертая глава посвящена описанию свойств эйлеровых сетей. В них для каждой вершины выполняется равенство г1" = г"1" , и, следовательно, все вершины нейтральны.

В регулярной эйлеровой сети Т = г5ит. Из доказательства этого факта следует истинность ряда утверждений:

4.1. В эйлеровой сети Q = (r°l", ...,г°"'), где Q - вектор предельного состояния при IV= Т.

4.2. Если V, е 2~(0), то V ? > О V, е 2~(г). (Это означает, что зона 2 '(0) в процессе функционирования сети не может расширяться.)

4.3. Если IV> Т, предельное состояние существует (существование предельного состояния при IV < Т для всех регулярных сетей было доказано в главе 2).

4.4. Если IV> Т, для каждой вершины из зоны 2~(0) в

предельном состоянии выполнится: q*k = г™".

4.5. Любая вершина в эйлеровой сети является потенциальным аттрактором: при IV> гтт существует такое начальное состояние, из которого она может оказаться в зоне 2+*.

4.6. Все аттракторы эйлеровой сети пассивны: вершина может удержаться в зоне 2+(/), но не может туда перейти.

4.7. При IV > г5ит некоторые из вершин, принадлежащих зоне 2+(0) могут оказаться в 2~(() и, соответственно, на границе 2~ .

Для квазисимметричной сети, заданной матрицей Я, на рис. 3 приведены два примера ее функционирования. Поведение сети изменяется в зависимости от величины суммарного ресурса IV: а) ресурс меньше порогового значения — в сети происходят затухающие колебания, Ь) ресурс больше порогового значения — вершина у2 остается в зоне 2+*, вершина V; покидает зону 2'(/) за первые пять тактов. Начиная с этого момента ресурс во всех вершинах изменяется монотонно.

1 50 1 1 1

1 2 50 1 1

1 1 3 50 1

1 1 1 4 50

50 1 1 1 5

Рис. 3. Функционирование квазисимметричной сети: 'a) W= 50 < Т, 6(0) = (50, 0, 0, 0, 0), Ь) W= 285 > Т, 6(0) = (205, 100, 0, 0, 0).

Предельное состояние сети при fV= 1 и W<T. Распределение ресурса в вершинах эйлеровых сетей в процессе их функционирования может быть весьма разнообразным - изменение количества ресурса в вершинах может происходить монотонно и немонотонно. Существование предельного состояния при малых ресурсах было доказано для любой регулярной сети, но для эйлеровых сетей вектор предельного состояния выражается только через пропускные способности.

Утверждение 4.1. В регулярной эйлеровой сети вектор предельного состояния при W= 1 имеет вид:

nut

< fOllt

Г

V, sum

Для любого ресурса IV <Т предельное состояние можно найти непосредственно из матрицы Я и значения ресурса IV:

Q =

Г

\ sum

-w,

-W

Функционирование эйлеровой сети при IV > Т. Если при 1¥> Т в начальном состоянии в зоне 2'(0) находятся т вершин с номерами от 1 до т, то вектор начального состояния О(О) можно представить в следующем виде:

е(0)=4г +с,(0),...,с' -¿/„,+1(0),...,С' -4,(0)).

Величины С](0), ..., ст(0) > 0 назовем начальными профицитами вершин; величины <4+,(0), ..., с/„(0) > 0 - начальными дефицитами.

25

с5мт(0) = dswn (0) = ^ ¿/ДО) - суммарные начальные

7=1 j=m+\

профицит и дефицит.

На любом такте t> 0 дефицит и профицит связаны соотношением:

csum(t) - dslim(t) = const = W-rsum.

Вектор предельного состояния при W> Т имеет вид:

Q* ={гГ +c*m,r%,,-.,гГ),где сх,...,ст >0.

Предельные состояния и потоки при больших ресурсах. Для

потоков в эйлеровой сети с |Z+(0)| = т выполняется соотношение: F"(/+l) = F°,"{Q)P,R', где

Р =

Ех К

о, R.'г

, Ei - единичная матрица размера /их/и, Oi -

нулевая матрица (п-т)хт, Я12 - блоки стохастической матрицы

размеров тх(п-т) и (п-т)х(п-т) соответственно. Предел степеней матрицы Р существует и находится по формуле:

рсо _

О,

\(е2 -^2Г

On

Е2 - единичная матрица (п-т)х(п-т).

Прямоугольную матрицу [rx(e2 -¿¡J"'] обозначим через Rc.

Для нее выполняется равенство: (г™',...,г°м)Яс =(г™и...,г™'). С

помощью этой матрицы вычисляются предельные состояния при произвольном начальном состоянии.

Для произвольного начального состояния (3(0) минимальные значения профицитов в каждой вершине из зоны Z+(0), при которых

они не перейдут в зону обозначим через с/" / = 1т.

Теорема 4.4 (о предельном состоянии). Пусть в эйлеровой сети с произвольным начальный состоянием при \У> Т

6(0 )4г +с\(®)т--У,п" +ст(0),с+\ -</т+1( 0),...,Се -¿„(.о))

первые m вершин упорядочены по убыванию отношения Д = .

с/"

Значения с"', i = 1, ..., m,рассчитываются по формуле:

п-т

~т__ont

Ci

■ т = гш У гса ■ i = 1 m i i jLÊ 'ijU-m+j ' ' i,

7=1

"'+7 out

rm+j

dm_+Ji 0) r.

где am+j , j= 1, ..„«-m.

Предельное состояние при условии, что с,(0) > с™ V / = 1, ..., т, описывается вектором:

<2* 4г' + С](0) — с{",...,г™' + ст(0) — с™, С'„ -У:")- (2)

Если для вершины ут е 2+(0) ст(0) < с™, то значение т уменьшается на к, и за новое начальное состояние принимается вектор:

а,еи№)=(>г'+с. ..., с* + т-Ртс%.к, ,

т Л т Гс1

С. -¿„(о,

,=1 х 4 м х г?

7=1 7=1 ^

где значение к равно количеству вершин, для которых

Рт-к+\ = - = Рт-

Величина т и начачьное состояние пересчитывается до тех пор, пока все разности с,(0) — с;ш не станут неотрицательными. Предельное состояние описывается формулой (2).

В пятой главе исследуются циклические эргодические сети. Пусть в циклической сети ресурс, меньший минимальной пропускной способности ребер, находится в начальном состоянии в одной из вершин. Тогда на каждом такте множество вершин с ненулевым ресурсом будет изменяться. Вершины, имеющие ресурс на одном и том же такте I, называются циклическим классом. Количество циклических классов с/ равно НОД длин всех циклов сети. Сеть, состоящую из с! циклических классов, будем называть

27

Ациклической сетью. При малых ресурсах в сети происходят незатухающие колебания между с1 последовательными предельными векторами. Однако для выделенного класса начальных состояний эти векторы совпадают, и сеть приходит к глобальному равновесию (устойчивому состоянию).

На рис. 4 изображена сеть с двумя циклическими классами {уь у4, у5} и {у2, Уз}, заданная матрицей Я.

Я =

Рис. 4. Циклическая сеть, заданная матрицей Я

Для этой сети бесконечные колебательные процессы при 2(0) = (1,0, 0, 0, 0) представлены на рис. 5 а), достижение равновесного состояния при 0(0) = (1, 1, 0, 0, 0) представлено на рис. рис. 5 Ь).

0 1 0 0 0

2 0 0 2 0

0 0 0 2 3

0 2 1 0 0

0 0 2 0 0

Рис. 5. Функционирование циклической сети: а) 0(0) = (1, 0, 0, 0, 0), Ь) 6(0) = (1, 1, 0, 0, 0)

Последовательность степеней стохастической матрицы с1-циклической ресурсной сети Я\ Я'2, ..., Я"1, В"я\ ... состоит из с]

" Г>' °° п

сходящихся подпоследовательностей с пределами л, , ..., , которые выражаются через одну предельную матрицу Я^: Я~=Я^Я, Я?=Я?Я2, ... ЯХл = , где В? - предел

тс/ г>|2</ гхЗ^

последовательности: К ,Я ,Я ,...

Для предельных матриц и векторов ¿/-циклических сетей имеет место ряд утверждений, вытекающих непосредственно из результатов, полученных для циклических цепей Маркова. Приведем основные из них.

Утверждение 5.3. В эргодической с1-циклической ресурсной сети, функционирующей по правилу 2, существует предельный цикл длины <1, состоящий из предельных векторов

£>*, ..., О*/, определяемых по формулам: 2*=(, 02 = , ... £)*, = £>(0)Я'Х, где Я?- предел степеней

стохастической матрицы, кратных с/.

Утверждение 5.5. Предельные векторы эргодической с1-циклической сети , ..., являются собственными векторами матрицы Я^' , соответствующими собственному числу Л = 1 кратности с1.

Последовательность степеней Я'к суммируема по Чезаро к матрице А (Дж.Кемени, Дж.Снелл. Конечные цепи Маркова, М., Наука, 1970. С. 132):

А= Пт-^=-(Е + Я+...+Яс1-1)ВУ (3)

к j=l с/

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

Теорема 5.1. В эргодической с1-циклической ресурсной сети, функционирующей по правилу 2, начиная с некоторого момента

предельные векторы (9*, ..., совпадают тогда и только тогда, когда в каждом из циклических классов при Г = ( находится

IV

одинаковое количество ресурса —. Вектор предельного состояния

с1

равен Щ21*, где 01* - любая строка матрицы А, формула (3).

Пороговое значение Т и функционирование сети при IV > Т.

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

предельное состояние Q*\ q{ = Q*d =Q*. При больших ресурсах циклические сети ведут себя как регулярные.

Теорема 5.2. В эргодической d-циклической ресурсной сети существует единственное пороговое значение Т, такое, что:

при W< Т все вершины за конечное число тактов переходят на правило 2, и в сети имеется d предельных векторов;

при W> Тхотя бы один потенциальный аттрактор за конечное число тактов переходит на правило 1. Предельный поток существует и единствен. Предельное состояние существует; единственно оно в том и только в том случае, когда сеть имеет один аттрактор.

Теорема 5.3. В эргодической d-циклической ресурсной сети вершина Vj является потенциальным аттрактором, если и только

rout

если /'= arg min , где вектор Q'* определяется по формуле

/е{1,...,я} gi

(4)

" m=l

векторы Qlm (т = 0, ..., d) - предельные векторы при IV = 1 и произвольном начальном состоянии.

Теорема 5.4 (о предельном состоянии). В эргодической d-циклической ресурсной сети при IV > Т значения неаттрактивных компонент вектора предельного состояния

Q = (i/i,..., <у„) вычисляются по формуле

q* = qx* ■ J, где:

1) ' Jk, jk ~ номера потенциальных аттракторов,

гош

определяющиеся из условия: jk= arg min -L-р,

/е}1,...,«} q)

2) вектор Q1* определяется по формуле (4),

out

Ъ)Т= min -Ц—,

/б{1....,и} q}

Оставшийся ресурс распределяется между потенциальными аттракторами.

Теорема 5.5 (о предельном п о т о к е). В эргодической ¿циклической ресурсной сети при W>T предельный поток существует и единствен и определяется по формуле:

fin* /•out* „l*rr . 777/7* T?OUt* W*^ Рл Л

fi =Ji =4iT>F =Fi =Q T = Q,zde

1) вектор Q1* определяется по формуле (4),

out

2) T = min .

/е{1,..., и} q)

Шестая глава посвящена исследованию потоков и предельных состояний в поглощающих сетях. Матрицу R поглощающей сети с / стоками, имеющими номера от 1 до /, можно представить в виде блочной матрицы:

R =

D о,

r2

, где D — диагональная матрица размера 1x1 с

произвольными неотрицательными диагональными элементами, равными пропускным способностям петель в стоках, 0\ — нулевая матрица размера / х (п - Г), R^ - матрица размера (п -/) х /, иЛ2-квадратная матрица (и — I) х(п — Г).

Стохастическая матрица Л', соответствующая такой матрице Я, будет иметь вид

(ЕХ

U r2

Поглощающие сети с единственным предельным состоянием. Рассмотрим сеть, для матрицы которой выполняется условие: гапк = 1. Введем обозначение: R\ = Н. Для таких сетей предельное состояние не зависит от начального и справедлива следующая теорема.

Теорема 6.1. В поглощающей сети с матрицей

R =

D o,

H Ri

в которой rank Н= 1, для любого начального

состояния (2(0) = (^i(O), ..., q„(0)) выполнится: ' hm h'"

л

где W~ - , h'J - сумма j-го столбца матрицы Н, hsum -

/=/+1

сумма всех элементов матрицы Н.

Поглощающие сети общего вида. Пороговое значение Т.

В регулярных сетях при W<T все вершины за конечное число шагов переходят на правило 2, предельное состояние единственно. В поглощающей сети с произвольной матрицей пропускной способности предельное состояние не единственно ни при каком значении суммарного ресурса, за исключением случая rank Н = 1, когда оно единственно при всех значениях ресурса.

Теорема 6.2. В поглощающей сети порогового значения ресурса Т не существует.

Замечание. В поглощающих сетях коэффициент

j r°ut симметричности х =-> гДе ^ = miQ "ИТ" > обращается в нуль

rsum ...,»} q.

на стоках без петель (петли в стоках не влияют функционирование сети и предельное состояние, и поэтому ими можно пренебречь). Для всех регулярных сетей %6 (0> !]• В поглощающих сетях значение % = 0, что соответствует «полностью несимметричной» сети.

В поглощающей сети с / стоками предел последовательности степеней Rk существует и определяется по формуле:

где Е2 - единичная матрица размера (п - Г) х (и - Г).

Теорема 63. В поглощающей сети с I стоками матрица Я.'Г остается неизменной при любых изменениях диагональных элементов матрицы Я.

Теорема 6.4. В поглощающей сети с I стоками для любого ресурса IV и любого начального состояния £)(0) = (¿^(О), ..., цпЩ) предельное состояние рассчитывается по формуле:

где R'x - предельная матрица, определяемая по формуле (5).

(5)

е*=2(0)д|=о,

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

произведения таких матриц существует и равен Я'* (формула (5)).

*

Следствие 6.1. Вектор предельного состояния Q не зависит от наличия или отсутствия петель в вершинах.

Следствие 6.2. В поглощающей сети с I стоками элементы 1-й строки матрицы Я'х (/ > /) соответственно равны компонентам вектора предельного состояния при начальном состоянии 0,(0) = (0, ..., 0, 1, 0,..., 0), где единице равна 1-я компонента:

/ т '

е\

е1

qI 1 i:

(в\, ...,е/- первые I вектор-столбцов единичной матрицы Епхп).

В седьмой главе рассматриваются сети, в которых можно ставить и решать задачи управления; формулируются прямая и обратная задачи управления. Для того чтобы в некоторой ресурсной сети можно было поставить задачу управления, необходимо, чтобы предельное состояние в сети зависело от начального. При этом в сети должны быть активные аттракторы - пассивные аттракторы не могут притягивать ресурс. Этим условиям удовлетворяют поглощающие сети с rank Я, > 1 (при любом значении ресурса) и несимметричные сети с несколькими аттракторами при W> Т.

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

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

1. Прямая задача управления: распределение фиксированного суммарного ресурса между стоками. Зная матрицу Я'х и используя свойство линейности оператора перехода в предельное состояние, можно задать начальное состояние, при котором решение будет иметь минимальное расстояние до целевого в евклидовом пространстве. Задача управления формулируется в виде задачи оптимизации:

и-/

■ 5>.-=1.

ы

х1 >0.

/

где У; > 0, / = 1, ..., /; = 1, П '■ Уг'- ■■■ '■ у,I - целевая пропорция

7=1

распределения ресурса \¥в стоковых компонентах; : хг: ... •.хп.1-искомая пропорция распределения ресурса IV в переходных

вершинах, = {е2 - блок матрицы Я" (формула (5)).

Это задача квадратичного программирования. Доказано, что целевая функция выпукла. Задача может быть решена обобщенным методом множителей Лагранжа с ограничением на

неотрицательность переменных, если матрица Я™^ имеет ранг,

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

2. Обратная задача: достижение заданной величины ресурса в одном или нескольких стоках при минимачьном суммарном ресурсе. Если управление ресурсом происходит в одном из / стоков сети, такая задача всегда имеет точное решение. Для того чтобы стоковая вершина V/ (/ < I) получила нужное количество ресурса при

34

минимальном суммарном ресурсе, нужно выбрать переходную вершину у, (/' > Г), такую, что из всех стоков она отдает в вершину v, наибольшее количество ресурса, т.е. должно выполниться условие:

'ос __'а>

rpass ji ~ , , , rpass ki •

ке{п-/+1.....и}

*

Пусть q{ — количество ресурса, которое должен получить сток с номером / в предельном состоянии. Тогда общее количество

ресурса, которое в начальном состоянии должно находиться в

*

переходной вершине у,-, будет равно —. Поскольку весь ресурс

v

pass ji

в начальном состоянии должен быть сосредоточен в у,, выполняется *

равенство: W— —. Эта величина суммарного ресурса к

'pass ji

*

минимальна для заданного значения qi.

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

Управление в несимметричных сетях. Исследование несимметричных сетей с несколькими аттракторами показало, что управлять в них можно не всем ресурсом, а лишь его излишком AIV= W—Т. Доказано, что распределение ресурса сверх порогового значения AWпроисходит в соответствии с тем же законом, что и в поглощающей сети, полученной из несимметричной удалением выходных ребер аттракторов. Однако существует поправка на регулярность SW, зависящая от пропускных способностей выходных ребер аттракторов и начального распределения ресурса. Стохастическую матрицу поглощающей сети, полученную из R' заменой строк, соответствующих аттракторам, нулевыми вектор-

строками, обозначим R'afagrf) , предел ее степеней - R'™bsorb .

Поправки при разных значениях ресурса и максимальные поправки, которые возникают, когда ресурс сосредоточен в одном источнике, описаны в теореме 7.1.

Теорема 7.1. Пусть в регулярной несимметричной сети с I аттракторами ..., V/, ресурс \У> Т в начальном состоянии находится в источнике V,, у > /. Тогда вектор предельного состояния равен

е + (0, 0,..., О), при №<Т + (ЯГт-Ж_т)

£+(щЛ,...,щ\о,...,о), при т+(шт-ш_т)<№<т+т йнщ +га1тгЬ]Х-Ш, ...,Щ+га1огЬГЫУ, 0,...,0),

при \У>Т + Ш

Q

где вектор (О, ..., W-T, О, ...,0) имеет ненулевую компоненту с номером т<1;т находится из условия т = arg max r^sorb k ;

О < 5Wj < 5W;• - поправки при T+ (5Wm - SW.m) < IV< T+ SIV; 5Wm = max SWk - поправка, соответствующая аттрактору v,„;

SfV_m = max SlVk - вторая no величине поправка при ресурсе,

сконцентрированном в источнике v,;

Ш = ; AW = W-(T + 3V); /=1

причем существует аттрактор v„ для которого SfVj = О, / < I.

Описаны переходные процессы, происходящие в несимметричных сетях. Каждый скачок в сети, при котором один из аттракторов изменяет правило функционирования, ведет к накоплению величины SWj в нем.

Существуют начальные состояния, при которых поправки не накапливаются. Эти состояния описываются теоремами 7.2-7.3.

Теорема 7.2. Пусть регулярная несимметричная ресурсная сеть с I потенциальными аттракторами (/ > 1) имеет суммарный ресурс W> Т, и начальное ее состояние Q(0) представимо в виде:

<2(0) = Q + Д0(О) > где Q - предельное состояние при W = Т, AQ(0) — вектор распределения излишков ресурса W — Т. Тогда предельное состояние представимо в виде суммы двух векторов:

Q = ß + Aß(0)Ä'

,GO

absorb •

Теорема 7.3. Пусть в регулярной несимметричной ресурсной сети с I потенциальными аттракторами с номерами 1, ..., / и к источниками с номерами 1+1, ..., 1+к, начальное состояние задано вектором:

<2(0) = ¡91(0),... ,9/(0), дм +Д Щ+1 +Щ+ь...,Чм +Щ+к 0))

где величины = £ (/' = Ж' ...,1+к) -

/е{1,...,/,/+*+1,...,л} ГI"

необходимые минимальные излишки в каждом источнике, г'" -суммарная входная пропускная способность вершин из 2 (0) по ребрам из вершин-источников, ¿/,(0) - дефициты всех вершин из Г{Ъ)\ 1=1,...,/, /+А+1. м, Дбу > 0 = /+1,..., /+*. Тогда предельное состояние представимо в виде:

о*=й+щ-к:,,о,-,,,

где Л0 - вектор длины п с ненулевыми компонентами Л<2у (/ = /+1,...,/+*).

Поправки находятся по теореме 7.4.

Теорема 1 А. Пусть в регулярной несимметричной ресурсной сети с I потенциальными аттракторами (I > 1), имеющими номера 1,...,/, суммарный ресурс 1¥>Т+ Л Г/О) (д^(0) > Ш) в

начальном состоянии находится в вершине-источнике v]■. Тогда

предельное состояние представимо в виде:

ё=в+лдл'^чт, т,..., т, о,..., о),

ненулевая компонента имеет

1

где Aß = ß(0)- 0,...,0,Х^Д-,0

V »=1 номер j.

При этом для аттрактора с номером /0 = arg min r'^bsorb ¡k

M1...../}

выполняется: 8W, = 0, а остальные значения ЗУ/ находятся по 'о

формуле:

Щ = (ч* ~ С") - (<7/„ - С) .

'absorb jl0

Полученные результаты показывают, что управление ресурсом в несимметричных сетях сложнее, чем в поглощающих. Оно сводится к управлению излишком ДIV= IV- Т, с учетом указанных ограничений на возникновение поправок.

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

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

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

На каждом такте дискретного времени / ресурс, имеющийся в вершине, передается в ребра по правилам 1, 2.

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

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

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

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

2. Для изменения инерционности системы отдельно увеличивается или уменьшается пропускная способность петель.

Чем пропускная способность петли больше, тем больше ресурса остается в вершине. В терминах модели это означает, что большая часть вещества не покидает заданную площадь, и перераспределение происходит небольшими порциями.

Программная реализация модели. На рис. 6 представлены данные о выбросе, распределенные в узлах сетки 10x10 (количество узлов по горизонтали и вертикали можно задавать произвольно).

координата правого верхнегоynia. х =: 30 30;

= 30 iJ 30 i 30

Ф Минуты секунды )десятичные координаты

Сетка

строк: m = 10 ЕЗ Показать вершины

столбцов: п = 10 | [3 Показать сетку

Текущие координаты х = 15.46231

у = 23 1S256

GD Задать течение

Направление. Скорость ¡О 1.00 ЩШ V

Ветер

Направление: ЮЗ - ■Щ

Сипа ветра. 2 00 [м/с

Непроницаемая граница

ГЗ восток £3 запад Г] север [j сг [ Применить

Редактировать данные

Закрыть

Рис. б. Интерфейс программы с введенными данными о выбросе

Результатом работы модели является таблица с последовательностью векторов состояний сети на каждом такте. Этот результат программа конвертирует в файл Excel и в текстовый документ.

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

Для каждого такта программа рисует изолинии распространения вещества в автоматическом режиме.

Рис. 7. Изолинии для t = 100

В системе построения изолиний Surfer написан скрипт, позволяющий анимировать распространение вещества и проследить за ним в динамике.

2. Программа «ресурсная сеть». Для исследования ресурсных сетей написана программа, имитирующая функционирование сети, заданной матрицей пропускных способностей. Входные данные -матрица пропускных способностей и вектор начального состояния, выходные данные - протокол работы сети и предельное состояние. Точность вычислений, количество знаков после запятой в результате и максимальное число итераций - параметры, настраиваемые пользователем. Результаты выдаются на экран, и при этом автоматически заносятся в текстовый файл и файл Excel. Все описанные в работе примеры рассчитаны с помощью данной программы.

В заключении приведены результаты работы:

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

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

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

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

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

6. Описаны колебательные процессы в циклических сетях при малых ресурсах, найдены (1 предельных векторов в (/-циклической сети и ее предельные матрицы. Найден класс начальных состояний, при которых существует глобальное равновесие; найден вектор равновесного состояния. При больших ресурсах доказано, что циклическая сеть приобретает свойства регулярной сети, и предельное состояние и поток в ней всегда существуют.

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

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

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

9. Разработан программный инструмент для экспериментальных исследований ресурсных сетей.

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

11. Два указанных программных продукта защищены свидетельствами о регистрации программ для ЭВМ. Модель распространения загрязняющих веществ в водной среде внедрена в ФГУП АзНИИРХ, что подтверждено актом о внедрении.

Список публикаций по теме диссертации

Публикации в изданиях из перечня ВАК РФ российских рецензируемых научных журналов:

1. Кузнецов О.П., Житкова Л.Ю. Двусторонние ресурсные сети -новая потоковая модель // Доклады Академии Наук, 2010, том 433, №5.-С. 609-612.

2. Кузнецов О.П., Жилякова Л.Ю. Полные двусторонние ресурсные сети с произвольными пропускными способностями // Управление большими системами. Специальный выпуск 30.1 "Сетевые модели в управлении". М.: ИПУ РАН, 2010. -С. 640 - 664.

3. Жилякова Л.Ю. Несимметричные ресурсные сети. I. Процессы стабилизации при малых ресурсах // Автоматика и телемеханика, 2011, № 4. - С.133 - 143.

4. Жилякова Л.Ю. Применение ресурсных сетей для моделирования распространения веществ в водной среде // Проблемы управления, 2011, № 2. - С. 46 - 51.

5. Жилякова Л.Ю. Полные несимметричные ресурсные сети. Случай одного приемника. // Известия высших учебных

заведений Северо-Кавказский регион. № 4 (164) 2011 г. -С. 14-18.

6. Жилякова Л.Ю. Несимметричные ресурсные сети. II. Потоки при больших ресурсах и их стабилизация // Автоматика и телемеханика, 2012, №6. - С. 103 - 118.

7. Жилякова Л.Ю. Несимметричные ресурсные сети. III. Исследование предельных состояний // Автоматика и телемеханика, 2012, №7. - С. 67 — 77.

8. Жилякова Л.Ю. Исследование эйлеровых ресурсных сетей / Управление большими системами. Выпуск 41. М.: ИПУ РАН, 2013.-С. 28-50.

9. Жилякова Л.Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах / Управление большими системами. Выпуск 43. М.: ИПУ РАН, 2013. С. 34-54.

10. Жилякова Л.Ю. Управление предельными состояниями в поглощающих ресурсных сетях // Проблемы управления, 2013, №3.-С. 51-59.

Статьи в реферируемых международных изданиях:

11. OlegP. Kuznetsov, Ludmila Yu. Zhilyakova. Flows and Limit States in Bidirectional Resource Networks // Preprints of the 18th IF AC World Congress. Milano (Italy) August 28 - September 2, 2011. -P. 14031 - 14035.

12. Oleg P. Kuznetsov, Ludmila Yu. Zhilyakova. Nonsymmetric resource networks. The study of limit states. // Management and Production Engineering Review. Volume 2, Number 3, September 2011. -P. 33-39

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

13. Жилякова Л.Ю. Поиск в ассоциативной модели памяти // IX международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-2009. Киев, «Просвп-а», 2009. - С. 124 - 130.

14. Жилякова Л.Ю. Алгоритм построения ассоциативной ресурсной сети // X международная научно-техническая мультиконференция. Актуальные проблемы информационно-

компьютерных технологий, мехатроники и робототехники,

2009.-С. 232-236.

15. ЖиляковаЛ.Ю. Процессы изменения проводимостей в ассоциативной ресурсной сети // X международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-

2010. Киев, «Просвгта», 2010. - С. 85 - 91.

16. ЖиляковаЛ.Ю. Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ'2010. Труды конференции, том 1. М. - Физматлит, 2010. - С. 335 - 343.

17. Кузнецов О.П., ЖиляковаЛ.Ю. Исследование эргодичности ресурсных сетей с произвольной проводимостью // X международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-2010. Киев, «Просв1та», 2010. - С. 106 - 112.

18. Кузнецов О.П., Житкова Л.Ю. Ресурсные сети и их приложения в информационных технологиях. // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2011): материалы Международной научно-технической конференции. Минск, 10-12 февраля 2011. - С. 147 - 154.

19 .ЖиляковаЛ.Ю. Рекурсивный поиск в динамической ассоциативной ресурсной сети // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2011): материалы Международной научно-технической конференции. Минск, 10-12 февраля 2011. - С. 155 - 160.

20. Кузнецов О.П., ЖиляковаЛ.Ю., Губанов Д. А., Куливец С.Г. Сетевые модели: ресурсы, влияния, конфликты // Системный анализ и семиотическое моделирование: материалы первой всероссийской конференции с международным участием (SASM-2011). - Казань: Изд-во «Фэн» Академии наук РТ, 2011. - С. 225 - 232.

21. Кузнецов О.П., ЖиляковаЛ.Ю., Губанов Д.А., Куливец С.Г. Сетевые модели в социально-экономической сфере // XI международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-2011. Киев, «Просвй-а», 2011. - С. 233 - 240.

22. Жилякова Л.Ю. Ресурсная сеть как модель переноса вещества в водной среде// XI международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-2011. Киев, «Просвгга», 2011. - С. 196 - 202.

23. Жилякова Л.Ю., Кузнецов О.П. Ресурсные сети и процессы рассеяния на графах. // Теория активных систем / Труды международной научно-практической конференции (14-16 ноября 2011 г., Москва, Россия). Том 1. С. 55 — 58.

24. Жилякова Л.Ю. Дискретные модели рассеяния на графах // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2012): материалы Международной научно-технической конференции. Минск: БГУИР, 2012. -С. 71-76.

25. Жилякова Л.Ю. Модели рассеяния на графах и их приложения // XII международная конференция имени Т.А. Таран Интеллектуальный анализ информации ИАИ-2012. Киев, «Просвгга», 2012. - С. 181 - 187.

26. Жилякова Л.Ю. Механизмы структурирования информации в ассоциативной модели памяти // Пятая международная конференция по когнитивной науке. Калининград, 18-24 июня 2012 г.-С. 802-803.

27. Жилякова Л.Ю. Управление распределением ресурса в неоднородных ресурсных сетях // Тринадцатая национальная коференция по искусственному интеллекту с международным участием КИИ-2012 (16-20 октября 2012 г., г. Белгород, Россия): Труды конференции. Т. 3. - Белгород: изд-во БГТУ, 2012. -С. 48-55.

Материалы всероссийских конференций:

28. Жилякова Л.Ю. Организация памяти в ассоциативной ресурсной сети с переменной топологией // Научная сессия НИЯУ МИФИ-2010. Аннотации докладов. Том 3. М. Изд-во НИЯУ МИФИ, 2010. - С. 77.

29. Кузнецов О.П., Жилякова Л.Ю. Процессы стабилизации в динамических ресурсных сетях // Труды Научной сессии НИЯУ МИФИ-2010. В 6 томах. Том V. Информационно-телекоммуникационные системы. Проблемы информационной безопасности. М.: НИЯУ МИФИ, 2010. - С. 53 - 56.

30. Кузнецов О.П., Жилякова Л.Ю. Ресурсные сети: предельные состояния и потоки. Материалы 4-й Всероссийской мультиконференции по проблемам управления МКПУ-2011, Т.1. Таганрог: изд. ТТИ ЮФУ 2011. - С. 62 - 66.

31. Жилякова Л.Ю. Модель ассоциативной памяти, основанная на динамической ресурсной сети // 5-я Российская мультиконференция по проблемам управления (МКПУ-2012). «Управление в технических, эргатических, организационных и сетевых системах» (УТЭОСС-2012). Санкт-Петербург, 2012. -С. 1160- 1163.

32. Кузнецов О.П., Жилякова Л.Ю. Управление предельным состоянием в ресурсных сетях // 5-я Российская мультиконференция по проблемам управления (МКПУ-2012). «Управление в технических, эргатических, организационных и сетевых системах» (УТЭОСС-2012). Санкт-Петербург, 2012. -С. 1176- 1179.

Свидетельства о регистрации программ для ЭВМ

33. Жилякова Л.Ю. Свидетельство об официальной регистрации программы для ЭВМ № 2010617260 Модель распространения химических веществ и пассивных биологических объектов «Substance Spreading». Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. 2010.

34. Жилякова Л.Ю. Свидетельство об официальной регистрации программы для ЭВМ № 2010617261 Модель неоднородной ресурсной сети «Resource Distribution». Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. 2010.

Зак. 62. Тир. 100. ИПУ РАН

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА РОССИЙСКОЙ АКАДЕМИИ НАУК

УДК 519.711.74 На правах рукописи

Ми

05201351774

ЖИЛЯКОВА Людмила Юрьевна

РЕСУРСНЫЕ СЕТИ И АНАЛИЗ ИХ ДИНАМИКИ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и

автоматизации)

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

Научный консультант: д.т.н., проф. О.П. Кузнецов

Москва 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................6

ГЛАВА 1. ДИНАМИЧЕСКИЕ ГРАФОВЫЕ МОДЕЛИ....................................20

1.1. Потоковые модели..........................................................................................21

1.1.1. Классические потоковые модели...........................................................21

1.1.2. Потоки в сетях с нестандартной достижимостью................................26

1.1.3. Задачи, сводящиеся к статическим потоковым моделям....................28

1.1.4. Динамические задачи. Потоки во времени (flow over time)................29

1.2. Случайные блуждания и рассеяние на графах............................................30

1.2.1. Области применения моделей случайного блуждания.......................30

1.2.2. Конечные цепи Маркова и их классификация.....................................32

1.2.3. Графы переходов конечных цепей Маркова........................................35

1.2.4. Дискретная модель достижения консенсуса........................................36

1.2.5. Неоднородные цепи Маркова................................................................39

1.3. Целочисленные пороговые модели..............................................................40

1.3.1. Chip-firing game........................................................................................40

1.3.2. Модель «куча песка»...............................................................................46

1.3.3. Графовая интерпретация «кучи песка» и chip-firing game..................48

1.4. Ресурсная сеть.................................................................................................49

1.4.1. Основные определения...........................................................................49

1.4.2. Классификация ресурсных сетей по топологии...................................51

1.4.3. Классификация ресурсных сетей по пропускным способностям......55

1.4.4. Полные однородные ресурсные сети....................................................58

1.4.5. Ресурсная сеть и динамические графовые модели..............................63

ГЛАВА 2. МАРКОВСКИЕ ПРОЦЕССЫ В РЕГУЛЯРНЫХ РЕСУРСНЫХ СЕТЯХ. СВОЙСТВА РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЕЙ..........68

2.1. Предельное состояние регулярной сети при W= 1.....................................68

2.2. Предельное состояние регулярной сети при малых ресурсах...................70

2.3. Регулярные несимметричные сети и их свойства.......................................72

2.4. Пороговое значение Т....................................................................................81

2.5. Коэффициент симметричности сети.............................................................82

2.6. Аттракторы и их классификация..................................................................84

2.6.1. Потенциальные аттракторы....................................................................84

2.6.2. Классификация аттракторов...................................................................90

2.6.3. Признаки аттрактивности вершины......................................................90

ГЛАВА 3. ПОТОКИ И ПРЕДЕЛЬНЫЕ СОСТОЯНИЯ В РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЯХ...........................................................................97

3.1. Поток ресурса..................................................................................................97

3.1.1. Поток при Ж< Т.......................................................................................97

3.1.2. Поток при Ж> Г......................................................................................98

3.2. Семейство сетей, соответствующих одной стохастической матрице.....109

3.2.1. Матрицы с большей выходной пропускной способностью вершин-источников........................................................................................................112

3.2.2. Матрицы с большей выходной пропускной способностью вершин-приемников.......................................................................................................112

3.2.3. Матрицы с другой вершиной-приемником........................................114

1 *

3.3. Вектор и пороговое значение Т............................................................116

3.4. Свойство аттрактивности и предельное состояние сети..........................117

3.5. Построение матрицы Я с произвольным количеством аттракторов по заданной матрице ............................................................................................121

3.6. Оценка числа сетей с неединственным аттрактором................................124

3.7. Полная сеть с одним приемником и одним источником..........................125

ГЛАВА 4. РЕГУЛЯРНЫЕ ЭЙЛЕРОВЫ СЕТИ................................................130

4.1. Существование предельного состояния и пороговое значение Т...........130

4.2. Свойства эйлеровых сетей...........................................................................132

4.3. Предельное состояние сети при 1 и Ж<Т.........................................134

4.4. Функционирование сети при \¥> Т............................................................137

4.5. Предельные состояния и потоки при больших ресурсах.........................138

4.5.1. Предельное состояние сети при неизменной зоне ....................138

4.5.2. Предельное состояние эйлеровой сети. Общий случай....................141

4.5.3. Предельные потоки при W> Ти задача нахождения вектора Ст

(случай отсутствия ресурса в зоне Z~(0))......................................................144

4.5.4. Задача нахождения вектора Ст (случай стационарной зоны Z^it)) 150

4.5.5. Задача нахождения вектора Ст (общий случай)...............................153

ГЛАВА 5. ЭРГОДИЧЕСКИЕ ЦИКЛИЧЕСКИЕ СЕТИ...................................164

5.1. Элементарные циклы и их свойства...........................................................165

5.2. Функционирование произвольных циклических сетей при малом ресурсе ................................................................................................................................180

5.2.1. Функционирование циклической сети при W- 1..............................181

5.2.2. Предельные векторы и циклы ¿/-циклической сети...........................185

5.2.3. Достижение глобального равновесия при малых ресурсах..............189

5.3. Пороговое значение Г и функционирование циклических сетей при больших ресурсах................................................................................................195

5.3.1. Пороговое значение Т...........................................................................195

5.3.2. Критерий аттрактивности и потенциальные аттракторы..................197

5.3.3. Предельное состояние и предельный поток при больших ресурсах 198 ГЛАВА 6. ПОГЛОЩАЮЩИЕ СЕТИ...............................................................203

6.1. Свойства поглощающих ресурсных сетей.................................................203

6.2. Поглощающие сети с единственным предельным состоянием...............207

6.3. Поглощающие сети общего вида. Пороговое значение Т........................210

6.4. Предельные состояния в поглощающих сетях..........................................213

6.4.1. Матрица /?|С0 и ее свойства....................................................................213

6.4.2. Вектор предельного состояния и его свойства...................................217

6.4.3. Нелинейное изменение промежуточных состояний..........................220

ГЛАВА 7. УПРАВЛЕНИЕ В РЕСУРСНЫХ СЕТЯХ.......................................225

7.1. Управление в поглощающих сетях.............................................................225

7.1.1. Прямая задача управления. Распределение фиксированного суммарного ресурса между стоками..............................................................226

7.1.2. Обратная задача управления. Достижение заданной величины ресурса в одном или нескольких стоках при минимальном суммарном

ресурсе..............................................................................................................230

7.2. Управление в несимметричных сетях........................................................232

7.2.1. Поглощающая сеть, соответствующая несимметричной, и поправка на регулярность 5W.........................................................................................233

7.2.2. Зависимость 5W от выходных пропускных способностей аттракторов ...........................................................................................................................244

7.2.3. Нелинейные переходы при функционировании сети и неоднородная цепь Маркова...................................................................................................246

7.2.4. Предельное состояние сети при fsum(t) > Т..........................................249

7.2.5. Начальные состояния, не создающие поправку.................................250

7.2.6. Оценка поправки 5W.............................................................................253

7.2.7. Управление ресурсом в потенциальных аттракторах........................256

ГЛАВА 8. ПРАКТИЧЕСКИЕ ПРИЛОЖЕНИЯ И ИХ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.....................................................................................................259

8.1. Модель распространения вещества в водной среде, основанная на ресурсной сети.....................................................................................................259

8.1.1. Анализ существующих подходов и описание модели......................259

8.1.2. Топология и правила функционирования ресурсной сети................261

8.1.3. Расчет перетоков между районами......................................................263

8.1.4. Начальное распределение ресурса по узлам сетки............................265

8.1.5. Управляющие параметры модели........................................................266

8.1.6. Программная реализация модели........................................................267

8.1.7. Условия применения и возможное расширение модели...................275

8.2. Программа «Ресурсная сеть».......................................................................275

ЗАКЛЮЧЕНИЕ....................................................................................................280

ЛИТЕРАТУРА.....................................................................................................283

ПРИЛОЖЕНИЕ....................................................................................................302

ВВЕДЕНИЕ

В работе исследуется новая потоковая модель, названная ресурсной сетью. Ресурсная сеть представляет собой ориентированный граф, вершины которого способны хранить неограниченное количество ресурса, а ребра обладают ограниченной пропускной способностью. На каждом такте дискретного времени происходит перераспределение ресурса между вершинами с выполнением закона сохранения. Вершины отдают ресурс в соответствии с одним из двух правил с пороговым переключением. Если вершина обладает ресурсом, большим, чем суммарная пропускная способность всех ее исходящих ребер, в каждую смежную с вершину она отдает по полной пропускной способности соответствующего ребра; если ресурса недостаточно, он отдается весь, распределяясь пропорционально пропускным способностям исходящих ребер. При наличии петли ресурс, прошедший по ней, возвращается в вершину на следующем такте. Модель параллельна: на каждом такте в перераспределении участвуют все вершины, имеющие ресурс. Если все вершины распределяют ресурс по правилу 2, функционирование сети описывается однородной цепью Маркова, если хотя бы одна вершина функционирует правилу 1, вектор, описывающий состояния системы, изменяется нелинейно. В зависимости от топологии, пропускных способностей и количества ресурса сети демонстрируют принципиально разное поведение. Произведена классификация ресурсных сетей. Исследованы устойчивые и циклические состояния и потоки для разных классов сетей.

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

состояний, при решении проблем централизованного и децентрализованного управления сложными системами, задач распределения нагрузки в электрических, транспортных, компьютерных, коммуникационных и других сетях, в системах обработки распределенной информации. Разнообразие предметных областей влечет за собой разнообразие применяемых моделей и методов. Основные направления развития классических графовых моделей обусловлены их применением в задачах о нахождении потоков, обладающих заданными характеристиками или удовлетворяющих критерию оптимальности по совокупности параметров. В большинстве этих задач ищутся некоторые выделенные пути на графе. Исследованием потоковых моделей занимались многие российские и зарубежные специалисты алгоритмической теории графов, среди которых Г.М. Адельсон-Вельский, Е.А. Диниц, А.В. Карзанов, А.И. Ерзин, И.И. Тахонов, Я.М. Ерусалимский, L.R. Ford, D.R. Fulkerson, J. Edmonds, R.M. Karp, E.W. Dijkstra, T.C. Hu, R.K. Ahuja, T.L. Magnanti, J.B. Orlin и другие исследователи. Принципиально иной подход используется в моделях рассеяния на графах: в них рассматриваются все возможные пути между вершинами в связном графе. Такая формулировка задач может быть названа «интегральной по путям» [158]. Алгоритмами, построенными на основе случайных блужданий, решаются задачи распределения нагрузки в электрических и компьютерных сетях, моделируется распространение мнений в социальных сетях, производится анализ значимости пользователей и сайтов Интернет (алгоритм PageRank и его модификации), решаются задачи информационного управления. Задачи анализа топологических характеристик графов, сходимости асимптотических методов, спектрального анализа матриц смежности и лапласовских матриц, получения качественных оценок конечных состояний и многие другие задачи решались в работах следующих авторов: П.Ю. Чеботарев, Р.П. Агаев, А.И. Ерзин, И.И. Тахонов, B.JI. Стефанюк, J.G. Kemeni, J.L. Snell, Ph. Blanchard, D. Volchenkov, D.J. Aldous, L. Lovâsz, P. Winkler и др. Еще один вид моделей - пороговые

целочисленные модели, в частности, игры выстреливания фишек (<chip-firing games), в которых рассеяние происходит только в тех вершинах, для которых хранимая в них величина превосходит пороговое значение. Основные результаты в исследовании этих моделей получены в работах L. Lovász, P. Winkler, N.L. Biggs, A. Björner, R.J. Anderson, P.W. Shor, J. Spencer, E. Tardos, F. Chung, R. Ellis, E. Prisner. Такими пороговыми моделями, в частности, описываются явления самоорганизующейся критичности «лавина» или «абелева куча». Эти исследования принадлежат, в основном, зарубежным авторам: Р. Bäk, С. Tang, К. Wiesenfeld, R. Cori, D. Rossin, D. Dhar, T. Sadhu, S. Chandra, E.R. Speer и др.

Функционирование ресурсных сетей, исследованных в настоящей работе, отличается от всех известных моделей. Вершины в них отдают ресурс в исходящие ребра по двум разным правилам. Выбор правила в каждой вершине обусловлен количеством содержащегося в ней ресурса. Указанные особенности расширяют область применимости сетевых моделей и позволяют имитировать нелинейные процессы; делимость ресурса обеспечивает сходимость там, где в пороговых моделях она не имела места. Моделирование сложных систем с помощью ресурсных сетей позволяет при их анализе выделять объекты предметной области, соответствующие классу аттрактивных вершин, способных аккумулировать большую часть ресурса в сети. Для классов сетей, в которых предельное состояние зависит от начального, ставятся и решаются прямая и обратная задачи управления. Именно этим обусловлена актуальность настоящей диссертационной работы.

Цель работы и задачи исследования. Основная цель работы исследование функционирования ресурсных сетей, предельных состояний (равновесных или циклических) и потоков в ресурсных сетях при любой топологии, любом количестве ресурса и его начальном распределении по вершинам, их качественных и количественных характеристик; выявление классов сетей, в которых предельные состояния существуют и зависят от начальных, постановка и решение задач управления в таких сетях.

Для достижения этой цели поставлены следующие задачи:

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

2. Определение порогового значения ресурса для каждого класса сетей, при котором некоторое множество вершин изменяет правило функционирования. Исследование процессов, происходящих в сетях в окрестности порогового значения ресурса.

3. Исследование функционирования регулярных сетей при малых ресурсах.

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

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

6. Исследование явления аттрактивности и нахождение критерия аттрактивности вершин в регулярных несимметричных сетях.

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

8. Исследование поглощающих сетей с несколькими стоками и несимметричных сетей с несколькими аттракторами.

9. Определение условий, при которых возможна постановка задачи управления в сетях. Формулировка двух задач управления.

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

Методы исследования. Для описания предельных состояний и потоков использовались методы конечных цепей Маркова, теории матриц, теории графов, спектрального анализа, исследования операций и численные методы. При исследовании предельных состояний и потоков, а также динамики переходных состояний и видов асимптотических процессов, использовалась программа, написанная в среде Visual FoxPro 9.0. Все примеры работы сети (протоколы, гистограммы, графики