ДИНАМИЧЕСКИЕ РЕСУРСНЫЕ СЕТИ презентация

Содержание

Функции на ребрах Ориентированный граф G(V, E); V – множество вершин, ⏐V⏐= n; E – множество ребер, e = (u, v); ⏐Е⏐= m. Hа ребрах определена числовая функция (поток)

Слайд 1ДИНАМИЧЕСКИЕ РЕСУРСНЫЕ СЕТИ

О.П. Кузнецов Институт проблем управления им. В.

А. Трапезникова РАН,
г. Москва
olkuznes@ipu.rssi.ru

Л.Ю. Жилякова ПИ ЮФУ,
г. Ростов-на-Дону
zhilyakov@aaanet.ru

Тверь, КИИ-2010

Слайд 2Функции на ребрах
Ориентированный граф G(V, E); V – множество вершин, ⏐V⏐=

n;
E – множество ребер, e = (u, v); ⏐Е⏐= m.
Hа ребрах определена числовая функция (поток)
f(e) = f(u, v), u, v ∈ V. 

Дивергенция вершины (разница между входящим и выходящим потоками)

divf(v) =

так как всякое входящее ребро является выходящим.

Слайд 31. Статические потоки
1. Выделены две вершины: s (источник) и t

(сток). Остальные вершины называются внутренними; для них divf(v) = 0.
2. На функцию f(е) наложены ограничения:
0 ≤ f(е) ≤ с(е);
с(е) называется пропускной способностью (емкостью, проводимостью) ребра е.
 Из п.1 следует, что divf(t) = − divf(s) = M(f) – мощность (объем, величина) потока.

1а.Классическая постановка Форда-Фалкерсона: s-t-поток (1-1-задача)

Слайд 4Пример
Матрица потока F = ||fij||n × n

Слайд 5Разрезы
Разрез А = (X, Y) - разбиение множества вершин на два

класса, причем s ∈ X, t ∈ Y.
U+(A) – множество вершин из X в Y;
U−(A) – множество вершин из Y в X.
c(A) = - пропускная способность разреза.
divf(A) =

M(f) = divf(A) = − ≤ = c(A) –
мощность потока не превосходит пропускной способности любого разреза.

Слайд 6Теорема Форда-Фалкерсона:
1. Если для всех е ∈ Е с(е) –

целые числа, то существует целочисленный максимальный поток (поток максимальной мощности).
2. Мощность максимального потока равна пропускной способности минимального разреза: M(f) = с(А).
Алгоритм Форда –Фалкерсона строит максимальный поток только в целочисленном случае.
В общем случае алгоритм Форда-Фалкерсона может не сойтись, причем даже в пределе может получиться немаксимальный поток.

Слайд 71б. Модификации классической постановки
Многополюсные потоки: источники s1, …, sk и стоки

t1, …, tl (k-l-задача).
Дивергенция в промежуточных вершинах по-прежнему равна нулю.
Задача о максимальном суммарном потоке решается простой редукцией к 1-1-задаче:

1. Статические потоки

Слайд 8
Многопродуктовый поток: имеется множество продуктов K = {1, . . .

, k}, k источников s1, …, sk, k стоков t1, …, tk (по одному источнику и стоку для каждого продукта), пропускные способности с(е) ребер; задано k функций fi на ребрах, причем fi задает поток i-го продукта из si в ti.
Задача о максимальном многопродуктовом потоке: найти поток максимальной суммарной мощности ΣMi при стандартных ограничениях.

1б. Модификации классической постановки

1. Статические потоки

Слайд 92. Динамические потоки (потоки во времени - flow over time)
Для каждого

ребра е задано время передачи τ(е), пропускная способность c(e), коэффициент цены a(e) на единицу потока. Поток, вошедший в ребро е в момент θ, выходит из е в момент θ + τ(е).
Задача о максимальном потоке во времени: передать от s к t максимальный поток за время Т.

