如何解决不平等制度？
我已将问题（表格布局算法）简化为以下问题：
假设我有 N 个变量 X1, X2, ..., XN 。我还有一些（未确定的）不等式，例如：
X1 >= 2
x2 + X3 >= 13
。
每个不等式都是一个或多个变量的总和，并且始终使用 >= 运算符将其与常量进行比较 我无法提前说出每次会有多少个不等式，但所有变量都必须是非负的，因此每个变量已经有一个。
如何以变量值尽可能小的方式求解这个系统？
添加：阅读维基百科文章并意识到我忘记提及变量必须是整数。我想这会导致 NP 困难，是吧？
I've reduced my problem (table layout algorithm) to the following problem:
Imagine I have N variables X1, X2, ..., XN. I also have some (undetermined) number of inequalities, like:
X1 >= 2
x2 + X3 >= 13
etc.
Each inequalities is a sum of one or more variables, and it is always compared to a constant by using the >= operator. I cannot say in advance how many inequalities I will have each time, but all the variables have to be non-negative, so that's already one for each variable.
How to solve this system in such a way, that the values of the variables are as small as possible?
Added: Read the wikipedia article and realized that I forgot to mention that the variables have to be integers. Guess this makes it NP-hard, huh?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在 xi 满足线性约束的情况下最小化 x1 + x2 + ... 称为线性规划。 Wikipedia 中对此进行了详细介绍
Minimizing x1 + x2 + ... where the xi satisfy linear constraints is called Linear Programming. It's covered in some detail in Wikipedia
您遇到的是一个非常基本的线性编程问题。您想要最大化方程
X_1 + ... + X_n，但有许多算法可以解决此类问题。最著名的是 Simplex 算法，它将非常有效地求解方程（有某些注意事项）平均情况下，尽管存在 LP 问题，Simplex 算法需要指数级数量的步骤来解决（在问题大小方面）。
LP 求解器有多种实现方式。例如 LP_Solve 应该满足您的大部分要求
What you have there is a pretty basic Linear Programming problem. You want to maximize the equation
X_1 + ... + X_nsubject toThere are numerous algorithms to solve this type of problem. The most well known is the Simplex algorithm which will solve your equation (with certain caveats) quite efficiently in the average case, although there exist LP problems for which the Simplex algorithm will require exponentially many steps to solve (in the problem size).
Various implementations of LP solvers exist. For example LP_Solve should satisfy most of your requirements
您还可以将您的线性模型直接发布到 NEOS 平台 (http://neos. mcs.anl.gov/neos/solvers/index.html）。您首先要做的就是用代数语言（例如 AMPL）编写模型。然后NEOS将求解模型并通过电子邮件返回结果。
You may also post directly your linear model to NEOS platform (http://neos.mcs.anl.gov/neos/solvers/index.html) . What you simply have to do first is write your model in an algebraic language such as AMPL. Then NEOS will solve the model and returns the results by e-mail.
线性编程
Linear programming