仓库管理员的最优入库方案问题

mathe

一个悲催的仓库管理员要将`m`种不同品牌的物品放到`n`个仓库里去。
每种物品的大小和数量都相同，每个仓库的剩余容量也差不多，
所以每个仓库按规定分配总数量相同的物品 （每种品牌的物品数量是`\gcd(m,n)`的倍数）。
同一个仓库中，不同品牌的物品要用盒子分开存放，相同品牌全放在一个盒子里。
为了让盒子数最少，仓库管理员应如何分配物品至各仓库？

比如三个品牌A,B,C和两个仓库a,b可以只需要4个盒子：

	A	B	C
a	2u	0	u
b	0	2u	u

这个例子揭示了问题的数学模型：已知一个m×n的非负整数矩阵各行等和，各列亦等和. 求非零元素最少的这种矩阵。

hujunhua

可以假定m,n互质，得到本原解。非互质可由本原解铺对角阵得到。
比如2×3的一个解为

2	0	1
0	2	1

则4×6的对应解为

2     0     1     0     2     1	0
0	2     0     1     0     2     1

hujunhua

貌似辗转相除法可解。以下为8×13的猜想结果。

8									2	3
	8							2			3
		8						1	1			3
			8									5
				8							5
					8					5
						8			5
							8	5

mathe

发现junhua和我的构造方法不同，得出的解确是同样好，都是m+n-gcd(m,n).只是不知道这是否总是最优解。我的方法构造的8X13的解如下：

8									2	3
	8							2			3
		8					1					4
			8			1						4
				8							5
					8					5
						7			6
							7	6

hujunhua

最优性的一个启发性说明：
从代数上看涉及一个包括m+n个约束方程的m*n元线性方程组，当gcd(m,n)=1时，实际上只有（m+n-1)个的独立约束，相应的系数矩阵的秩为m+n-1。
所以在方程的任意解中，最少得有（m+n-1)个非零分量。
（11月14日无节操修订）

mathe

只要将长度为1的线段分别平均n等分和m等分即可。在m,n不互素时有部分分割线重合

mathe

已经确定解最优了，用图论可以证明，考虑连通分支即可。

对应每种入库方案，可以构造一个包含 m+n 个点的二分图 G(E, m, n)，可将 G 的两部分顶点分别涂为黑白两色，白点对应品牌，黑点对应仓库。
如果某个仓库存放某个品牌的`x`成物品，就在对应的黑点和白点间连一条边并标上权值`xn`，如此构成G的边集 E。优化目标是使得 |E|最小。
一个结点发出的所有边的权重之和称为该结点的权汇。
按规则，每个黑点的权汇等于 m, 每个白点的权汇等于 n，全部边的权重之和=所有黑点权汇之和=所有白点权汇之和 = mn.
二分图 G(E, m, n) 的邻接矩阵可以简化为一个 m×n 矩阵，矩阵元素就是边的权重。

设 G(E, m, n) 包含 k 个连通分支`G_i(E_i, m_i, n_i),(i=1, 2, …, k)`
`m_1+m_2+…+m_k=m`
`n_1+n_2+…+n_k=n`
`|E|=|E_1|+|E_2|+…+|E_k|`
由于两个不同的连通分支是互不影响的，因此，要使 |E| 最小，只需要使每个`|E_i|`最小。
而边最少的连通图是树，`G_i(E_i, m_i, n_i)`达到树时`|E_i|=m_i+n_i-1`. 于是得最小值
`\begin{split}|E|&=|E_1|+|E_2|+…+|E_k|\\
&=(m_1+n_1-1)+(m_2+n_2-1)+…+(m_k+n_k-1)\\
&=m+n-k\end{split}`
可见欲使 |E| 达到最小，须使 k 达到最大，即 G 含有最多的连通分支。让我们来看看 G 最多能含有多少个连通分支。
对每一个连通分支`G_i(E_i, m_i, n_i)`，所有白点权汇之和为`m_i n`, 黑点为 `m n_i`，所以有 `m_i n=m n_i`，即`m_i/n_i=m/n`。
设 d= gcd(m,n), `m/n`的既约分数为`m’/n’`, 则`m_i`的最小值为`m’`, `n_i`的最小值为`n’`,  G最多可包含 d 个连通分支。所以
|E|=m+n-d=m+n-gcd(m,n)

至此，问题归结到 gcd(m,n)=1 的基本情况，这时 G 是连通的， |E|=m+n-d=m+n-1。
剩下的情况就是要讨论对于哪些树 G(E,m,n) 可以导出一个第 6 行所述的 m×n 邻接矩阵，并且其中至少存在一个全正数矩阵。
另外，本题中我们限定了物体数量是整数，但是在假设物体是可以无限分割的前提下，即使数量不是整数，对于盒子的最少数目我们也可以有同样的结论。

mathe

接着就gcd(m,n)=1的基本情况，证明每一个树G（E,m,n）恰好对应一个带权邻接矩阵，也就是如果存在，必然可以唯一决定各边的权重值。

