logo标签列表

解决不等式以找到最小值

pythonlanguage-agnosticequationlinear-programminginequality
3

我正在解决一个编程问题，核心是一组方程和不等式：

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]被限制为非负整数集合。
乍一看，这个问题似乎有多种解决方案。你能提供一些实际数据来参考吗？ - Lasse V. Karlsen
x[0]到x[n]是否大于或等于零？ - Federico A. Ramponi
是的，他们确实这样做。感谢您澄清问题。 - pbh101
嗯，那我也会坚持线性规划... - Federico A. Ramponi
整数！那么这就是一个整数规划问题（更加困难），需要使用分支定界等算法。 - Federico A. Ramponi
显示剩余2条评论
5个回答
11
这看起来像是一个线性规划问题。单纯形算法通常能够得出良好的结果。它基本上沿着由不等式限定的子空间的边界行走，寻找最优解。
从视觉上考虑：每个不等式表示一个半空间，在n维空间中是一个平面，你必须在右侧。你的效用函数是你要优化的。如果空间是封闭的，最优解将位于封闭空间的一个顶点；如果它是开放的，那么最优解可能是无限的。
3
请查看维基百科关于线性规划的条目。整数规划部分是您正在寻找的内容（x [i]约束为整数并不容易）。
搜索Python库以获取分支限界，分支定界等类似内容（我认为它们尚未在scipy中实现）。
其他有趣的链接：
2
1

你可能想使用Matlab或Mathematica，或者查看C语言数值计算中的代码，以获取有关如何实现最小化函数的想法。提供的链接是该书的1992年版本。新版本可在亚马逊上获得。

0

这个公司有一个工具可以做那种事情。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接