gifts2017

Взаимозачет из графина

Опубликовал Александр Рытов (Арчибальд) в раздел Управление - Теория учета

Исследование графа задолженности.

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

     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.

 

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Александр Рытов (Арчибальд) 31.05.11 13:47
В http://infostart.ru/public/78737/ и предыдущих статьях обсуждалась реализация работы с графами, представленными ТаблицейЗначений. То есть до логистической задачи добраться легко. Другое дело - как ее решать...
2. Игорь Исхаков (Ish_2) 31.05.11 13:57
Как ты так клепаешь свои темы ?
И главное легко и непринужденно...
Сколько стоит, правда , такая легкость - вопрос другой... скучный и нудный.
А пока я отдаю должное легкости и непринужденности.
3. Александр Рытов (Арчибальд) 31.05.11 14:12
(2) Я ж по профильному образованию оптимизатор (кафедра общих проблем управления). А с графами недавно мы изрядно поразвлекались. ;)
4. Игорь Исхаков (Ish_2) 31.05.11 14:23
Статья должна содержать сквозной пример, на котором автор покажет всё своё искусство проведения взиморасчетов.

Чтобы подчеркнуть преемственность к начальному материалу Машкова :
структура начальных(входных) данных должна быть такой же, т.е. должна быть определена ТаблицаДолгов с колонками Д-р,К-р,Долг (и лишь потом переход к графу)

Прозрачность твоего подхода и его отличия от подхода Машкова была бы более четкой если бы в качестве сквозного примера ты выбрал сквозной пример №2 из темы Машкова.

А у тебя ? Осенило красивом подбором картинок и ты решил поделиться с публикой своими впечатлениями ?
Дескать , можно и вот так .. ?
Легко и непринужденно отвечаю : ну, и что ?
5. Михаил Ражиков (tango) 31.05.11 14:28
Фигня, Ар.
тут надо инструмент замутить. завлечь и впарить
6. Александр Рытов (Арчибальд) 31.05.11 16:19
(5) Вот именно. Не впаришь это никому.
7. Александр Рытов (Арчибальд) 31.05.11 16:23
8. Михаил Ражиков (tango) 31.05.11 16:30
если с конца "слау" подходить - то да, не впаришь
подходить надо с конца картинки:
вот такая у тебя, СЭР(А) дебеторка/кредиторка.
чтоб закрыть - тебе надо столько-то нала
чтоб столько нала получить - вот такой процент заплатишь банку
чтоб не платить банку - вот такая шняга
и вот тут-то выскакивает 1снег весь в белом: шняга, СЭР(А)!
9. Александр Рытов (Арчибальд) 31.05.11 16:40
(8) Сны разума порождают чудовищ :o
10. Михаил Ражиков (tango) 31.05.11 16:45
да ладно, Ар, еще никто не жаловался
11. Игорь Исхаков (Ish_2) 31.05.11 17:47
(9) Ты пойми.
Для чего мне нужен максимально понятный и преемственный к теме Машкова табличный интерфейс ?
Для того, чтобы вынуть камень из-за пазухи и методично пройтись по твоим графинам.
Показать сколько они стоят .
Ты НЕЧЕСТНО затрудняешь мне задачу.
Я опровергать твои вымыслы рисованными рисунками, что ли, буду ?

P.S.
А графины твои должны разбиты вдрызь , для того чтобы все женщины , которые..боже мой !.. снимают
перед тобой шляпу , перебежали ко мне. Вот и весь мой сказ.
12. Михаил Ражиков (tango) 31.05.11 17:50
у меня такое впечатление, что Игорь прочитал где-то слово "поллюция"
13. Александр Рытов (Арчибальд) 01.06.11 08:16
(11) И что у тебя за пазухой кроме обхода дерева запросом? "Деревянная" структура взаимных задолженностей (вернее, платежей) давно изучена - еще в 20-е годы прошлого века Перельман выпустил книгу "Занимательная математика", в которой разбираются финансовые пирамиды. Мои же графины небьющиеся как раз потому, что работают с произволдьными структурами.
А рисунки просто для красивости. Провести строгое доказательство с множеством латинских, греческих и готических символов нетрудно, но не наглядно...
14. Игорь Исхаков (Ish_2) 01.06.11 08:27
(13) Еще раз.
Даже не касаясь сути , говорю тебе - статья твоя ни на какую альтернативу статье Машкова не тянет.
Подробного описания твоего алгоритма не содержит.
Никаких доказательств тезиса :
Я хочу показать, что после проведения «обычных» двусторонних взаимозачетов, а также «циклических» взаимозачетов требование (2) становится несущественным.
в статье мы не находим.

