ДИНАМИЧЕСКИЕ РЕСУРСНЫЕ СЕТИ О.П. Кузнецов Институт проблем управления им. В. А. Трапезникова РАН, г. Москва Л.Ю. Жилякова ПИ ЮФУ, г. Ростов-на-Дону Тверь, КИИ-2010

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

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

4 Пример sabct s 21 a 11 b 2 c 1 t Матрица потока F = ||f ij || n n a c 4 1 s b t

5 Разрезы Разрез А = (X, Y) - разбиение множества вершин на два класса, причем s X, t Y. U + (A) – множество вершин из X в Y; U (A) – множество вершин из Y в X. c(A) = - пропускная способность разреза. div f (A) = M(f) = div f (A) = = c(A) – мощность потока не превосходит пропускной способности любого разреза.

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

7 1б. Модификации классической постановки Многополюсные потоки: источники s 1, …, s k и стоки t 1, …, t l (k-l-задача). Дивергенция в промежуточных вершинах по-прежнему равна нулю. Задача о максимальном суммарном потоке решается простой редукцией к 1-1-задаче: s1s1 sksk t1t1 tltl s t Потоковая сеть 1. Статические потоки

8 Многопродуктовый поток: имеется множество продуктов K = {1,..., k}, k источников s 1, …, s k, k стоков t 1, …, t k (по одному источнику и стоку для каждого продукта), пропускные способности с(е) ребер; задано k функций f i на ребрах, причем f i задает поток i-го продукта из s i в t i. Задача о максимальном многопродуктовом потоке: найти поток максимальной суммарной мощности M i при стандартных ограничениях. 1б. Модификации классической постановки 1. Статические потоки

9 2. Динамические потоки (потоки во времени - flow over time) Для каждого ребра е задано время передачи (е), пропускная способность c(e), коэффициент цены a(e) на единицу потока. Поток, вошедший в ребро е в момент, выходит из е в момент + (е). Задача о максимальном потоке во времени: передать от s к t максимальный поток за время Т. svt (s, v) = 3, c(s, v) = 2 (v, t) = 2, c( v, t) = 1 Задача: передать 2 единицы потока за минимальное время. Можно послать 2 единицы потока в первое ребро в течение интервала [0, 1). Так как в первом ребре время передачи равно 3, то эти две единицы придут в v в интервале [3, 4). Тогда можно начинать передавать поток объема 1 во второе ребро с момента 3, передача закончится к моменту 5. Тогда весь поток придет в t в интервале [5, 7). Время передачи = 7, часть потока хранится в v. Другой вариант: начать передавать 1 единицу потока в интервале [0, 2). Время передачи также равно 7, но хранения в v нет.

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

11 Ресурсная сеть - граф, вершинам которого приписаны неотрицательные числа q i (t), называемые ресурсами, а ребрам (v i, v j ) - неотрицательные числа r ij, постоянные во времени и называемые проводимостями (пропускными способностями); n – число вершин. Состояние Q(t) сети в момент t – это вектор (q 1 (t), …, q n (t)). Правила передачи ресурса (правила функционирования сети) учитывают следующие условия: а) сеть замкнута, т.е. ресурсы извне не поступают; б) ресурс, отдаваемый на выход, вычитается из ресурса вершины; ресурс, приходящий по входам, прибавляется к ресурсу вершины. В замкнутой сети суммарный ресурс сохраняется: W = const. W = (закон сохранения) 3. Ресурсные сети

12 Состояние Q(t) называется устойчивым, если Q(t) = Q(t + 1). Очевидно, что в этом случае Q(t) = Q(t + 2) = Q(t + 3) = … Состояние Q * = (q 1 *, …, q n * ) называется асимптотически достижимым из состояния Q(0), если для любого > 0 существует t такое, что для всех t > t q i * - q i (t)

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

14 q1q1 q2q2 q4q4 q3q3 q5q5

15 Пример 1: n = 5, r = 2, W = 35 (начальный ресурс в одной вершине) t Функционирование ОДПС (строки соответствуют моментам времени) Функционирование ОДПС (строки соответствуют моментам времени)

