如何解决不平等制度？

StackOverflow https://stackoverflow.com/questions/1432580

题

我已将问题（表格布局算法）减少到以下问题：

想象一下，我有N个变量X 1 ，X 2 ，...，X N 。我也有一些（未确定的）不等式，例如：

X 1 ＆gt; = 2
x 2 + X 3 ＆gt; = 13
等

每个不等式是一个或多个变量的总和，并且始终使用＆gt; =运算符将其与常量进行比较。我不能事先说出每次会有多少不等式，但所有变量都必须是非负的，所以每个变量已经是一个。

如何以这种方式解决这个系统，变量的值尽可能小？

已添加：阅读维基百科文章并意识到我忘了提及变量必须是整数。猜猜这让NP很难，是吗？

有帮助吗？

解决方案

最小化x1 + x2 + ...其中xi满足线性约束称为线性编程。 维基百科

中详细介绍了这一点。

其他提示

您所拥有的是一个非常基本的线性编程问题。您希望最大化 X_1 + ... + X_n 等式

X_1 >= 2
X_2 + X_3 >= 13
etc.

有许多算法可以解决这类问题。最着名的是单纯形算法，它可以非常有效地解决您的等式（有一些警告）平均情况，虽然存在LP问题，Simplex算法需要指数级的许多步骤才能解决（问题大小）。

存在LP解算器的各种实现。例如， LP_Solve 应满足您的大部分要求

您也可以直接将线性模型发布到NEOS平台（ http：/ /neos.mcs.anl.gov/neos/solvers/index.html ）。您首先要做的就是用AMPL等代数语言编写模型。然后NEOS将解决模型并通过电子邮件返回结果。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top