如何解决不平等制度? [英] How to solve a system of inequalities?

问题描述

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

I've reduced my problem (table layout algorithm) to the following problem:

想象一下，我有N个变量X ₁ ，X ₂ ，...，X _N .我也有一些(不确定的)不平等现象，例如:

Imagine I have N variables X₁, X₂, ..., X_N. I also have some (undetermined) number of inequalities, like:

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

X₁ >= 2
x₂ + X₃ >= 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?

已添加:阅读Wikipedia文章，并意识到我忘了提到变量必须是整数了.猜猜这使它变得NP难，是吧?

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?

推荐答案

在xi满足线性约束的情况下最小化x1 + x2 + ...称为线性规划. 维基百科

Minimizing x1 + x2 + ... where the xi satisfy linear constraints is called Linear Programming. It's covered in some detail in Wikipedia

这篇关于如何解决不平等制度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！