我有一个欠定线性方程组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
2 回答
你所拥有的通常被称为integer-linear programming并且它被称为NP-hard(这意味着在解决方案出来之前不要屏住呼吸) .
如果你想在没有整数的情况下解决它,你有一个线性程序,因此可以使用
linprog
. 如果您将未知矩阵视为未知条目的向量,则列总和就是同样,行和是
这些是你的等式约束,你也有不等式约束,但只能绑定未知值 .
linprog
可以将它们绑定为额外的参数 . 然而,你没有一个客观函数可以弥补所有未知数的总和或其中一个或任何其他线性目标所做的事情,或者你可以将它留空并获得任何可行的结果 .如果您有某些条目保证为零等等,那么所有解决方案都可能被强制为整数 . 否则,您需要具有非凸特定整数编程求解器,例如given here
'fmincon'优化方法可能能够帮助您 - 它允许在运行之前添加非线性不等式约束:http://uk.mathworks.com/help/optim/ug/nonlinear-inequality-constraints.html
编辑:刚刚发现使用行和以帮助确定优化的答案,所以我给出的答案可能是有限的用途 . 仍然值得一试 .