在等式约束条件下解决线性规划问题

Question

我曾经提出过一个问题，可以在这里找到：
计算最优组合

并且有人建议我使用线性规划。我查阅了关于线性规划和单纯形法的资料。但是我所看到的所有例子都有不等式约束条件，这些条件通过松弛变量转换为等式。然后单纯形法交换基本变量和非基本变量以获得最优解。

但是我的问题是：

最小化：
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 个方程。有人能否给我提供一种解决方法？

- user1925405

---

投票关闭。这不是一个在SO上通常使用的“编程问题”。这是关于线性规划中单纯形法应用的问题。 - High Performance Mark

这是一个编程问题。请查看问题中的链接。我遇到了关于建议方法的困惑，所以我想在这里提问，以便人们可以建议另一种编程技术，如果线性编程不起作用的话。 - user1925405

Answer 1

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

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

这意味着标记为 a1 的系数实际上是不同的；否则你的整个线性规划问题将高度相互依赖，要么很容易求解，要么根本不可解。接下来，您需要添加松弛变量来将不等式再次转换为等式：

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是您的初始基本变量，您可以开始进行枢轴操作。如果初始基本解已经可行，则可以寻找最优解，否则可以寻找可行解。

- MvG

---

谢谢！您能否解释一下如何将最小化转换为最大化？我认为只需要在目标函数中取反变量。即上述函数应该变成最大化：-x1 -x2 -x3 ... -xn。是这样吗？如果是，那么单纯形法现在该怎么进行呢？它必须选择一个非基本变量，使得目标函数中的系数为正，对吗？ - user1925405

或者你使用的是Duality。但我还没有能够理解它。如果适用的话，你能否请解释一下？ - user1925405

@user1925405：逐步介绍单纯形法超出了SO答案的范围，我认为。如果在线资源不足够，建议您获取Cormen等人的书籍《算法导论》的副本。据我所记，其中的单纯形描述非常易懂。简短回答：在最大化和最小化之间切换意味着否定目标函数。如果您不理解单纯形法的特定步骤，请发布一个新问题，并提供明确（最好是简单）的数字可能会有所帮助。 - MvG

Answer 2

在 Kenneth Steiglitz 和 Christos Papadimitiou 的《组合优化》教材中，您可以找到对单纯形算法的详细、自包含的描述。如果我没记错的话，当只给出等式约束但没有基础时，会引入成本为零的附加人工变量来构建人工基础。直观地说，这就像在约束矩阵的一侧“粘贴”一个单位矩阵。然后，启动单纯形算法以“驱逐”人工基础，即迭代直到不再有人工变量包含在基础中，这意味着已找到原始公式的基础。

- anonymous

Answer 3

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

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

一个相关的问题是this。

- Ali

Answer 4

线性规划可以解决这个问题。不要使用两个不等式来描述约束条件，只需将其输入到像GLPK这样的求解器中即可。例如，您可以用几行GMPL代码编写它：

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 必须保持非负，并且限制条件可能会更加复杂，就像您链接的帖子中那样。

- Ggouvine