Перераспределить кучу на кучки с min дисперсией

[melnikoff]

Прошу подсказать как решается данная задача.
Допустим, имеется большая куча песка массы $M$. Имеется совок, который всегда зачерпывает песка массы $m$. Причем, $M=m\cdot k$, где $k \in \mathbb{N}$.
Необходимо, зачерпывая совком песок из большой кучи, насыпать $N$ куч массами $M_1, M_2, ..., M_N$. Совсем необязательно, чтобы $M_i$ было кратно $m$.
При этом требуется, чтобы в изначальной куче песка не осталось. То есть мы изначально целимся в значения масс $M_i$, но если у нас в первоначальной куче остался песок, то мы вынуждены его перераспределять между новыми кучками.
Пусть, в итоге мы получили кучи с массами $M_{fact\;i} : k_1\cdot m, k_2\cdot m, ... , k_N\cdot m$.
Из скольки совков должна состоять каждая куча, чтобы ряд чисел $\frac{M_1}{k_1}, \frac{M_2}{k_2}, ..., \frac{M_N}{k_N}$ имел максимальную кучность (минимальную дисперсию?)?
Не могу причесть данную задачу ни под одну из известных. Первая мысль была о задаче о плотнейшей упаковке, но тут нет отграничения по массе для каждой кучки.
Прошу пинка в нужном направлении.

[waxtep]

Видимо, предполагается, что $N\leqslant k$, иначе хотя бы в одной куче песка не будет и вопрос лишен смысла. А про сумму масс $M_1,M_2,\ldots, M_N$ что-то известно? Что она $\leqslant M$, например?

[Dmitriy40]

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

[melnikoff]

waxtep в сообщении #1540301 писал(а):

Видимо, предполагается, что $N\leqslant k$

Да.

waxtep в сообщении #1540301 писал(а):

А про сумму масс $M_1,M_2,\ldots, M_N$ что-то известно? Что она $\leqslant M$, например?

В общем случае сумма целевых масс кучек может быть как больше $M$, так и меньше.

-- 24.11.2021, 03:28 --

Dmitriy40 в сообщении #1540305 писал(а):

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

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

[Dmitriy40]

melnikoff в сообщении #1540307 писал(а):

Более того, в самом начале дисперсия будет расти.

Почему? Ведь под дисперсией Вы понимаете разброс отклонений от целевой массы каждой кучки, а эти отклонения на каждом шаге могут лишь уменьшаться.
Расти дисперсия могла бы лишь если какое-то $M_i<m/2$, т.е. даже первый раз не сыпанёшь. Но даже это алгоритму не мешает, он в такую просто и не будет сыпать.

Вот насчёт глобальности да, не уверен.

Можно пойти и с конца: минимально возможная дисперсия легко считается (округляем все $M_i/m$ к ближайшим целым $k_i$ и считаем дисперсию), пока требуемое количество песка $m \sum k_i \ne M$ повторяем: если $M$ меньше, то вычитаем $1$ из $k_i$ с наименьшей дисперсией, если $M$ больше, то прибавляем $1$ к $k_i$ с наименьшей дисперсией.

PS. Кстати ради упрощения можно сразу было взять $m \equiv 1$ и тогда $M$ и все $k$ станут просто неотрицательными целыми.

[waxtep]

То есть, кабы $k_i$ не были обязаны быть натуральными, мы бы взяли $k_i=k\dfrac{M_i}{\sum{M_i}}$ и в ус не дули - дисперсия требуемой величины нулевая. Я бы в качестве первого приближения взял эти величины округленные к ближайшему целому (или к единице, если ближайшее ноль) и повычитал из наиболее крупных $k_i$ избыток $\sum{k_i}$ над $k$ в какой-нибудь осмысленной пропорции; затем понадеялся на близость этого приближения к глобальному минимуму и положился на библиотечные функции поиска минимума локального

[melnikoff]

waxtep в сообщении #1540311 писал(а):

То есть, кабы $k_i$ не были обязаны быть натуральными, мы бы взяли $k_i=k\dfrac{M_i}{\sum{M_i}}$

Это, к сожалению, невозможно, так как в реальности совки - это сотрудники, и объем совка - усредненная производительность сотрудника.

-- 24.11.2021, 15:01 --

Dmitriy40 в сообщении #1540310 писал(а):

melnikoff в сообщении #1540307 писал(а):

Более того, в самом начале дисперсия будет расти.

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

Я понимаю под дисперсией ряда чисел именно обычную дисперсию - стандартное отклонение от среднего значения этого же ряда в квадрате. То есть мне важна кучность именно ряда чисел $\frac{M_i}{k_i}$, а не $|M_i - M_{fact \; i}|$.

Dmitriy40 в сообщении #1540310 писал(а):

Расти дисперсия могла бы лишь если какое-то $M_i<m/2$, т.е. даже первый раз не сыпанёшь.

А представьте, что $M >> \sum\limits_{i}M_i$. Тогда мы будем вынуждены отсыпать как минимум 1 совок в каждую кучку.

