在MATLAB中求解方程组

问题描述

我有一个不确定的线性方程组Ax = b(即未知量多于方程组)，我想在matlab中求解.

I have a system of under-determined linear equations Ax = b (i.e. more unknowns than equations) that I would like so solve in matlab.

我知道这通常意味着无数个解决方案，但是我也知道解决方案应为正整数且小于一定数量.我可以找到满足这些额外要求的所有解决方案吗?

I know that this would usually mean an infinite number of solutions, but I also know the solutions should be positive integers and less than a certain number. Can I find all the solutions that meet those additional requirements?

此问题来自一个未知矩阵，在该矩阵中我知道每一行和每一列的总和.

This problem come from having an unknown matrix where I know the sum of each row and column.

例如要查找的未知矩阵

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

已知行金额

5
7
3

列汇总知道

2 6 6 1

我尝试了lsqnonneg(A，b)函数，该函数仅给出一个有效的解决方案

I've tried the lsqnonneg(A,b) function which gives only one valid solution

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

推荐答案

您拥有的通常被称为 integer-线性编程，并且已知它是NP困难的(这意味着在解决方案出来之前不要屏住呼吸).

What you have is often called integer-linear programming and it is known to be NP-hard (which means don't hold your breath until a solution comes out).

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

If you want to solve it without the integerness, you have a linear program and hence can use linprog. If you think of your unknown matrix as vector of unknown entries then column sum is just

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可以将它们绑定为额外的参数.但是，您没有目标函数，您可以组成诸如最小化的所有未知数之和之类的东西，或者其中之一或任何其他线性目标会做的事情，或者可以将其保留为空，从而得到任何可行的结果.

These are your equality constraints also you have the inequality constraints but only to bound the unknown values. linprog can bound them as extra arguments. However you don't have an objective function which you can make up something like sum of all unknowns minimized or one of them or any other linear objective would do or you can leave it empty and you get any feasible result.

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

如果某些输入项保证为零等，则可能所有解决方案都被强制为整数.否则，您需要具有非凸特定的整数编程求解器，例如这里

If you have certain entries that are guaranteed to be zero etc. Then it might be possible that all solutions are forced to be integers. Otherwise you need to have nonconvex specific integer programming solvers for example given here

这篇关于在MATLAB中求解方程组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！