在等式约束的情况下求解线性程序

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个方程
有人能给我推荐一条出去的路吗

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

Answer 2

在教材中

Kenneth Steiglitz和Christos Papadimitiou 的"组合优化"

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

Answer 3

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

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

一个相关的问题是。

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必须保持非负，并且约束有点复杂，就像在你的链接文章中一样。