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

我问了一个问题，可以在这里找到：
计算最优组合 https://stackoverflow.com/questions/17232596/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 个方程。
有人能给我建议一条出路吗？

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

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 是您的初始基本变量，您可以开始旋转。如果初始基本解已经可行，则寻找最优解；如果初始基本解不可行，则寻找可行解。