我正在研究一个归结为一组方程和不等式的编程问题：
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并且B由a[0 - n]和组成b[0 - n ]。
我目前正在用 Python 解决这个问题，但一般来说问题是与语言无关的。
澄清更新：系数x[0 - n]仅限于非负整数集。
pbh101
问问题
2003 次
5 回答
11
这看起来像一个线性规划问题。Simplex 算法通常会给出很好的结果。它基本上走在由不等式界定的子空间的边界上，寻找最优值。
直观地想一想：每个不等式都表示一个半空间，一个 n 维空间中的平面，你必须在它的右侧。您的效用函数就是您要优化的功能。如果空间是封闭的，则最优值将位于封闭空间的顶点之一；如果它是开放的，那么最优值可能是无限的。
于 2008-10-22T19:59:29.227 回答
3
查看有关线性规划的维基百科条目。整数编程部分是您要搜索的内容（x[i] 是整数的约束并不容易）。
在 python 库中搜索 branch&bound、branch&cut 等（我认为它们尚未在 scipy 中实现）。
其他有趣的链接：
于 2008-10-22T21:28:01.577 回答
2
看起来这是一个线性规划问题。
于 2008-10-22T19:56:32.320 回答
1
您可能想使用 Matlab 或 Mathematica 或查看来自Numerical Recipes in C的代码，以获得有关如何实现最小化函数的想法。提供的链接是本书 1992 年的版本。较新的版本可在亚马逊获得。
于 2008-10-22T20:07:37.433 回答
0
这家公司有一个工具来做这种事情。
于 2008-10-22T20:33:19.987 回答