Автоматика и телемеханика, № 4, 2011
Системный анализ и исследование операций
© 2011 г. Л.Ю. ЖИЛЯКОВА, канд. физ.-мат. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
НЕСИММЕТРИЧНЫЕ РЕСУРСНЫЕ СЕТИ. I. ПРОЦЕССЫ СТАБИЛИЗАЦИИ ПРИ МАЛЫХ РЕСУРСАХ
Рассматриваются процессы динамического распределения ресурсов в двусторонних несимметричных ресурсных сетях с петлями и исследуются условия их стабилизации. Показано, что при единичном суммарном ресурсе процесс перераспределения задает регулярную цепь Маркова, а вектор предельного состояния соответствует вектору предельных вероятностей и является собственным вектором стохастической матрицы, соответствующей матрице пропускной способности. Доказано, что а) при ресурсе, не превосходящем некоторого порогового значения, вектор предельного состояния также существует, единствен и пропорционален вектору предельных вероятностей; б) для любой связной сети пороговое значение суммарного ресурса существует и единственно.
1. Введение
Существует ряд прикладных задач, связанных с ресурсами в сетях, которые не могут быть формализованы в рамках классической потоковой модели Форда - Фал-керсона [1, 2] или ее динамических модификаций [3]. К таким задачам относятся управление распределением ресурса в виртуальных сетях [4], поиск в ассоциативной модели памяти [5], моделирование распространения веществ и пассивных гидро-бионтов в водной среде и другие задачи, в которых не предполагается направленного течения ресурса от источников к стокам.
Ресурсная сеть - новая потоковая модель, которая была предложена в [6]. Эта модель принципиально отличается от модели Форда - Фалкерсона и других сетевых моделей, обладающих источниками и стоками (например, [7]). Все вершины в ресурсной сети имеют одинаковый статус, и их способность удерживать ресурс определяется суммарными пропускными способностями входящих и исходящих ребер. Потоковая модель без источников и стоков предложена в [8], однако в ней за состояние принимается распределение ресурса по ребрам, а величина ресурса в каждой вершине остается постоянной. В ресурсной сети, предложенной в [6], состояние соответствует распределению ресурса в вершинах и значение ресурса в вершинах изменяется во времени. В [6] были рассмотрены полные однородные ресурсные сети, т.е. сети, представленные полными графами с одинаковыми пропускными способностями всех ребер. Целью настоящей работы является исследование свойств связных (необязательно полных) несимметричных ресурсных сетей, в частности исследование сходимости процесса перераспределения ресурса, нахождение предельных состояний при малых суммарных ресурсах, а также определение порогового значения ресурса Т, при превышении которого сеть вблизи предельного состояния изменяет правило функционирования.
2. Основные определения
1. Ресурсной сетью [6] называется двусторонний ориентированный граф, вершинам которого приписаны неотрицательные числа qj(t), называемые ресурсами и изменяющиеся в дискретном времени t, а ребрам Wj) - неотрицательные числа rjj, постоянные во времени и называемые пропускными способностями; п -число вершин графа. Свойство двусторонности означает, что если существует ребро (wj, Wj) с ненулевой пропускной способностью rjj, то обязательно существует и противоположно ориентированное ребро (г^, Wj) с ненулевой пропускной способностью rjj, причем равенство rjj = r^ в общем случае не выполняется. Двустороннюю пару будем обозначать < wj), (г^, Wj) >.
Каждая вершина обладает петлей с пропускной способностью rjj1.
2. Состоянием Q(t) сети в момент t считаем вектор Q(t) = (^i(t),..., ^„(t)), состоящий из значений ресурсов в каждой вершине.
3. Состояние Q(t) называется устойчивым, если Q(t) = Q(t + 1) = Q(t + 2) = = Q(t + 3) = ...
4. Состояние Q* = (q*,..., ) называется асимптотически достижимым из состояния Q(0), если для любого е > 0 существует te такое, что для всех t > >tek* - ®(t)| < е, i = 1, 2,..., п.
5. Состояние сети называется предельным, если оно либо устойчиво и достижимо из Q(0) за конечное время, либо асимптотически достижимо из Q(0).
6. Матрицей пропускной способности назовем матрицу R = ||г^ ||„х„. Если пары < (Wj, Wj), (wj, Wj) > не существует, то rjj =0 и r^ =0.
Из определения ресурсной сети вытекают следующие свойства матрицы R:
1) R - неотрицательная матрица: V i,j rjj > 0;
2) V i rjj > 0;
3) V ij (rjj > 0 ^ rjj > 0).
7. Суммарной пропускной способностью сети rSMm назовем сумму пропускных
„ „
способностей всех ее ребер: rSMm = Y1 2 rjj.
j=ij=i
8. Суммарную пропускную способность входных ребер вершины с номером i на-
„
зовем ее входной пропускной способностью и обозначим через rj" = ^ r^j; сум-
j=1
марную пропускную способность выходных ребер соответственно назовем выходной
„
пропускной способностью и обозначим через r°Mi = Y1 rjj. Пропускная способность
j=1
петли входит в обе суммы.
9. Распределение ресурса в сети происходит по одному из двух правил, выбор которых зависит от величины ресурса в вершинах. В момент t +1 вершина отдаст в ребро, соединяющее ее с вершиной w^:
rjfc единиц ресурса, если qj(t) > r°Mi (правило 1);
rjfc
out lift) в противном случае (правило 2). rj
„
По правилу 1 вершина отдаст за такт работы всего r°Mi = Y1 rjj ресурса. По
j=1
правилу 2 вершина отдает весь свой ресурс. Если ресурс в вершине равен выходной пропускной способности вершины: qj(t) = r°Mi, то применение правил 1 и 2 даст одинаковые результаты.
1 В [1] исследовались сети без петель.
10. Суммарный ресурс всех вершин обозначим через Ш. В сети выполняется закон сохранения: при функционировании ресурс не поступает извне и не расходуется:
п
q¿(Ь) = Ш.
¿=1
11. Ресурсная сеть называется однородной, если пропускные способности всех ребер одинаковы. В противном случае сеть называется неоднородной.
12. Ресурсная сеть называется симметричной, если симметрична ее матрица пропускной способности.
В симметричных сетях у каждой вершины входная и выходная пропускные способности совпадают. Однако конфигурации, обеспечивающие совпадение входов и выходов, не исчерпываются только симметричными сетями. Поэтому введем следующее определение:
13. Ресурсная сеть называется квазисимметричной, если
/1 \ V/ ' „¿п ^-ОиЪ
(1) V» ^ = г1 .
14. Если сеть неквазисимметричная, в ней существует хотя бы пара вершин, для которых г*п — г°и = 0. Для произвольной вершины v¿ обозначим эту разность через Д^: Дг = г*п — г°иг. Тогда все вершины сети можно разделить на три класса:
1) вершины-приемники, для которых Дr¿ > 0;
2) вершины-источники, для которых Дг < 0;
3) нейтральные вершины, для которых Дг = 0.
В симметричных и квазисимметричных сетях все вершины нейтральны.
15. Сеть будем называть несимметричной, если она не удовлетворяет условию квазисимметричности (1). Несимметричная сеть обладает как минимум одним источником и одним приемником.
Пусть среди п вершин сети имеется I вершин-приемников, к источников и п — I — к нейтральных вершин. Будем считать, что приемники имеют номера от 1 до I, источники - от I +1 до I + к, нейтральные вершины - от I + к + 1 до п.
16. Путь от нейтральной вершины к источнику, не содержащий вершин-приемников, назовем неположительным путем.
3. Свойства вершин-источников и нейтральных вершин
Свойство 1. Если для некоторого Ь' q¿(t') < г°иг, qj(Ь') < г°и4, г|п = г*п, = qj (Ь') и множества вершин, смежных v¿ и Vj, совпадают, то для всех Ь > Ь' q¿(t) = qj(Ь) (%,] > I). При таких условиях с момента Ь обе вершины отдают весь свой ресурс, а получают одинаковое количество ресурса.
Свойство 1 соответствует следующему свойству однородных сетей: если для некоторого Ь' q¿(Ь') = qj(Ь'), то для всех Ь > Ь' q¿(Ь) = qj(Ь) [6].
Свойство 2. В процессе функционирования несимметричной сети ресурс в нейтральных вершинах может временно стабилизироваться, а затем снова изменяться.
Свойство 3. Если для некоторого Ь' q¿(Ь') < г*п, то для всех Ь > Ь' q¿(Ь) < г*п (г>/).
Множество вершин, у которых q¿(Ь) < г°и4, будем называть зоной Z-(Ь), а множество вершин с q¿(Ь) > г'и - зоной Z +(Ь). Вершины из Z-(Ь) функционируют по правилу 2, а вершины из Z +(Ь) - по правилу 1.
Для вершин-источников условие q¿(Ь) < г*п сильнее условия v¿(Ь) € Z-(Ь), для нейтральных вершин эти условия равносильны. Поэтому из свойства 3 следует, что при переходе в зону Z- вершина уже никогда не покинет эту зону.
£ VI г>2 Уз г>4 г>5
0 0,000 100,000 0,000 0,000 0,000
1 2,000 95,000 1,000 1,000 1,000
2 3,000 91,000 2,000 2,000 2,000
3 3,800 87,800 2,800 2,800 2,800
18 16,406 68,598 4,999 4,999 4,999
19 17,405 67,597 4,999 4,999 4,999
20 18,405 66,597 5,000 5,000 5,000
21 19,404 65,596 5,000 5,000 5,000
22 20,404 64,596 5,000 5,000 5,000
80 78,404 6,596 5,000 5,000 5,000
81 79,404 5,596 5,000 5,000 5,000
82 80,269 4,933 4,933 4,933 4,933
83 80,873 4,782 4,782 4,782 4,782
110 82,856 4,286 4,286 4,286 4,286
111 82,857 4,286 4,286 4,286 4,286
Проиллюстрируем все три свойства следующим примером.
Пример 1. Выравнивание ресурса в вершинах 2-5 (свойство 1), временная стабилизация (свойство 2), зона Z- (свойство 3). Ш = 100, п = 5. Сеть с приемником «1 и источником «2: Г21 = 2, остальные г^- равны 1. Ресурс в источнике «2: ^(0) = = (0, 100, 0, 0, 0). Распределение ресурсов представлено в табл. 1.
Процесс распределения делится на три этапа. На первом этапе (такты 0-19) нейтральные вершины набирают ресурс до значения суммарной выходной пропускной способности: г°и4 = 5. На втором этапе (такты 20-81) в нейтральных вершинах происходит стабилизация: эти вершины сохраняют ресурс, равный г°и4, а перераспределение идет между источником и приемником. На третьем этапе (такты с 82-го) ресурс источника «2 становится меньше его выходной пропускной способности и нейтральные вершины начинают получать ресурс, который меньше, чем г°и4; ресурс в источнике становится равным ресурсу в нейтральных вершинах.
Теорема 1. В связной несимметричной сети для всех источников и нейтральных вершин, из которых имеются неположительные пути, для любого суммарного ресурса Ш и его начального 'распределения ^
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.