Оптимальное погашение задолженностей

Журнал "Аудит и финансовый анализ"

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

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

Долговые обязательства могут возникать между различными участниками экономических отношений. Это может быть государство или администрация отдельных регионов, это могут быть группы людей, например жители некоторого района, это могут быть отдельные предприятия или объединения предприятий и т.д. В рамках простейшей модели, которая будет здесь рассматриваться, все эти кредиторы и должники считаются равноправными. Отличаются они только по объему кредиторской и дебиторской задолженности, и поэтому для их обозначения мы будем использовать единый термин – предприятие.

Итак, пусть имеется n предприятий. Задолженности между предприятиями описываются квадратной матрицей A={a_ij}, элементы которой являются скалярными неотрицательными величинами a_ij, i,j=1,…,n. Величина a_ij показывает количество денежных средств, измеряемых в некоторой единой валюте, которое j-е предприятие должно i-у предприятию. В качестве критерия, характеризующего общий уровень задолженностей, выберем сумму дебиторской и кредиторской задолженности по всем предприятиям и обозначим ее W, где

Вторым аргументом у функции W будет матрица погашения, поэтому вместо нее пока стоит нулевая матрица.

Погашение задолженностей будем описывать неотрицательными величинами x_ij, i,j =1,…,n. Эти величины имеют следующий смысл. Если x_{ij £} a_ij, то это означает, что предприятие i “прощает” или гасит часть долга в размере x_ij предприятию j. Если же x_ij > a_ij, то предприятие i гасит весь долг a_ij и дополнительно принимает на себя долговое обязательство в пользу предприятия j в размере x_ij -a_ij.

Таким образом, если к исходному состоянию задолженностей, описываемому матрицей A, применить схему погашения долгов, описываемую матрицей X, то получится новая матрица долгов B={b_ij}, которую мы будем обозначать B=AÑ X, где

Для того чтобы при погашении долгов баланс долгов каждого предприятия не изменялся необходимо, чтобы величины x_ij удовлетворяли следующим условиям:

где

Матрицы X={x_ij}, удовлетворяющие этому условию, будем называть циркуляциями.

Применение схемы погашения, описываемой неотрицательной циркуляцией X к исходной матрице долгов A приводит к изменению общей задолженности, которая принимает следующий вид

Стремление к уменьшению общей задолженности приводит к постановке следующей оптимизационной задачи.

Найти наименьшее значение W(A,X) по всем неотрицательным циркуляциям X, и найти циркуляцию, которая реализует это наименьшее значение.

В математической записи задача имеет вид

Нетрудно видеть, что количество переменных в этой задаче равно (так как ), количество линейных ограничений, не считая условия неотрицательности, равно n, а целевая функция является выпуклой полиэдральной функцией. Методы решения таких задач хорошо разработаны, но сложность применения этих общих методов здесь заключается в том, что число переменных может быть очень большим и время решения может быть неприемлемым для пользователя. Так уже при n=100 число переменных равно 99 900. Поэтому естественно возникает вопрос о разработке специальных методов решения, позволяющих сократить время вычислений.

Прежде всего, получим более простое выражение для величины W(A,X). Разобьем выражение для W(A,X) на две суммы

Во второй сумме индексы i и j можно поменять местами и тогда получим

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

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

Прежде всего, отметим, что погашение долгов с помощью неотрицательной циркуляции X не меняет баланса долгов предприятий, т.е.

Действительно

Покажем также, что

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

Оптимальное погашение долгов будем строить последовательно. Сначала проведем погашение долгов между парами предприятий. Выберем два предприятия i-е и j-е и рассмотрим матрицу погашения X(i,j), у которой только два элемента x_ij и x_ji могут быть отличны от нуля. Поскольку X(i,j) – это неотрицательная циркуляция, то x_ij = x_ji = x³ 0. Положим .

