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

02.06.11

Учетные задачи - Взаиморасчеты

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

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

     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.

 

См. также

SALE! 10%

Перенос данных из УТ 10.3 в УТ 11 / КА 2 / ERP 2. Переносятся документы, справочники и остатки

Обмен между базами 1C Взаиморасчеты Оптовая торговля Логистика, склад и ТМЦ Файловый обмен (TXT, XML, DBF), FTP Платформа 1С v8.3 1С:Управление торговлей 10 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Управленческий учет Платные (руб)

Предлагаем качественное и проверенное временем решение для перехода с УТ 10.3 на УТ 11 / КА 2 / ERP 2. Перенос данных находится в продаже с 2015 года, постоянно развивается, им воспользовались уже более 240 компаний. Можно перенести начальные остатки, нормативно-справочную информацию и все возможные документы. При выгрузке можно установить отбор по периоду, организациям и складам. При выходе новых релизов конфигураций 1C оперативно выпускаем обновление переноса данных.

50722 45650 руб.

24.04.2015    190284    268    238    

268

"Акты сверки +" Групповая подготовка и рассылка актов сверки для Бухгалтерии 3.0.

Взаиморасчеты Email рассылки Акт сверки Платформа 1С v8.3 Бухгалтерский учет 1С:Бухгалтерия 3.0 Бухгалтерский учет Платные (руб)

Внешняя обработка для Бухгалтерии 3.0 - позволяет автоматически формировать документы «Акт сверки расчетов» с контрагентами за выбранный период с последующей фоновой отправкой на почту контрагента.

3000 руб.

25.11.2020    21987    157    4    

146

Перенос начальных остатков из Парус 7.71 в БГУ

Внешние источники данных Взаиморасчеты Учет ОС и НМА Логистика, склад и ТМЦ Бюджетный учет Платформа 1С v8.3 Бухгалтерский учет 1С:Бухгалтерия 2.0 1С:Бухгалтерия государственного учреждения Государственные, бюджетные структуры Россия Бюджетный учет Платные (руб)

Перенос словарей и начальных остатков из ПП Парус-Бухгалтерия Бюджет 7.71 в 1Сv8 БГУ2. Заполнение словарей и документов по вводу начальных остатков. Не требуется установка ПП Парус7. Возможна дозагрузка. Позволит автоматически и наиболее полно ввести данные в программу для начала работы. 

15600 руб.

08.12.2011    81470    128    123    

146

УТ 11, КА 2, ERP 2: Настраиваемые под каждую организацию печать и подпись ответственных лиц в печатных формах (ТОРГ-12, Счёт-фактура, УПД, УКД, Заказ клиента, Акт сверки, М-15 и др.)

Печатные формы Взаиморасчеты Оптовая торговля Производство готовой продукции (работ, услуг) Акт сверки Оперативный учет Управляемые формы 1С:Управление торговлей 11 Россия Бухгалтерский учет Управленческий учет Платные (руб)

Задайте для каждой организации свою печать и для каждого физического лица свою подпись. Выберите в документе печатную форму "... с печатью и подписью" - и автоматически сформируется табличный документ с печатью и подписями той организации и ответственных лиц, которые указаны в документе.

12000 руб.

13.03.2018    56268    176    76    

112

Автоматический зачет авансов в 1С:УНФ по ФИФО

Взаиморасчеты Платформа 1С v8.3 1С:Управление нашей фирмой 1.6 1С:Управление нашей фирмой 3.0 Россия Управленческий учет Платные (руб)

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

12000 руб.

22.07.2021    23471    24    34    

31

Дебиторская задолженность по срокам долга

Взаиморасчеты Платформа 1С v8.3 1С:Комплексная автоматизация 1.х 1С:Управление торговлей 10 1С:Управление производственным предприятием 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Бухгалтерский учет Управленческий учет Платные (руб)

