线性方程组，附加最小变量和约束

Question

我有一个线性方程组，我已经使用高斯-乔丹消除将其简化为行梯队矩阵。我有 n 个变量 Xn 的系统(其中 Xn 在 N0 中(=正整数((有多个解决方案，我想找到所有 Xn 的总和最小的女巫的解决方案。

我怎样才能以编程方式做到这一点？

例如，考虑以下线性方程组：

x1 +              + x5 + x6 = 2
     x2           + x5      = 1       
          x3           + x6 = 1
               x4 + x5 + x6 = 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 (而前 3 个解决方案只有 2

个(

在有多个最小解决方案的情况下(例如这里，解决方案 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

(确切的语法取决于工具(。