Задача: передать 2 единицы потока за минимальное время.
Можно послать 2 единицы потока в первое ребро в течение интервала [0, 1). Так как в первом ребре время передачи равно 3, то эти две единицы придут в v в интервале [3, 4). Тогда можно начинать передавать поток объема 1 во второе ребро с момента 3, передача закончится к моменту 5. Тогда весь поток придет в t в интервале [5, 7). Время передачи = 7, часть потока хранится в v. Другой вариант: начать передавать 1 единицу потока в интервале [0, 2). Время передачи также равно 7, но хранения в v нет.

Слайд 102. Динамические потоки
Быстрейшие потоки: передать от s к t заданный объем

потока за минимально возможное время.
Потоки с ранним прибытием: построить s-t-поток, максимизирующий объем потока, прибывающего в сток раньше момента θ для всех θ ∈ [0, T).
Потоки с поздним отправлением: построить s-t-поток, максимизирующий объем потока, выходящего из источника позже момента θ для всех θ ∈ [0, T).
Потоки с ценами (NP-трудные задачи):
-  найти поток минимальной стоимости в данном интервале времени:
-  найти быстрейший поток, не превосходящий заданной стоимости.
Быстрейшие многопродуктовые потоки (NP-трудные задачи).

Другие задачи

Слайд 11Ресурсная сеть - граф, вершинам которого приписаны неотрицательные числа qi(t), называемые

ресурсами, а ребрам (vi, vj) - неотрицательные числа rij, постоянные во времени и называемые проводимостями (пропускными способностями); n – число вершин.
Состояние Q(t) сети в момент t – это вектор (q1(t), …, qn(t)).
Правила передачи ресурса (правила функционирования сети) учитывают следующие условия:
а) сеть замкнута, т.е. ресурсы извне не поступают;
б) ресурс, отдаваемый на выход, вычитается из ресурса вершины; ресурс, приходящий по входам, прибавляется к ресурсу вершины.
В замкнутой сети суммарный ресурс сохраняется: W = const.

W = (закон сохранения)

3. Ресурсные сети

Слайд 12Состояние Q(t) называется устойчивым, если Q(t) = Q(t + 1). Очевидно,

что в этом случае Q(t) = Q(t + 2) = Q(t + 3) = …
Состояние Q* = (q1*, …, qn*) называется асимптотически достижимым из состояния Q(0), если для любого ε > 0 существует tε такое, что для всех t > tε
⎢qi* - qi(t)⎢ < ε, i = 1, 2, …, n.
Состояние сети называется предельным, если оно либо устойчиво, либо асимптотически достижимо.
Ресурсная сеть называется однородной, если все проводимости равны, а правило функционирования сети – следующее:
в момент t+1 вершина vi по каждому из своих mi выходящих ребер отдает:
r единиц ресурса, если mi r ≤ qi(t);
qi(t)/mi в противном случае.

Слайд 13Пару ребер назовем двусторонней парой. Ресурсную сеть,

все вершины которой соединены двусторонними парами, будем называть двусторонней полной сетью (ДПС).
Сначала рассмотрим однородные ДПС (ОДПС) без петель. Для ОДПС mi = n – 1 для всех i.
Поэтому правило функционирования переформулируем:
В момент t + 1 вершина vi на каждую из своих n – 1 выходных связей отдает:
r единиц ресурса, если (n – 1) r ≤ qi(t) (правило1);
qi(t)/(n – 1) в противном случае (правило 2 – отдается весь ресурс).

Слайд 15
Пример 1: n = 5, r = 2, W = 35

(начальный ресурс в одной вершине)

0 35.00 0.00 0.00 0.00 0.00
1 27.00 2.00 2.00 2.00 2.00
2 21.00 3.50 3.50 3.50 3.50
3 16.50 4.63 4.63 4.63 4.63
4 13.13 5.47 5.47 5.47 5.47
5 10.59 6.10 6.10 6.10 6.10
6 8.70 6.58 6.58 6.58 6.58
7 7.27 6.93 6.93 6.93 6.93
8 6.93 7.02 7.02 7.02 7.02
9 7.02 7.00 7.00 7.00 7.00
10 7.00 7.00 7.00 7.00 7.00
11 7.00 7.00 7.00 7.00 7.00


































t

