在matlab中求解欠定方程组

Question

我有一个欠定线性方程组 Ax = b（即未知数多于方程），我想在 matlab 中求解。

我知道这通常意味着有无限多个解，但我也知道解应该是正整数且小于某个特定数。我能找到满足这些附加要求的所有解决方案吗？

这个问题来自于一个未知的矩阵，我知道每行和每列的总和。

例如要查找的未知矩阵

0 3 2 0
0 2 4 1
2 1 0 0

行总和已知

5
7
3

列和知道

2 6 6 1

我试过 lsqnonneg(A,b) 函数，它只给出一个有效的解

0 0 5 0
0 6 0 1
2 0 1 0

Answer 1

'fmincon' 优化方法可能可以帮助您 - 它允许在运行之前添加非线性不等式约束：http://uk.mathworks.com/help/optim/ug/nonlinear-inequality-constraints.html

编辑：刚刚发现使用行总和来帮助确定优化答案，所以我给出的答案可能用途有限。不过还是值得一试。

Answer 2

你所拥有的通常被称为 integer-linear programming 并且众所周知它是 NP-hard（这意味着在解决方案出现之前不要屏住呼吸）。

如果你想在没有整数的情况下解决它，你有一个线性程序，因此可以使用 linprog。如果您将未知矩阵视为未知条目的向量，那么列总和就是

col_sum = kron(eye(4),[1,1,1]);

col_sum =

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

同理，行总和为

row_sum = repmat(eye(3),1,4);

row_sum =

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

这些是您的等式约束，您也有不等式约束，但仅用于限制未知值。 linprog 可以将它们绑定为额外的参数。但是，您没有 objective 函数，您可以将所有未知数的总和最小化或其中之一或任何其他线性 objective 做，或者您可以将其留空并得到任何可行的结果。

Aeq = [col_sum;row_sum]
beq = [2 6 6 1 5 7 3]';

X = linprog([],[],[],Aeq,beq,zeros(12,1),10*ones(12,1))% 0 <= vars <= 10

X = reshape(X,3,4)

X =

    0.6550    2.0160    2.0160    0.3130
    1.1192    2.5982    2.5982    0.6845
    0.2258    1.3859    1.3859    0.0025


>> sum(X,1)

ans =

    2.0000    6.0000    6.0000    1.0000

>> sum(X,2)

ans =

    5.0000
    7.0000
    3.0000

如果您有某些保证为零的条目等。那么可能所有的解决方案都被强制为整数。否则你需要非凸特定的整数规划求解器，例如 given here

在matlab中求解欠定方程组

Solve underdetermined system of equations in matlab

matlab

math

matrix

equation-solving