如何解决不平等制度?

发布于 2024-08-05 18:15:04 字数 401 浏览 8 评论 0原文

我已将问题(表格布局算法)简化为以下问题:

假设我有 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

自找没趣 2024-08-12 18:15:04

在 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

深居我梦 2024-08-12 18:15:04

您遇到的是一个非常基本的线性编程问题。您想要最大化方程X_1 + ... + X_n,但

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

有许多算法可以解决此类问题。最著名的是 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_n subject to

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

There 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

单身狗的梦 2024-08-12 18:15:04

您还可以将您的线性模型直接发布到 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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文