[waxtep]

melnikoff в сообщении #1540336 писал(а):

waxtep в сообщении #1540311 писал(а):

То есть, кабы $k_i$ не были обязаны быть натуральными, мы бы взяли $k_i=k\dfrac{M_i}{\sum{M_i}}$

Это, к сожалению, невозможно, так как в реальности совки - это сотрудники, и объем совка - усредненная производительность сотрудника.

Давайте на примере покажу, что предлагаю, видимо выражаюсь недостаточно ясно. Пусть $M=10$ совков песка требуется разложить на кучки по $(1,10,100)$ совков (раз мы заговорили о производстве, видимо типичной будет ситуация $\sum{M_i}>M$). Понятно, что из $10$ совков $111$ не выйдет, поэтому речь о разбиении $10$ на сумму трех натуральных чисел в пропорции максимально напоминающей $1:10:100$ (в смысле поставленной вами задачи минимизации дисперсии величин $M_i/k_i$):

Нулевое приближение для $k_i$ (не соблюдается условие натуральности): $10/111,100/111,1000/111$
Первое приближение (округление к ближайшему натуральному): $1,1,9$
Второе приближение (приведение $\sum{k_i}$ к $k$): $1,1,8$
В этом примере просто нет других вариантов, но в общем случае надо изобрести какую-то правдоподобную эвристику избавления от избытка либо недостатка в $\sum{k_i}$ вызванного округлением.
Третье приближение (в идеале точное решение): запуск алгоритма поиска локального минимума, стартуя со второго приближения; в данном примере не требуется, в силу его простоты.

[Dmitriy40]

melnikoff в сообщении #1540336 писал(а):

То есть мне важна кучность именно ряда чисел $\frac{M_i}{k_i}$, а не $|M_i - M_{fact \; i}|$.

Простите, но как Вы тогда считаете дисперсию при любом $k_i=0$? Я этот момент обошёл вниманием, но раз Вы про увеличение дисперсии на первых шагах, то он важен.

melnikoff в сообщении #1540336 писал(а):

А представьте, что $M >> \sum\limits_{i}M_i$. Тогда мы будем вынуждены отсыпать как минимум 1 совок в каждую кучку.

По моему не обязательно, это зависит от соотношения $M_i$ между собой, если некоторые из них достаточно намного меньше остальных, то для них выгоднее $k_i=0$. Вот скажем для примера waxtep с 1:10:100 разве $k_1$ не лучше сделать $0$ вместо $1$, ведь $10/111$ ближе к нулю чем к единице и ноль даст меньший вклад в дисперсию?

waxtep
Согласен с Вашим пониманием и примером, только видимо нулевые $k_$ (пустые кучки) тоже допустимы. Добавлю для melnikoff: это ровно описанный мною подход с конца, причём ранее я сразу и эвристику выбора кучки привёл (считаем что получится при изменении данной кучки и выбираем самую подходящую). В принципе для каждой кучки дисперсию можно не пересчитывать, ведь понятно же что сумма квадратов при увеличении выражения под квадратом может лишь расти и соответственно можно искать минимальный прирост квадрата разности, что позволяет сразу выразить условие выбора кучки через $M_i, k_i$ (всё равно их отношение сравнивается с константой $m$). И кстати там модуля уже не будет, будет два варианта выражения, для уменьшения $k_i$ и для увеличения.

[waxtep]

Dmitriy40 в сообщении #1540353 писал(а):

Согласен с Вашим пониманием и примером, только видимо нулевые $k_$ (пустые кучки) тоже допустимы.

Тогда ведь на ноль делить придется, и соответствующая $M_i/k_i$ ускачет в небеса. Если я правильно понял, поставленная ТС задача на самом деле является подзадачей более глобального вопроса планирования ресурсов и сроков: сначала распределили ресурсы по работам квази-оптимальным образом (отсюда несколько необычное требование минимизировать дисперсию именно $M_i/k_i$), потом посчитали срок выполнения плана работ в целом. Может быть, на самом деле, имеет смысл по-другому выделить подзадачу, ну тут зависит от физического смысла того, что нужно ТС в итоге.

[Dmitriy40]

waxtep в сообщении #1540373 писал(а):

Тогда ведь на ноль делить придется, и соответствующая $M_i/k_i$ ускачет в небеса.

Я понимаю, но это проблема ТС, что он вот так определил дисперсию. Можно переформулировать по другому и бесконечности уйдут, например просто доопределить $M_i/k_i\equiv0$ при $k_i =0$ (доопределить $x/0\equiv0$). Это вполне физично: если работник страшно медлителен, то выгоднее оставить его сачковать отдыхать чем поручать работу.

[waxtep]

Dmitriy40 в сообщении #1540379 писал(а):

Это вполне физично: если работник страшно медлителен, то выгоднее оставить его сачковать отдыхать чем поручать работу.