Функционирование ОДПС
(строки соответствуют моментам времени)


Слайд 16Свойство 1.
Если для некоторого t’ qi(t’) = qj(t’), то для

всех t > t’ qi(t) = qj(t).
Это следует из того, что с момента t обе вершины получают и отдают одинаковое количество ресурса.
Свойство 2.
Если для некоторого t’ qi(t’) ≤ r(n – 1), то для всех t > t’ qi(t) ≤ r(n – 1).
Это следует из того, что vi в момент t отдает весь свой ресурс, а получить от других n – 1 вершин может не более чем r(n – 1).
Свойство 3.
Если для всех i qi(t) ≥ r(n – 1), то состояние Q(t) устойчиво.
Это следует из того, что все вершины получают и отдают r(n – 1) единиц ресурса.

Три свойства ОДПС

Слайд 17Теорема 1.
Для однородного двустороннего полного графа без петель с числом

вершин n > 2 существует порог выравнивания T = rn(n – 1), не зависящий от начального состояния сети. Иными словами,
1. Если суммарный ресурс W ≤ T, то при любом начальном состоянии сети происходит выравнивание ресурса, т.е. ее предельным состоянием является вектор



2. Если W > T, то при любом начальном состоянии сети, в котором хотя бы в двух вершинах ресурсы не равны, выравнивание не происходит.


Слайд 18 Пример 2: n = 5, r = 2, W =

25, T = 40

0 7.00 6.00 5.00 4.00 3.00
1 4.50 4.75 5.00 5.25 5.50
2 5.13 5.06 5.00 4.94 4.88
3 4.97 4.98 5.00 5.02 5.03
4 5.01 5.00 5.00 5.00 4.99
5 5.00 5.00 5.00 5.00 5.00
6 5.00 5.00 5.00 5.00 5.00
7 5.00 5.00 5.00 5.00 5.00
8 5.00 5.00 5.00 5.00 5.00






t









5

Слайд 19














С(t) - сумма всех ci(t) (превышений над порогом),
D(t) - сумма

всех dj(t) (недостач до порога)
C(0) – начальный профицит Z+,
D(0) – начальный дефицит Z-
C(0) - D(0) = s - сальдо

Слайд 20Пример 3: n = 5, r = 2, W = 43,

T = 40. Зона Z+ уменьшается: s = 3, l = 2.
0 12.00 10.00 9.00 7.00 5.00
1 11.00 9.00 8.00 7.25 7.75
2 10.75 8.75 7.75 7.94 7.81
3 10.63 8.63 7.94 7.89 7.92
4 10.56 8.56 7.95 7.96 7.96
5 10.53 8.53 7.98 7.98 7.98
6 10.52 8.52 7.99 7.99 7.99
7 10.51 8.51 7.99 7.99 7.99
8 10.50 8.50 8.00 8.00 8.00
9 10.50 8.50 8.00 8.00 8.00
10 10.50 8.50 8.00 8.00 8.00
11 10.50 8.50 8.00 8.00 8.00

Слайд 21Теорема 2.
Если W > rn(n – 1), то предельным состоянием

сети является вектор
(q1 − hl, …, ql − hl, r(n – 1), …, r(n – 1)),

где l = k и hk = , если ck(0) ≥ ;

в противном случае l ≤ k – наибольшее целое число, такое, что cl(0) ≥ hl,

hl = , где Cl(0) = .























Слайд 22
i
q
r (n-1)
k
l
n
l+1
…
O
1
t = j
t= t’
t = tlim

Слайд 23Окончательное распределение

Слайд 24Свойство эргодичности
Однородная сеть при W > T является неэргодической системой: предельное

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

Слайд 25Потоки в ресурсных сетях
Ресурс, выходящий из вершины vi по ребру (vi,

vj) в момент t, приходит в вершину vj в момент t + 1.
Соответственно, будем считать, что этот ресурс на интервале (t, t + 1) находится на ребре (vi, vj).
Его величину назовем выходным потоком sij(t) .
Матрицей потока S(t) назовем матрицу ||sij(t)||n×n.
– выходной поток из вершины vi в момент t (сумма элементов i-й строки матрицы S(t)).
Входным потоком в вершину vj в момент t + 1 назовем сумму элементов j-го столбца S(t):  
кроме того, положим
В однородных сетях с петлями все столбцы матрицы потока одинаковы.