Если ты считаешь , что представленные картинки - это и есть описание алгоритма и доказательств, то мне очень жаль.
Упоминание "степени" в конце статьи скорее вредит тебе.
15. Александр Рытов (Арчибальд) 01.06.11 10:24
(14) Статья (первая) Машкова интересна своей экономической частью, что я и отметил плюсиком. А математическая часть там откровенно слабая. Моя статья направлена на прояснение поставленной задачи (сведения ее к известной).
Касательно требований наличия цепочки задолженностей, а также односвязности таблицы (графа) задолженностей. В сфере применимости многосторонних взаимозачетов (холдинг), да и вообще, когда есть организатор/гарант процесса "односвязность" таблицы задолженностей вытекает уже из того, что это одна таблица, анализируемая одним дилером. И если у дилера есть задача минимизации количества строк в этой таблице, зачем ему реальная односвязность?
Простейший пример:
А Б 10
А В 20
Г Д 10
Е Д 20
Если требовать односвязности, задолженностей 4, и это минимум. Иначе легко получить
А Д 30
Г Б 10
Е В 20
И внутри холдинга это вполне реально.
Насчет подробности описания алгоритма - это уж на чей вкус. Если бы речь шла о букваре, я бы согласился с такой претензией. А в дискуссии на уровне ученых степеней - уж пардон. Имеющий глаза, да увидит. Канву доказательства. И может попытаться опровергнуть какое-либо из промежуточных утверждений. Претензию типа "я не понял юмора, значит, не смешно" не принимаю.
16. Игорь Исхаков (Ish_2) 01.06.11 10:59
(15) Статья № 1 Машкова для взгляд программиста оригинальная и сильная.
Табличный алгоритм взаимозачета превосходно реализуем запросной техникой.
Без всяких "семерочных" переборов.

В статье Машкова только один прокол : указанный алгоритм работоспособен только для односвязных графов.
Заметь (обращаю внимание математика , коим ты представляешься!), это было ДОКАЗАНО :
приведен конкретный пример удовлетворяющий начальным условиям автора, подробно повторен ход решения автора и получен неверный результат.
Все доводы Машкова, что дескать он это и так подразумевал и опустил как несложный вопрос - это разговоры в пользу бедных. Полный алгоритм получился более громоздким и затратным.

Теперь скажи , что доказывать или опровергать в твоей статье ? Набросок , идею ?
Увиденную тобой "канву доказательств" с картинками ?
Понимать их можно по-разному.
17. Александр Рытов (Арчибальд) 01.06.11 12:02
(16)
В статье Машкова только один прокол : указанный алгоритм работоспособен только для односвязных графов.
Теперь цитата из статьи
Для выполнения расчетов временно введем в рассмотрение вспомогательную фирму «Помощник», которая помогает урегулировать долговые отношения между участниками многостороннего взаимозачета.
Нам не важно сейчас, существует ли "помощник" реально, или его функции берет на себя кто-то из участников взаимозачета. Важно, что определен состав участников, т.е. множество контрагентов, согласных принять участие в "групповухе", вписавших в таблицу задолженностей свои строки и готовых подписать многосторонний договор о перераспределении задолженностей. После этого согласия уже не имеет значения, была ли пара кредитор-дебитор, появившаяся в итоге, ранее связана цепочкой взаимных долгов. Так что "неверный" результат в твоем примере не доказывает ничего.
18. Игорь Исхаков (Ish_2) 01.06.11 12:23
(17) Так не пойдет. Хочешь предложить мне переливание из пустого в порожнее ?
Машков лишь после приведенных доказательных примеров признал, что
Вся моя теория относится к таким множествам участников и их задолженностям, графы которых являются односвязными.
Далее опубликовал тему с необходимым алгоритмом разбиения графа на односвязные.

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

