Такая задачка:
2-мерная матрица, например,


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

Кто-то решал такую задачку? Она вроде довольно часто встречается при планировании.
Поиском ничего полезного не нашел.

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

Внешне похоже на решение, но не самое точное и не самое быстрое.



Исправлено 1 раз(а). Последнее : Ydin, 08.04.12 22:49

что значит "должны быть" - они действительно соответствуют, постоянны во "времени" или ..., ... какие изначальные "незыблимыые" числа есть в матрице (кстати, удобно для неизвестных, на каком-то этапе значение использовать значение NULL... ну, NULL тоже, бывает зуже задействован... )

...а что в конкретно, "в словах" решается..?



Исправлено 1 раз(а). Последнее : of63, 08.04.12 23:13

Если спросить это преобразование элементов матрицы, - то наверняка найдется "тандартное" преобразование, которое сделаете Вы сами...

Есть головное предприятие, в которое входят 2 подчиненных.
Продажи этих предприятий состоят из продаж 3-х видов продукции.
Верхняя строка: Продажи всего, продажи первого вида, второго, третьего.

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


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

Всеми любимое "дерево" ? и что? стройте соотв. табличку...или что-то тоньше? ... извинимте, я пиян...

вот я строил табличку с иерархией, типо:

CREATER CURSOR xxx (имя C(50), ID I, IDгл I )

... кому я советую...



Исправлено 2 раз(а). Последнее : of63, 09.04.12 00:15

Получаем

12 5 5 2
4.8 2.2 1.72 0.88
7.2 2.8 3.28 1.12

Тонкого не строю

а если все-таки проще:

* структура таблички:
ID I && UN, уникальный номер (записи)просто ID записи
IDгл I && ссылка(UN) на уникальный номер ГЛАВНОГО образования
TXT C(90) && всякое название поля, в котором лежит название...

... т.е. таблица, с типровыми свойствами каждого элемента (строки), но самосвязная...



Исправлено 1 раз(а). Последнее : of63, 09.04.12 00:29

Про дерево я не говорил. Смотрится так
[attachment 13249 yu.gif]
Это электронные таблицы. Но меня сама задачка интересует.
Хоть, вроде и решена.



Исправлено 1 раз(а). Последнее : Ydin, 09.04.12 00:29

т.е:
"в первой строчке - общие суммы и количества
"потом по группам суммы всякие и количества"
"ИТОГО - не может быть , чтобы не требуется!"

(решается (суммы) либо в фокс, либо в шаблоне эксел, - я за Эксел )

Здесь все на формулах - кто куда входит. Все сделано и 14 лет работает.
За дерево, конечно, спасибо. Какой Иксел - свое решение электронных таблиц. На Девконе показывал.
Я спрашиваю только о задачке. Кто-то ее уже решал.



Исправлено 1 раз(а). Последнее : Ydin, 09.04.12 00:39

12 раскидать на 6+4 пропорционально?
12/(6+4) = 1.2 - коэффициент.
Тупо перемножаем все числа (кроме верхней строки) на этот коэффициент - задача решена.
Если же стоит дополнительно условие "циферки в клетках должны быть целыми" - вот тогда задача заметно усложнится...

т.е. для

получаем

где сумма второй и третьей строки
не дает первой:


Исправлено 6 раз(а). Последнее : Ydin, 09.04.12 23:47

Тогда надо сначала сделать это для первого столбца, получить
а затем проделать то же самое построчно

Если, конечно, я правильно понял задачу.

P.S. Нет, похоже это не совсем то. Тогда надо в литературе копаться. Что-нибудь вроде линейного программирования.



Исправлено 1 раз(а). Последнее : leonid, 10.04.12 00:09

И сумма второй и третьей строки
4.8 1.2 2.4 1.2
7.2 2.4 3.6 1.2
не дает первой для не первого столбца

Ydin
т.е. для

12    5    5    2  
 4    1    2    1  
 6    2    3    1

получаем

12    5    5    2
4.8    1.2    2.4    1.2
7.2    2.4    3.6    1.2

где сумма второй и третьей строки

12    3.6    6    2.4

не дает первой:

12    5    5    2

для каждого столбца кроме первого суммарного берем
Анов=Астар/СуммСтолбцастар*Сумма СтолбцаНов(первая строчка) - все
для контроля потом составляем первый столбец как сумму строк
и контроль сумма верхняя строка

т.е. для 3 и 4 столбца значения не поменяются - бо нет смены общей суммы
а для 2 столбца
А2нов=1/3*5=1,66666
А3нов=2/3*5=3,33333

так внимательнее прочитал
значит начало как и было

для каждого столбца кроме первого суммарного берем
Анов=Астар/СуммСтолбцастар*Сумма СтолбцаНов(первая строчка)

получаем матрицу


потом учитывая общее распределение
приводим ее к
тут
каждая строчка расчитывается как


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

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

как вариант обхода проблемы точности - можно предложить все строки окурглять до нужного количества знаков - а одну из строк получать как разницу суммы с суммой остальных





Исправлено 2 раз(а). Последнее : Mitchman, 10.04.12 02:20

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

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

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

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

в предложенном мной алгоритме принцип несколько иной - когда дельта каждой ячейки разбрасывается по остальным ячейкам строки, то на ячейку с большей величиной распределится большая часть этой дельты. То есть при дельте = 3 и двух ячейках для ее распределения, хранящих, например 10 и 20, в ячейку, хранящую 10, будет добавлено 1, а в ячейку хранящую 20, будет добавлено 2. А минимальный квадрат суммы отклонений получится при распределении 1.5 + 1.5, а не 1 + 2. Так что при желании этот момент в алгоритме можно подкорректировать.

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

Нет, первый столбец нельзя считать как сумму, надо распределять.
Он ведь на сумму по первой строки должен выйти.
Все по удельным весам.
Эта задача решается в таких программах, как SAP R3, Галактика.
Но у меня их нет, чтобы проверить правильность своего решения.
Просто я математику подзабыл и довольно прилично.
Подобную задачу в молодости решал.
Просто подобрать числа - не проблема. Оптимально надо, когда сумма квадратов отклонений старых и новых значений минимальная



Исправлено 1 раз(а). Последнее : Ydin, 10.04.12 16:39

2 akvvohinc.
Да, условие важное - числа положительные.
Если бороться с округлением, то может быть дельту распределять и проходит.
Здесь номер не идет, сразу в минусы попадаем по кому-то.
Когда аналитически эта задача решается, то минимизируется не сумма квадратов, а логарифм от нее.
Это вносит несимметричность, поменяв последовательность столбцов, получим разные результаты.
Для округления, наверняка, Ваш алгоритм проходит.



Исправлено 1 раз(а). Последнее : Ydin, 10.04.12 16:52

Эту задачу называли раньше двумерной балансировкой. Но Гугл с Яндексом по такому термину к результату не привели.
Я расчитывал, что кто-то с ней имел дело. Если нет, то нет, но не думайте, что это тривиальная задача.