matlabで未決定の方程式系を解く

Question

matlabで解決したいと思っている未定1次方程式Ax = b（すなわち、方程式より未知数）の系があります。

これは通常、無限の数の解を意味することがわかっていますが、解も正の整数であり、一定の数より小さくなければなりません。これらの追加要件を満たすすべてのソリューションを見つけることはできますか？

この問題は、各行と列の合計を知っている未知の行列を持つことに起因します。

5 
7 
3 

列の和が

2 6 6 1 

を知っている知ら

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

行の合計を見つけるために、未知の行列私は、唯一の有効な解決策を提供しますlsqnonnegを（A、B）の機能を試してみた

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

Answer 1

あなたの持っているものは、しばしばinteger-linear programmingと呼ばれ、NP-hard（解決策が出るまで息を止めないこと）を意味します。

整数なしで解きたいのであれば、リニアプログラムがあり、linprogを使うことができます。あなたは、未知のエントリのベクトルとしてご不明な行列を考える場合は、列合計は同様に、行の合計が

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 

これらは、あなたの等式制約されているだけで

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 

です、その後もあなたは不等式制約を持っているだけに未知の値を束縛する。 linprogはそれらを余分な引数として拘束できます。しかし、すべての未知数を最小化したものやそれらの1つまたは他の線形目的関数の和のようなものを作ることができる目的関数を持っていないか、空にしておけば実行可能な結果が得られます。

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

Answer 2

'fmincon'最適化アプローチはあなたを助けることができるかもしれない - それは実行する前に追加する非線形不等式制約することができます：http://uk.mathworks.com/help/optim/ug/nonlinear-inequality-constraints.html

編集：ただ、最適化された答えを判断するために、行和の使用を見つけたので、私は与えた答えがあるかもしれません限られた使用の。しかし、まだショットの価値があるだろう。