3

我问了一个问题，可以在这里找到：
计算最优组合

并被建议线性规划。我查阅了线性规划和单纯形法。但是我遇到的所有示例都有不等式约束，这些约束使用松弛变量转换为等式。然后单纯形法交换基本变量和非基本变量以获得最优解。

但我的问题是：

最小化：
x1 + x2 + ... + xn

服从：
a1*x1 + a1*x2 + a1*x3 + ... + a1*xn = c1；
a2*x1 + a2*x2 + a2*x3 + ... + a2*xn = c2;
a3*x1 + a3*x2 + a3*x3 + ... + a3*xn = c3;

现在我不知道如何在这里应用单纯形法，因为这里没有任何基本变量。
我也不能只求解线性方程，因为我有 n 个变量和 3 个方程。
有人可以建议我离开这里吗？

4

4 回答 4

5

您可以将每个方程式重写为两个不等式：

a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≤ c1
a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≥ c1

这假设标记的系数a1实际上是不同的；否则你的整个 LP 将是高度相互依赖的，要么解决起来微不足道，要么根本无法解决。接下来，您添加松弛变量以再次将不等式变为等式：

a1*x1 + a1*x1 + a1*x3 + … + a1*xn + y1a = c1    y1a ≥ 0
a1*x1 + a1*x1 + a1*x3 + … + a1*xn - y1b = c1    y1b ≥ 0

现在这些 y1a 和 y1b 是您的初始基本变量，您可以开始旋转。如果初始基本解决方案已经可行，则找到最佳解决方案，如果不可行，则找到可行解决方案。

于 2013-06-25T05:05:43.007 回答
2

在教科书上

Kenneth Steiglitz 和 Christos Papadimitiou 的“组合优化”

您可以找到关于单纯形算法的详细、独立的描述。如果我没记错的话，对于只给出等式约束但没有基础的情况，引入了一个人工基础，其中每个成本为零的附加人工变量。直观地说，这就像在约束矩阵的一侧“粘合”一个单位矩阵。然后，单纯形算法开始“驱除”人工基础，即迭代直到基础中不再包含人工变量，这意味着找到了原始公式的基础。

于 2013-06-26T13:28:08.820 回答
1

您不必自己做，这就是建模语言存在的原因。我建议您尝试GLPK或SCIP。

他们有自己的建模语言，GLPK 有 GNU MathProg，SCIP 有 ZIMPL，所以你可以方便地编写你的 LP 问题。阅读文档。

一个相关的问题是this。

于 2013-06-25T08:12:06.373 回答
0

线性规划将解决这个问题。不要使用两个不等式来描述约束，只需将其提供给像 GLPK 这样的求解器。例如，你可以用几行 GPLL 来编写它：

param k, n;
param a{1..k}{1..n};
param c{1..k};
var x{1..n}, >= 0;

minimize cost : sum{i in 1..n} x[i];
s.t. constraints{j in 1..k} : sum{i in 1..n}(a[j][i] * x[i]) = c[j];

但是，正如您在此处所述，您的模型可能没有最优解：没有非负性约束，它只是一个欠定线性系统，具有无限解。我假设 x 必须保持非负数，并且约束要复杂一些，如您的链接帖子中所示。

于 2014-11-11T17:16:28.680 回答