树的边从叶到根是有层级的，边的权重可以逐级确定。
一级边就是叶结点所连的边——叶柄，一个叶结点只有一个叶柄，所以叶柄的权重可以决定下来，就是它的叶结点的权汇。
叶柄的另一端我们称为蒂。去掉所有的叶结点和叶柄，蒂的余汇可以决定下来。
必定有些蒂变成了新的叶，也就产生了新的叶柄，此即二级边，同理，新叶柄——二级边的的权重也可以决定下来，就是新叶的余汇。
重复上述过程，层层剥离，直到所剩的边都成为叶柄，这些就是顶级边了。于是所有的边都有了唯一决定的权重。
最后一个蒂就是树的根结点，当它是白点时，所有顶级边被标定的权重之和必等于 n, 黑点则等于 m。

对于一条给定的边，为了确定它的权重，除了上述逐级计算的程序，也可以用一个赋权公式直接计算，方便快捷。
我们从树的截断开始导出这个公式。
去掉树的任意一条边 e，树就被截断为两个子树，不妨分别称为边 e 的白端子树和黑端子树（解释略，请顾名思义）。
树的结点被两个子树瓜分，设白端子树分得的白点和黑点数为`m_w,n_w`，黑端子树为`m_b,n_b`. 记边 e 的权重为`r_e`.
白端子树的所有白点权汇之和等于`n\cdot m_w-r_e`，所有黑点权汇之和等于`m\cdot n_w`，由此可得`r_e=n\cdot m_w-m\cdot n_w`.
黑端子树的所有白点权汇之和等于`n\cdot m_b`，所有黑点权汇之和等于`m\cdot n_b-r_e`，由此可得`r_e=m\cdot n_b-n\cdot m_b`.
将两式写作连等式为： \[\begin{equation}r_e=n\cdot m_w-m\cdot n_w=m\cdot n_b-n\cdot m_b\end{equation}\]此即所期望的赋权公式。赋权公式表明边的权重仅与截断的结点数分配有关，而与两端子树的结构无关。
由赋权公式立即得到两个推论：
        推论1：各边权重都是整数。
        推论2（正数树判别式）：只有对于任一处截断都成立\[\begin{equation}\frac{m_w}{n_w}>\frac mn>\frac{m_b}{n_b}\end{equation}\]才能保证每条边的权都是正数（这样的树才是合符要求的解）。
那么是否一定存在每条边的权都是正数的树呢？答案是肯定的，因为我们已经有了3#的辗转相除法所产生的实例。

至此我们证明了：最优解E≥m+n-1, 并且最小值是可以达到的。

辗转相除法一开始就有最多的叶子，并且在上述层层剥离过程中每次都产生最多的新叶子，显然是一种极端解。
最优解当然应该不止极端解这一种。现在考虑进阶问题：
给定较小的m,n,请问本题有多少个本质不同的解。置换仓库或品牌可相互转化的认为是本质相同的。这个应该需要计算机计算了。

mathe

以后不妨假定m>n>1（即白点多于黑点），先考虑 m 与  n 互素的基本情况，记不同构的解数为f(m, n)。容易证明，\[f(dm, dn)=\left(\begin{split}f(m,n)&+d-1\\d\end{split}\right)\]
对于给定的 n,  当 m  充分大时应有 f(m, n)=f(m-n, n), 诚如是，我们就可以将讨论范围缩减到一个有限的基本范围.
我们来确定 这个“充分大”的下界。
先确定叶结点的数量范围。叶结点都是白点，对应于邻接矩阵中只一个非零元素（等于 n）的列.
假定叶结点有 a 个。其余 m-a 个白点都至少连着两条边， 所以所有白点发出的边数之和不小于 a+2(m-a), 即 m+n-1≥a+2(m-a).
得                a≥m-n+1
m个白点中，余下的非叶结点数 (m-a) ≤ n-1 个。显然，当不等式取等号时，这些高层级白点都是2度点。

因此，如果存在一个非任何叶之蒂的黑点，其度必不大于(n-1). 它的边都是高层级边，权都不超过(n-1), 所以该黑点的权汇不超 ` (n-1)^2`。
那么，当`m>(n-1)^2`时，每一个黑点都必定是叶蒂。
这就可以从每个叶蒂上去掉一片叶子，就得到一个树G'(E', m-n, n)，由它可通过在每个黑点上加一片叶子还原到树G（E, m, n)。
所以，对于给定的n,  那个充分大 m的下界不超过 `(n-1)^2`。对于更大的m，本原解都可以由基本范围的解树在每个蒂上加同样多的叶子得到。

当`m=(n-1)^2`时，可构造唯一一个包含非蒂黑点的树G(E, m, n)。 除此以外，其它树的黑点皆蒂，可以从去叶的G'(E',m-n, n)还原。
但是我们用它对应的邻接矩阵表述起来更为方便，如下：

(n-2)个`D_{n-1}`	`I_{n-1}`
(n-1)(n-2)个0	(n-1)个(n-1)

这里`I_{n-1}`为(n-1)阶单位矩阵，`D_{n-1}=n\cdot I_{n-1}`。比如n=4时的样子就是这样的：

4			4			1
	4			4			1
		4			4			1
						3	3	3

mathe

在最优方案树中，显然所有叶结点必须是白点，这些叶结点我们称为 1 阶白点。需要的话记为`W^1`, 可用下标来特指。
有些蒂（黑点）在去除所有叶及叶柄后变成了新的叶结点，我们称为 1 阶黑点。需要的话记为`B^1`, 可用下标来特指。
接着可以定义 2 阶白点和 2 阶黑点等，记为`W^2, B^2`等，直到根结点。

通过计算各阶白点和黑点数目可统计不等价树的数目。