求解最小值的不等式
我正在研究一个编程问题，该问题可归结为一组方程和不等式：
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 的值，该值将给出 C 的绝对最小值>，给定输入 D 和列表以及由 a[0 - n] 和 < 组成的 A 和 B代码>b[0 - n]。
我目前正在用 Python 解决这个问题，但这个问题通常与语言无关。
澄清更新：系数x[0 - n]仅限于非负整数集合。
I'm working on a programming problem which boils down to a set of an equation and inequality:
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
I want to solve for the values of X that will give the absolute minimum of C, given the input D and lists and A and B consisting of a[0 - n] and b[0 - n ].
I'm doing the problem at the moment in Python, but the problem in general is language-agnostic.
CLARIFICATION UPDATE: the coefficients x[0 - n] are restricted to the set of non-negative integers.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这看起来像是一个线性规划问题。 Simplex 算法 通常会给出良好的结果。 它基本上沿着由不等式界定的子空间的边界行走，寻找最优值。
直观地思考一下：每个不等式都表示一个半空间，即 n 维空间中的一个平面，您必须位于其右侧。 你的效用函数就是你想要优化的。 如果空间是封闭的，则最佳位置将位于封闭空间的顶点之一； 如果它是开放的，则最优值可能是无限的。
This looks like a linear programming problem. The Simplex algorithm normally gives good results. It basically walks the boundaries of the subspace delimited by the inequalities, looking for the optimum.
Think of it visually: each inequality denotes a half-space, a plane in n-dimensional space that you have to be on the right side of. Your utility function is what you're trying to optimize. If the space is closed, the optimum is going to be at one of the apexes of the closed space; if it's open, it's possible that the optimum is infinite.
查看维基百科有关线性规划的条目。 整数编程部分就是您正在寻找的内容（x[i] 是整数的约束并不容易）。
在Python库中搜索branch&bound、branch&cut等（我认为它们还没有在scipy中实现）。
其他有趣的链接：
Have a look at the wikipedia entry on linear programming. The integer programming section is what you're searching for (the constraint of the x[i] being integers is not an easy one).
Search python libraries for branch&bound, branch&cut and the like (I don't think they have been implemented in scipy yet).
Other interesting links:
看起来这是一个线性规划问题。
It looks like this is a linear programming problem.
您可能想使用 Matlab 或 Mathematica 或查看 C 语言数值食谱 中的代码关于如何实现最小化函数的想法。 提供的链接指向该书 1992 年版本。 较新的版本可在亚马逊购买。
You might want to use Matlab or Mathematica or look at code from Numerical Recipes in C for ideas on how to implement minimization functions. The link provided is to the 1992 version of the book. Newer versions are available at Amazon.
这家公司有一个工具可以做这类事情。
This company has a tool to do that sort of thing.