Автоматика и телемеханика, № 7, 2012
© 2012 г. Л.Ю. ЖИЛЯКОВА, канд. физ.-мат. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
НЕСИММЕТРИЧНЫЕ РЕСУРСНЫЕ СЕТИ. III. ИССЛЕДОВАНИЕ ПРЕДЕЛЬНЫХ СОСТОЯНИЙ1
Работа посвящена методам вычисления предельного состояния и предельного потока ресурсной сети при больших значениях ресурса. Для этого исследуются процессы распределения ресурса в семействах сетей с различными матрицами пропускной способности, соответствующими одной стохастической матрице. Пороговое значение ресурса Т, по разные стороны которого сеть функционирует по разным правилам, и координаты вектора предельного состояния для вершин-неаттракторов выражаются через параметры матрицы пропускной способности и матрицы предельных переходов цепи Маркова, соответствующей рассматриваемой стохастической матрице. При наличии в сети нескольких потенциальных аттракторов предельное количество ресурса в них зависит от начального состояния.
1. Введение
Ресурсная сеть - потоковая модель, предложенная в [1]. Сеть функционирует в дискретном времени: на каждом такте вершины принимают ресурс по входящим ребрам и отдают его по ребрам исходящим. В [2, 3] исследовались процессы стабилизации для разных значений ресурса. В [2] было показано, что при значениях ресурса, не превосходящих некоторой пороговой величины Т, функционирование связной двусторонней сети с петлями соответствует цепи Маркова и предельное состояние описывается вектором предельных вероятностей, соответствующим этой цепи. Для двусторонней сети, содержащей петли, такая цепь оказывается регулярной. Предельное состояние сети существует и единственно. Вектор предельного состояния является левым собственным вектором стохастической матрицы Я', полученной из матрицы пропускной способности Я нормированием строк, а также матрицы предельных переходов цепи Маркова (Я. Доказана теорема о существовании и единственности порогового значения Т для каждой сети.
В [3] рассматривается функционирование сети с ресурсом, большим порогового значения. В этом случае некоторые вершины сети притягивают к себе излишки ресурса; ресурс в остальных вершинах в предельном состоянии одинаков при любом сколь угодно большом ресурсе, циркулирующем в сети. Для доказательства сходимости процесса распределения ресурса при больших значениях вводится понятие потока. Поток ресурса определяется сход-
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант № 11-01-00771).
3* 67
ным образом с определением потока в модели Форда - Фалкерсона [4, 5], однако между ресурсной сетью и классическими потоковыми моделями существует ряд принципиальных различий. Во-первых, в модели Форда-Фалкерсона и ее модификациях ресурс течет от источников к стокам, тогда как в ресурсной сети направленность потока отсутствует. Во-вторых, состояние ресурсной сети определяется распределением ресурса по вершинам, а не по ребрам. В-третьих, вершины ресурсной сети обладают неограниченной емкостью и могут удерживать сколь угодно большие количества ресурса.
Работа [3] посвящена исследованию потоков при разных начальных состояниях сети. Доказано, что для любого ресурса, превышающего пороговое значение Т, предельный поток существует и равен Т. Из существования предельного потока следует и существование предельного состояния сети. Таким образом, в [2, 3] доказана стабилизация процесса перераспределения ресурса в несимметричной сети при любом суммарном ресурсе и его начальном распределении по вершинам.
Настоящая работа посвящена выводу формул для вычисления значения Т и координат вектора предельного состояния Q* при произвольной величине суммарного ресурса. Для установления зависимости этих значений от параметров сети исследуются предельные состояния семейства сетей, матрицы пропускных способностей которого соответствуют одной и той же стохастической матрице Я'.
Будем использовать определения основных понятий в области ресурсных сетей, данные в [3].
2. Семейство сетей, соответствующих одной стохастической матрице
Любой матрице пропускной способности Я соответствует единственная матрица Я':
Я =
{ Гц
г 21
Т\и \ Г2п
(
Я' =
V Г
п1
/
„оиЬ
Гп 1
\ гогЛ \ 1 п
Г\п \
„оуЛ
С другой стороны, одной стохастической матрице Я' соответствует бесконечное множество матриц пропускных способностей Я, поскольку пропорциональное изменение строк матрицы Я инвариантно относительно Я'. Так, например, матрицам Я1 и Я2 соответствует одна и та же матрица Я':
Я1 =
2 1
70
2 2
35
Я2 =
98 15 10
98 98 30 45 51
Я' =
(1 1 1
3 3 3
1 1 1
6 3 2
5 5 1
и 16 16 )
Заметим, что пропорциональное изменение г-й строки матрицы Я соответствует изменению пропускных способностей всех выходных ребер г-й вершины сети.
1
1
Г
пп
Г
пп
п
Инвариантность относительно К' задает отношение эквивалентности на множестве матриц пропускной способности Ki. Семейство матриц пропускной способности, имеющих одну и ту же стохастическую матрицу К', обозначим через [К']; [К'] - классы эквивалентности на множестве матриц пропускной способности,
Kk - Km & Kk е [К']&Кт е [К'].
Исследуем предельное распределение ресурса для различных матриц пропускной способности, соответствующих одной и той же стохастической матрице К', и влияние изменения суммарной пропускной способности на пороговое значение T.
Сначала приведем несколько примеров функционирования сетей с различными матрицами пропускной способности, соответствующими одной стохастической матрице. Эти примеры иллюстрируют влияние выбора матрицы пропускной способности Щ из заданного семейства [К'] на координаты вектора предельного состояния, величину порогового значения T, а также на способность вершины быть потенциальным аттрактором.
Все примеры рассматриваются для семейства матриц, соответствующих стохастической матрице 3 х 3:
/ 1 1 1 \
3 3 3 1 4 5 10 10 10 111
\ 3 3 3 )
К' =
Пример 1. Матрица пропускной способности:
(1)
Суммарный ресурс Ш = 1. Q(0) = (1, 0, 0). Протокол работы сети задан табл. 12. Таблица 1
t г>1 V2 г'з
0 1,000 0,000 0,000
1 0,333 0,333 0,333
2 0,256 0,356 0,389
3 0,250 0,357 0,393
4 0,250 0,357 0,393
2 Конечность таблицы не означает конечности процесса. Предельное состояние достигается асимптотически; в последующих строках первые три знака совпадают.
Полученное предельное состояние Ql* позволяет построить матрицу (Я', состоящую из трех одинаковых строк Q1*:
/ 0,25 0,357 0,393 \ (Я')~ = 0,25 0,357 0,393 .
0,25 0,357 0,393
Кортеж р = {(г!п; г'О"*) , ..., (г%П; г™*)} для этой сети будет следующим: р = {(6, 3), (9,10), (10,12)}. Сеть обладает одним приемником и двумя источниками.
При увеличении суммарного ресурса Ш координаты вектора предельного состояния будут расти пропорционально, пока Ш не достигнет порогового значения Т. Далее ресурс во всех неаттракторах стабилизируется, и накопление происходит только в аттракторе. В [3] доказано, что пороговое значение Т достигается, когда одна из вершин в предельном состоянии получает ресурс, равный своей выходной пропускной способности. Для данной сети Т ~ 12.
Пример 2. Та же матрица пропускной способности (1); Q(0) = (12, 0, 0).
Протокол работы сети - табл. 2.
Таблица 2
* г>1 г>2 1'3
0 12,000 0,000 0,000
1 10,000 1,000 1,000
2 8,433 1,733 1,833
3 7,218 2,304 2,478
4 6,274 2,748 2,978
38 3,001 4,285 4,714
39 3,000 4,286 4,714
40 3,000 4,286 4,714
Как видно из протокола, ресурс в вершине-приемнике в предельном состоянии достиг значения гО", равного 3.
При дальнейшем увеличении ресурса приемник переходит на функционирование по правилу 1, т.е. отдает по полной пропускной способности в каждое выходное ребро, оставляя излишки себе. Так, например, для суммарного ресурса Ш = 100 в этой сети предельное состояние (с точностью до трех знаков) будет: Q* = (91, 4,286, 4,714).
Таким образом, пороговое значение Т находится как сумма Т ~ 3 + 4,286 + + 4,714 = 12.
2.1. Матрицы с большей выходной пропускной способностью
вершин-источников
Исследуем изменение вектора предельного состояния для матрицы из того же семейства Я2 € [Я'], которая отличается от Я1 пропорциональным увеличением всех пропускных способностей одного из источников.
Пример 3. Третья строка матрицы Я отличается от третьей строки матрицы (1) в пять раз:
Суммарный ресурс Ш = 1. Q(0) = (1,0,0).
Протокол работы программы для суммарного ресурса Ш = 1 полностью совпадает с протоколом примера 1, см. табл. 1.
Пороговое значение Т для такой сети также равно 12.
Таким образом, из экспериментов видно, что при пропорциональном увеличении выходных пропускных способностей источников
1) вектор предельного состояния Q1*, соответствующий Ш = 1, остается неизменным,
2) пороговое значение Т остается постоянным и при его превышении ресурс во всех вершинах неаттракторах в предельном состоянии не изменяется для любого Ш > Т.
2.2. Матрицы с большей выходной пропускной способностью
вершины-приемника
Рассмотрим матрицу Яз £ [Я'], которая отличается от Я1 большей пропускной способностью приемника. Для этого в матрице (1) начнем пропорционально увеличивать пропускные способности первой вершины. Однако при увеличении выходной пропускной способности приемника следует обозначить границу, при переходе которой эта вершина перестанет быть приемником, т.е. начнет отдавать больше, чем получать.
Пример 4. Выходные пропускные способности приемника матрицы (1) увеличены вдвое:
Суммарный ресурс Ш = 1. Q(0) = (1,0,0).
Кортеж р имеет вид р = {(7, 6), (10,10), (11,12)}. Первая вершина осталась приемником, а вторая вершина из источника превратилась в нейтральную.
Протокол работы сети полностью совпал с протоколом из примеров 1, 3, см. табл. 1. Предельное распределение единичного ресурса оказалось тем же.
Однако пороговое значение, при котором в приемнике начинает происходить накопление ресурса и он переходит на правило 1, изменяется. Суммарная выходная пропускная способность вершины-приемника увеличилась вдвое. Как показывают эксперименты, при этом вдвое увеличивается и пороговое значение Т, и значения ресурсов, на которых происходит стабилиз
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.