Один из лучших вариантов отчета по дебиторской задолженности. Отображает сроки возникновения задолженности, просроченной задолженности с точностью до регистратора, а также многое другое, вне зависимости от схемы взаиморасчетов (online / offline) и объекта расчетов (УТ 11.3, 11.4, 11.5, КА 2.4, 2.5, ERP 2.4, 2.5), состояния флажка "по документам расчета" ( УТ 10, КА 1.1, УПП 1.3) в договоре. Группирует задолженность по интервалам. Имеет большое количество настроек. Не требует доработок конфигурации.

13800 руб.

28.09.2012    94392    588    268    

139

Управление автосервисом на платформе 1С 8.3

Управление взаимоотношениями с клиентами (CRM) Взаиморасчеты Производство готовой продукции (работ, услуг) Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Автомобили, автосервисы Управленческий учет Платные (руб)

Профессиональная программа по управлению автосервисом на платформе 1С 8.3 - все что нужно для решения задач учета и контроля в автосервисах. Увеличьте прибыльность автосервиса за счет отлаженных процессов в 1С. Еще никогда контроль и учет в автосервисе не были такими простыми, доступными и наглядными!

18000 руб.

27.11.2015    65068    30    40    

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


Я ни слова до сих пор не сказал о содержании твоего подхода. Ни плохого , ни хорошего.
Лишь возмущался качеством подачи материала, которое не даёт оппоненту возможности всё проверить.
Ведь ценность или убогость того или иного подхода даёт только сравнение.
Статья Машкова прозрачна для меня от начала до конца без дополнительных и наводящих вопросов автору ,потому что все написано ясно , однозначно , определенно и сразу понятно как это может быть реализовано на 1с.
Вот так.
27. hogik 443 01.06.11 18:05 Сейчас в теме
(26)
"Я ни слова до сих пор не сказал о содержании твоего подхода. Ни плохого , ни хорошего.
Лишь возмущался качеством подачи материала, которое не даёт оппоненту возможности всё проверить."(с)
А "плюс", первым, кто поставил? :-)
28. Ish_2 1104 01.06.11 18:06 Сейчас в теме
29. hogik 443 01.06.11 18:58 Сейчас в теме
(28)
Игорь.
Это рекомендация не читать Ваши комментарии дальше (2) сообщения?
Извините, я их уже все прочел... :-)
30. Ish_2 1104 01.06.11 19:00 Сейчас в теме
(29) Если у Вас что-то по существу обсуждаемого вопроса , то милости просим .
31. hogik 443 01.06.11 19:17 Сейчас в теме
(30)
Игорь.
Спасибо за приглашение.
Но, я не вижу обсуждения - очередная попытка от Ish_2 опустить собеседника до:
"...превосходно реализуем запросной техникой. Без всяких "семерочных" переборов."(с)
32. Ish_2 1104 01.06.11 19:23 Сейчас в теме
(31) Дежурный укол. Не более.
А по делу у Вас что-нибудь есть сказать ?
33. hogik 443 01.06.11 19:28 Сейчас в теме
(32)
По делу всё сказано автором данной публикации.
34. Ish_2 1104 01.06.11 19:28 Сейчас в теме
35. hogik 443 01.06.11 22:06 Сейчас в теме
(34)
"Всё как обычно."(с)
Игорь, а чего Вы хотели? Я уже не могу долго находиться в позе смотрящего в "замочную скважину"(с). Старческий радикулит не позволяет...
10. tango 506 31.05.11 16:45 Сейчас в теме
да ладно, Ар, еще никто не жаловался
12. tango 506 31.05.11 17:50 Сейчас в теме
у меня такое впечатление, что Игорь прочитал где-то слово "поллюция"
36. Ish_2 1104 02.06.11 07:57 Сейчас в теме
Вообщем , завершаю. Не дал ты мне бросить камень. Не во что.
Диалоги на уровне "Моя тема - ништяк !" - "Твоя тема - отстой !" быстро утомляют.
Тебе повезло. Ты остаешься при своих графинах.
37. Арчибальд 2706 02.06.11 08:41 Сейчас в теме
(36) Ну вот... А я теорему Машкова про Д+К-1 доказал. В его ветке.
38. Ish_2 1104 02.06.11 08:56 Сейчас в теме
39. Арчибальд 2706 02.06.11 08:59 Сейчас в теме
40. Арчибальд 2706 02.06.11 12:08 Сейчас в теме
+ (38) Теперь и здесь (восьмой скрин).
41. samashkov 71 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, это просто. Каждая из задолженностей является функцией некоторого параметра Х. Можно построить графики зависимости этих задолженностей от этого параметра Х, или графики зависимости степени удовлетворения дополнительного условия от параметра Х, и исследовать их на предмет наилучшего удовлетворения заданному дополнительному условию.
Может быть, все это действительно элементарно для специалистов по графам (или по «графиням», или по «графинам»), и задача, которая, как я полагал, впервые решена мною, давно уже решена логистами (или логистиками, а может быть логиками), но в таком случае, пожалуйста, объясните нам, простым бухгалтерам, которые умеют определять дебиторскую и кредиторскую задолженность по отношению к любому своему контрагенту, но не умеют решать логистические задачи, как от вашей «канвы» перейти к работоспособному алгоритму, который находит все возможные решения для многостороннего взаимозачета, где задолженности заданы таблицей задолженностей.
43. Арчибальд 2706 02.06.11 17:58 Сейчас в теме
(41) Моя "канва" - это не канва алгоритма, а канва доказательства того, что призвольный граф задолженностей может быть сведен к одной или нескольким совокупностям чистых дебиторов и чистых кредиторов. А далее можно строить уже вырианты решений.
Исходить будем из того, что все участники согласны на реструктуризацию задолженностей - чтобы не заморочиваться на "односвязность". Т.е. из таблицы задолженностей исключены несогласные (или таблица разбита на подтаблицы, например, по критерию "связности"). Алгоритм выделения подтаблиц, описанный во второй Вашей статье, легко реализуется за один проход исходной таблицы.
Теперь сам алгоритм "для простого бухгалтера".
Подсчитав для каждого сальдо задолженностей, получим нечто вроде Вашей таблицы 1 из (42), вернее, две подтаблицы - дебиторов 1д и кредиторов 1к.
Упорядочивая списки кредиторов и дебиторов всеми возможными способами и сопоставляя эти упорядоченные списки (как на 8-м скриншоте) получим все возможные финальные варианты. Их будет не более Д!*К!/2.

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

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

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