Слайд 26Основные понятия
Зона Z–, зона Z+
Пороговое значение T
Предельное

состояние

Слайд 27Матрицей проводимости будем называть матрицу R = ||rij||n × n.

Матрица

проводимости

Свойства матрицы проводимости:
1. R – неотрицательная матрица: ∀i, j rij ≥ 0
2. ∀i rii > 0
3. ∀i, j (rij > 0 ⇔ rji > 0)



Несимметричные сети

Слайд 28Входная и выходная проводимости
Суммарную проводимость входных ребер вершины vi будем называть


ее входной проводимостью и обозначать:




Суммарную проводимость выходных ребер, назовем выходной проводимостью и обозначим через:

Проводимость петли входит в обе суммы.

Слайд 29Входная и выходная проводимости вершины


Слайд 30Классификация сетей
Ресурсная сеть называется:
однородной, если все элементы матрицы R одинаковы:

rij = r ∀i,j, и
неоднородной в противном случае;
симметричной, если симметрична ее матрица проводимости;
квазисимметричной, если

∀i:    (1)

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



Слайд 31Обозначим через Δri разность между входной и выходной проводимостями вершины vi:


Классификация вершин несимметричной сети

Тогда все вершины сети делятся на три вида:
вершины-приемники, для которых Δri > 0;
вершины-источники, для которых Δri < 0;
нейтральные вершины, для которых Δri = 0.

Δri =  


Суммарной проводимостью сети, rsum, назовем сумму проводимостей всех ее ребер:


Слайд 32В симметричных и квазисимметричных сетях все вершины нейтральны.
Путь от нейтральной

вершины к источнику, не содержащий вершин-приемников, назовем неположительным путем.
Пусть среди n вершин сети имеется l приемников, k источников, и n – l – k нейтральных вершин.
Будем считать, что приемники имеют номера от 1 до l, источники – от l + 1 до l + k, нейтральные вершины – от l + k + 1 до n.

Классификация вершин несимметричной сети

Слайд 33Правила функционирования сети
Распределение ресурса в сети происходит по одному из двух

правил, выбор которых зависит от величины ресурса в вершинах.
В момент t + 1 вершина vi в ребро, соединяющее ее с вершиной vk, отдаст:

правило 1: rik единиц ресурса, если

правило 2: в противном случае.



Слайд 34

















Ресурс вершины qi

Изменение ресурса в вершине за один такт (правило 1)



i

Слайд 35



















Ресурс вершины qi
Изменение ресурса в вершине за один такт (правило 2)




Слайд 36Свойства вершин-источников и нейтральных вершин
Свойство 1. В процессе функционирования несимметричной
сети

ресурс в нейтральных вершинах может временно
стабилизироваться, а затем снова изменяться.


Свойство 2. Если для некоторого t' qi(t') ≤ , то для всех t > t'
qi(t) <  (i > l).

Множество вершин с ресурсом qi(t), меньшим , – зона Z–(t).
Из свойства 2 следует, что источники и нейтральные вершины, раз попав в Z–, уже не смогут ее покинуть.

Поскольку для них выполняется:


Слайд 37t v1 v2 v3 v4 v5

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
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
…
79 77.404 7.596 5.000 5.000 5.000
80 78.404 6.596 5.000 5.000 5.000
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. Временная стабилизация ресурса в нейтральных вершинах (св-во 1).
W = 100, n = 5. Ресурс находится в вершине-источнике: Q(0)=(0, 100, 0,0,0).

Слайд 38Свойства вершин-источников и нейтральных вершин (i > l)
Теорема 3. В связной несимметричной

сети при любом начальном состоянии и любом начальном ресурсе существует такой момент времени t', начиная с которого все источники и нейтральные вершины, из которых имеются неположительные пути (пути к источнику, не содержащие вершин-приемников), будут находиться в зоне Z–(t).

