如何解决不平等制度？

Question

我已将问题(表格布局算法)减少到以下问题:

想象一下,我有N个变量X ₁,X ₂,...,X _ñ.我也有一些(未确定的)不等式,例如:

X ₁ > = 2
x ₂ + X ₃ > = 13
等

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

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

补充:阅读维基百科文章并意识到我忘了提到变量必须是整数.猜猜这让NP很难,是吧？

Answer 1

最小化x1 + x2 + ...其中xi满足线性约束称为线性编程.它在维基百科中有一些细节

Answer 2

你有什么基本的线性规划问题.你想最大化方程X_1 + ... + X_n受

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

有许多算法可以解决这类问题.最着名的是Simplex算法,它可以在平均情况下非常有效地解决您的等式(有一些警告),尽管存在LP问题,Simplex算法需要指数级的许多步骤来解决(在问题大小中).

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