"Канва" против конкретного алгоритма НЕ ТЯНЕТ .
Набор картинок - не требует анализа.
Здесь обсуждать нечего.
46. Арчибальд 2706 03.06.11 08:19 Сейчас в теме
(44) Еще раз, для особо упертых:
Моя "канва" - это не канва алгоритма, а канва доказательства ...
Иными словами, канва доказательства существования (множества!) решений, а не канва алгоритма нахождения (одного?) решения. Цитирую оппонента:
В результате два участника «D» и «Е» имеют не равные нулю дебиторские задолженности и два участника «В» и «С» имеют не равные нулю кредиторские задолженности. В этом случае окончательное решение неоднозначно. Одно из возможных решений можно получить, например, следующим образом...
А ведь с тремя дебиторами и тремя кредиторами решений аж 18 штук. И в 43 посте предложен внятный алгоритм нахождения исчерпывающего множества решений.
Так что мягче, зеленое или соленое?
(45) Это основная проблема Игоря. :D
47. Ish_2 1104 03.06.11 08:24 Сейчас в теме
(46) Будет алгоритм - поговорим. А на второй круг не пойдём.
42. samashkov 71 02.06.11 17:01 Сейчас в теме
Машков - Арчибальду
в таблицах 1 и 2 все пробелы пропали и все почему - сместилось влево. Перерисовываю эти таблицы снова.
Табл. 1
Дебитор Кредитор Задолженность
D. . . . . . . . .1
Е. . . . . . . . .16
. . . . В. . . . .11
. . . . С. . . . .6
Табл. 2
Дебитор Кредитор Задолженность
D. . . .С. . . . Х
D. . . .В. . . .1 – Х
Е. . . .В. . . .10 + Х
Е. . . .С. . . .6-Х
45. tango 506 02.06.11 20:10 Сейчас в теме
обратите, как элегантен Ар :)
Оставьте свое сообщение