16 Свойство 1. Если для некоторого t q i (t) = q j (t), то для всех t > t q i (t) = q j (t). Это следует из того, что с момента t обе вершины получают и отдают одинаковое количество ресурса. Свойство 2. Если для некоторого t q i (t) r(n – 1), то для всех t > t q i (t) r(n – 1). Это следует из того, что v i в момент t отдает весь свой ресурс, а получить от других n – 1 вершин может не более чем r(n – 1). Свойство 3. Если для всех i q i (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 = t 5

19 T = rn(n – 1) Z+Z+ Z-Z- С(t) - сумма всех c i (t) (превышений над порогом), D(t) - сумма всех d j (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 =

21 Теорема 2. Если W > rn(n – 1), то предельным состоянием сети является вектор (q 1 h l, …, q l h l, r(n – 1), …, r(n – 1)), где l = k и h k =, если c k (0) ; в противном случае l k – наибольшее целое число, такое, что c l (0) h l, h l =, где C l (0) =.

22 i q r (n-1) kln l+1… O 1 t = jt = j t= t t = t lim t = 0t = 0

23 i q r(n-1) kln l+1… O 1 t=t lim Окончательное распределение

24 Свойство эргодичности Однородная сеть при W > T является неэргодической системой: предельное состояние в ней всегда зависит от начального. Только вершины, имевшие запас ресурса в начальном распределении, могут сохранить излишек в предельном состоянии.

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

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

27 Матрицей проводимости будем называть матрицу R = ||r ij || n n. Матрица проводимости Свойства матрицы проводимости: 1. R – неотрицательная матрица: i, j r ij 0 2. i r ii > 0 3. i, j (r ij > 0 r ji > 0) Несимметричные сети

28 Входная и выходная проводимости Суммарную проводимость входных ребер вершины v i будем называть ее входной проводимостью и обозначать: Суммарную проводимость выходных ребер, назовем выходной проводимостью и обозначим через: Проводимость петли входит в обе суммы. r3ir3i r1ir1i r2ir2i r4ir4i riirii i ri1ri1 ri2ri2 ri4ri4 riirii i ri3ri3

29 Входная и выходная проводимости вершины v1v1 v2v2 v3v3 v4v4 v5v5 v1v v2v v3v v4v v5v

30 Классификация сетей Ресурсная сеть называется: однородной, если все элементы матрицы R одинаковы: r ij = r i,j, и неоднородной в противном случае; симметричной, если симметрична ее матрица проводимости; квазисимметричной, если i: (1) несимметричной, если она не удовлетворяет условию квазисимметричности (1), то есть существует хотя бы одна вершина (таких вершин будет как минимум две), для которой выполнится:

31 Обозначим через r i разность между входной и выходной проводимостями вершины v i : Классификация вершин несимметричной сети Тогда все вершины сети делятся на три вида: вершины-приемники, для которых r i > 0 ; вершины-источники, для которых r i < 0 ; нейтральные вершины, для которых r i = 0. r i = Суммарной проводимостью сети, r sum, назовем сумму проводимостей всех ее ребер:

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

33 Правила функционирования сети Распределение ресурса в сети происходит по одному из двух правил, выбор которых зависит от величины ресурса в вершинах. В момент t + 1 вершина v i в ребро, соединяющее ее с вершиной v k, отдаст: правило 1: r ik единиц ресурса, если правило 2: в противном случае.

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

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

36 Свойства вершин-источников и нейтральных вершин Свойство 1. В процессе функционирования несимметричной сети ресурс в нейтральных вершинах может временно стабилизироваться, а затем снова изменяться. Свойство 2. Если для некоторого t' q i (t'), то для всех t > t' q i (t) l). Множество вершин с ресурсом q i (t), меньшим, – зона Z – (t). Из свойства 2 следует, что источники и нейтральные вершины, раз попав в Z –, уже не смогут ее покинуть. Поскольку для них выполняется:

37 tv1v2v3v4v5tv1v2v3v4v … … … Пример 1. Временная стабилизация ресурса в нейтральных вершинах (св-во 1). W = 100, n = 5. Ресурс находится в вершине-источнике: Q(0)=(0, 100, 0,0,0).

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

Пример 2. Нейтральная вершина остается в зоне Z + W = 100, n = 5. Ресурс в нейтральной вершине ( вершина v 5 ), связанной только с приемником v 1 (у вершины v 5 нет неположительных путей) tv 1 v 2 v 3 v 4 v …

40 Пороговое значение ресурса Т Теорема 4. В несимметричной сети существует пороговое значение суммарного ресурса Т, такое, что при W Т все вершины, начиная с некоторого t', переходят в зону Z – (t) ; при W > T зона Z + (t) непуста для любого t. Т единственно и не зависит от суммарного ресурса W и его начального распределения Q(0). Для однородных сетей выполняется равенство: Т = r sum. Для несимметричных сетей Т < r sum.

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. Ресурс в первом приемнике. tv 1 v 2 v 3 v 4 v …

45 Пример 4. Сеть с двумя приемниками. W = 100, n = 5. Ресурс во втором приемнике, но все равно ресурс забирает первый. tv 1 v 2 v 3 v 4 v … … …

46 Вершину, способную в предельном состоянии остаться в зоне Z +, назовем потенциальным аттрактором. Если приемники имеют разные входные и выходные проводимости, в сети существует единственный потенциальный аттрактор. Классификация вершин

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

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

49 Пример 5. Сеть с двумя равными приемниками (куда положили, там и останется). W = 100, n = 5. Ресурс в первом приемнике. tv 1 v 2 v 3 v 4 v … Ресурс вершины v 2 стремится к значению ее выходной проводимости снизу; этот приемник не сможет перейти с правила 2 на правило 1. Таким образом, если весь ресурс в одном из потенциальных аттракторов, остальные останутся в зоне Z - (t).

50 Пример 6. Сеть с двумя равными приемниками. W = 100, n = 5. Ресурс во втором приемнике. tv 1 v 2 v 3 v 4 v … Ресурс вершины v 1 стремится к значению ее выходной проводимости снизу.

51 Пример 7. Сеть с двумя равными приемниками. W = 100, n = 5. Ресурс в первом источнике ( вершина v 3 ). tv 1 v 2 v 3 v 4 v … … … Оба потенциальных аттрактора переходят в Z + (t), но набирают разное количество ресурса.

52 Пример 8. Сеть с двумя равными приемниками. W = 100, n = 5. Ресурс в нейтральной вершине ( вершина v 5 ). tv 1 v 2 v 3 v 4 v … … …

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

54 Пример 9. Сеть с двумя неравными приемниками. W = 100, n = 5. Ресурс в нейтральной вершине. tv 1 v 2 v 3 v 4 v … В Z + (t) оказывается более «слабый» приемник, потому что он «паразитирует» на сильном.

55 Пример 10. Изменим проводимость ребра r 12 на 1. W = 100, n = 5. Ресурс в нейтральной вершине. tv 1 v 2 v 3 v 4 v … В Z + (t) оказывается «сильный» приемник – «слабому» уже не хватает мощности.

Пример 11 (совпадает с примером 1). Потенциальный аттрактор – нейтральная вершина. W = 100, n = 5. Ресурс в нейтральной вершине ( вершина v 5 ), связанной только с источником tv 1 v 2 v 3 v 4 v …

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

58 Классификация сетей по наличию потенциальных аттракторов (W>T) Все вершины однородной сети являются пассивными аттракторами. Однородная сеть представляет собой неэргодическую систему. Несимметричная сеть с одним (потенциальным) аттрактором всегда будет эргодической системой. Несимметричная сеть с более чем одним потенциальным аттрактором является частично эргодической: координаты вектора предельного состояния для не-аттракторов не зависят, а для потенциальных аттракторов зависят от начального распределения ресурса

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

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

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

62

63 Публикации 1. О.П. КУЗНЕЦОВ. Однородные ресурсные сети I. Полные графы. // Автоматика и телемеханика, 2009, 11, с О.П. КУЗНЕЦОВ, Л.Ю. ЖИЛЯКОВА. Двусторонние ресурсные сети – новая потоковая модель. // Доклады Академии Наук, 2010, том 433, 5, с. 609–612.

64 СПАСИБО ЗА ВНИМАНИЕ