Мало того, отказ от требования односвязности графа при такой "групповухе" может привести к анекдотическим последствиям :
Исходный граф :
К-р Д-р Долг
А    В  10
С    D  10  
Полученная таблица к распределению :
А    D  10
С    B  10  

Ты хочешь отмахнуться от требования односвязности как от пустяка , а я говорю ,
что этот пустяк к тебе вернется как дубина.
19. Александр Рытов (Арчибальд) 01.06.11 13:12
(18) Юноша повелся на твое словоблудие. Не думаю, что это может быть предметом гордости.
то пусть получает вместо одного должника - десять
Что у меня, что у Машкова: Максимум, два. Как правило - один и останется.
А в 15 посте я привел реальный и конкретный пример двусвязного графа с 4 задолженностями, который по алгоритму Машкова превращается в трехсвязный с тремя задолженностями. И где твои "доказательства"?
20. Игорь Исхаков (Ish_2) 01.06.11 13:57
(19)
1. Юноша , без степени , публикует не цветные картинки с наброском идеи , а
внятный, подробный , цельный алгоритм. Такой подход говорит об уважении автора к возможным оппонентам.
Такой алгоритм можно исследовать : опровергать или убеждаться в его правильности. Твоя же статья содержит не алгоритм , который можно подтвердить или опровергнуть, а некую "канву". Критиковать которую бессмысленно , потому что ты всегда можешь сказать , что под картинкой понимал совсем другое.
Размещая такую статью, ты не уважаешь возможных оппонентов , потому что не даешь им возможности убедиться в безусловной правильности твоего алгоритма.
Таким мне видится взрослый подход к анализу и сравнению твоей статьи и Машкова.

2. "И где твои доказательства ?"
Мои доказательства неверности алгоритма Машкова сводились только к одному :
Приведен конкретный пример с корректными (по автору ) начальными условиями , произведено корректное (по автору)преобразование и получен неверный результат распределения. Это означает, что общее решение приведенное в статье автора совсем не общее , а частное. Что и подтвердил автор , признав необходимость предварительного разбиения графа на односвязные. Точка.
Никаких других примеров я не касался и никаких других целей не ставил.
Это означает, что твой 15 пост к моим доказательствам никакого отношения не имеет.

P.S. Писал всё ,скрипя зубами : Господи, это же так очевидно, чего я развожу тут.
Но это ,очевидно - необходимо.
Ведь и ты ,публикуя свою "канву", был совершенно убежден
" А чего тут развозить ? По "канве" и так всё понятно, картинок хватит.."
21. Александр Рытов (Арчибальд) 01.06.11 14:48
(20)
Это означает, что твой 15 пост к моим доказательствам никакого отношения не имеет
Естественно не имеет, за отсутствием доказательств. У тебя наличествует только утверждение, что алгоритм Машкова дал неверный результат, с которым утверждением сгоряча согласился Машков, не рассматривавший и не обдумывавший многосвязные взаимозачеты. Я же продолжаю утверждать, что при естественных условиях, без которых вообще проблематично организовать многосторонний взаимозачет, результат вполне верен. Твой пример ничего не опровергает, хотя и может показаться несколько неестественным. Я же утверждаю, что и ситуация, в которой кредиторы просто обмениваются своими дебиторами (твой пример), вполне реальна (например, планируется натуральное погашение долгов и встает вопрос минимизации грузоперевозок), и даже встречается в деловом обороте не так уж редко.
Я своей статьей отнюдь не пытаюсь спорить с сутью предложенного алгоритма - я и использую, фактически, тот же алгоритм. Моя статья показывает лишь то обстоятельство, что математический аппарат решения поставленной задачи известен уже давно, а не ждал тысячи лет статьи Машкова.
22. Игорь Исхаков (Ish_2) 01.06.11 15:38
(21) Придётся еще раз рассмотреть пример , пример вызывающий у тебя возражения.
Итак. Мы рассматриваем пример , опровергающий первоначальный алгоритм Машкова без учета многосвязности исходного графа.
Исходный граф задолженностей :
К-р Д-р Долг 
А    В  10 
С    D  10   