А, ну я немного по-другому смысл величин истолковал: $M_i$ - объем работ одной из $N$ выполняемых параллельно задач, $M$ - общий ресурсный пул, $k_i$ - выделяемый на $i$-ую задачу ресурс. Тогда $M_i/k_i$ по смыслу - календарная длительность выполнения $i$-ой задачи, ну и желательно чтобы эти длительности кучно легли, давая оптимальное время реализации всех $N$ задач плана работ в совокупности. Кстати, в таком разрезе можно переформулировать задачу как минимаксную - на самое короткое время выполнения наиболее долгой из задач (поможет ли это чем-то, я не знаю).

[Dmitriy40]

waxtep в сообщении #1540396 писал(а):

А, ну я немного по-другому смысл величин истолковал:

По моему в общем аналогично. И требование $k_i>0$ у Вас записано в требовании выполнения всех $N$ задач. А вдруг какие-то можно и проигнорировать? Тут только исходная задача может дать ответ, можно или нет.

waxtep в сообщении #1540396 писал(а):

Тогда $M_i/k_i$ по смыслу - календарная длительность выполнения $i$-ой задачи, ну и желательно чтобы эти длительности кучно легли, давая оптимальное время реализации всех $N$ задач плана работ в совокупности.

А вот тут (логическая) ошибка: оптимальное по дисперсии время будет меньше минимально необходимого. Потому что дисперсия позволяет выбросы (длительности $i$-ой задачи) и вверх от среднего ($m$), а минимально необходимое время лишь вниз, оно же считается как максимум всех времён, а не среднее их же. Вы же сами дальше так и пишете про минимакс. Именно поэтому я не стал упоминать минимакс, не знаю как переформулировать чтобы в нём разрешились выбросы вверх (выше минимизируемого максимума, что бы это ни значило). Понятно что можно условием минимакса назначить не длительности, а их дисперсию, но это получается тавтология, оно и так уже есть в исходном условии.

[melnikoff]

waxtep в сообщении #1540373 писал(а):

Тогда ведь на ноль делить придется, и соответствующая $M_i/k_i$ ускачет в небеса. Если я правильно понял, поставленная ТС задача на самом деле является подзадачей более глобального вопроса планирования ресурсов и сроков: сначала распределили ресурсы по работам квази-оптимальным образом (отсюда несколько необычное требование минимизировать дисперсию именно $M_i/k_i$), потом посчитали срок выполнения плана работ в целом. Может быть, на самом деле, имеет смысл по-другому выделить подзадачу, ну тут зависит от физического смысла того, что нужно ТС в итоге.

Приведу условие изначальной задачи (мне кажется, так будет более понятно), которую я переформулировал в терминах кучек.
Имеется $N$ цехов одного профиля и $k$ рабочих. Каждый рабочий может выполнять усредненный объем работы в день $m$, но может выполнять и больше, если не хватает персонала. Тогда избыток работы в цеху перераспределяется на всех рабочих в равных долях.
В каждом цеху ежедневно нужно выполнять соответствующий объем работы: $M_1, M_2, ..., M_N$.
Задача состоит в том, чтобы перераспределить всех рабочих по всем цехам так, чтобы все $k$ рабочих имели по возможности равную (близкую) нагрузку.
Другими словами, нужно минимизировать дисперсию последовательности значений нагрузок для всех рабочих. Кстати, выше я, видимо, ошибочно говорил о минимизации дисперсии значений не для сотрудников ($k$ значений), а для цехов ($N$ значений).
Ещё вижу, что параметр $m$ не нужен для решения, хотя ожидается, что среднее значение для нагрузки будет близко к $m$.

(Оффтоп)

Завтра отвечу на последние сообщения. Сегодня уже вырубает.

[Dmitriy40]

melnikoff в сообщении #1540449 писал(а):

Имеется $N$ цехов одного профиля и $k$ рабочих. Каждый рабочий может выполнять усредненный объем работы в день $m$, но может выполнять и больше, если не хватает персонала. Тогда избыток работы в цеху перераспределяется на всех рабочих в равных долях.
В каждом цеху ежедневно нужно выполнять соответствующий объем работы: $M_1, M_2, ..., M_N$.
Задача состоит в том, чтобы перераспределить всех рабочих по всем цехам так, чтобы все $k$ рабочих имели по возможности равную (близкую) нагрузку.

Позволю себе дополнить неуказанные условия: $\sum\limits_i^N k_i = k > N;\; k_i>0;\; i=1\ldots N;\; k,k_i,N\in\mathbb{N}$ ($k_i$ - количество рабочих в цеху $i$). В принципе задача поменялась несущественно. waxtep, Вы были правы, $k_i=0$ недопустимо.

При $k<N$ решений очевидно нет. При $k=N$ решение тривиально: все $k_i=1$.
При $k>N$ для точного решения нужен перебор, предложенные выше методы (которые вполне рабочие) глобального оптимума могут и не найти.
$m$ да, излишне, если только нет условия не перегружать рабочих слишком сильно, вот тогда "слишком сильно" и будет функцией от $m$. И некоторые решения исчезнут (например банальные $\sum\limits_i^N M_i > k f(m)$, но не только они).