Написать эту статью меня побудило обсуждение в этой публикации задачи минимизации количества взаимных задолженностей в некой группе контрагентов. Вот авторский текст:
1. «Правда остается чисто математическая постановка задачи – имеется некоторое множество контрагентов, каждый контрагент должен некоторые произвольные суммы денег произвольному подмножеству этого множества контрагентов. Требуется упростить структуру задолженностей, т.е. переопределить задолженности контрагентов друг другу так, чтобы количество задолженностей стало минимальным, а суммарная задолженность каждого контрагента всем остальным оставалась бы той же самой. И в такой математической постановке задача, наконец, решена спустя несколько тысяч лет после возникновения товарного производства и установления товарно-денежных отношений».
2. Кроме того, «обязательным условием осуществления многостороннего взаимозачета является наличие хотя бы одного участника, у которого есть и дебиторская, и кредиторская задолженности другим участникам».
Я хочу показать, что после проведения «обычных» двусторонних взаимозачетов, а также «циклических» взаимозачетов требование (2) становится несущественным. Точнее: в произвольной группе участников можно так переопределить структуру задолженностей, не увеличивая общего их количества, что каждый участник будет либо только дебитором, либо только кредитором.
Структуру задолженностей естественно представить в виде ориентированного графа с вершинами-контрагентами, и дугами-задолженностями. Направление дуги – от дебитора к кредитору, вес дуги – сумма задолженности. Разность весов всех входящих и всех исходяших дуг образует (долговое) сальдо вершины графа.
Допустимым преобразованием графа будем называть любое изменение набора дуг, не изменяющее сальдо вершин и не увеличивающее количества дуг.
Шаг 1. Агрегирование двусторонних обязательств.
Достаточно очевидное допустимое преобразование иллюстрируется Рис. 1.
Шаг 2. Разрываем циклы (Рис. 2).
То есть мы уменьшили на 15 веса всех дуг цикла. Здесь проиллюстрированы еще два очевидных момента: если в цикле есть две задолженности одинаковой величины, то взаимозачет лучше делать на эту величину (удаляются сразу две дуги). Кроме того, отрицательный вес дуги можно изменить на положительный, изменяя направление дуги.
Шаг 3. Ликвидация цепочек.
После ликвидации циклов у нас появился класс вершин-суперкредиторов, т.е у которых все дуги входящие. Займемся исключением у суперкредиторов предков, которые сами имеют предков. Пусть суперкредитор С имеет дебитора Р («родителя») с задолженностью v, который является кредитором Д («деда») с задолженностью w. Задолженность Д перед С составляет z >= 0. Ситуация изображена на рис. 3 а). Далее, при v > w мы приходим к рис. 3 б), а при w > v – к рис 3. в).
Заметим, преобразование допустимо, то есть не изменились никакие сальдо и не увеличилось количество дуг, даже если пунктирной дуги на рис. 3а) изначально не было (z=0).
В случае б), если у Р есть еще дебитор Д1, поступим так же. В конце концов у суперкредитора С не останется дедов, и мы перейдем к следующему суперкредитору.
Шаг 4. Задача, эквивалентная первоначальной.
Итак, было показано, что произвольный граф задолженностей эквивалентен «гамаку» (рис. 4), в котором количество дуг не превышает количества дуг первоначального графа.
А дополнительные предположения типа односвязности или, тем более, наличия цепочек длины больше 1, только сужают область применения взаимозачетов.
В общем, задача эквивалентна следующей.
Имеется Q партий однородного товара, размещаемого на N складах. Суммарный объем партий равен суммарной емкости складов. Требуется разместить товар так, чтобы отчет о размещении вида «Склад - Партия - Количество» имел минимальное количество строк.
Стандартная задача логистики…
На скринах приведена последовательность шагов для примера, похожего на пример 2 из исходной статьи (одну веточку забыл, а перерисовывать лень).
PS На Нобелевскую не претендую... Степень есть уже... Зачем все это?..
02.06.2011. Добавил скриншот, из которого видно, что произвольный "гамак" с К кредиторами и Д дебиторами дает количество задолженностей, не превышающее (К-1)+(Д-1)+1=К+Д-1.
