Содержание к диссертации
Введение
1. Глава 1. Клиринговые системы. Анализ возможностей 8
1.1. Экономические предпосылки необходимости создания математических моделей клиринговых систем 8
1.2 Цели и задачи моделирования клиринговых систем 19
1.3 Обзор существующих моделей клиринговых систем 22
1.4 Выводы 38
2. Глава 2. Непрерывные модели клиринговых систем 39
2.1 Процедуры построения непрерывных потоковых моделей 39
2.2 Первая непрерывная потоковая модель с приоритетами 43
2.3 Вторая непрерывная потоковая модель 55
2 4 Информационная-аналитическая система для реализации взаиморачсчета между предприятиями 56
3. Глава 3. Дискретная потоковая модель клиринговых систем 64
3.1 Построение дискретной потоковой модели 67
3.2 Непрерывный аналог дискретной потоковой модели 71
3.3 Эвристический алгоритм решения задачи о наборе суммы по подмножеству 77
3.4 Сравнительный анализ предложенного эвристического алгоритма с известными полиномиальными алгоритмами 81
3.5 Численное исследование дискретной потоковой модели 82
3.6 Информационно-аналитическая система для реализации межбанковского клиринга 84
3.7 Сравнительный анализ дискретной потоковой модели и известных методов расчетов клиринговых систем 96
Заключение 98
Список литературы 100
- Цели и задачи моделирования клиринговых систем
- Первая непрерывная потоковая модель с приоритетами
- Информационная-аналитическая система для реализации взаиморачсчета между предприятиями
- Эвристический алгоритм решения задачи о наборе суммы по подмножеству
Введение к работе
Актуальность темы
Данная работа посвящена математическому исследованию возможностей клиринговых систем как механизма развязывания неплатежей и погашения взаимной задолженности между субъектами экономической деятельности (предприятиями, банками и бюджетами разных уровней). Связано это с тем, что проблема погашения долгов предприятий и банков по-прежнему остается одной из серьезнейших проблем экономики России. Кризис неплатежей до сих пор является серьезной преградой на пути устойчивого экономического роста, потому что предприятия-неплательщики не могут ни привлечь инвестиции для своего развития, ни погасить значительные недоимки в бюджет. Как следствие, товарно-денежные отношения, характерные для нормально функционирующей рыночной экономики, все в большей степени вытесняются бартером.
Одним из важнейших и приоритетных направлений деятельности кредитных организаций является расчетно-кассовое обслуживание своих клиентов. Экономический и финансовый кризис, который пришелся на 17 августа 1998 года, обострил проблему неплатежей между субъектами экономической деятельности, что выразилось в резком увеличении сроков проведения платежей. Система кредитных организаций России существенно утратила ликвидность, вал неплатежей между предприятиями усилился неплатежами между банками. Скорость функционирования системы взаимных расчетов упала до опасного для жизнедеятельности экономики уровня, что привело к тому, что размер оборотных средств необходимых для поддержания производства часто оказывался неприемлемым. Несмотря на то, что остроту кризиса 1998 года к настоящему времени удалось несколько ослабить, тем не менее его последствия до сих пор оказывают самое негативное влияние на функционирование всей кредитно-денежной системы России о чем свидетельст-
вуют данные Госкомстата России о соотношении поступлений и недоимки в бюджетную систему России за 1995-2001 гг. приведенные ниже. Кроме того никто не может гарантировать, что дефолт 1998 года никогда не повторится, и поэтому нужно быть готовым, в случае возникновения подобной ситуации в будущем, выйти из нее с минимальными для общества издержками для чего нужно иметь соответствующие опробованные механизмы.
Многообразие причин, вызывающих неплатежи, не позволяет с помощью какой-либо одной меры ликвидировать неплатежи или, по крайней мере, радикально снизить их уровень и изменить тенденцию к росту взаимной задолженности. Поэтому разработка системных подходов, методик и алгоритмов, нацеленных на снижение уровня неплатежей между субъектами экономической деятельности, являются актуальными, практически значимыми и полезными.
Цель и задачи исследования
Основная цель исследования состоит в разработке информационно-аналитической системы, включающей в себя современные реляционные СУБД, модели, методы и алгоритмы, которые в применении к клиринговым системам позволят существенно снизить уровень неплатежей или потребности в оборотных средствах между субъектами экономической деятельности. В соответствии с целью исследования поставлены следующие задачи:
анализ возможностей существующих клиринговых систем;
моделирование клиринговых систем как потоковых задач в некоторой специальным образом построенной сети;
разработка потоковой модели, позволяющей снизить уровень взаимной задолженности между предприятиями и бюджетом;
разработка потоковой модели, позволяющей снизить уровень взаимной задолженности между предприятиями без участия бюджета;
моделирование возможных жизненных ситуаций, которые могут возникнуть при реализации на практике упомянутых выше двух потоковых моделей;
разработка дискретной потоковой модели клиринговых систем для погашения платежей в системе кредитных организаций с фиксированным размером подкрепления (модель ДПМ);
анализ существующих алгоритмов решения модели ДПМ;
разработка оригинального полиномиального эвристического алгоритма решения модели ДПМ;
численное исследование модели ДПМ;
разработка информационно-аналитической системы реализующей все перечисленные выше модели.
Объект исследования
Объектом исследования являются клиринговые системы.
Предмет исследования
Предметом исследования является процесс взаимных расчетов между субъектами экономической деятельности Российской Федерации.
Теоретические и методологические основы исследования
Теоретическую и методологическую основу диссертации составляют труды российских и зарубежных ученых-экономистов и математиков по методам системного анализа, методам экономико-математического моделирования, теории исследования операций, теории графов, теории управления.
Информационную основу для анализа и проведения сравнительных расчетов составляют статистические данные о взаимных задолженностях субъектов экономической деятельности республики Башкортостан.
Научная новизна исследования
Разработана информационно-аналитическая система, которая в применении к клиринговым системам позволяет усовершенствовать известные и предложить новые подходы к процессу оптимизации взаимных расчетов между субъектами экономической деятельности, а именно:
впервые предложено рассматривать клиринговые системы как
потоковые задачи в некоторой специальным образом построен
ной сети;
На основе предложенного подхода:
разработана потоковая модель, позволяющая снизить уровень взаимной задолженности между предприятиями и бюджетом. Для ее решения используется известный эффективный алгоритм наикратчайших путей поиска максимального потока;
разработана потоковая модель, позволяющая снизить уровень взаимной задолженности между предприятиями без участия бюджета. Для ее решения используется известный эффективный алгоритм поиска циркуляции минимальной стоимости;
разработана дискретная потоковая модель клиринговых систем для погашения платежей в системе кредитных организаций с фиксированным размером подкрепления (модель ДПМ);
разработан оригинальный полиномиальный эвристический алгоритм решения модели ДПМ;
проведено численное исследование модели ДПМ, показавшее высокую эффективность предложенного алгоритма;
разработана информационно-аналитическая система реализующая все перечисленные выше модели и учитывающая возможные
жизненные ситуации, которые могут возникнуть при реализации этих моделей на практике.
Практическая значимость
Модели, методы и алгоритмы, разработанные в исследовании, применялись в Международном институте инвестиционных проектов при разработке НИР «Методы повышения эффективности клиринговых расчетов как механизм снижения уровня неплатежей» на примере республики Башкортостан в 2000-2001гг.
Публикации
Основные результаты исследования отражены в трех публикациях автора общим объемом 1.8 п.л.
Апробация результатов исследования
Основные положения исследования докладывались и обсуждались на научном семинаре «Клиринг и межбанковские финансовые операции» в Институте системного анализа РАН, состоявшемся 25 сентября 2001г.
Результаты исследования докладывались на научном семинаре в Международном институте инвестиционных проектов, состоявшемся 4 декабря 2001г.
Структура и объем работы
Диссертация состоит из введения, трех глав и заключения. Основное содержание диссертации изложено на 99 страницах печатного текста. Список использованной литературы составляет 86 наименований.
Цели и задачи моделирования клиринговых систем
Решить проблему восстановления управляемости расчетной системы обеспечения ее прозрачности можно только создав альтернативный механизм осуществления расчетных операций, направленный на ускорение оборачиваемости имеющейся денежной массы.
Для решения данной проблемы на федеральном и региональном уровне представляется перспективным создание региональных электронных центров взаиморасчетов, которые на основании информации о дебиторско-кредиторской задолженности предприятий выстраивают замкнутые цепочки и производят электронный взаиморасчет.
В настоящее время разработана система мер, позволяющая разрешить перечисленные проблемы без денежной эмиссии и эмиссии денежных суррогатов на основе создания механизма хозяйственного и бюджетного клиринга. Суть клиринга состоит в функционировании унифицированного механизма расчетов, который дает возможность в денежной форме выразить и урегулировать все виды встречных требований. При этом появится эффективная альтернатива неденежным расчетным операциям (бартеру, зачетам, денежным суррогатам) и восстановится нормальное функционирование системы денежного обращения в стране.
С целью ускорения оборачиваемости денежной массы предлагается внедрить инструменты клиринговых расчетов, направленные на погашение просроченной задолженности бюджетной системы и недоимки хозяйствующих субъектов по налогам и другим обязательным платежам перед бюджетной системой. На этой же основе может осуществляться урегулирование иных видов просроченной дебиторско-кредиторской задолженности организаций и расшивка неплатежей в народном хозяйстве.
Предлагаемый механизм расчетов может быть организован либо через систему Банка России, либо через систему коммерческих банков. Для его реализации через систему Банка России потребуется внести изменения в за конодательство, разрешающие открывать счета хозяйствующих субъектов в Банке России. Для реализации через систему коммерческих банков достаточно решения Правительства РФ. В указанном решении должен быть определен уполномоченный банк, в котором откроют корсчета остальные банки. Таким банком может быть любой банк, выбранный Правительством РФ.
Внедрение указанной системы мер позволит в полном объеме исполнять бюджетные обязательства, даст мощный импульс для совершенствования рыночных отношений в Российской Федерации, позитивно повлияет на работу предприятий, выполняющих государственный заказ, предприятий военно-промышленного комплекса, предотвратит инфляционный процесс. При этом будет ограничено участие посредников, вызванное отсутствием в настоящий момент платежных средств, укреплена бюджетная и банковская система на федеральном, региональном и местном уровнях. Существенно упростится хозяйственное взаимодействие, контрольно-ревизионная работа, возрастут налоговые доходы бюджетной системы.
Взаиморасчеты между предприятиями и банками в нынешней ситуации позволяет существенно снизить задержки в проведении платежей, поскольку реализуется идея взаимного зачета, и каждый участник гарантированно получает ту сумму средств, которая уходит от него его партнерам. Взаиморасчеты предназначены для развязки просроченных и текущих задолженностей между предприятиями и бюджетом без привлечения каких-либо денежных средств для осуществления расчетов.
Существуют ряд трудностей при применении идеи взаиморасчета: сложность оперативного сбора информации, сомнительность ее достоверности, недостаточная скорость реагирования на быстро меняющуюся ситуацию, проблемы уплаты налогов и прочие. Однако, несмотря на перечисленные трудности, можно настолько усовершенствовать процедуру взаиморасчета, что она станет обычным и часто используемым приемом для регулирования внутрихолдинговых отношений и для восстановления нормальных хозяйственных связей на уровне регионов и России в целом.
В последние десятилетия объем финансовых потоков между кредитными организациями на западе существенно возрос. При этом возрос не только общий объем взаимных платежей, в гораздо большей степени увеличилось количество платежей, подлежащих обработке. Подобный резкий рост уровня взаимных расчетов может произойти и в России.
Обработка столь большого количества платежей стала возможна благодаря использованию электронных расчетных систем и расчетов на клиринговой основе [18,39,54,67].
В отличие от валовых расчетов, при которых каждый платеж обрабатывается последовательно, клиринг осуществляет многосторонний зачет взаимных встречных платежей участников, причем оплате подлежит только разница между суммами взаимных обязательств.
Клиринг представляет собой, в самом общем виде, систему безналичных расчетов за товары и услуги, основанную на зачете взаимных требований и обязательств и использующуюся банками в целях снижения нуждаемости в средствах и упрощения обмена платежами.
Как известно, расчеты по платежам могут производиться либо на валовой, либо на чистой основе. В первом случае расчеты по каждой сделке осуществляются отдельно, во втором — банки, участвующие в производстве платежей, дают возможность требованиям и обязательствам накопиться на протяжении определенного периода времени (как правило, это один операционный день). В конце данного периода проводятся расчеты только по взаимно зачтенным обязательствам. Такой взаиморасчет сумм кредиторской и дебиторской задолженности может иметь место между двумя сторонами (двусторонний взаиморасчет) или тремя и более сторонами (многосторонний взаиморасчет).
Первая непрерывная потоковая модель с приоритетами
Рассмотрим первый алгоритм взаиморасчета долгов между предприятиями. Во взаиморасчете могут участвовать государственные органы управления бюджетом, ГНИ и предприятия.
Будем задолженности предприятий друг другу описывать с помощью ориентированного графа, узлы которого соответствуют самим предприятиям, а дуги - их задолженностям, причем направление дуги всегда от дебитора к кредитору.
Итак, пусть задан ориентированный граф G=[H,U], где Н - множество вершин, a U - множество дуг графа. Будем обозначать каждую дугу ueU графа упорядоченной парой (xisXj), где Xj - начало дуги, a Xj - ее конец (XJGH,XJGH).
Пусть u = (XJ,XJ). Тогда обозначим через С(и) заданную положительную величину задолженности предприятия Xj предприятию Xj, (заметим, что между двумя узлами Xj и Xj может существовать несколько «параллельных» дуг по числу задолженностей между соответствующими предприятиями).
Пусть L = {xi,x2,...,xN} - заданный линейный порядок, где Х[ - предприятие с наивысшим приоритетом (всегда бюджет), xN - предприятие с самым низким приоритетом, N 2. Приоритет предприятий за исключением бюджета можно выставлять в зависимости от его статуса в регионе, объема задолженности или по каким-нибудь другим неформальным признакам.
Пусть f(u) - неизвестная величина погашения задолженности по дуге и по взаиморасчету. Тогда формально задача взаиморасчета может быть сформулирована следующим образом: lex max (f(x,,H),f(x2,H),..., f(xN.,,H),f(xN,H)) (2) №)} f(x,H)-f(H,x) = 0,xeH (3) 0 f(u) C(u), иєА,(х), хєН (4) О f(u) C(u) 0 (I [f(u) - C(u)]), ueA2(x), xeH (5) ueAi(x) Здесь: f(x,H) = Z f(u), f(H,x) = I f(u), где A(x) = {u=(p,q)eU I p=x}, иєА(х) ueB(x) B(x) = {u=(p,q)eU q=x}, A,(x) = {u-(x,x,) eU}, A2(x) = A(x)\A,(x), 0(z) - функция Хэвисайда: 0(z) = 1, если z 0; 0(z) = 0, если z 0. Сумма по пустому множеству в формуле (5) по определению полагается равной 0.
Формула (2) определяет целевую функцию от многих переменных. Лексикографический максимум следует понимать так: сначала ищется максимум для первого выражения (в данном случае для f(xbH)), затем при фиксированном значении этого максимума ищется максимум для второго выражения (в данном случае для f(x2,H)) и т.д. и, наконец, при фиксированном значении максимумов для всех предыдущих выражений ищется максимум для последнего выражения (в данном случае для f(xN,H)).
Формула (3) - это условия нулевого баланса, т.е. сколько средств приходит к предприятию от дебиторов по взаиморасчету, столько же передается другим предприятиям-кредиторам.
Формула (4) указывают, что величина погашения по каждой задолженности не может превышать саму задолженность.
Формула (5) задает очередность потока: пока для узла х хі не будут насыщены все дуги ведущие в узел X] не допускается пропускать поток по остальным дугам, выходящим из узла х.
При решении задачи (2) - (5) использовать классический алгоритм Форда-Фалкерсона (АФФ) [71], нельзя, так как в этом случае он не гарантирует выполнение очередности платежей, о которой говорилось выше. Для учета очередности платежей предлагается использовать алгоритм кратчайших путей (АКП) [1], который позволяет наращивать максимальный поток от источника к стоку кратчайшим путем. Это позволяет первоначально погашать задолженность перед бюджетом, а затем уже между предприятиями. Ранг вершины сети. Нам понадобятся некоторые определения из теории графов. Длиной пути L мы будем называть число принадлежащих ему дуг (более общее определение длины пути мы не рассматриваем). Мини t it мальный для пути L из V в V называется кратчайшим, его длина - расстоянием l(v ,v") от V до V . Расстояние / (s, v) от источника S до вершины V называется рангом Г (v) последней в рассматриваемой сети (относительно полюса S). Ранг источника S равен нулю, а ранги не достижимых из S вершин равны + оо.
Лемма о сегментах. Пусть L= {li\,...uj - кратчайший путь из Vo в V/ , a VQ, V/,..., V/ - последовательность его вершин. Тогда любой сегмент Li у— {lii,... Uj/ пути L является кратчайшим путем из начала Ui_/ своей первой дуги в конец V, последней дуги Uj. )
В противном случае, заменив этот сегмент более коротким путем L —{ll i ,... Ufm} из V,./ в Vj , мы получим более короткий путь L — ]ul9...,ui_l,ul,...,um,Uj+l,...9ulf из VQ eV/ Лемма об изменении рангов вдоль дуги. Пусть U - произвольная дуга і it рассматриваемой сети, V - ее начало, "У - конец. Тогда r(v") r(v ) + l. Если же и принадлежит кратчайшему пути L ={Uj,...,Uk=U,..., uj из S в любую вершину УЄ V, то r(v") = r(v ) + l. Модификация АФФ, в которой на каждой итерации находится крат-чайший увеличивающий путь, называется алгоритмом кратчайших путей (АКП). Число итераций в нем не превосходит П3 , т.е. конечно. Точность этой оценки доказана Н. Заде построением экстремального примера. Теорема о монотонном изменении рангов. Пусть/- поток в сети G, L - кратчайший путь из S в t в сети Gf, фL - поток в сети Gf вдоль пути L, f = f PL. Тогда в сети Gf ранги всех вершин УЄ V относительно вершины S не меньше чем в сети Gf. Из этой теоремы сразу следует, что при АКП ранги V (v) вершин VG V в сетях Gf монотонно не убывают (здесь и далее индекс в обозначении ранга Г (v) опускаем).
Информационная-аналитическая система для реализации взаиморачсчета между предприятиями
Данная глава посвящена так называемой дискретной модели клиринга. По-прежнему модель клиринга ассоциируется с некоторой потоковой задачей в специальным образом построенной сети. Однако ее основное и принципиальное отличие от моделей рассмотренных в главе 2 состоит в том, что величина потока в сети складывается из множества «неделимых» составляющих, каждая из которых либо целиком входит в поток, либо не входит в него вовсе. Практическим приложением такой модели является классический межбанковский клиринг, где величина потока складывается из множества платежных поручений клиентов банка. Однако существенным отличием предлагаемой модели от классического межбанковского клиринга является то, что здесь заранее фиксируются так называемые подкрепления банков, что превращает модель в NP-полную задачу целочисленного линейного программирования. Для решения поставленной задачи предлагается использовать ее сетевую специфику и находить решение релаксированной задачи алгоритмом «дефекта» Форда-Фалкерсона, а затем уже для каждой дуги решать известную в литературе задачу о наборе суммы по подмножеству. Для последней задачи предлагается оригинальный полиномиальный эвристический алгоритм, который сравнивается с самыми быстрыми на сегодняшний день приближенными полиномиальными алгоритмами Бабата Л.Г. [7] и Лоуэра [79]. Проводятся численные эксперименты, показывающие эффективность предложенного алгоритма.
Для развязки неплатежей между банками Центральный банк России (ЦБ) трижды проводил сеансы взаиморасчетов (правда, как оказалось только по платежам в бюджет), позволив банкам задействовать их "неприкосновенный запас" - зарезервированные суммы на корреспондентских счетах в ЦБ [66]. Однако, хотя эти разовые мероприятия и позволили несколько смягчить
кризис неплатежей, они не превратились в систему. При нормальной работе банковской системы наиболее подходящим решением для ускорения прохождения платежей между банками и уменьшения реального потока платежных средств между ними является создание клиринговых палат или домов. Поясним сказанное на примере двух банков, когда клиринг происходит на чистой основе. Если в течение операционного дня банк "А" должен перечислить банку "Б" 100 млн. руб., а банк "Б" банку "А" - только 40 млн. руб., то согласно методологии многостороннего клиринга [54] для каждого банка рассчитывается его позиция как разница между тем, что он должен и тем, что ему должны и, если эта позиция положительна, то банк обязан закрыть позицию или, другими словами, перевести на специальный счет только сумму, равную величине этой позиции. В данном примере позиция банка "А" - +60 млн. руб., а позиция банка "Б" - -60 млн. руб. Поэтому по клирингу банк "А" должен перечислить на специальный счет только 60 млн. руб., а банк "Б" вообще не должен делать никаких перечислений (ему наоборот придут средства со специального счета в размере 60 млн. руб.). Несмотря на очевидные плюсы, такая технология имеет и существенный минус - у каждого банка должно быть достаточно средств, чтобы закрыть свою позицию. В данном примере у банка "А" должно быть в наличии 60 млн. руб.
В предлагаемой нами схеме взаиморасчета суммы взаимных задолженностей могут погашаться частично на максимально возможную величину, при которой позиция каждого банка остается нулевой или не превосходит заранее заданной величины (об этом будет сказано ниже). Так в нашем примере сумма, погашаемая в результате взаиморасчетов между банками "А" и "Б", составит 40 млн. руб. В результате проведения взаиморасчета банк "Б" уже ничего не должен будет банку "А", а банк "А" останется должен банку "Б" -60 млн. руб., которые он может уже погашать обычным способом, т.е. вне рамок взаиморасчета в зависимости от своей платежеспособности.
Для проведения взаиморасчетов по предлагаемой схеме между банками должна существовать либо расчетная палата, либо банк с полной лицензией, в котором открыты корреспондентские счета других банков - участников взаиморасчета [23]. Если проводить взаиморасчет между предприятиями, то здесь, как правило, не возникает проблем с частичным погашением любой задолженности, так как имеется достаточно времени на согласование этого вопроса как с дебитором, так и с кредитором. В этом случае можно гарантированно строить схему взаиморасчета с нулевой позицией для каждого его участника. Однако совсем иная ситуация возникает, если проводить взаиморасчеты с банками в режиме реального времени. Не вдаваясь во все детали этой технологии, отметим только, что задолженности банков друг перед другом складываются из множества платежных поручений клиентов банков. Поэтому платежное поручение при взаиморасчете нельзя выполнить частично (его можно выполнить либо целиком, либо совсем не исполнять) [72]. Поэтому в общем случае даже теоретически может не существовать такого ненулевого взаиморасчета, при котором позиции всех банков были бы равны нулю. Исходя из этого предполагается, что для "сглаживания" дискретности по платежным поручениям, каждый банк резервирует (депонирует) в расчетной палате небольшую сумму "живых" денег (так называемое подкрепление), которую он готов потратить при проведении взаиморасчета. Отметим, что эта сумма, как правило, оказывается существенно меньше той общей суммы, которую банку удается погасить в результате взаиморасчета. Заметим также, что время на то, чтобы определить, какие платежные поручения можно погасить по взаиморасчету и сообщить об этом соответствующим банкам, у расчетной палаты очень ограничено. Все это накладывает достаточно жесткие ограничения на время решения поставленной задачи.
Эвристический алгоритм решения задачи о наборе суммы по подмножеству
Для решения задачи (8) - (10) построим специальную сеть G = [N,U], где N - множество узлов, a U - множество дуг сети. Множество N состоит из М + 1 вершин, пронумерованных от 0 до М. Вершины от 1 до М соответствуют банкам задачи. Вершина 0 - искусственная. Соединим вершины і и j графа направленной дугой u = (i,j) с началом в узле і и концом - в узле j, если имеется хоть одно платежное поручение от банка і к банку j (другими словами, если Ку 0). Кроме того соединим вершину 0 графа со всеми остальными вершинами и все остальные вершины - с вершиной 0. Полученное множество дуг и будет составлять множество U. Дуги, инцидентные узлу 0, будем называть искусственными, а остальные - естественными. Множество искусственных дуг обозначим через Uo, а естественных - через Uj. Очевидно, что множества Uo и U являются разбиением множества U. Припишем каждой дуге u = (i,j) число, которое будем называть верхней пропускной способностью дуги и и обозначать через c(u) = с (i,j). Первоначально числа c(i,j) формируются по правилу: c(id) = Xp,jk ecjm і 0и j 0; k = l С(0,І) = ОІДЛЯІ = Ї7М; c(j,0) = oo для j = l,M.
Зададим также на каждой дуге u = (i,j) функцию a(u) = a(i,j), которую будем называть ценой потока на дуге и. Функция а(и) определяется по формуле: а(и) = 0, если UGUO, и а(и) = 1, если UGUI.
Обозначим через F(u) = F(i,j) неизвестную функцию потока по дуге UGU. Тогда легко видеть, что, если условие (10) заменить на условие л ,є[0Д], i=W;j=m к=Щ, (ID то тогда задачу (8),(9),(11) можно свести к следующей задаче поиска максимального потока в сети G[N,U]: a(u) F(u) max (12) u F(u) F(i,N) - F(Nj)=0 дляі=0,М (13) 0 F(u) c(u) дляиеи. (14) Здесь так же, как и в [1], принято обозначать под F(i,N) сумму F (и) по всем дугам и, ИСХОДЯЩИМ ИЗ узла і, а под F(N,i) - по всем дугам, ведущим в узел і.
Для решения задачи (12)-(14) существует эффективный алгоритм циркуляции минимальной стоимости в сети. Опишем этот алгоритм. Задача нахождения циркуляции минимальной стоимости является более общей, чем задача о поиске максимального потока по крайней мере в трех отношениях: (а) как нижние границы, так и пропускные способности задаются для каждого дугового потока и рассматриваются непосредственно; (б) коэффициент стоимости для любой дуги имеет произвольный знак; (в) вычисления по этому методу могут начинаться с любой циркуляции, допустимой или нет, и с любого набора узловых чисел. Рассмотрим задачу в виде циркуляции, т.е. построим поток F, удовлетворяющий условиям F(x, N) - F(N, х) = 0 при всех х є N, (14а) Цх, у) F(x, у) С(х, у) при всех (х, у) є А (146) и минимизирующий линейную функцию стоимости Ta(x,y)F(x,y) А
Если нужно построить допустимый поток из s в t заданной величины v, минимизирующий функцию стоимости, то достаточно добавить обратную дугу (t, s) с L(t, s) = C(t, s) = v, a(t, s) = 0, чтобы получить задачу в форме циркуляции. Если требуется построить максимальный допустимый поток из s в t, минимизирующий функцию стоимости, то можно взять L(t, s) = 0, C(t, s) большим и a(t, s) отрицательным и большим по величине.
Допустимые циркуляции могут и не существовать. В этом случае алгоритм заканчивается выделением множества X узлов,для которого нарушаются условия следующей теоремы.
Теорема. Для того, чтобы ограничения (14а), (146) где 0 L(x, у) С(х, у), были допустимы, необходимо и достаточно, чтобы для всех XczN выполнялось неравенство С(Х,ХЛ) ЦХЛ,Х). Докажем эту теорему.
Пусть данная сеть есть [N; А], и предположим, что L и С - нижняя и верхняя граничные функции, определенные на А, где 0 L С. Допустимая циркуляция в сети [N; А] есть функция F, определенная на А и удовлетворяющая условиям (14а) и (146).
Расширим сеть [N; А] до сети [N ; А ], присоединив два узла s, t и множества дуг (s, N) и (N, і). Функция пропускной способности определяется на А формулами С (х, у) = С(х, у) - Цх, у), (х, у) є А C (s, х) = L(N, х), xeN С (х, t) = Цх, N), xeN
Легко проверить, что допустимая циркуляция F в сети [N; А] порождает поток F из s в t в сети [N ; А ] по правилу F (x, у) = F(x, у) - Цх, у), (х, у)єА F (s, х) = L(N, х), xeN F (x, t) = Цх, N), xeN
Необходимое и достаточное условие существования потока из s в t величины L(N, N) состоит в том, чтобы пропускные способности всех разрезов были не меньше L(N, N). Пусть (X , Хл ) - разрез, отделяющий s и t в сети [N ; А ]. Определим множество XczN и его дополнение ХЛ в N следующим образом:
