在给定行和列总和的约束的情况下找到NxN矩阵的元素 - Mathematica或Matlab

Question

我正在尝试找到NxN矩阵的元素,以便满足给定的行和列总和.唯一的另一个约束是矩阵的元素被限制为整数0和1.

这可能是Matlab或Mathematica中的一些简单的线条(我在这里寻找并在R中发现了一些相关的问题),但我的相关编码经验只是在约束优化中 - 我在这里失去了没有目标函数最小化.

我的第一个想法是设置一个线性代数问题,Ax = b,但这不起作用,因为A'A是单数.(我将在下面的评论中提供详细信息,以防它有所帮助.)

我的下一个想法是试图通过赋予它"约束Ax = b和整数约束"的"虚拟"目标函数来"欺骗"Mathematica中的NMinimize求解器:

    x = Map[Subscript[x, #] &, Range[1, Ngrid^2]];
    x = Map[Subscript[x, #] &, Range[1, Ngrid^2]];
    NMinimize[{x.x\[Transpose], A.x == b && Apply[And,Thread[GreaterEqual[x, 0]]] && 
    Apply[And, Thread[LessEqual[x, 1]]] && Element[x,Integers]}, x, 
    Method -> "DifferentialEvolution", MaxIterations -> 2000];

但它遇到了相同的"递归"错误.

我有一种感觉,这不是解决问题的方法.是否有一些命令允许我根据约束填充矩阵的元素？如果它没有生成唯一的解决方案,有没有办法查看解决方案集？

谢谢,丹

编辑:这是我对线性代数解决方案的想法,Ax = b:

A是0s和1s的2N×N ^ 2矩形矩阵.每列对应于解向量x中的N ^ 2个元素之一(我们之后的重构的NxN矩阵).(编辑:前N行对应于受每个行约束影响的x元素,后N行对应于受每个列约束影响的x元素.)

x是0和1的N ^ 2×1矢量(重构的N×N解矩阵).

b是行和列总和的2N x 1向量(约束).

例:

如果N = 3并且我们想要找到x(ETA:下面的"x"是我们所追求的解决方案;我们不提前知道它):

    1   0   0
    1   0   1
    0   1   0

我们可以写A =

    1   1   1   0   0   0   0   0   0
    0   0   0   1   1   1   0   0   0
    0   0   0   0   0   0   1   1   1
    1   0   0   1   0   0   1   0   0
    0   1   0   0   1   0   0   1   0
    0   0   1   0   0   1   0   0   1

并且z =

    1
    2
    1
    2
    1
    1

求解不像x = inv(A'A)*A'z那么简单,因为A'A没有逆.

提前感谢您提供的任何帮助!

Answer 1

这是一种天真的方法.这取决于您需要如何扩展:

n = 3;
sumsrows = {2, 1, 1};
sumscols = {1, 2, 1};
X = Array[x, {n, n}];

fi = FindInstance[
   And @@ Thread[(Tr /@ X) == sumsrows] && 
   And @@ Thread[(Tr /@ Transpose@X) == sumscols] && 
   And @@ Thread[0 <= Flatten@X <= 1], Flatten@X, Integers]

Partition[fi[[1, All, 2]], n] // MatrixForm