Нетрудно видеть, что полученная матрица погашения X(i,j) является оптимальной матрицей погашения для пары предприятий i,j. Это следует из того, что в точке x достигается минимум функции

Обозначим V неотрицательную циркуляцию, равную сумме всех матриц X(i,j) по всем парам (i,j) таким, что i>j. Для исходной матрицы A проведем погашение с помощью циркуляции V. Полученная после погашения матрица B=AÑ V обладает рядом полезных свойств.

Если неотрицательная циркуляция X такова, что найдутся индексы i и j такие что и , то существует неотрицательная циркуляция, такая что для любых i и j, где i¹ j, и W(B,X)³ W(B,Z).

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

Первое свойство очевидно. Для доказательства второго свойства положим для всех i¹ j. Очевидно . Наименьшее значение функции , как функции от t, достигается на отрезке

Поскольку , то

Аналогично

Следовательно, в точке достигается минимум функции , откуда и следует справедливость второго свойства.

Из второго свойства легко следует, что погашение матрицы B с помощью односторонней циркуляции приводит к простой матрице. Следовательно, последовательное погашение простой матрицы B с помощью односторонних циркуляций приводит к простой матрице долгов. Таким образом, в дальнейшем мы можем оперировать только с простыми матрицами долгов и односторонними циркуляциями. Однако применяемая до сих пор форма представления долгов и циркуляций будет не вполне удобна, так как последовательное применение односторонних циркуляций не эквивалентно погашению с помощью суммы этих циркуляций и, кроме этого, сумма односторонних циркуляций может не быть односторонней циркуляцией.

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

;

.

Легко видеть, что C и Y являются антисимметричными матрицами, т.е. , . Для антисимметричных матриц C и Y формулы перехода к исходным матрицам имеют вид:

Отметим, что полученные по этим формулам матрицы долгов являются простыми, а схемы погашения односторонними. Посмотрим теперь, во что преобразуются условия циркуляции и формулы погашения для антисимметричных матриц. Условие циркуляции принимает вид:

.

Матрицы Y, удовлетворяющие этому условию будем называть сбалансированными.

Пусть-это простая матрица долгов после погашения матрицы долгов с помощью односторонней циркуляции X. Тогда

=

.

В матричной записи C¢ =C-Y как видим, теперь последовательное применение сбалансированных матриц погашения эквивалентно применению одной сбалансированной матрицы погашения, равной сумме матриц погашения.

Покажем теперь, что формула для суммарной задолженности не изменится. Действительно,

.

Теперь построение оптимального погашения будем строить, последовательно погашая долги для простейших структур, состоящих из трех предприятий. Выберем три предприятия с индексами i,j,k и будем рассматривать сбалансированные матрицы погашения Z, для которых только величины могут быть отличны от нуля. Среди таких сбалансированных матриц будем искать матрицы Z, минимизирующие величину W(С,Z). Элементарный перебор показывает, что могут встретиться только две принципиально разные структуры из трех предприятий.

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

Легко видеть, что оптимальная сбалансированная матрица содержится среди матриц первого типа, и она ищется из условия минимизации по переменной t, на множестве t³ 0, функции

Оптимальное значение параметра t равно средней из величин , обозначим это среднее . При оптимальном погашении значение суммарной задолженности уменьшается

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

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

Если рассматривать сбалансированные матрицы первого типа, то приходим к задаче минимизации по переменной t на множестве t³ 0 функции

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

Если рассматривать сбалансированные матрицы второго типа, то приходим к задаче минимизации по переменной t на множестве t³ 0 функции

В этом случае минимум функции достигается при t=0 и соответственно получаем, а минимальное значение функции равно . Легко видеть, что

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

