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

Question

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

MAX 7X1+5X2

S.t :

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

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

∇f_obj = (7, 5)

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

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

上图(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

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

所以，第三个约束条件x1 >= 100可以去掉，因为考虑到第四个约束条件x1,x2 >= 0.

，实际上x1必须大于等于262,5

Answer 3

好的，答案如下：-

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

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

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

Eliminate a redundant equation from a linear programming

math

mathematical-optimization

linear-programming

linear-equation