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

Question

我问了一个问题,可以在这里找到:
计算最佳组合

并且已经建议线性编程.我已经查找了线性编程和Simplex方法.但是我遇到的所有例子都有不等式约束,这些约束使用松弛变量转换成等式.然后,单纯形法交换基本变量和非基本变量以获得最优解.

但我的问题是:

最小化:
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是您的初始基本变量,您可以开始旋转.如果初始基本解决方案已经可行,要么找到最佳解决方案,要么找不到可行解决方案.