math - 从线性规划中消除冗余方程

Question

我被要求用更少的方程重写这个线性规划问题。

MAX 7X1+5X2

英石 ：

4X1+3X2 <= 2400
2X1+0.5X2 <= 750
X1 >= 100
X1,X2 >= 0

我所做的是我使用单纯形法，我发现最大利润是 4030，X1 = 100 和 X2=666。我可以用它说to obtain the maximum profit, X1 has always to be 100, then the third equation is an extra吗？

Answer 1

由于我们只考虑一个简单的二维问题，我们可以用图形解决这个问题。首先注意目标函数的梯度是

∇f_obj = (7, 5)

从现在开始，我们将用 和 表示X1您x的X2变量y。

约束描述了下面的多面体(a)，目标函数的水平曲线在(b)（更亮的轮廓：增加的目标函数值）中给出。

最佳值由(b)上面的红点标记，(x^*, y^*) = (262.5, 450)。

很明显，不等式约束4x+3y <= 2400和2x+0.5y <= 750都是活跃的，因为在这两者的交集处给出了最优值。

然而，约束x >= 100( X1 >= 100) 是无效的，因此是多余的。

Answer 2

[1] 2x1 + 0.5x2 ≤ 750  
[2] 2x1 + 0.5x2 ≤ 4500 / 6
[3] 6 * (2x1 + 0.5x2) ≤ 4500
[4] 12x1 + 3x2 ≤ 4500
[5]
    12x1 + 3x2 ≤ 4500
 - 4x1 + 3x2 ≤ 2400
  ---------------------
     8x1 ≤ 2100
[6] x1 ≥ 2100 / 8
[7] x1 ≥ 262,5

3x2步骤[2]中的那个6是指第一个约束比第二个约束大多少次0.5x2，简而言之3x2 / 0.5x2 = 6。

因此，可以消除第三个约束x1 >= 100，因为实际上，考虑到第四个约束，x1 必须大于或等于 262,5 x1,x2 >= 0。

Answer 3

好的，所以答案如下：-

X1 >= 100。<=> X1-100 >= 0 X1 - 100 = y

或 X1 = y+100 在前 2 个等式中将 X1 替换为 (y+100)。将非负性方程中的 X1 替换为 y，删除第三个方程。