Слайд 39Пример 2. Нейтральная вершина остается в зоне Z+
W = 100,

n = 5. Ресурс в нейтральной вершине (вершина v5), связанной только с приемником v1 (у вершины v5 нет неположительных путей)

t v1 v2 v3 v4 v5

0 0.000 0.000 0.000 0.000 100.000
1 1.000 0.000 0.000 0.000 99.000
2 1.200 0.200 0.200 0.200 98.200
3 1.507 0.357 0.357 0.340 97.440
…
92 4.997 2.398 2.398 1.998 88.208
93 4.997 2.398 2.398 1.999 88.208
94 4.997 2.398 2.398 1.999 88.207
95 4.998 2.399 2.399 1.999 88.207
96 4.999 2.399 2.399 1.999 88.206
97 5.000 2.399 2.399 1.999 88.205

Слайд 40Пороговое значение ресурса Т
Теорема 4. В несимметричной сети существует
пороговое значение суммарного

ресурса Т, такое, что
при W ≤ Т все вершины, начиная с некоторого t',
переходят в зону Z–(t);
при W > T зона Z+(t) непуста для любого t.
Т единственно и не зависит от суммарного ресурса W
и его начального распределения Q(0).

Для однородных сетей выполняется равенство: Т = rsum.
Для несимметричных сетей Т < rsum.

Слайд 41При W ≤ T и t > t' все вершины сети

функционируют по правилу 2:

Функционирование сети при W ≤ T


Q(t+1) = Q(t)⋅R'


где

R' является стохастической матрицей.

Слайд 42Теорема 5. Для ресурсной сети, являющейся связным двусторонним графом с петлями,

при W ≤ Т предельное состояние Q*
1) существует;
2) единственно и не зависит от начального распределения ресурса по вершинам, а только от суммарного количества ресурса в сети.

Предельное состояние при W ≤ T

Слайд 43Функционирование сети при W > T
При W > Т в несимметричных

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

Слайд 44Пример 3. Сеть с двумя приемниками (первый более «мощный»).
W = 100,

n = 5. Ресурс в первом приемнике.

t v1 v2 v3 v4 v5

0 100.00 0.000 0.000 0.000 0.000
1 96.000 1.000 1.000 1.000 1.000
2 92.995 1.876 1.710 1.710 1.710
…
31 83.799 4.536 3.888 3.888 3.888
32 83.798 4.536 3.888 3.888 3.888
33 83.797 4.537 3.889 3.889 3.889
34 83.796 4.537 3.889 3.889 3.889

Слайд 45Пример 4. Сеть с двумя приемниками.
W = 100, n = 5.

Ресурс во втором приемнике, но все равно ресурс забирает первый.

t v1 v2 v3 v4 v5
0 0.000 100.000 0.000 0.000 0.000
1 1.000 96.000 1.000 1.000 1.000
2 1.995 92.876 1.710 1.710 1.710
3 2.759 90.431 2.270 2.270 2.270
…
19 6.951 80.817 4.077 4.077 4.077
20 7.193 80.574 4.077 4.077 4.077
21 7.436 80.331 4.078 4.078 4.078
22 7.678 80.089 4.078 4.078 4.078
…
331 82.678 5.089 4.078 4.078 4.078
332 82.921 4.846 4.078 4.078 4.078
333 83.133 4.726 4.047 4.047 4.047
334 83.296 4.682 4.007 4.007 4.007
335 83.420 4.646 3.978 3.978 3.978
…
371 83.796 4.537 3.889 3.889 3.889

Слайд 46Вершину, способную в предельном состоянии остаться в зоне Z+, назовем потенциальным

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

Классификация вершин

Слайд 47Сеть с одним аттрактором является эргодической системой.
При любом фиксированном значении

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

Сеть с одним аттрактором

Слайд 48Сеть с несколькими потенциальными аттракторами является частично эргодической системой.
При W

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

Сеть с несколькими потенциальными аттракторами

Слайд 49Пример 5. Сеть с двумя равными приемниками (куда положили, там и

останется).
W = 100, n = 5. Ресурс в первом приемнике.

