Ресурсные сети с вентильной достижимостью

Ресурсные сети с вентильной достижимостью

Х. Абдулрахман, Я.М. Ерусалимский, В.А. Скороходов Южный федеральный университет, Ростов-на-Дону

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

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

1. Введение

Ресурсные сети введены и исследованы в работах О.П. Кузнецова и Л.Ю. Жиляковой (см., например, [1 - 5]). Ресурсная сеть - это сеть, для каждой дуги которой указана пропускная способность, а для каждой вершины - величина находящегося в ней ресурса. В каждый момент дискретного времени ресурс каждой вершины перераспределяется между смежными с ней вершинами по определённым правилам.

В работах [2-3] рассмотрены правила перераспределения ресурса между смежными вершинами и разработаны методы нахождения порогового значения в ресурсных сетях. Однако, для ресурсных сетей с ограничениями на достижимость (см. [6], [7]) задача поиска предельного распределения ресурса является более сложной, поскольку прохождение ресурса по некоторым путям в сети, существенно меняет правило для его распределения (см. [8 - 10]).

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

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

2 Эргодические ресурсные сети с вентильной достижимостью

Приведем основные определения и понятия необходимые для дальнейшего изложения (см. [1-5], [7], [10], [11]).

Определение 1. Ресурсной сетью называется ориентированная сеть 0(Х,и, /), для которой в каждый момент времени г (> 0) задана вектор-функция 0(1) = (я (г);...; яп (г)) (п =| X |). Здесь величина яг (г) > 0 V1 е [1; п]2 называется количеством ресурса в вершине хг в момент времени г, а 0(1) -состоянием сети в момент времени г.

Состояние 0(0) называется начальным распределением ресурса в сети О, а следующие состояния сети определяются из соотношения

Я

Величины Р (и, г) в соотношении (1) определяются по следующему правилу (полагаем здесь, что х1 - начальная вершина дуги и):

г (иХ д}.(г) > £ г (у);

Р (и, г) = <

1 ]+

г

^ , Я (г), Я (г) ^ Xг(у).'

Определение 2. Состояние 0(1) называется устойчивым, если выполняется 0(1) = 0(г +1) = 0(г + 2) = 0(г + 3) = •••, а состояние 0* = (я*;• ;яП) называется асимптотически достижимым из состояния 0(0), если для любого е> 0 существует 1 г такое, что для всех 1 > 1е д*-дг(1) <е, V1 е[1;п]2.

Определение 3. Состояние 0 называется предельным, если оно либо устойчиво и за конечное число шагов получается из начального состояния 0(0), либо асимптотически достижимо из начального состояния 0(0).

Рассмотрим вопрос распределения ресурсов в эргодических (сильно связных) ресурсных сетях с вентильной достижимостью [6], [7].

Пусть эргодическая ресурсная сеть G (X, и, /) такая, что и = и0 и и и... и ик при этом иг и и] = 0 (V 0 < / < ] < к). Путь / называется

вентильно-накопительным путем порядка (к > 1) длины (п eN) на сети G, если к т дуг вентильного пути / содержалась хотя бы одна дуга множества и], то следующая дуга пути обязана быть дугой множества и0 и и1 и... и и]+1.

Сетью с вентильной достижимостью называется сеть, в которой допустимыми путями являются только вентильно-накопительные пути. Согласно [7], основной подход к решению задачи о вентильной достижимости состоит в построении вспомогательного графа G'(X', и', /'), количество вершин которого больше, чем у исходной сети G (X, и, /), но на котором нет ограничений на достижимость. При этом каждому пути на вспомогательном графе соответствует единственный вентильно-накопительный путь на исходном (см. [6], [7]).

Согласно указанному подходу, правила построения вспомогательной сети G' для сети G с условием вентильной достижимости имеют вид:

каждой вершине х сети G ставится в соответствие к +1 вершина (х0, х1,...,хк} на вспомогательной сети G'. Каждой дуге /(и) = (х,у) е и1 (1<к) исходной сети G ставится в соответствие к -1 +1 дуга (и1,и1+1,...,ик} на вспомогательной сети G' такая, что /'(и1) = (х1, у1+1), /'(иш) = (х1 +, у1 +); а каждой дуге и = /(х, у) е ик сети G ставится в соответствие одну дугу ик такую, что /'(ик) = (хк, ук). Пропускные способности дуг исходной сети G переносятся на соответствующие дуги вспомогательной сети G'.