Итак, начиная с антисимметричной матрицы долгов С, будем искать тройки предприятий, для которых оптимальное погашение, описанным выше способом, приводит к строгому уменьшению суммарной задолженности. После нахождения соответствующей сбалансированной матрицы проведем погашение и с полученной после погашения матрицей долгов проделаем такую же процедуру. Для доказательства конечности описанного процесса погашения дополнительно предположим, что все суммы задолженности выражены целыми числами. Это предположение всегда выполнено на практике, так как суммы задолженностей всегда выражаются целым числом копеек. Нетрудно также видеть, что случай с суммами задолженностей, выраженных рациональными числами, сводится к целочисленному случаю.

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

Итак, в конце процесса погашения возникнет такая антисимметричная матрица долгов, что оптимальное погашение по любой тройке предприятий не уменьшает суммарной задолженности. Это означает, что любое предприятие является либо чистым должником, т.е. этому предприятию никто не должен, либо чистым кредитором, т.е. это предприятие никому не должно. Поскольку при погашении долгов балансы задолженностей предприятий не меняются, то в итоге суммарная задолженность предприятий равна сумме модулей балансов задолженностей по всем предприятиям. Учитывая, что суммарная задолженность не может быть меньше суммы модулей балансов, окончательно получаем, что алгоритм последовательного погашения приводит к снижению суммарной задолженности до величины глобального минимума, то есть

Хотя алгоритм последовательного погашения достаточно трудоемок и его реализация может потребовать достаточно большого времени, но его достоинством является то, что он позволяет полностью описать окончательное состояние матрицы долгов. Поскольку окончательное состояние матрицы долгов может быть найдено независимо от алгоритма, то необходимость в реализации этого алгоритма отпадает, а оптимальная циркуляция может быть найдена, как разность исходного состояния матрицы долгов и конечного состояния матрицы долгов. Таким образом, решение задачи погашения сводится к нахождению конечного состояния матрицы долгов.

Решение этой задачи включает два этапа. На первом этапе вычисляются величины балансов предприятий, т.е. величины

Все предприятия разбиваются на три группы: кредиторы – K, дебиторы – D и нейтралы – N:

,

,

.

На втором этапе решается система уравнений относительно y_ij,

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

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

Изменение размеров погашения отдельного предприятия нарушает условия циркуляции и так трансформированная схема погашения уже не является допустимой. Поэтому предлагается представлять пользователю схему погашения, как последовательность погашений, имеющих вид цепочки. Цепочка – это такое погашение, когда одна и та же сумма погашается по замкнутой цепочке предприятий. Нетрудно показать, что любую одностороннюю циркуляцию можно представить через последовательность цепочек погашения.

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

Алгоритм задачи оптимального погашения и разложение получившейся циркуляции на цепочки погашения был реализован в программном комплексе “Взаимозачеты” для Windows 95. По своей структуре программа естественным образом распадается на два блока. Первый блок предназначен для проведения аналитических исследований путем сравнений балансов между предприятиями или группами предприятий. Второй блок реализует алгоритм полного погашения и формирования цепочек погашения относительно выбранных пользователем предприятий.

Все необходимые данные, содержащие информацию о предприятиях и долгах, содержатся в базе данных типа Microsoft Access 97 в двух таблицах Enterprises и Debts. Кроме этого, для удобства включения предприятий в схему погашения и проведения аналитических исследований между группами предприятий возможно формировать в базе данных статические наборы предприятий, именуемые объединениями. Информация об объединениях и об их составе содержатся в таблицах Unions, Union-Enterprises.

Рассмотрим более подробно структуру и функциональные возможности каждого блока.

Сразу после запуска программы пользователю предоставляется возможность выбрать, с какой именно базой данных по долгам и предприятиям он собирается работать. Это может быть как учебная база данных с примерами (по умолчанию), так и рабочая база данных – достаточно лишь указать путь к любой из них. После этого пользователь может либо загрузить ранее сохраненную схему погашения или файл примеров, либо создать новую. Создав новую схему погашения, пользователь в диалоговом режиме добавляет в нее те предприятия или объединения, между которыми он хотел бы провести взаимозачет. Все данные об предприятиях или объединениях, как находящихся в базе данных, так и включенных в схему погашения, а также их свойства отображаются в левой области экрана на панели Структура схемы погашения.

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