После преобразований строго по статье Машкова с фирмой посредником Р получаем таблицу :
К-р Д-р Долг 
А    Р  10 
Р    B  10  
С    P  10
P    D  10
...Показать Скрыть

Из этой таблицы в зависимости от способа распределения получим :
либо Вариант 1
К-р Д-р Долг 
А    В  10 
С    D  10   

либо Вариант 2
А    D  10 
С    B  10  

либо Вариант 3 и др.
А    В  5 
А    D  5  
C    B  5
C    D  5
Либо множество других вариантов .
При варианте 3 и др. тебе придется объяснять всем изумленным представителям фирмм А,B,C,D , что в результате нашей оптимизации количество ваших дебиторов(кредиторов) увеличилось (!). Мужчина ты серьезный , допускаю , что тебе это удалось.

Но критерий распределения долгов, согласованный с фирмами A,B,C,D , может быть таким что "машине придется" выбирать между вариантами 1 и 2. Она выберет вариант случайным для нас образом, т.е. эти варианты для "машины" неразличимы. Если "машина покажет " вариант 2
А    D  10 
С    B  10 
То никакой серьезный вид тебе не поможет. Ты можешь сколько угодно "хмурить лоб и щурить глаза"
предствители фирм A,B,C,D - будут только ржать.

Что означает этот пример ?
Этот пример означает , что первоначально приведенный алгоритм в статье Машкова может выдать непримелемый для нас результат. Отсюда вытекает необходимость предварительного исследования графа на односвязность.

P.S. Заметь , я расписываю всё подробно ,ясно , определенно, чтобы у тебя появился объект для критики .
Давая тебе возможность критики , я выказываю своё уважение тебе как оппоненту.
23. Александр Рытов (Арчибальд) 01.06.11 16:04
(22) Посмотри мой третий коммент ко второй статье Машкова:
Написание такого продукта - всего лишь вопрос представления ЛПР (лицу, принимающему решения) альтернативных распределений в наглядном виде.
Никакого случайного выбора. Вариант 3 - это "справедливое распределение", о котором вообще речь не идет в задаче минимизации количества задолженностей, как и о всяких других специфических вариантах. Остаются варианты 1 и 2, между которыми я (ЛПР) должен выбирать. Между прочим, поскольку я ЛПР, представителям фирм A, B, C, D будет не до смеха. Это мои дочерние компании, и граф их взаимных задолженностей уже по этой причине "односвязен". Все привязаны ко мне.
К примеру, я собираюсь обанкротить одного из двух дебиторов и знаю, что один из кредиторов банкротство выдержит, а второй понесет неприемлемый ущерб. Вот тут-то я и заставлю кредиторов обменяться дебиторами - а куда они денутся.
24. Игорь Исхаков (Ish_2) 01.06.11 16:37
(23) Посмотрел твой пост. Сам твой подход к осмыслению задачи представлется мне глубоко ошибочным.
Ты кто ?
Ты - разработчик алгоритма.
Твоя задача , как разработчика , создать алгоритм с максимально широкой областью применения, максимально абстрагируюсь от конкретных мотивов ЛПР и т.д. Такой алгоритм в дальнейшем может быть настроен на какие угодно пожелания и ограничения.
Ты же заранее задаешь себе выгодные начальные условия : приводишь конкретные мотивы ЛПР , которые могут упростить тебе разработку алгоритма. Разработчики , наевшиеся г.. , знают чем чревато такое сужение постановки задачи. Дескать : а у нас только холдинг, а у нас такой ЛПР ...
Что мы получаем ?
Что в самом начале разработки , игнорируя проверку на односвязность, мы можем получить такой результат , который при определенных условиях нас не устроит (Абстрактные фирмы A,B,C,D - ржут).
Только вероятность такого события заставляет нас просчитывать такой вариант и вводить проверку на односвязность графа. Не понадобится - очень хорошо ! Понадобится - изменил настройки и вперед !
25. Александр Рытов (Арчибальд) 01.06.11 17:00
(24) Мои шаги 1-3 превращают произвольный исходный граф в набор односвязных "гамаков", не добавляя при этом связей между подграфами. Это и есть наиболее универсальный подход, с масимально широкой областью применения. Этап проверки на односвязность при таком подходе просто не нужен, равно как и условие о том, что имеются "дебитокредиторы". Как потом работать с "гамаками" - выходит за рамки статьи. Участники взаимозачета могут оставаться в рамках первоначальных областях, могут "естественным образом" разбиться на более мелкие группы, однако же никто им не мешает заводить связи, изначально отсутствующие (я привел пример, когда это может потребоваться. Может, конечно и не потребоваться). Ваше с Машковым требование односвязности - это всего лишь необоснованное сужение области применения взаимозачетов.
26. Игорь Исхаков (Ish_2) 01.06.11 17:21
(25)
Ваше с Машковым требование односвязности - это всего лишь необоснованное сужение области применения взаимозачетов.


