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

[waxtep]

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

Кстати, выше я, видимо, ошибочно говорил о минимизации дисперсии значений не для сотрудников ($k$ значений), а для цехов ($N$ значений).

Угу. Таким образом, минимизации подлежит следующая величина:

$$D=\sum_{i=1}^N{k_i\left(\frac{M_i}{k_i}-\frac{L}k\right)^2}$$

где $L=\sum_{i=1}^N{M_i}$ Посмотрим, как изменится величина $D$ при переходе $d$ рабочих из цеха номер $p$ в цех номер $s$, если я нигде не наврал, то

$$\Delta D_{p\rightarrow s}(d)=d\left(\frac{M_p^2}{k_p(k_p-d)}-\frac{M_s^2}{k_s(k_s+d)}\right)$$

Есть оптимальное значение количества переходящих рабочих (в смысле максимального уменьшения дисперсии при переходе рабочих из цеха $p$ в $s$), снова, если не наврано:

$$d_{p\rightarrow s}^{opt}=\frac{k_pM_s-k_sM_p}{M_p+M_s}$$

Оно не обязано быть целым и в поисках оптимума имеет смысл проверить округленные в обе стороны значения.
Дальше я бы как-то так действовал:
1. В качестве начального приближения раскидал бы $k$ рабочих по цехам по описанному в предыдущих сообщениях методу;
2. Повычислял бы значений $d_{p\rightarrow s}^{opt}$ и соответствующих $\Delta D_{p\rightarrow s}(d)$ для пар соседних по величине нагрузки $M_i$ цехов (а может быть, для верности, для всех пар цехов; их явно немного, можно себе позволить);
3. Произвел бы перевод рабочих из цеха в цех, начиная с самых больших по модулю $d_{p\rightarrow s}^{opt}$ и контролируя, что один и тот же цех не подвергается миграции более одного раза;
4. Верил бы, что процесс сойдется к глобальному минимуму $D$ и возвращался на шаг 2 до тех пор, пока возможность оптимизации есть; вера-верой, но для избегания бесконечного цикла поставил бы максимально допустимое количество возвращений на шаг 2;
5. Отлаживал бы алгоритм на каверзных примерах и размышлял как его улучшить.

[Dmitriy40]

(Оффтоп)

Хотел я предложить аналогичное (только почти без формул): отсортировать массив цехов по величине нагрузки $M_i/k_i$, пытаться перевести одного рабочего из $\min$ (начала массива) в $\max$ (конец массива) если это уменьшает дисперсию, с пересортировкой массива (она оптимизируется, ведь переставляется всего два элемента) и повтором пока находится хотя бы один возможный перевод. Требованием уменьшения дисперсии на каждом шаге исключаем зацикливание и хождение по кругу перестановок. Но пока писал понял что сильнее уменьшить дисперсию может перевод $\neg\min\to\max$ (не из минимума), или $\min\to\neg\max$, или даже $\neg\min\to\neg\max$. Т.е. перебор всех пар в поисках наибольшего уменьшения дисперсии. Но пока писал это, дошло что любой такой перевод меняет картину/множество допустимых (по условию максимального уменьшения дисперсии) переводов и значит глобальный оптимум может и не найтись. А это снова полный перебор. Ну и всё стёр.

[melnikoff]

waxtep, Dmitriy40, спасибо! Очень помогли.
waxtep, выкладки верные, перепроверил.
Поэкспериментировал с различной инициализацией алгоритма. Независимо от первоначальной рассадки рабочих по цехам в итоге алгоритм сходится к одному значению $D$. При этом, если инициализировать алгоритм рассадкой

$$ k_i=\begin{cases} round\left(k\dfrac{M_i}{\sum{M_i}}\right)&\text{, если $round\left(k\dfrac{M_i}{\sum{M_i}}\right)>0$;}\\ 1&\text{, если $round\left(k\dfrac{M_i}{\sum{M_i}}\right)=0$.}\\ \end{cases} $$

с последующим дораспределением оставшихся и подрезанием лишних, чтобы $\sum{k_i}=k$, алгоритм сходится всего за одну-две итерации (в одной итерации происходит пересадка рабочих между парами цехов, при этом каждый цех участвует в пересадке не более 1 раза).
Доказать, что значение $D$, которому сходится алгоритм, является глобальным минимумом, у меня пока не получилось.
В общем, с практической точки зрения, задача решена.

Теперь меня волнует другой вопрос.
К какому классу задач можно отнести эту задачу? Вряд ли она является новой.

[Dmitriy40]

(Оффтоп)

Запись системы можно упростить до $k_i=\max \left(1, \left\lfloor k\dfrac{M_i}{\sum M_i} \right\rceil \right)$, где $\lfloor\ldots\rceil$ обозначено округление к ближайшему $\operatorname{round}(\ldots)$.

По моему это одна из модификаций задачи о рюкзаке.