При реализации некоторых задач в ориентированных графах приходится строить замкнутые пути-контуры. Особенно они широко стали применяться с внедрением современных информационных технологий в банковских системах, в системах электронных переводов денег и других областях человеческой деятельности. Если в 60-х годах прошлого века в задачах сетевого планирования замкнутые контуры считались отрицательным явлением, они выявлялись для ликвидации, то в настоящее время замкнутые контуры в задачах взаимных расчетов стали «палочкой-выручалочкой».
При реализации некоторых задач электронных платежных систем приходится строить замкнутые схемы (контуры) прохождения платежных поручений по расчетным счетам и определять такую последовательность схемы проведения взаиморасчетов, чтобы общая сумма выполненных платежных поручений была бы максимальной, т.е. решается оптимизационная задача замкнутых контуров. Такие взаиморасчеты позволяют выполнить часть платежных поручений, не снижая текущего объема средств расчетных счетов. Алгоритмы оптимизации двухсвяззанных и многоуровневых замкунтых контруов представлены в [1, 2]. В данной статье рассматривается оптимизация многосвязанных контуров, т.е. обобщенная постановка задачи.
Задача снижения взаимозадолженностей предприятий с применением ориентированных графов решается в двух этапах. На первом этапе строятся замкнутые контуры, а на втором – определяется оптимальная последовательность выполнения платежных поручений по замкнутым схемам.
Существующие алгоритмы построения путей в сетях в основном осуществляются путем поиска с возвратом, и поэтому в многоразмерных графах поиск путей замкнутых контуров занимает достаточно длительное время даже на современных ЭВМ. Выходом из положения могут стать удаления из графов лишних дуг, не участвующих в замкнутых контурах, и таким образом уменьшить размерность задачи и, соответственно, время построения замкнутых контуров.
Итак, пусть задан ориентированный граф (орграф) , где — множество вершин, — множество его дуг. Если — дуга, то вершина называется началом дуги , а — концом. По отношению к вершине дуга является выходной дугой, а для — входной. Для вершин множества введем функции , указывающие количество входных дуг вершины , и — количество выходных дуг. Вершины, не имеющие входных дуг, называются корнями орграфа, а вершины, не имеющие выходных дуг, называются ветвями орграфа.
Определение. Ориентированный граф считается подстриженным, если для всех его вершин .
Приведем алгоритм стрижки орграфов.
Шаг 1. Для всех вершин множества вычисляем и . Далее для каждой дуги выполняем последовательно шаги 2 и 3 алгоритма.
Шаг 2. Рассматривая очередную дугу из множества , проверяем и . Для каждой дуги, для которой выполняется хотя бы одно из этих условий, производятся вычисления в соответствии с 3-им шагом. Иначе рассматриваем следующую дугу.
Шаг 3. Из множества исключаем дуги следующим образом. В зависимости от того, какое условие выполнилось на предыдущем шаге, либо из значений или , либо из значений или отнимаем единицу. Корректировке подвергается один из , , или , у которого текущее значение отличается от нуля. Переход ко 2-ому шагу.
Если при рассмотрении дуг множества хотя бы один раз выполняется 3-й шаг алгоритма, то действие шагов 1-3 алгоритма повторяется снова. В противном случае, заканчивая работу алгоритма, получаем подстриженный орграф.
Утверждение. Подстриженный ориентированный граф имеет хотя бы один контур.
Действительно, если орграф подстриженный, то его вершины принадлежат либо некоторому замкнутому контуру, либо пути, соединяющему разные контуры. В противном случае, этот путь был бы тупиковым, что противоречит условию. Следовательно, если подстриженный орграф не пустой, то в нём обязательно будет контур.
Для реализации второго этапа задачи введем обозначения:
Аi – расчетный счет клиента i (отправителя) в банке;
Аj – расчетный счет клиента j (получателя) в банке;
Sij – величина платежных поручений, отправляемых от клиента Аi клиенту Аj .
Предположим, выявлено несколько замкнутых контуров Сk =, …, (k=1,2,3….,m), которые составляют цепочку списков платежных поручений. По каждому контуру определим его пропускную способность Sk,=min {}. Тогда общая сумма потенциально возможных осуществляемых платежных поручений по контурам составит , где nk – количество платежных поручений контура Сk.
Если контур связан с контуром , тогда выполнение платежных поручений по контуру возможно уменьшит пропускную способность контура на величину Sk, т.е. пропускная способность общих дуг контуров и будет .
Составим квадратную матрицу , размерность которой равна количеству связанных контуров m. Для каждого контура Сk отведем одну строку матрицы. Диагональ матрицы заполняем величиной . Остальные столбцы j строки i заполняем величиной
где i, j=1, 2, …, m; .
Сумма элементов каждой строки (i=1, 2, …, m) матрицы означает потенциально возможный объем выполняемых платежных поручений, если взаиморасчет осуществляется по схеме Сi первым. Поэтому для достижения максимального значения общей суммы выполняемых платежных поручений необходимо упорядочить контуры Ск по убыванию значений и по этой последовательности схем провести взаиморасчеты. Алгоритм оптимизации последовательности выполнения платежных поручений многосвязанных контуров покажем на численном примере.
Пусть задано семь взаимосвязанных контуров (см. рисунок):
C1(А1, А2 , А6 , А3 , А1), C2(А3, А4 , А5 , А6 , А3), C3(А3, А4 , А8 , А7, А3),
C4(А7, А11 , А12 , А8 , А7), C5(А5, А6 , А10 , А9, А5), C6(А9, А13 , А14 , А10, А9) и C7(А11, А12 , А13 , А14, А11).
А3 А4 А5А6
А7 А8А9А10
А11А12А13А14
Определим S1 = min {S12 , S26 , S63 , S31 } = min {10, 10, 40, 10}=10;
S2 = min {12, 10, 11, 40} = 10; S3 = min {12, 8, 11, 9} = 8;
S4 = min {7, 8, 9, 11} = 7; S5 = min {11, 7, 10, 7} = 7;
S6 = min {7, 8, 6, 10} = 6; S7 = min {8, 3, 8, 3} = 3;
Количество дуг в контурах равно: n1= n2 = n3 = n4 = n5 = n6 = n7 = 4.
Определим связанность контуров. Контур C1 связан с контуром C2; C2 связан с контурами C1, C3 и C5; контур C3 связан с контурами C2 и C4; контур C4 связан с контурами C3 и C7; контур C5 связан с контурами C2 и C6; контур C6 связан с контурами C5 и C7; контур C7 связан с контурами C4 и C6.
Вычислим элементы диагонали матрицы: r11 = S1× n1= 40; r22 = S2 n2 = 10×4 = 40; r33 = S3× n3 = 8× 4 = 32; r44 = S4× n4= 7×4 = 28; r55 = S5× n5 = 7× 4 = 28; r66 = S6× n6= 6×4 = 24 и r77 = S7× n7 = 3× 4 = 12.
Элементы диагонали и другие элементы матрицы переносим в таблицу, и вычислим значения :
| С1 | С2 | С3 | С4 | С5 | С6 | С7 | ||
| С1 | 40 | 40 | 32 | 28 | 28 | 24 | 12 | 204 |
| С2 | 40 | 40 | 8 | 28 | 4 | 24 | 12 | 156 |
| С3 | 40 | 16 | 32 | 12 | 28 | 24 | 12 | 164 |
| С4 | 40 | 40 | 16 | 28 | 28 | 24 | 4 | 180 |
| С5 | 40 | 16 | 32 | 28 | 28 | 12 | 12 | 168 |
| С6 | 40 | 40 | 32 | 28 | 16 | 24 | 8 | 188 |
| С7 | 40 | 40 | 32 | 20 | 28 | 20 | 12 | 192 |
Упорядочивая по убыванию его значений, получим .
Соответствующая этому неравенству последовательность контуров показывает оптимальную схему проведения электронных взаиморасчетов.
Общая сумма выполняемых платежных поручений будет равнаS = 40+12+20+20+20+24+24=160 единицам.
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
- Абдугафаров А., Дадажанов Т.К., Мирзаев Х.М.Алгоритм оптимизации снижения взаимной задолженности // Узб. журн. Проблемы информатики и энергетики. № 3, Ташкент, 2004. – с. 10-14.
- Абдугафаров А. К вопросу оптимизации многоуровневых контуров. // Узб. журн. Проблемы информатики и энергетики. № 6, Ташкент, 2005. – с. 23-27.