t v1 v2 v3 v4 v5

0 100.00 0.000 0.000 0.000 0.000
1 96.000 1.000 1.000 1.000 1.000
2 92.900 1.900 1.733 1.733 1.733
3 90.493 2.593 2.304 2.304 2.304
4 88.625 3.132 2.748 2.748 2.748
…
39 82.144 5.000 4.285 4.285 4.285
40 82.144 5.000 4.286 4.286 4.286
41 82.143 5.000 4.286 4.286 4.286

Ресурс вершины v2 стремится к значению ее выходной проводимости снизу; этот приемник не сможет перейти с правила 2 на правило 1. Таким образом, если весь ресурс в одном из потенциальных аттракторов, остальные останутся в зоне Z-(t).

Слайд 50Пример 6. Сеть с двумя равными приемниками.
W = 100, n =

5. Ресурс во втором приемнике.

t v1 v2 v3 v4 v5

0 0.000 100.00 0.000 0.000 0.000
1 1.000 96.000 1.000 1.000 1.000
2 1.900 92.900 1.733 1.733 1.733
3 2.593 90.493 2.304 2.304 2.304
4 3.132 88.625 2.748 2.748 2.748
…
39 5.000 82.144 4.285 4.285 4.285
40 5.000 82.144 4.286 4.286 4.286
41 5.000 82.143 4.286 4.286 4.286

Ресурс вершины v1 стремится к значению ее выходной проводимости снизу.

Слайд 51Пример 7. Сеть с двумя равными приемниками.
W = 100, n =

5. Ресурс в первом источнике (вершина v3).

t v1 v2 v3 v4 v5
0 0.000 0.000 100.000 0.000 0.000
1 2.000 1.000 95.000 1.000 1.000
2 2.967 2.133 90.967 1.967 1.967
3 3.741 3.069 87.708 2.741 2.741
…
12 9.416 7.748 73.364 4.736 4.736
13 10.153 8.274 72.100 4.736 4.736
14 10.889 8.800 70.837 4.737 4.737
15 11.626 9.326 69.574 4.737 4.737
…
66 49.205 36.168 5.153 4.737 4.737
67 49.660 36.554 4.596 4.596 4.596
…
76 50.123 37.017 4.287 4.287 4.287
77 50.124 37.018 4.286 4.286 4.286

Оба потенциальных аттрактора переходят в Z+(t), но набирают разное количество ресурса.

Слайд 52Пример 8. Сеть с двумя равными приемниками.
W = 100, n =

5. Ресурс в нейтральной вершине (вершина v5).

t v1 v2 v3 v4 v5
0 0.000 0.000 0.000 0.000 100.000
1 1.000 1.000 1.000 1.000 96.000
2 1.900 1.900 1.733 1.733 92.733
…
14 5.966 5.966 4.498 4.498 79.072
15 6.215 6.215 4.499 4.499 78.572
16 6.464 6.464 4.500 4.500 78.072
…
162 42.964 42.964 4.500 4.500 5.071
163 43.214 43.214 4.500 4.500 4.571
164 43.379 43.379 4.414 4.414 4.414
…
171 43.569 43.569 4.287 4.287 4.287
172 43.570 43.570 4.287 4.287 4.287
173 43.571 43.571 4.286 4.286 4.286

Слайд 53Критерий аттрактивности
Вершина является потенциальным аттрактором, тогда и только тогда, когда при

W=T ее ресурс в предельном состоянии равен ее выходной проводимости.

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

Слайд 54Пример 9. Сеть с двумя неравными приемниками.
W = 100, n =

5. Ресурс в нейтральной вершине.

t v1 v2 v3 v4 v5
0 0.000 0.000 0.000 0.000 100.000
1 1.000 1.000 1.000 1.000 96.000
2 2.504 1.838 1.552 1.552 92.552
3 3.529 2.766 2.051 2.051 89.603
4 4.439 3.495 2.487 2.487 87.091
5 5.222 4.123 2.855 2.855 84.945
…
158 6.268 84.100 3.211 3.211 3.211
159 6.267 84.101 3.211 3.211 3.211
160 6.267 84.102 3.210 3.210 3.210
161 6.266 84.103 3.210 3.210 3.210
162 6.266 84.103 3.210 3.210 3.210
163 6.266 84.104 3.210 3.210 3.210