Множество дуг вспомогательной сети, соответствующих дуге и на исходной сети будем обозначать через Аи, а подмножества вершин вида

]-тым уровнем вентильности.

Пример 1. Рассмотрим эргодическую сеть О с вентильной достижимостью на рис.1, для которого дуги щ, и2, ..., и10 таковы, что

/(и1) = ^ /(и2) = (Х2 , Х4) , / (из) = (Х4 , X3), / (и4) = X1), / (и5) = (Х^ Х5) ,

/ (иб) = (Х5 , / (и7) = (Х5 , ^ / 08) = (Х6, X7), / (и9) = ^ / Ою) = (Х7) .

Положим к = 2, ио = {,и2,и3,и4,и7,и8,и9}, и1 = {и10}, и2 = {и5,и6}. Согласно, методу построения вспомогательной сети

Рис. 1. Сеть О и соответствующая ей вспомогательная сеть О'. Рассмотрим ресурсную сеть О (X, и, /) с вентильной достижимостью

и рассмотрим матрицу

г як (о

ао=

Як (О

• чкп (О

яГ(0 О) ... ¿-1(0

*0(О я0(О ... ¿(0,

где д/ ( 0 которой является величиной ресурса вершины I в момент времени I, имеющего_/-й уровень вентильности. Не нарушая общности, будем полагать, что такая матрица определяет состояние не только на исходной сети О, но и на вспомогательной сети О'. Другими словами, распределение ресурса в сети с вентильной достижимостью мы будем моделировать при помощи вспомогательной сети.

Рассмотрим правила распределения ресурса в сети с вентильной достижимостью. Поскольку каждой дуге и исходной сети с пропускной

способность г(и) соответствует множество дуг Au на вспомогательной ресурсной сети, то, как и в случае классического потока в сетях с вентильной достижимостью (см., например, [6]), необходимо выполнение следующего условия: суммарный поток по дугам множества Аи не может превосходить

величину г(ы). Таким образом, будем полагать, что распределение ресурса в сети G, с состоянием О '(^ происходит по правилу, аналогичному (1). Ресурсные потоки по дугам вспомогательной сети определяются следующим образом:

рассмотрим дугу и' е и', её пропускная способность равна г (и' ). Пусть дуга и' соответствует дуге и е иа, (а = 0,1,...,к) исходной сети G. Тогда будем полагать, что величина потока, проходящего по данной дуге в момент времени t имеет вид:

> \ qf(t) г (и') F(и',t) = ---^ ' • тт^

Е ^

Е г

Е q/

]=а vе[xв]

]=а

в =

[в

где qв(t) - количество ресурса вершины хв = (p1 о /' )(и') в момент времени t, г = 0,1,...,п, в = 0,1,...,к .

Пример 2. Рассмотрим эргодическую ресурсную сеть G примера 1 с пропускными способностями г (и) = г (и4) = г (и5) = г (и7) = г (и9) = 2,

г (и2) = г (и6) = 1, г (и3) = г (и8) = 3, г (и10) = 5 . Пусть начальное состояние на вспомогательной сети G' имеет вид:

'1 0 2 1 0 2 3 ^

О '(0) =

4 0 1 1 0 0 2 0 10 12 10

у

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

О '(1) =

(1,933 0,4 1,267 0 1,257 0 5,571^ 3,067 1,6 2,333 1 0,571 2 1 ч 0 0 00000 ,

О '(10) =

(0,588 3,818 0,592 0,989 1,826 1,227 4,873^ 0,660 6,075 0,640 0,625 0,016 0,043 0,027 ч 0 0 0 0 0 0 0 J

3 Нахождение порогового значения и предельного

Пусть О (X, и, /) - эргодическая ресурсная сеть с вентильной достижимостью. Отметим, что её вспомогательная сеть О' (X' , и' , /' ) в общем случае состоит из множеств изолированных вершин, стоков и компонент связности И}- .

Заметим, что каждая изолированная вершина х е X' вспомогательной сети в предельном состоянии имеет величину ресурса такую же, как и в начальном состоянии, т.е. я * = я(0), где я (0) - количество ресурса в вершине

^ , /-Ч ^ *

х в момент времени г = 0, а я - его величина в предельном состоянии.

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

Отметим что, каждая компонента является связной подсетью вспомогательной сети О', порождённой множеством X' с X ', состоящей, из нескольких (не менее одной) компонент сильной связности Ир.

Рассмотрим компоненту И 0 - компонента сильной связности,

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

Отметим что, после конечного число тактов компонента И0 собирает ресурс, суммарной величины Ж0 (0 < Ж0 < Ж), который в предельном состоянии будет распределяться только по её вершинам. Поскольку

компонента Н0 изоморфна О, значит, пороговое значение Т0 компоненты Н0 является величиной порогового значения Тбез исходной сети G(X,и,/) без ограничения на достижимость. Величина Т0 = Тбез компоненты Н0 может быть найдена применением метода, описанного в работе [12].

Рассмотрим вопрос о существовании единственного предельного состояния вспомогательной сети G'. Выделим три случая в зависимости от величины суммарного ресурса Ж0, который будет распределяться между

вершинами компоненты Н0 в предельном состоянии.

Первый случай, если Ж0 > Т0.

Поскольку каждой дуге и е и1 исходной сети соответствует

последовательность дуг и1, и1+1, ..., ик на вспомогательной сети, и в любой момент времени t суммарная величина ресурсных потоков, проходящих по дугам и1, и1+1, ..., ик не может превышать величины пропускной способности дуги и , значит, в предельном состоянии выполняется F * (и1) + F * (и1+1) + . + F * (ик) < г (и).

Отметим что, при условии Ж0 > Т0 существует и единственно предельное состояние для отдельно взятой компоненты сильной связности Н0 (см. [5], [11]) и допустим что, существует хотя бы одна компонента

сильной связности Н нижних уровнях, не имеющая единственного предельного состояния. Это означает что, предельные потоки циркулируют в компоненте Н' с некоторым периодом больше единицы. Отсюда получим что, предельные потоки и в компоненте Н0 должны циркулировать с тем же периодом, следовательно, в компоненте Н0 также не существует единственного предельного состояния. Получили противоречие. Таким образом, при условии Ж0 > Т0 для всей вспомогательной сети существует

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

Для дальнейшего изложения введём отношение частичного порядка на множестве компонент сильной связности вспомогательной сети:

Будем считать, что компонента сильной связности И0 является

компонентой нулевого порядка. Далее удаляем все вершины компоненты И 0 ,

а также все вершины, из которых достижима компонента И0. В результате

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

Отметим, что после конечного число тактов каждая компонента сильной связности И вспомогательной сети О собирает величину суммарного ресурса 0 < Ж(И) < Ж, которую будет распределяться на нее в предельном состоянии, а нахождение порогового значения Т (И) компоненты И может быть найдено как в работах [11] и [12].

Определения 4. Две компоненты сильной связности Иi и И}

вспомогательной сети О' будем называть связанными, если на них существуют хотя бы две дуги и1 е Иг и и2 е Ир которые соответствуют

одной дуге исходной сети.

Введём в рассмотрение множество щ(И) - множество компонент, следующего порядка, связанных с компонентой И . Определим величину Ж = Ж0 + в(И 0), где

д( И) =

0, у( И) = 0;

X тт{Т(И'), Ж(И') + в(И' )}, щ(И) * 0.

И' ещ

здесь Т(Н') и Ж(Н') - соответственно пороговое значение и суммарная величина ресурса для компоненты Н .

Для величин Ж и Т0 в сети с вентильной достижимостью возможны следующие ситуации:

- если Ж > Т0, то предельное состояние на вспомогательной сети существует и единственно (см. [5], [8], [11]), при этом для Ж > Т0 предельное состояние существует, и оно не зависит от начального состояния в том и только в том случае, когда на каждой компоненте сильной связности вспомогательной сети существует единственный потенциальный аттрактор. В противном случае распределение ресурса сверх порогового значения Ж - Т0 зависит от начального состояния на каждой компоненте сильной связности. В предельном состоянии каждая неаттрактивная вершина имеет величину ресурса, равную сумме входящих пропускных способностей, а аттрактивные вершины собирают все «лишние» ресурсы в данной компоненте сильной связности;

- если Ж < Т0, то существование единственного предельного состояния на вспомогательной сети зависит от начального состояния (см. [1], [11]).

Третий случай, если Ж0 = 0.

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

Литература

1. Жилякова Л.Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах // Управление

большими системами. 2013. № 43. С. 34-54.

2. Zhilyakova L.Yu. Asymmetric resource networks. I. Stabilization processes for low resources // Automation and Remote Control. 2012. Vol. 72, No 4. pp. 798-807.

3. Zhilyakova L.Yu. Asymmetric resource networks. II. Flows for large rosource and their stabilization // Automation and Remote Control. 2012. Vol. 73, No 6. pp. 1016-1028.

4. Zhilyakova L.Yu. Asymmetric resource networks. III. A study of limit states // Automation and Remote Control. 2012. Vol. 73, No 7. pp. 1165-1172.

5. Жилякова Л.Ю. Эргодические циклические ресурсные сети. II. Большие ресурсы // Управление большими системами. 2013. № 45. С. 6-29.

6. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003. № 2. С. 3-5.

7. Ерусалимский Я.М., Скороходов В.А., Кузьминова М.В., Петросян А.Г. Графы с нестандартной достижимостью: задачи, приложения. Ростов-на-Дону: Южный федеральный университет, 2009. 195 с.

8. Абдулрахман Х., Скороходов В.А. Ресурсные сети с магнитной достижимостью // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2016. № 4. С. 4-10.

9. Ерусалимский, Я.М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях // Инженерный вестник Дона. 2015. №.1 URL: ivdon.ru/ru/magazine/archive/n1y2015/2782/.

10. Орлов В.В. О заполнении вершин ориентированного графа // Инженерный вестник Дона. 2017. №.4 URL: ivdon.ru/ru/magazine/archive/n4y2017/4574.

11. Скороходов В.А. Задача нахождения порогового значения в эргодической ресурсной сети // Управление большими системами. Выпуск 63. М.: ИПУ РАН. 2016. С. 6-23.

12. Skorohodov V.A., Chebotareva A.S. Maximum flow problem in a network with special conditions of flow distribution // Journal of Applied and Industrial Mathematics. 2015. Vol. 22, No 3. pp. 55-74.

References

1. Zhilyakova L.Yu. Upravlenie bol'shimi sistemami, 2013. № 43. pp. 34-54.

2. Zhilyakova L.Yu. Automation and Remote Control. 2012. Vol. 72, No 4. pp. 798-807.

3. Zhilyakova L.Yu. Automation and Remote Control. 2012. Vol. 73, No 6. pp. 1016-1028.

4. Zhilyakova L.Yu. Automation and Remote Control. 2012. Vol. 73, No 7. PP. 1165-1172.

5. Zhilyakova L.Yu. Upravlenie bol'shimi sistemami. 2013. № 45. pp. 6-29.

6. Erusalimskij Ya.M., Skorokhodov V.A. Izvestiya vuzov. Severo-Kavkazskii region. Estestvennye nauki. 2003. No 2. pp. 3-5.

7. Erusalimskij Ya.M., Skorokhodov V.A., Kuzminova M.V., Petrosyan A.G. Grafy s nestandartnoi dostizhimost'yu: zadachi, prilozheniya [Graphs with nonstandard reachability: tasks, applications]. Rostov-na-Donu: Yuzhnyi federal'nyi universitet, 2009. 195p.

8. Abdulrahman H., Skorokhodov V.A. Izvestiya vuzov. Severo-Kavkazskii region. Estestvennye nauki. 2016. No 4. pp. 4-10.

9. Erusalimskij Ya.M. Inzenernyj vestnik Dona (Rus), 2015, №1. URL: ivdon.ru/ru/magazine/archive/n1y2015/2782/.

10. Orlov V.V. Inzenernyj vestnik Dona (Rus), 2017. №4. URL: ivdon.ru/ru/magazine/archive/n4y2017/4574/.

11. Skorokhodov V.A. Upravlenie bol'shimi sistemami. Vypusk 63. M: IPU RAN, 2016. pp. 6-23

12. Skorohodov V.A., Chebotareva A.S. Journal of Applied and Industrial Mathematics. 2015. Vol. 22, No 3. pp. 55-74.