algorithm - 关于线性分配问题的表述

Question

我正在查看此处定义的分配问题的标准定义

我的问题与这两个约束有关（乳胶符号如下）：

\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n

具体来说，为什么需要第二个约束？第一个不是已经涵盖了所有的 x_{ij} 对吗？

Answer 1

考虑x_ij具有i行和j列范围的矩阵。

第一个等式表示，对于i每一行（即每一行！），该行中的值之和等于 1。

第二个等式表示，对于每个j（即，对于每一列！），该列中的值之和等于 1。

Answer 2

不。鉴于中的所有条目X都是0or 1，一个约束说“1每列中恰好有一个” - 另一个说“1每行中恰好有一个”（我总是忘记传统上矩阵下标的方向）。这些陈述具有独立的真值。

Answer 3

这甚至不是远程编程问题。但无论如何我都会回答。

第一个是对 j 的总和，对于 i 的每个值。第二个是 i 的总和，对于 j 的每个值。

因此，本质上，这些约束集之一要求矩阵 x_{i,j} 矩阵的各行的总和必须为单位。另一个约束是要求该矩阵的列的总和必须是统一的。

（编辑）似乎我们在这里仍然不清楚。考虑矩阵

[0 1]
[0 1]

必须同意，该矩阵各行的总和对于每一行都是 1。但是，当你形成第一列元素的总和时，它为零，而第二列元素的总和，我们找到 2。

现在，考虑一个不同的矩阵。

[0 1]
[1 0]

看到这里，行或列的总和始终为 1。