algorithm - 在等式约束的情况下求解线性规划

Question

我问了一个问题，可以在这里找到:
Computing the optimal combination

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

但我的问题是:

最小化:
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 个方程.
有人可以建议我离开这里吗？

Answer 1

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

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 是您的初始基本变量，您可以开始旋转。要么在初始基本解已经可行的情况下寻找最优解，要么在不可行的情况下寻找可行的解决方案。