0

问题：

最小化x1+x2+...+xn

已知k1*x1+k2*x2+...kn*xn = T

k1,k2,...,kn并且T是已知整数并且 > 0

k1 > k2 > k3 > ... > kn

所有的 x 也是整数并且 >= 0

找到所有的 x

我试图使用 Rglpk 和 Glpk。但我找不到只有一行矩阵的例子。这是整数编程吗？它可以解决吗？非常感谢。

我写的一些 Ruby 代码：

ks = [33, 18, 15, 5, 3]
t = 999

problem = Rglpk::Problem.new
problem.name = "test"
problem.obj.dir = Rglpk::GLP_MIN

rows = problem.add_rows(1)
rows[0].name = "sum of x equals t"
rows[0].set_bounds(Rglpk::GLP_UP, t, t)

cols = problem.add_cols(ks.size)
ks.each_with_index do |k,index|
  cols[index].name = "k: #{k}"
  cols[index].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)
end

problem.obj.coefs = Array.new(ks.size, 1)

problem.set_matrix(ks)

problem.simplex
minimum_x_sum = problem.obj.get
xs = []
cols.each do |col|
  xs << col.get_prim
end
xs
4

1 回答 1

3

是的，它是一个整数程序，一个相当有名的程序，即所谓的“背包问题”。因此，您可以使用您提到的任何一个包来解决它（前提是变量的数量不是太多），但更有效的方法是使用动态编程（参见上面的链接）。这里使用 DP 实现起来非常简单。这是我通过谷歌搜索找到的一个 Ruby 实现。

我应该提到一些相关的花絮。首先，您的约束是等式约束：

k 1 x 1 + k 2 x 2 +...+ k n x n = T

但这通常被（DP）背包算法假定为不等式：

k 1 x 1 + k 2 x 2 +...+ k n x n <= T

要处理等式约束，您可以稍微修改算法，或添加以下项：

M*(T - x 1 + x 2 +...+ x n )

对于您要最小化的目标，其中M是一个非常大的数字（也许是 10 6），从而在最优解中强制相等。（展开后，每个 x i的系数变为。可以忽略1-M常数项。）MT

还有两个细节：

  • DP 算法允许目标中的变量具有除 以外的系数1（并且当所有系数相等时效率没有增益1）；和
  • 如果 DP 算法最大化（而不是最小化）目标，您可以简单地对目标中的变量系数取反，以获得最小化问题的最优解。
于 2015-09-07T18:13:37.590 回答