最小限の変数の追加制約がある線形方程式の合計

Question

私はすでにGauss-Jordan消去を使用して行エシロン行列に縮小された線形方程式系を持っています。 n変数Xn（ここでXnはN0（=正の整数）にあります）を持つ私のシステムは複数の解を持ち、私は魔法使いの解を見つけたいと考えていますすべてのXnの和は最小ですです。

どうすればいいですかプログラムによって？例えば

線型方程式のこのシステムで考えてみましょう。私は取得したい最小限のソリューションの

x1 +    + x5 + x6 = 2 
    x2   + x5  = 1  
      x3   + x6 = 1 
       x4 + x5 + x6 = 1 

1は次のようになります。

x3 = x4 = x5 = 0 
x1 = x2 = x6 = 1 

もう一つは

x2 = x4 = x6 = 0 
    x1 = x3 = x5 = 1 

だろう。しかし私はしたくないです

x1 = 2 
x2 = x3 = x4 = 1 
x5 = x6 = 0 

このシステムの解決策でもありますが、x1 + x2 + x3 + x4 + x5 + x6 = 5（2番目の最初の解決策では3にすぎません）のような基準では最小限ではありません。

（溶液1および2の両方が最小限である、ここでのように、）複数の最小限の溶液の場合には

、私は以来限り、それは最小限のもの

Answer 1

の一つであるとして返され、最小限のソリューションを気にしません変数はすべて非負であり、この問題は本質的に整数プログラミングと同じです。既製の整数型プログラムソルバーを使用し、

minimize x1 + x2 + x3 + x4 + x5 + x6 
subject to 
x1    + x5 + x6 = 2 
    x2   + x5  = 1 
      x3   + x6 = 1 
       x4 + x5 + x6 = 1 
integers 
x1, x2, x3, x4, x5, x6 >= 0 

（正確な構文はツールによって異なります）を使用してください。