3

我有一个线性方程组，我已经使用 Gauss-Jordan 消元法将其简化为行梯形矩阵。我的具有 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 不是最小的（而前 2 个解决方案只有 3 个）

如果有多个最小解决方案（例如这里，解决方案 1 和 2 都是最小的），我不关心返回的最小解决方案，只要它是最小解决方案之一

4

1 回答 1

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

（确切的语法取决于工具）。

于 2017-02-07T21:42:02.623 回答