似乎是个带约束条件的极值问题

zhcosin

最近工作上遇到一个问题，抽去业务细节，简化成数学模型大概是这样的，某公司下属20多个业务代表处，每个业务代表处都有一批外包人员，这些外包人员都来自于为数不多的几个外包服务公司(不超过20个)，现在要为这些外包人员打上 A、B、C、D、E、F、G、H、I、J等业务标签(共十个业务标签)，目标是希望整个公司下各个业务标签的外包人数要大致相等。当然最理想的办法就是为整个公司的外包人员随机分配标签，但是在管理上存在难度，为方便管理，要求同一业务代表处下来源于同一外包公司的人员要打上相同的业务标签，整个公司的外包人员大概有几万，而各业务代表处的外包人员分布并不均匀，几百到几千不等，现在想要寻找一个自动化分配业务标签的方法。

再进一步抽象的话，基本就是这样的，把公司外包人员在各业务代表处与来源外包公司的数量分布作成一个二维矩阵，要为矩阵的每个元素打上已知数目的标签之一，最后相同标签的元素进行求和得到该标签下的一个量，不同标签的量形成一个有限序列，问要如何打标签才能使该有限序列方差最小?

事实上实际问题并不需要这个方差最小，只要大致满足就可以了，感觉这类问题是应该用人工智能算法，神经网络遗传算法之类的来解决。

业余的业余

不知道理解是否正确:

比如 $m$ 个业务代表处 ( $m\le 30$), $n$ 个外包公司 ($n\le 20$)，这样可以构造一个二维数组 $a_{mn}$, 其中 $a_{ij}$ 是业务代表处 $i$ 中来自外包公司 $j$ 的人员的个数。

要求一个算法，把这不超过 $600$ ($m\times n$)个整数分成 $10$ 个组，使各组中数的总和构成的数组满足特定的统计特性，比如方差最小。

业务比较生疏了，可能是胡说八道。确定性的算法(比如分枝限界，回溯法之类的状态空间搜索算法)对这个规模的问题可能不现实。当然我实际上大大夸张了这个问题的规模，现实中不大可能所有的业务代表处都有所有外包公司的人员，也就是说会存在大量的 $a_{ij}=0$. 这些为 $0$ 的元素当然可以直接忽略。当然这样处理后的一维整数数组可能还是不适合确定性的算法(状态空间是颗10叉树，回溯加适当的剪枝应该就优化到顶了).

一个比较现实的做法可以用某个策略构造一个较优的解，再用随机算法在给定的时间界限类改进这个解。具体可行性如何要试试才知道。

比如可以试着把这些数按从大到小排序，
1. 取第一个桶(标签），从大取起，到此桶当前总和快超未超平均值时停止
2. 用同样的办法取剩下的9个桶.

剩下未归入特定桶的数的个数如果已经较少，可用确定性算法处理。否则往当前总和最小的桶中装剩下的最大的数，一直到剩下的数小到适合用确定性算法(标准的子集树回溯法)处理。这样会得到一个较好的解。这个解可以再在给定的时间限制内用随机算法改进，比如一个随机的策略可以这样: 随机的从每个桶中取一个，再用确定性算法找出最有分配这些数的解，如果比当前最优解更好，那就得到了一个更优解。或许应该从随机的桶中取出随机个数的数，使取出的总个数适合于用确定性算法处理，然后用确定性算法处理之。重复这个过程直到总运行时间达到设定的上限，这样就得到了一个合理成本下的较优解。