1. Название предприятия;
2. Задолженность общая – сумма кредиторской и дебиторской задолженности предприятия;
3. Баланс общий – сумма внутреннего и внешнего баланса предприятия;



5. Кредит внутренний – суммарный кредит предприятия всем предприятиям организации-кредитора;
6. Кредит внешний – суммарный кредит предприятия всем предприятиям организации-дебитора;
6. Кредиторская задолженность – сумма внутреннего и внешнего кредита предприятия;
7. Дебит внутренний – суммарный дебит предприятия всем предприятиям организации-кредитора;
8. Дебит внешний – суммарный дебит предприятия всем предприятиям организации-дебитора;
9. Дебиторская задолженность – сумма внутреннего и внешнего дебита предприятия;
10. Баланс внутренний – разность внутреннего кредита и дебита предприятия;
11. Баланс внешний – разность внешнего кредита и дебита предприятия;

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

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

Программные требования: установленная Microsoft Windows 95/98/NT (русская версия) и СУБД Microsoft Access 97. Минимальные аппаратные требования для программного комплекса “Взаимозачеты”: PC-совместимый компьютер с процессором не ниже Intel Pentium 100, не менее 16 мегабайтами оперативной памяти и 20 мегабайтами свободного пространства на жестком диске (точнее, на любом из логических дисков); операционная система Windows 9x или Windows NT 4.0 с установленными библиотеками поддержки баз данных Microsoft Jet 3.5 (Microsoft Access 97).

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

Приведем теперь некоторые результаты применения алгоритма полного погашения с помощью программы “Взаимозачеты” для различного набора предприятий.

1) схема погашения состоит из 3-х предприятий

Ситуация до погашения

Ситуация после погашения

Цепочки погашения:

Цепочка0: 1–>3–>1 (20 x 2 = 40),

где 20 – сумма погашения, 40 – эффективность погашения.

Цепочка1: 1–>2–>3->1 (20 x 3 = 60).

Общая эффективность погашения: 40 + 60 = 100.

2) схема погашения состоит из 5-ти предприятий

Ситуация до погашения

Ситуация после погашения

Цепочки погашения:

Цепочка0: 3–>1–>3 (20 x 2 = 40).

Цепочка1: 5–>3–>4->5 (20 x 3 = 60).

Цепочка2: 5–>3–>1->2->4->5 (20 x 5 = 100).

Цепочка3: 3->2–>3 (10 x 2 = 20).

Общая эффективность погашения: 220

3) схема погашения состоит из 10-ти предприятий

Ситуация до погашения

Ситуация после погашения

Цепочки погашения:

Цепочка0: 6–>4–>5->6 (30 x 3 = 90).

Цепочка1: 10–>8–>6->9->10 (30 x 4 = 120).

Цепочка2: 1–>2–>5->3->1 (40 x 4 = 160).

Цепочка3: 10–>1–>3->4->5->6->7->8->9->10

(20 x 9 = 180)

Цепочка4: 8–>6–>7->8 (10 x 3 = 30).

Цепочка5: 6–>1–>2->5->6 (10 x 4 = 40).

Цепочка6: 3–>2–>3 (10 x 2 = 20).

Общая эффективность погашения: 640.

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

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

В заключение необходимо отметить, что описанная версия программного комплекса “Взаимозачеты” не включает пока в себя блок редактирования данных о долгах и предприятиях и блок формирования документов на основании полученных цепочек погашения. Редактирование данных может быть сделано в СУБД Microsoft Access 97, а формирование документов легко может быть добавлено после предоставлении заказчиком описания форматов требуемых документов.

Контактный телефон:

(095) 252-0496, Молодцов Дмитрий Анатольевич.

[an error occurred while processing this directive]

Версия для печати