关于线性分配问题的表述
我正在查看此处定义的分配问题的标准定义
我的问题是具有两个约束（乳胶符号如下）：
\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} 对吗？
I'm looking at the standard definition of the assignment problem as defined here
My question is to do with the two constraints (latex notation follows):
\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n
Specifically, why the second constraint required? Doesn't the first already cover all pairs of x_{ij}?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
考虑矩阵
x_ij，其中i覆盖行，j覆盖列。第一个方程表示对于每个
i（即，对于每一行！）该行中的值之和等于 1。第二个方程表示每个
j的 thta (也就是说，对于每一列！）该列中的值之和等于 1。Consider the matrix
x_ijwith theiranging over the rows, andjranging over the columns.The first equation says that for each
i(that is, for each row!) the sum of values in that row equals 1.The second equations says thta for each
j(that is, for each column!) the sum of values in that column equals 1.不会。鉴于
X中的所有条目都是0或1，一个约束条件是“只有一个1 在每列中” - 另一个说“在每行中恰好有一个1”（我总是忘记传统上矩阵下标的方向去）。这些陈述具有独立的真值。No. Given that all the entries in
Xare0or1, one constraint says 'there is exactly one1in each column' - the other says 'there is exactly one1in each row' (I always forget which way round matrix subscripts conventionally go). These statements have independent truth values.这根本就不是一个编程问题。但无论如何我都会回答。
第一个是对 i 的每个值的 j 求和。第二个是 i 的总和，对于 j 的每个值。
因此本质上，这些约束集之一要求矩阵 x_{i,j} 矩阵的各行之和必须为 1。另一个约束是要求该矩阵各列的总和必须是统一的。
(edit) 看来我们这里还没有说清楚。考虑矩阵
我们必须同意该矩阵的各行之和为每行 1。但是，当计算第一列元素的总和时，它为零，而第二列元素的总和为 2。
现在，考虑另一个矩阵。
请注意，行上或列下的总和始终为 1。
This is not even remotely a programming problem. But I'll answer it anyway.
The first is a sum over j, for EACH value of i. The second is a sum over i, for EACH value of j.
So essentially, one of these constraint sets requires that the sum across the rows of the matrix x_{i,j} matrix must be unity. The other constraint is a requirement that the sum down the columns of that matrix must be unity.
(edit) It seems that we are still not being clear here. Consider the matrix
One must agree that the sum across the rows of this matrix is 1 for each row. However, when you form the sum of the elements of the first column, it is zero, and the sum of the elements in the second column, we find 2.
Now, consider a different matrix.
See that here, the sum over the rows or down the columns is always 1.