В рамках алгоритма Машкова требование ПРОВЕРКИ и возможной разбивки на односвязные подграфы необходимо .
Такая предварительная процедура резко расширяет возможности метода.
Грубо говоря, нам всё равно какой граф исследовать. Поэтому я не понял о каком сужении ты говоришь.

Мои шаги 1-3 превращают произвольный исходный граф в набор односвязных "гамаков", не добавляя при этом связей между подграфами. Это и есть наиболее универсальный подход, с масимально широкой областью применения. Этап проверки на односвязность при таком подходе просто не нужен, равно как и условие о том, что имеются "дебитокредиторы".


Я ни слова до сих пор не сказал о содержании твоего подхода. Ни плохого , ни хорошего.
Лишь возмущался качеством подачи материала, которое не даёт оппоненту возможности всё проверить.
Ведь ценность или убогость того или иного подхода даёт только сравнение.
Статья Машкова прозрачна для меня от начала до конца без дополнительных и наводящих вопросов автору ,потому что все написано ясно , однозначно , определенно и сразу понятно как это может быть реализовано на 1с.
Вот так.
27. Владимир (hogik) 01.06.11 18:05
(26)
"Я ни слова до сих пор не сказал о содержании твоего подхода. Ни плохого , ни хорошего.
Лишь возмущался качеством подачи материала, которое не даёт оппоненту возможности всё проверить."(с)
А "плюс", первым, кто поставил? :-)
28. Игорь Исхаков (Ish_2) 01.06.11 18:06
29. Владимир (hogik) 01.06.11 18:58
(28)
Игорь.
Это рекомендация не читать Ваши комментарии дальше (2) сообщения?
Извините, я их уже все прочел... :-)
30. Игорь Исхаков (Ish_2) 01.06.11 19:00
(29) Если у Вас что-то по существу обсуждаемого вопроса , то милости просим .
31. Владимир (hogik) 01.06.11 19:17
(30)
Игорь.
Спасибо за приглашение.
Но, я не вижу обсуждения - очередная попытка от Ish_2 опустить собеседника до:
"...превосходно реализуем запросной техникой. Без всяких "семерочных" переборов."(с)
32. Игорь Исхаков (Ish_2) 01.06.11 19:23
(31) Дежурный укол. Не более.
А по делу у Вас что-нибудь есть сказать ?
33. Владимир (hogik) 01.06.11 19:28
(32)
По делу всё сказано автором данной публикации.
34. Игорь Исхаков (Ish_2) 01.06.11 19:28
35. Владимир (hogik) 01.06.11 22:06
(34)
"Всё как обычно."(с)
Игорь, а чего Вы хотели? Я уже не могу долго находиться в позе смотрящего в "замочную скважину"(с). Старческий радикулит не позволяет...
36. Игорь Исхаков (Ish_2) 02.06.11 07:57
Вообщем , завершаю. Не дал ты мне бросить камень. Не во что.
Диалоги на уровне "Моя тема - ништяк !" - "Твоя тема - отстой !" быстро утомляют.
Тебе повезло. Ты остаешься при своих графинах.
37. Александр Рытов (Арчибальд) 02.06.11 08:41
(36) Ну вот... А я теорему Машкова про Д+К-1 доказал. В его ветке.
38. Игорь Исхаков (Ish_2) 02.06.11 08:56
39. Александр Рытов (Арчибальд) 02.06.11 08:59
40. Александр Рытов (Арчибальд) 02.06.11 12:08
+ (38) Теперь и здесь (восьмой скрин).
41. Sergej Mashkov (samashkov) 02.06.11 16:52
Машкова - г-ну Арчибальду
Я, к сожалению, не являюсь специалистом ни по графам, ни по «графиням», ни по «графинам», хотя, полагаю, кое-что смыслю в графиках. Но, как, наверное, и большинство бухгалтеров, будучи дилетантом в этих вопросах, тем не менее, хочу заметить, что как только на основании таблицы задолженностей Вы нарисовали граф, то Вы сразу увидели, что этот граф односвязный (или многосвязный), имеет циклы (или их не имеет), имеет супер-пупер-кредиторов (или супер-пупер-дебиторов) и т.д. Таким образом, сам процесс рисования графа, как мне кажется, является процессом выделения односвязных подмножеств, обнаружения циклов, цепочек и т.д.
Вы пишите, что представленным набором преобразований графов Вы наметили «канву». Очень может быть, что программист квалификации выше некоторой по этой «канве» может восстановить работоспособный алгоритм. Я, к сожалению, не смог. Например, в Вашей «канве» - "шаг 2. Разрываем циклы (рис. 2). Все очень наглядно и понятно. Для человека, имеющего глаза и смотрящего на уже нарисованный граф. А для машины? Она же имеет только таблицу задолженностей. И из этой таблицы задолженностей нужно выделить замкнутый цикл. Это алгоритм примерно такой же сложности, как и алгоритм, описанный в 2-й моей статье. Причем, если в первоначальном графе циклов много, то и работать этот алгоритм должен много раз. От того, какой из циклов разрывается первым, а какой вторым результат может получиться различным. Для Вашего примера, представленного на рис. 5 – 11, результат может получиться другим. Ваше решение: D – 1 – >C; E – 5 – >C; E - 11 - >В. Еще одно возможное решение, полученное мною: D – 1 – >В; E – 6 – >C; E - 10 - >В.
Разумеется, возможны такие постановки задачи, когда достаточно найти хоть какое-то (первое попавшееся) решение. Но раз допустимых решений много, то можно ставить задачу о нахождении среди возможных решений какого-то определенного решения, удовлетворяющего каким-то дополнительным условиям. При решении этой же задачи (рис. 5) моим методом, получаем суммарные дебиторские и кредиторские задолженности участников, представленные в табл.1:
Табл. 1
Дебитор Кредитор Задолженность
D 1
Е 16
В 11
С 6
Далее говорим, что если дебитор D передаст часть Х (0<X<1) своей задолженности кредитору С, а оставшуюся часть – кредитору В, то окончательное распределение задолженностей будет таким, как представлено в табл. 2
Табл. 2
Дебитор Кредитор Задолженность
D С Х
D В 1 – Х
Е В 10 + Х
Е С 6 - Х
При Х=1 получаем найденное Вами решение, представленное на рис. 11, при Х=0 получим другое возможное решение, найденное мною из Ваших же графов. А как, используя «канву» вашего метода графов, построить алгоритм нахождения всего множества возможных решений, на котором можно искать определенное решение, удовлетворяющее какому-то дополнительному условию?
В моем решении, представленном табл.1, это просто. Каждая из задолженностей является функцией некоторого параметра Х. Можно построить графики зависимости этих задолженностей от этого параметра Х, или графики зависимости степени удовлетворения дополнительного условия от параметра Х, и исследовать их на предмет наилучшего удовлетворения заданному дополнительному условию.
Может быть, все это действительно элементарно для специалистов по графам (или по «графиням», или по «графинам»), и задача, которая, как я полагал, впервые решена мною, давно уже решена логистами (или логистиками, а может быть логиками), но в таком случае, пожалуйста, объясните нам, простым бухгалтерам, которые умеют определять дебиторскую и кредиторскую задолженность по отношению к любому своему контрагенту, но не умеют решать логистические задачи, как от вашей «канвы» перейти к работоспособному алгоритму, который находит все возможные решения для многостороннего взаимозачета, где задолженности заданы таблицей задолженностей.
42. Sergej Mashkov (samashkov) 02.06.11 17:01
Машков - Арчибальду
в таблицах 1 и 2 все пробелы пропали и все почему - сместилось влево. Перерисовываю эти таблицы снова.
Табл. 1
Дебитор Кредитор Задолженность
D. . . . . . . . .1
Е. . . . . . . . .16
. . . . В. . . . .11
. . . . С. . . . .6
Табл. 2
Дебитор Кредитор Задолженность
D. . . .С. . . . Х
D. . . .В. . . .1 – Х
Е. . . .В. . . .10 + Х
Е. . . .С. . . .6-Х
43. Александр Рытов (Арчибальд) 02.06.11 17:58
(41) Моя "канва" - это не канва алгоритма, а канва доказательства того, что призвольный граф задолженностей может быть сведен к одной или нескольким совокупностям чистых дебиторов и чистых кредиторов. А далее можно строить уже вырианты решений.
Исходить будем из того, что все участники согласны на реструктуризацию задолженностей - чтобы не заморочиваться на "односвязность". Т.е. из таблицы задолженностей исключены несогласные (или таблица разбита на подтаблицы, например, по критерию "связности"). Алгоритм выделения подтаблиц, описанный во второй Вашей статье, легко реализуется за один проход исходной таблицы.
Теперь сам алгоритм "для простого бухгалтера".
Подсчитав для каждого сальдо задолженностей, получим нечто вроде Вашей таблицы 1 из (42), вернее, две подтаблицы - дебиторов 1д и кредиторов 1к.
Упорядочивая списки кредиторов и дебиторов всеми возможными способами и сопоставляя эти упорядоченные списки (как на 8-м скриншоте) получим все возможные финальные варианты. Их будет не более Д!*К!/2.

