如何解决不平等制度?
-
07-07-2019 - |
题
我已将问题(表格布局算法)减少到以下问题:
想象一下,我有N个变量X 1 ,X 2 ,...,X N 。我也有一些(未确定的)不等式,例如:
X 1 > = 2
x 2 + X 3 > = 13
等
每个不等式是一个或多个变量的总和,并且始终使用> =运算符将其与常量进行比较。我不能事先说出每次会有多少不等式,但所有变量都必须是非负的,所以每个变量已经是一个。
如何以这种方式解决这个系统,变量的值尽可能小?
已添加:阅读维基百科文章并意识到我忘了提及变量必须是整数。猜猜这让NP很难,是吗?
解决方案
最小化x1 + x2 + ...其中xi满足线性约束称为线性编程。 维基百科
中详细介绍了这一点。其他提示
您也可以直接将线性模型发布到NEOS平台( http:/ /neos.mcs.anl.gov/neos/solvers/index.html )。您首先要做的就是用AMPL等代数语言编写模型。然后NEOS将解决模型并通过电子邮件返回结果。
不隶属于 StackOverflow