如果相等约束求解线性规划 [英] Solving a linear program in case of an equality constraint

问题描述

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

I had asked a question, which can be found here :
Computing the optimal combination

和已提出线性规划。我已经看过了线性规划和单纯形法。但这一切，我所遇到的例子有被转换成使用松弛变量等式不等式约束。单纯形法，然后互换的基本和所述非基本变量，以获得最佳的解决方案。

And had been suggested Linear programming. I have looked up Linear programming and the Simplex method. But all the examples that I have come across have inequality constraints which are converted into equalities using slack variables. The simplex method then interchanges the basic and the non basic variables to obtain an optimal solution.

但我的问题是：

But my problem is :

最小化：
X1 + X2 + ... + XN

minimize :
x1 + x2 + ... + xn

符合以下条件：
A1 * X1 + A1 * 2 + A1 * X3 + ... + A1 * XN = C1;
A2 * X1 + A2 * 2 + A2 * X3 + ... + A2 * XN = C2;
A3 * X1 + A3 * 2 + A3 * X3 + ... + A3 * XN = C3;

subject to :
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;

现在，我不知道怎样才能运用单纯形法这里我没有任何基本的变量在这里。照片我也不能只求解线性方程组，因为我有个变量和3个方程。
有人建议我一条生路吗？

Now I don't know how I can apply the simplex method here as I don't have any basic variables here.
Also I can't just solve the linear equations as I have n variables and 3 equations.
Can someone suggest me a way out here?

推荐答案

您可以您的每一个方程改写成两个不等式：

You can rewrite each of your equations into two inequalities:

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

这假定系数标记 A1 实际上是不同的;否则，你的整个LP是高度相互依存的，要么微不足道的解决与否可解的。接下来，您添加松弛变量把不等式变成等式再次：

This assumes that the coefficients labeled a1 are actually different; otherwise your whole LP would be highly interdependent and either trivial to solve or not solvable at all. Next you add slack variables to turn the inequalities into equalities again:

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及Y 1b是你最初的基本变量，你就可以开始转动。要么找到一个最佳的解决方案，如果初始的基本解决方案已经不可行，或者找到一个可行的解决方案，如果没有。

Now these y1a and y1b are your initial basic variables, and you can start pivoting. Either to find an optimal solution if the initial basic solution is already feasible, or to find a feasible solution if not.

这篇关于如果相等约束求解线性规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！