python - 求解最小值的不等式

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将给出的绝对最小值C，给定输入D和列表，A并且B由a[0 - n]和组成b[0 - n ]。

我目前正在用 Python 解决这个问题，但一般来说问题是与语言无关的。

澄清更新：系数x[0 - n]仅限于非负整数集。

score 11 · Accepted Answer

这看起来像一个线性规划问题。Simplex 算法通常会给出很好的结果。它基本上走在由不等式界定的子空间的边界上，寻找最优值。

直观地想一想：每个不等式都表示一个半空间，一个 n 维空间中的平面，你必须在它的右侧。您的效用函数就是您要优化的功能。如果空间是封闭的，则最优值将位于封闭空间的顶点之一；如果它是开放的，那么最优值可能是无限的。

score 3 · Accepted Answer

查看有关线性规划的维基百科条目。整数编程部分是您要搜索的内容（x[i] 是整数的约束并不容易）。

在 python 库中搜索 branch&bound、branch&cut 等（我认为它们尚未在 scipy 中实现）。

其他有趣的链接：

score 2 · Accepted Answer

2

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

于 2008-10-22T19:56:32.320 回答

score 1 · Accepted Answer

您可能想使用 Matlab 或 Mathematica 或查看来自Numerical Recipes in C的代码，以获得有关如何实现最小化函数的想法。提供的链接是本书 1992 年的版本。较新的版本可在亚马逊获得。

score 0 · Accepted Answer

0

这家公司有一个工具来做这种事情。

于 2008-10-22T20:33:19.987 回答

5 回答 5