Теперь по поводу предложенной Вами "х - парамертизации" и построения соответствующих графиков. В общем, мысль интересная. Но вот так сразу не приходит на ум, график какой целевой функции строить.
44. Игорь Исхаков (Ish_2) 02.06.11 19:02
(43),(41) Машкову на заметку.
Обратите внимание как элегантно выкрутился Арчибальд :
"Что Вы хотите ? Это же только "канва" , а конкретные решения могут быть различными... ".
И плавно перешел к другому вопросу.

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

Хм.. вычислить это заранее - было нетрудно.
Поэтому главный смысл выступлений оппонентов должен быть:

"Канва" против конкретного алгоритма НЕ ТЯНЕТ .
Набор картинок - не требует анализа.
Здесь обсуждать нечего.
45. Михаил Ражиков (tango) 02.06.11 20:10
обратите, как элегантен Ар :)
46. Александр Рытов (Арчибальд) 03.06.11 08:19
(44) Еще раз, для особо упертых:
Моя "канва" - это не канва алгоритма, а канва доказательства ...
Иными словами, канва доказательства существования (множества!) решений, а не канва алгоритма нахождения (одного?) решения. Цитирую оппонента:
В результате два участника «D» и «Е» имеют не равные нулю дебиторские задолженности и два участника «В» и «С» имеют не равные нулю кредиторские задолженности. В этом случае окончательное решение неоднозначно. Одно из возможных решений можно получить, например, следующим образом...
А ведь с тремя дебиторами и тремя кредиторами решений аж 18 штук. И в 43 посте предложен внятный алгоритм нахождения исчерпывающего множества решений.
Так что мягче, зеленое или соленое?
(45) Это основная проблема Игоря. :D
47. Игорь Исхаков (Ish_2) 03.06.11 08:24
(46) Будет алгоритм - поговорим. А на второй круг не пойдём.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа