求不等式的最小值

Question

我正在解决一个编程问题，主要是一个方程和不等式的组合：

x[0]*a[0] + x[1]*a[1] + ... x[n]*a[n] >= D
x[0]*b[0] + x[1]*b[1] + ... x[n]*b[n] =  C

我想找出一些值 X，使得在给定输入 D 和两个列表 A 和 B（分别包含 a[0 - n] 和 b[0 - n]）的情况下，C 的值达到绝对最小。

目前我在用 Python 来解决这个问题，但这个问题本身和编程语言无关，可以用任何语言来处理。

补充说明：这些系数 x[0 - n] 只能是非负整数。

Answer 1

看起来这是一个线性规划的问题。

Answer 2

看看这个维基百科上关于线性规划的内容。里面的整数规划部分正是你需要的（x[i]必须是整数这个限制可不是那么简单）。

可以搜索一下Python库，比如分支限界法、分支切割法之类的（我觉得这些在scipy里还没有实现）。

还有一些有趣的链接：

• GNU线性规划工具包
• IBM关于GLPK的文章

Answer 3

这看起来像是一个线性规划的问题。通常情况下，单纯形算法能给出不错的结果。它的基本原理是沿着由不等式划定的子空间的边界走，寻找最优解。

想象一下：每个不等式代表一个半空间，也就是在n维空间中的一个平面，你必须站在这个平面的某一侧。你的效用函数就是你想要优化的东西。如果这个空间是封闭的，最优解会出现在这个封闭空间的某个顶点；如果是开放的，最优解可能是无限的。