В Z+(t) оказывается более «слабый» приемник, потому что он «паразитирует» на сильном.

Слайд 55Пример 10. Изменим проводимость ребра r12 на 1.
W = 100, n

= 5. Ресурс в нейтральной вершине.

t v1 v2 v3 v4 v5
0 0.000 0.000 0.000 0.000 100.000
1 1.000 1.000 1.000 1.000 96.000
2 2.528 1.743 1.576 1.576 92.576
3 3.601 2.522 2.100 2.100 89.677
4 4.544 3.145 2.545 2.545 87.221
5 5.342 3.677 2.920 2.920 85.141
…
80 86.696 4.076 3.076 3.076 3.076
81 86.700 4.075 3.075 3.075 3.075
82 86.701 4.075 3.075 3.075 3.075
83 86.703 4.074 3.074 3.074 3.074
84 86.703 4.074 3.074 3.074 3.074
85 86.704 4.074 3.074 3.074 3.074

В Z+(t) оказывается «сильный» приемник – «слабому» уже не хватает мощности.

Слайд 56Пример 11 (совпадает с примером 1). Потенциальный аттрактор – нейтральная вершина.

W = 100, n = 5. Ресурс в нейтральной вершине (вершина v5), связанной только с источником

t v1 v2 v3 v4 v5

0 0.000 0.000 0.000 0.000 100.000
1 1.000 0.000 0.000 0.000 99.000
2 1.200 0.200 0.200 0.200 98.200
3 1.507 0.357 0.357 0.340 97.440
…
92 4.997 2.398 2.398 1.998 88.208
93 4.997 2.398 2.398 1.999 88.208
94 4.997 2.398 2.398 1.999 88.207
95 4.998 2.399 2.399 1.999 88.207
96 4.999 2.399 2.399 1.999 88.206
97 5.000 2.399 2.399 1.999 88.205

Слайд 57Классификация потенциальных аттракторов

Из примеров видно, что потенциальные аттракторы могут быть активными

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

Слайд 58Классификация сетей по наличию потенциальных аттракторов (W>T)
Все вершины однородной сети являются

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

Несимметричная сеть с одним (потенциальным) аттрактором всегда будет эргодической системой.

Несимметричная сеть с более чем одним потенциальным аттрактором является частично эргодической: координаты вектора предельного состояния для не-аттракторов не зависят, а для потенциальных аттракторов зависят от начального распределения ресурса

Слайд 591. При любом значении W процесс распределения ресурса сходится к предельному

состоянию.
2. Существует пороговое значение ресурса Т, превышение которого влечет за собой непустоту Z+.
3. При W ≤ T сеть представляет собой эргодическую систему.
4. При W > T в сети существуют аттракторы, которые стягивают на себя основную часть ресурса.
5. Потенциальные аттракторы могут быть активными и пассивными. Активными аттракторами могут быть только вершины-приемники несимметричной сети.

Основные результаты

Слайд 60Модель распространения вещества на заданной акватории. Начальные данные

Слайд 61Работа модели

Слайд 63Публикации
О.П. КУЗНЕЦОВ. Однородные ресурсные сети I. Полные графы. // Автоматика

и телемеханика, 2009, № 11, с.136-147.

О.П. КУЗНЕЦОВ, Л.Ю. ЖИЛЯКОВА.
Двусторонние ресурсные сети – новая потоковая модель. // Доклады Академии Наук, 2010, том 433, № 5, с. 609–612.

Слайд 64СПАСИБО ЗА ВНИМАНИЕ

Похожие презентации

Мелкозернистая параллельная реализация алгоритма Монтгомери 234
Образцы коллекций одежды 205
Альбом звукоподражаний(звуки [г], [к], [х]) 365
Современный урок и условия его успешной организации 226
Проектирование разработки газовой залежи 254
Экодом - экономный дом 231

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика